+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-08(77)

2019-09(96)

2019-10(14)

2019-11(12)

2019-12(13)

2020-01(26)

2020-02(32)

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

发布于2020-02-10 17:27     阅读(365)     评论(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


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

作者:232hdsjdh

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

来源:python黑洞网 www.pythonheidong.com

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

5 0

赞一赞 or 踩一踩

收藏该文
已收藏

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

相似文章

  5171. 最接近的因数

  Python实现生成西瓜数据集的Excel文件

  Leetcode - 删除排序数组中的重复项

  python第五天-字符串

  数据结构|LeetCode(力扣)经典题:队列

  python学习笔记(3)

  TYD_初识python数据可视化库-Matplotlib

  Scrapy安装与应用教程

  python实现修改文件中的内容

  mac环境下python3.6安装pyhanlp工具包

优质资源排行榜

 python经典电子书大合集下载 下载次数 8138

 零基础java开发工程师视频教程全套,基础+进阶+项目实战(152G) 下载次数 7550

 零基础前端开发工程师视频教程全套,基础+进阶+项目实战(共120G) 下载次数 7442

 零基础大数据全套视频400G 下载次数 7006

 零基础php开发工程师视频教程全套,基础+进阶+项目实战(80G) 下载次数 6893

 零基础软件测试全套系统教程 下载次数 6506

 全套人工智能视频+pdf 下载次数 6443

 IOS全套视频教程 基础班+就业班 下载次数 4680

 编程小白的第一本python入门书(高清版)PDF下载 下载次数 3648

10  effective python编写高质量Python代码的59个有效方法 pdf下载 下载次数 3361

11  Python深度学习 pdf下载 下载次数 3156

12  笨办法学python pdf下载 下载次数 3087

13  Python Cookbook第三版中文PDF下载高清完整扫描原版 下载次数 3024

14  树莓派Python编程指南 pdf下载 下载次数 3011

15  python从入门到精通视频(全60集)python视频教程下载 下载次数 3009

16  python项目开发视频 下载次数 3002

17  使用python+pygame开发的小游戏《嗷大喵快跑》源码下载 下载次数 3000

18  黑马2017年java就业班全套视频教程 下载次数 2992

19  Python基础教程 pdf下载 下载次数 2988

20  python实战项目 平铺图像板系统源码下载,适用于想要保存,标记和共享图像,视频和网页的用户 下载次数 2987

21  利用python实现程序内存监控脚本 下载次数 2987

22  老男孩python自动化视频 下载次数 2983

23  老王python基础+进阶+项目视频教程 下载次数 2974

24  尚硅谷Go学科全套视频 下载次数 2972

25  某硅谷Python项目+AI课程+核心基础视频教程 下载次数 2968

26  Web前端实战精品课程 下载次数 2967

27  Python算法教程_中文版 pdf下载 下载次数 2966

28  tron python小游戏 下载次数 2963

29  [小甲鱼]零基础入门学习Python 下载次数 2962

30  老男孩python全栈开发15期 下载次数 2958

31  2017最新web前端开发完整视频教程附源码 下载次数 2948

32  最新全套完整JAVAWEB2018开发视频 下载次数 2926

33  流畅的Python PDF下载高清完整扫描原版 下载次数 2919

34  Spring boot实战视频6套下载 下载次数 2910

35  python全套视频十五期(116G) 下载次数 2908

36  Python高性能编程 pdf下载 下载次数 2906

37  Python项目实战 下载次数 2887

38  30个小时搞定Python网络爬虫 含源码 下载次数 2884

39  简明python教程 (A Byte of Python)pdf下载 下载次数 2884

40  利用Python进行数据分析 pdf下载 下载次数 2884

41  python全自动抢火车票教程-python视频教程下载 下载次数 2883

42  尚硅谷大数据之Hadoop视频 下载次数 2876

43  Python A~B~C~ python视频教程下载 下载次数 2866

44  数据结构与算法视频(小甲鱼讲解-全) 下载次数 2864

45  web小程序表白天数倒计时源码下载 下载次数 2863

46  python基础视频教程 下载次数 2862

47  go语言全套视频 下载次数 2855

48  清华学霸尹成Python爬虫视频-ok 下载次数 2846

49  黑马前端36期最全视频和代码 下载次数 2843

50  2018最新全套web前端视频教程+源码下载 下载次数 2841