Python小白 Leetcode刷题历程 No.56-No.60 合并区间、插入区间、最后一个单词的长度、螺旋矩阵Ⅱ、第k个排列

写在前面：

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

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

觉得有用的话可以点赞关注下哦，谢谢大家！
········································································································································································
题解框架：

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

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

No.56.合并区间

难度：中等
题目描述：

在这里插入图片描述

题解代码（Python3.8）

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        l=len(intervals)
        res=[]
        if l==0:
            return res
        i=0
        left=intervals[i][0]
        right=intervals[i][1]
        while i<l:
            left=intervals[i][0]
            right=intervals[i][1]
            while i<l-1 and  intervals[i+1][0]<=right:
                i+=1
                right=max(intervals[i][1],right)
            res.append([left,right])
            i+=1
        return res

解题思路：
先按首位置进行排序;接下来,如何判断两个区间是否重叠呢?比如 a = [1,4],b = [2,3]。当 a[1] >= b[0] 说明两个区间有重叠.
但是如何把这个区间找出来呢?
左边位置一定是确定，就是 a[0]，而右边位置是 max(a[1], b[1])。所以,我们就能找出整个区间为:[1,4]。

No.57.插入区间

难度：困难
题目描述：

在这里插入图片描述

题解代码（Python3.8）

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        def merge(intervals):
            intervals.sort()
            l=len(intervals)
            res=[]
            i=0
            left=intervals[i][0]
            right=intervals[i][1]
            while i<l:
                left=intervals[i][0]
                right=intervals[i][1]
                while i<l-1 and  intervals[i+1][0]<=right:
                    i+=1
                    right=max(intervals[i][1],right)
                res.append([left,right])
                i+=1
            return res
        
        intervals.append(newInterval)
        return merge(intervals)

解题思路：
这道题一看难度是困难，实际上根上一题‘No.56.合并区间’一样，这道题就是将一个区间添加进intervals中，再合并空间（同上一题‘No.56.合并区间’操作一样）。所以，我们首先要定义一个merge函数（同上一题‘No.56.合并区间’的主函数一样），之后将新区间newInterval添加进intervals中，再调用merge函数即可。

No.58.最后一个单词的长度

难度：简单
题目描述：

在这里插入图片描述

题解代码（Python3.8）

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        res=0
        s=s.strip()
        for i in range(len(s)-1,-1,-1):
            if s[i]!=' ':
                res +=1
            else:
                break
        return res

或许有用的知识点：
这道题可以用到python中的strip()函数，strip()函数用于移除字符串头尾指定的字符（默认为空格或换行符）或字符序列。（注意：该方法只能删除开头或是结尾的字符，不能删除中间部分的字符。）

在这里插入图片描述

解题思路：
这道题比较简单，先使用strip()函数去掉字符串头尾的空格，之和从后往前判断字符串是否为空格即可。

No.59.螺旋矩阵Ⅱ

难度：中等
题目描述：

在这里插入图片描述

题解代码（Python3.8）

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        matrix=[[0 for _ in range(n)] for _ in range(n)]
        left,right,top,bottom = 0,n-1,0,n-1
        num,num_max = 1,n*n
        while num <= num_max:
            for i in range(left,right+1):        #顶端,从左到右(此处多一个数)   
                matrix[top][i] = num
                num += 1
            for i in range(top+1,bottom+1):      #右端,从上到下   
                matrix[i][right] = num
                num += 1
            for i in range(right-1,left-1,-1):   #底端,从右到左
                matrix[bottom][i] = num
                num += 1
            for i in range(bottom-1,top,-1):     #左端,从下到上（此处少一个数）
                matrix[i][left] = num
                num += 1
            left += 1
            right -= 1
            top += 1
            bottom -=1
        return matrix

或许有用的知识点：
matrix=[[0 for _ in range(n)] for _ in range(m)]可以创建一个m行n列的全0数组。

解题思路：
这道题先创建一个空数组，再将数字依次递增地按照顺序一层一层填入数组即可。注意，填入数组的四个方位的长度最好不要相等，否则当最内层只有一个元素时会发生错误，下面有一张图展示了数组填数的方法。

在这里插入图片描述

No.60.第k个排列

难度：中等
题目描述：

在这里插入图片描述

题解代码（Python3.8）

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        def backtrack(index,k):
            if index == n:
                return
            cnt = factorial[n-1-index]
            for i in range(1,n+1):
                if used[i]:
                    continue
                if cnt < k:
                    k -= cnt
                    continue
                path.append(i)
                used[i] = True
                backtrack(index+1,k)
        
        if n == 0:
            return ''
        used = [False for _ in range(n+1)]
        path = []
        factorial = [1 for _ in range(n+1)]
        for i in range(2,n+1):
            factorial[i] = factorial[i-1]*i
        backtrack(0,k)
        return ''.join([str(x) for x in path])

或许有用的知识点：
这道题要用到回溯算法。
used = [False for _ in range(n+1)]可以创建一个容量为n的布尔值型一维数组。
这道题严格来说并不是回溯算法，但是需要用到回溯算法中的‘剪枝’操作，而且这道题只有一条分支是有效的，因此回溯函数种不用设置‘状态返回’环节。

解题思路：
这道题我开始用暴力的方法尝试了一下，发现会超时。又发现这道题其实是个树形结构，而且只有一个叶是有效解，因此我们可以采用回溯算法来解决。又因为这道题只有一条分支是有效的，因此回溯函数种不用设置‘状态返回’环节。套用回溯算法的模板，则回溯算法的三个组成部分分别为：
1.回溯出口：索引位置等于n；
2.回溯主体：遍历[0,n+1),如果用过数字了，就继续，如果if cnt < k，则 k -= cnt并continue，当第一次cnt >=k,将i记录进path中，记录用过数字了，并进行下一轮的回溯backtrack(index+1,k)。
3.状态返回：本题不用设置。
定义完回溯函数后，我们还需要创建一个容量为n的布尔值型一维数组，以存储数字i是否使用过；再创建一个容量为n的一维数组，储存[1,n+1)的阶乘；之后引用回溯函数即可。