【PythonCode】力扣Leetcode46~50题Python版

前言

力扣Leetcode是一个集学习、刷题、竞赛等功能于一体的编程学习平台，很多计算机相关专业的学生、编程自学者、IT从业者在上面学习和刷题。
在Leetcode上刷题，可以选择各种主流的编程语言，如C++、JAVA、Python、Go等。还可以在线编程，实时执行代码，如果代码通过了平台准备的测试用例，就可以通过题目。
本系列中的文章从Leetcode的第1题开始，记录我用Python语言提交的代码和思路，供Python学习参考。

46. 全排列

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列 。你可以按任意顺序返回答案。

示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
提示：
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

代码实现：

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:result = []def backtrack(nums, temp):if not nums:result.append(temp)return for i in range(len(nums)):backtrack(nums[:i] + nums[i+1:], temp + [nums[i]])backtrack(nums, [])return result

解题思路：根据题意，原始数组中不含重复的元素，要返回用数组中的元素组成的全排列，也就是将数组中的不同元素按不同的顺序排列，得到不同的排列组合。这需要枚举所有不同的排列方式，可以使用回溯算法。回溯算法参考：循序渐进，搞懂什么是回溯算法

在代码中，每次从nums中取一个元素添加到排列中，然后将nums更新成删除此元素后的数组，用一个临时数组temp保存当前已经枚举的元素，每从nums中取出一个元素，都添加到temp中。当nums中的元素被枚举完时，得到一种排列组合，此时将temp添加到结果中，并往回回溯，枚举其他组合。

回溯的题目前面已经多次遇到，前面的力扣17题、22题、37题、39题、40题都是，可以访问本专栏前面的文章，结合起来一起看，加深理解。本题相对前面的题来说，属于简单的。

47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。

示例 1：
输入：nums = [1,1,2]
输出： [[1,1,2], [1,2,1], [2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 8
-10 <= nums[i] <= 10

代码实现：

class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:result = []def backtrack(nums, temp):if not nums and temp not in result:result.append(temp)return for i in range(len(nums)):backtrack(nums[:i] + nums[i+1:], temp + [nums[i]])backtrack(nums, [])return result

解题思路：本题是上一题的变体，唯一的区别是，上一题的原始数组中不含重复的元素，本题的原始数组中可包含重复的元素。相同的元素可以重复出现在一种组合中，但最后得到的排列中不能有重复的排列。所以代码与上一题唯一的区别是，将枚举的排列保存到结果中时，判断当前结果中是否已有相同的排列，有就不重复添加了。

48. 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
提示：
n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

代码实现：

class Solution:def rotate(self, matrix: List[List[int]]) -> None:"""Do not return anything, modify matrix in-place instead."""n = len(matrix)for i in range(n // 2):for j in range((n + 1) // 2):matrix[i][j], matrix[n-1-j][i], matrix[n-1-i][n-1-j], matrix[j][n-1-i] = matrix[n-1-j][i], matrix[n-1-i][n-1-j], matrix[j][n-1-i], matrix[i][j]

解题思路：题目要求将 n × n 的二维矩阵原地旋转90度。原地旋转就是不能使用新的矩阵，而是直接在原矩阵中交换相应位置的值。所以，解题的关键是找到交换位置的规律。

以题目中的示例1为例，其交换位置的关系如下图所示。因为是将矩阵旋转90度，所以先将矩阵分成四个象限，辅助观察规律。在旋转发生时，矩阵中每四个位置相互交换位置，如数字2,6,8,4，对应的索引分别为[0, 1]，[1, 2]，[2, 1]，[1, 0]，还有数字1,3,9,7，对应的索引分别为[0, 0]，[0, 2]，[2, 2]，[2, 0]。

可以看到，如果将需要旋转的数字分成4组，就是将上图中的不同颜色区域进行旋转。可以看到，第一行旋转后位置全在最后一列，旋转后列索引全是n-1，并且旋转后对应位置的行索引就是旋转前的列索引，也就是将matrix[i][j]旋转到了matrix[j][n-1-i]（这里列索引n-1-i是将i也考虑进来，表示更一般的规律）。最后一列旋转后位置全在最后一行，且列索引位置是从最大开始往前推，也就是将matrix[j][n-1-i]旋转到了matrix[n-1-i][n-1-j]。最后一行旋转后位置全在第一列，且行索引位置是从最大开始往前推，也就是将matrix[n-1-i][n-1-j]旋转到了matrix[n-1-j][i]。最后，再将matrix[n-1-j][i]旋转到matrix[i][j]。这样就找到了一般性的旋转规律。

当n为奇数时（上图n为3），正中心的数字不需要旋转，每组的数字个数为(n²-1)/4个，(n²-1)/4=((n-1)/2)×((n+1)/2)，所以我们需要遍历前(n-1)/2行和前(n+1)/2列（观察图形区域，第一个区域列数大于行数），找到第一个区域的数字，将它们与相应位置的数字相互交换位置。

当n为偶数时，以题目中的示例2为例，如下图所示。旋转的位置关系与n为奇数时相同，也是matrix[j][n-1-i]，matrix[j][n-1-i]，matrix[n-1-i][n-1-j]，matrix[n-1-j][i]的数字相互交换。n为偶数，所有数字位置都会变化，将矩阵分成4个区域，每组的数字为n²/4个，n²/4=(n/2)×(n/2)，所以我们需要遍历前n/2行和前n/2列，找到第一个颜色区域的数字，将它们与相应位置的数字相互交换位置。综合n为奇数和n为偶数，需要遍历n//2行和前(n+1)//2列（地板除奇数n-1和n一样，偶数n和n+1一样）。

根据上面的分析，只需要遍历矩阵中的第一个区域，将它们全部与对应索引关系的数字交换位置，即可达成旋转的效果。Python中交换值的写法很简洁，代码并不难。

49. 字母异位词分组

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词是由重新排列源单词的所有字母得到的一个新单词。

示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
示例 2:
输入: strs = [“”]
输出: [[“”]]
示例 3:
输入: strs = [“a”]
输出: [[“a”]]
提示：
1 <= strs.length <= 10⁴
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

代码实现：

class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:anagram_dict = {}for word in strs:sorted_word = ''.join(sorted(word))if sorted_word not in anagram_dict:anagram_dict[sorted_word] = [word]else:anagram_dict[sorted_word].append(word)return list(anagram_dict.values())

解题思路：同一组字母异位词中各字母出现的次数相同，只是顺序不同。组合方式类似于数字的不同排列，参考上面的46题和47题。这种情况前面已经遇到多次，可以用Python中的Counter来判断，参考：详解Python中非常好用的计数器Counter

如果将字符串排序，同一组字母异位词的排序结果相等。要将字符串数组中不同的字母异位词分组，可以将所有字符串排序，并将排序结果相等的字符串分到同一组中，Python中可以使用字典来实现。题目要求最后返回的是一个数组，分组完成后，取字典的values()转成列表即可。

50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xⁿ ）。

示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2^-2 = 1/2² = 1/4 = 0.25
提示：
-100.0 < x < 100.0
-2³¹ <= n <= 2³¹-1
n 是一个整数
要么 x 不为零，要么 n > 0 。
-10⁴ <= xⁿ <= 10⁴

代码实现：

class Solution:def myPow(self, x: float, n: int) -> float:if n == 0:return 1if x == 0:return 0if n < 0:x, n = 1/x, -nresult = 1while n:if n % 2 == 1:result *= xx *= xn //= 2return result

解题思路：幂运算的原理就是连乘，所以要自己实现幂运算函数功能，就是用乘法。

不过，如果用x乘n次（2³¹ <= n <= 2³¹-1）自己，时间复杂度为O(n)，运算会超时。所以这里连乘时应该使用二分法，将时间复杂度降到O(logn)。

将时间复杂度降到O(logn)的关键是，x乘自己后，将乘积结果赋值给自己，更新x，这样达到的效果就是乘logn次。不过n不一定能被2整除，n为奇数时要先做一次乘法处理。如果n不能被2整除，则先将x乘一次当前的累乘结果，不更新x，这样n减1（代码中可以省略n-1的操作，n除2时取整除），从奇数变成偶数，就可以被2整除了。如果n能被2整除，则可以直接将x乘自己并赋值给自己，n更新成n/2。

如果n是负数，则将x转换成1/x，将n转换成-n，从负数变成正数。

此外，还需要对一些特殊情况做处理，如n等于0。

---

相关阅读

【PythonCode】力扣Leetcode41~45题Python版

📢欢迎 点赞👍 收藏⭐ 评论📝 关注❤ 如有错误敬请指正！

☟ 学Python，点击下方名片关注我。☟