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)的阶乘；之后引用回溯函数即可。
