Python小白 Leetcode刷题历程 No.46-No.50 全排列、全排列Ⅱ、旋转图像、字母异位词分组、Pow(x,n)
写在前面：
作为一个计算机院的大学生，总觉得仅仅在学校粗略的学习计算机专业课是不够的，尤其是假期大量的空档期，作为一个小白，实习也莫得路子，又不想白白耗费时间。于是选择了Leetcode这个平台来刷题库。编程我只学过基础的C语言，现在在自学Python，所以用Python3.8刷题库。现在我Python掌握的还不是很熟练，算法什么的也还没学，就先不考虑算法上的优化了，单纯以解题为目的，复杂程度什么的以后有时间再优化。计划顺序五个题写一篇日志，希望其他初学编程的人起到一些帮助，写算是对自己学习历程的一个见证了吧。
有一起刷LeetCode的可以关注我一下，我会一直发LeetCode题库Python3解法的，也可以一起探讨。
觉得有用的话可以点赞关注下哦，谢谢大家！
········································································································································································
题解框架：
1.题目，难度
2.题干,题目描述
3.题解代码（Python3（不是Python，是Python3））
4.或许有用的知识点（不一定有）
5.解题思路
6.优解代码及分析（当我发现有比我写的好很多的代码和思路我就会写在这里）
········································································································································································
No.46.全排列
难度：中等
题目描述：
在这里插入图片描述
题解代码（Python3.8）
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def backtrack(path):
if len(path)==l:
res.append(path)
return
for i in range(l):
if block[i] == 1: #判断是否处理过
continue
block[i]=1
backtrack(path+[nums[i]])
block[i]=0
l=len(nums)
block=[ 0 for i in range(l)]
res=[]
backtrack([])
return res
或许有用的知识点：
这道题要用到回溯算法。
解题思路：
套用回溯算法的模板
1.回溯出口：
‘当前结果path的长度==列表的长度’时即为一个有效结果。
2.回溯主体：
先将回溯的范围和答案更新，之后进行剪枝剪枝条件为：该元素已使用过。（剪枝的题最好画画图，就会很容易理解）。
3.状态返回。
No.47.全排列Ⅱ
难度：中等
题目描述：
在这里插入图片描述
题解代码（Python3.8）
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def backtrack(path):
if len(path)==l:
res.append(path)
return
for i in range(l):
if block[i] == 1: #判断是否处理过
continue
if i>0 and nums[i] == nums[i-1] and block[i-1]==1: #剪枝
continue
block[i]=1
backtrack(path+[nums[i]])
block[i]=0
l=len(nums)
nums.sort()
res=[]
block=[ 0 for i in range(l) ]
backtrack([])
return res
或许有用的知识点：
如果涉及考虑重复元素，或者大小比较的情况，对列表排序是一个不错的选择，将重复的都放在一起，便于找到重复元素和剪枝。
解题思路：
这道题要考虑重复元素，我们不妨先把列表排序。
套用回溯算法的模板
1.回溯出口：
当前结果path的长度==列表的长度时即为一个有效结果。
2.回溯主体：
先将回溯的范围和答案更新，之后进行剪枝剪枝条件为：该元素已使用过，或者当前元素和上一个一样且前一个元素被使用过，我们要剪枝。剪枝的图像在优解代码与分析中。（剪枝的题最好画画图，就会很容易理解）。
3.状态返回。
优解代码及分析：
优解代码（Python3.8）
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def backtrack(path):
if len(path)==l:
res.append(path)
return
for i in range(l):
if block[i] == 1:
continue
if i>0 and nums[i] == nums[i-1] and block[i-1]==1: #这是与题解代码唯一不同的地方
continue
block[i]=1
backtrack(path+[nums[i]])
block[i]=0
l=len(nums)
nums.sort()
res=[]
block=[ 0 for i in range(l) ]
backtrack([])
return res
分析：
只分析与题解代码的不同之处。
在考虑重复及剪枝条件的时候，我们考虑的是：当当前元素和前一个元素值相同（此处隐含这个元素的index>0），并且前一个元素被使用过，我们要剪枝；但实际，如果条件设为：当当前元素和前一个元素值相同（此处隐含这个元素的index>0），并且前一个元素还没有被使用过的时候，我们要剪枝效率会更高。
回溯的图真的是天助，一定要自己画图理解，画图能很好理解递归过程：
-
if i > 0 and nums[i] == nums[i-1] and check[i-1] == 1
灰色为剪枝部分，蓝色为答案部分：
在这里插入图片描述
-
if i > 0 and nums[i] == nums[i-1] and check[i-1] == 0
灰色为剪枝部分，蓝色为答案部分：
在这里插入图片描述
能够明显发现第2种能够提前剪枝，减少计算步骤和搜索次数，并且第2种选择了重复元素的第一个，而第1种选择了重复元素的最后一个，虽然答案都相同，我们成年人当然是要选效率更高一些的那一种对吧~
No.48.旋转图像
难度：中等
题目描述：
在这里插入图片描述
在这里插入图片描述
题解代码（Python3.8）
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
l=len(matrix)
for i in range(l//2):
for j in range(i,l-i-1):
matrix[i][j],matrix[j][l-i-1],matrix[l-i-1][l-j-1],matrix[l-j-1][i] = \
matrix[l-j-1][i],matrix[i][j],matrix[j][l-i-1],matrix[l-i-1][l-j-1]
或许有用的知识点：
可以了解一下Python中的reverse()函数和reversed(),一般用于反转python中大多类型的数据，下面是这两个函数的一些介绍：
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
解题思路：
图像旋转，实际上是这四个位置上的数对应旋转。
因此，需要找到这四个位置索引的相互关系：
matrix[i][j]→matrix[j][n−i−1]→matrix[n−i−1][n−j−1]→matrix[n−j−1][i]
注意两个边界条件：
行只需遍历一半 ，[0,n//2)，列需要在[i,n−i−1)内。
复杂度分析
时间复杂度：O(n2)
空间复杂度：O(1)
优解代码及分析：
优解代码（Python3.8）
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
l=len(matrix)
for i in range(l):
for j in range(i,l):
matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]
for i in range(l):
matrix[i].reverse()
分析:
其实复杂度并没有降低，就是运用了矩阵转置的特性，比较好想。
在这里插入图片描述
No.49.字母异位词分组
难度：中等
题目描述：
在这里插入图片描述
题解代码（Python3.8）
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
from collections import defaultdict
dic_find=defaultdict(list)
for s in strs:
dic_find[''.join(sorted(s))].append(s)
return list(dic_find.values())
或许有用的知识点：
在dict中，由键依次取值比较简单 value=dic[key],而由值依次取键则需要key=list (dic.keys()) [list (dic.values()).index (val)]。本题中我们一次性取出所有值，则需要keys=dic.values()。
这道题需要用到defaultdict函数，Python中想预定义一个字典，且该字典之后要录入一些未定义的键时，要用defaultdict(list)预定义一个空字典（直接用dict定义会出现KeyError）。
使用defaultdict函数要引用collections库：即from collections import defaultdict。
以下是defaultdict函数的官方介绍：
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
解题思路：
以排序后的单词为 key，将所有字符串分组存入预定义字典，之后通过key输出字典的values即可。
No.50.Pow(x,n)
难度：中等
题目描述：
在这里插入图片描述
题解代码（Python3.8）
class Solution:
def myPow(self, x: float, n: int) -> float:
def reverse_search(x,n):
if n<1:
return 1
count,sum = 1,x
while count*2 <=n:
count += count
sum *=sum
return reverse_search(x,n-count)*sum
res = reverse_search(abs(x),abs(n))
res = -res if x<0 and n%2!=0 else res
res = 1/res if n<0 else res
return res
或许有用的知识点：
这道题要使用逆向二分算法。
二分算法是将问题不断地分成2份去求解，而逆向的二分算法就是把结果不断地扩大2倍以逼近要求值。
解题思路：
这道题如果累乘的话复杂度为O（n），通常情况这种方法是不符合时间要求的，我们需要使用复杂度更低的方法。我们定义一个逆向二分的函数，只需要一边记录x累乘的结果，一边记录累乘的次数，当累乘次数的两倍大于n时，n减去此次的累乘次数，再对剩余的幂次进行递归，将每次递归的累乘结果都累乘，作为返回。最后，再考虑符号问题。
网友评论