+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-08(77)

2019-09(96)

2019-10(14)

2019-11(12)

2019-12(13)

Python小白 Leetcode刷题历程 No.61-No.65 旋转链表、不同路径、不同路径Ⅱ、最小路径和、有效数字 (有题干 有代码 有思路心得)

发布于2020-02-10 17:27     阅读(438)     评论(0)     点赞(5)     收藏(5)


Python小白 Leetcode刷题历程 No.61-No.65 旋转链表、不同路径、不同路径Ⅱ、最小路径和、有效数字

写在前面:

作为一个计算机院的大学生,总觉得仅仅在学校粗略的学习计算机专业课是不够的,尤其是假期大量的空档期,作为一个小白,实习也莫得路子,又不想白白耗费时间。于是选择了Leetcode这个平台来刷题库。编程我只学过基础的C语言,现在在自学Python,所以用Python3.8刷题库。现在我Python掌握的还不是很熟练,算法什么的也还没学,就先不考虑算法上的优化了,单纯以解题为目的,复杂程度什么的以后有时间再优化。计划顺序五个题写一篇日志,希望其他初学编程的人起到一些帮助,写算是对自己学习历程的一个见证了吧。

有一起刷LeetCode的可以关注我一下,我会一直发LeetCode题库Python3解法的,也可以一起探讨。

觉得有用的话可以点赞关注下哦,谢谢大家!
········································································································································································
题解框架:

	1.题目,难度
	2.题干,题目描述
	3.题解代码(Python3(不是Python,是Python3))
	4.或许有用的知识点(不一定有)
	5.解题思路
	6.优解代码及分析(当我发现有比我写的好很多的代码和思路我就会写在这里)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

········································································································································································

No.61.旋转链表

难度:中等
题目描述:
在这里插入图片描述

题解代码(Python3.8)

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if (not head) or (not head.next) :
            return None if not head else head
        old_tail = head
        n = 1
        while old_tail.next:
            old_tail = old_tail.next
            n += 1
        old_tail.next = head
        
        new_tail = head
        for i in range(n - k%n -1):
            new_tail =new_tail.next
        new_head =new_tail.next
        new_tail.next = None
        return new_head
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

或许有用的知识点:
这道题可以使用快慢指针的思想。

解题思路:
链表中的点已经相连,一次旋转操作意味着:先将链表闭合成环,再找到相应的位置断开这个环,确定新的链表头和链表尾。所以,我们首先找到旧的尾部并将其与链表头相连old_tail.next = head,整个链表闭合成环,同时计算出链表的长度n;找到新的尾部,第 (n-k%n-1)个节点,新的链表头是第(n-k%n)个节点;断开环 new_tail.next = None,并返回新的链表头 new_head即可。

优解代码及分析:
优解代码(Python3.8)

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        # 下面有 if n==0 ...判断了,所以开头的判断可以省略
        #if not head or k<=0:
        #    return head
        # 创建一个哑节点,快指针,慢指针,统计节点个数的cur
        dummy = ListNode(-1)
        cur,n,fast,low,dummy.next = head,0,dummy,dummy,head
        # 统计链表个数
        while cur:
            cur,n = cur.next,n+1
        # 边界条件不要忘记处理了   
        if n==0 or k%n==0:
            return head
        # 还有一个边界条件不要忘了,k可能大于n,所以要取模
        n = k%n
        # 快指针先移动n步
        while fast.next and n>0:
            fast,n = fast.next,n-1
        # 快指针,慢指针一起移动,找到需要切割的点
        while fast.next:
            low,fast = low.next,fast.next
        # 改变链表的指向关系,注意这里的步骤不要乱了
        # 先让fast节点指向head(也就是dummy.next)
        # 再是head(也就是dummy.next)指向low的下一个节点
        # 这两步如果弄反了就会出现节点丢失了
        # 最后不要忘记将low.next置空
        fast.next,dummy.next,low.next = head,low.next,None
        return dummy.next
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

分析;
双指针法写起来思路比较清楚,代码比较简单,代码中有着极详细的注释,应该比较容易理解。

No.62.不同路径

难度:中等
题目描述:
在这里插入图片描述

题解代码(Python3.8)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        #第一行/第一列每个格都只有一种走法
        dp = [[1]*n] + [[1]+[0]*(n-1) for _ in range(m-1)]
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

或许有用的知识点:
这道题要用到动态规划的方法。

解题思路:
这道题可以使用动态规划的方法,套用动态规划的模板,对于这道题,假设dp[i][j]是从左上角到第i行第j列的方格有多少总走法,动态规划的三要素分别为:
状态:第一行和第一列都只有一种走法,其他格子走法=上面一格的走法+左边一格的走法
状态转移方程:dp[i][j] = dp[i-1][j] + dp[i][j-1]
边界条件: dp = [[1]n] + [[1]+[0](n-1) for _ in range(m-1)]
空间复杂度:O(n²)

优解代码及分析:
优解代码(Python3.8)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        cur = [1]*n
        for i in range(1,m):
            for j in range(1,n):
                cur[j] += cur[j-1]
        return cur[n-1]
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

分析:
其实也是动态规划的思想,只不过将创建的空间减少了一个维度,空间复杂度O(n)。

No.63.不同路径Ⅱ

难度:中等
题目描述:
在这里插入图片描述

题解代码(Python3.8)

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if (not obstacleGrid) or (not obstacleGrid[0]):
            return 0
        l_row = len(obstacleGrid)
        l_col = len(obstacleGrid[0])
        dp = [ [0]*l_col for _ in range(l_row)]
        #首位置
        dp[0][0] = 1 if obstacleGrid[0][0] != 1 else 0
        if dp[0][0] == 0:
            return 0
        #第一行
        for j in range(1,l_col):
            if obstacleGrid[0][j] != 1:
                dp[0][j] = dp[0][j-1]
        #第一列
        for i in range(1,l_row):
            if obstacleGrid[i][0] != 1:
                dp[i][0] = dp[i-1][0]
        #剩余位置
        for i in range(1,l_row):
            for j in range(1,l_col):
                if obstacleGrid[i][j] != 1:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[l_row-1][l_col-1]
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

或许有用的知识点:
这道题要用到动态规划的方法。

解题思路:
这道题根上一道题‘No.62.不同路径’很相似,是上一题的加强版。
这道题可以使用动态规划的方法,套用动态规划的模板,对于这道题,假设dp[i][j]是从左上角到第i行第j列的方格有多少总走法,动态规划的三要素分别为:
状态:第一行和第一列都只有一种走法,其他格子走法=上面一格的走法+左边一格的走法;但如果这一格有障碍物,该格的dp=0。
状态转移方程:if obstacleGrid[i][j] != 1: dp[i][j] = dp[i-1][j] + dp[i][j-1]
边界条件:
(#首位置)dp[0][0] = 1 if obstacleGrid[0][0] != 1 else 0 ;
(#第一行)if obstacleGrid[0][j] != 1: dp[0][j] = dp[0][j-1];
(#第一列)if obstacleGrid[i][j] != 1: dp[i][j] = dp[i-1][j] + dp[i][j-1]。

No.64.最小路径和

难度:中等
题目描述:
在这里插入图片描述

题解代码(Python3.8)

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        if (not grid) or (not grid[0]):
            return 0
        m = len(grid)
        n = len(grid[0])
        dp = [[0]*n for _ in range(m)]
        dp[0][0] = grid[0][0]           #首位
        for j in range(1,n):            #第一行
            dp[0][j] = dp[0][j-1] + grid[0][j]
        for i in range(1,m):            #第一列
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j])
        return dp[m-1][n-1]
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

或许有用的知识点:
这道题要用到动态规划的方法。

解题思路:
这道题可以使用动态规划的方法,套用动态规划的模板,对于这道题,假设dp[i][j]是从左上角到第i行第j列的方格路径的数字总和最小值,动态规划的三要素分别为:
状态:第一行和第一列都只有一种走法,其他格子的路径的数字总和最小值=(上面一格的路径的数字总和最小值+第i行第j列的方格的数字) 和 (左边一格的路径的数字总和最小值+第i行第j列的方格的数字)二者之间的最小值。
状态转移方程:dp[i][j] = min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j])
边界条件:
(#首位置) dp[0][0] = grid[0][0] ;
(#第一行)for j in range(1,n): dp[0][j] = dp[0][j-1] + grid[0][j];
(#第一列)for i in range(1,m): dp[i][0] = dp[i-1][0] + grid[i][0]。

No.65.有效数字

难度:困难
题目描述:
在这里插入图片描述

题解代码(Python3.8)

class Solution:
    def isNumber(self, s: str) -> bool:
        state = [
            {},
            # 状态1,初始状态(扫描通过的空格)
            {"blank": 1, "sign": 2, "digit": 3, ".": 4},
            # 状态2,发现符号位(后面跟数字或者小数点)
            {"digit": 3, ".": 4},
            # 状态3,数字(一直循环到非数字)
            {"digit": 3, ".": 5, "e": 6, "blank": 9},
            # 状态4,小数点(后面只有紧接数字)
            {"digit": 5},
            # 状态5,小数点之后(后面只能为数字,e,或者以空格结束)
            {"digit": 5, "e": 6, "blank": 9},
            # 状态6,发现e(后面只能符号位, 和数字)
            {"sign": 7, "digit": 8},
            # 状态7,e之后(只能为数字)
            {"digit": 8},
            # 状态8,e之后的数字后面(只能为数字或者以空格结束)
            {"digit": 8, "blank": 9},
            # 状态9, 终止状态 (如果发现非空,就失败)
            {"blank": 9}
        ]
        cur_state = 1
        for c in s:
            if c.isdigit():
                c = "digit"
            elif c in " ":
                c = "blank"
            elif c in "+-":
                c = "sign"
            if c not in state[cur_state]:
                return False
            cur_state = state[cur_state][c]
        if cur_state not in [3, 5, 8, 9]:
            return False
        return True
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

或许有用的知识点:
这道题要用到有限状态机(FSM),或者说有限状态机的一种特殊状态——有限自动机(DFA)的思想(在数字电路基础、Verilog、离散数学等大学专业课中应该学习过)。

解题思路:
以下为一个考虑到各种情况的有限自动机模型,状态机的结构可以结合代码中的注释一起理解。(自己设计一个状态机有时不能一开始就考虑到所有情况,要多测试不同情况)。我们的代码先创建一个state包含状态机的所有状态与内容,之和将字符串中的字符依次放入状态机运行,最后查看状态机的状态是否在指定状态即可。
在这里插入图片描述

发布了17 篇原创文章 · 获赞 17 · 访问量 720


所属网站分类: 技术文章 > 博客

作者:232hdsjdh

链接: https://www.pythonheidong.com/blog/article/231015/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

5 0
收藏该文
已收藏

评论内容:(最多支持255个字符)