Leetcode: 0041-0050题速览

本文材料来自于LeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer（第 2 版）》、《程序员面试金典（第 6 版）》题解

遵从开源协议为知识共享 版权归属-相同方式共享 4.0 国际 公共许可证

研一在读备战就业，制此集合便于空闲时间浏览，有任何疑惑问题欢迎讨论，共同进步

41. 缺失的第一个正数

题目描述

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

 

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

 

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1

难度：困难

标签：数组,哈希表

解法

方法一：原地交换

我们假设数组 $nums$ 长度为 $n$，那么最小的正整数一定在 $[1,..,n+1]$ 之间。我们可以遍历数组，将数组中的每个数 $x$ 交换到它应该在的位置上，即 $x$ 应该在的位置为 $x-1$。如果 $x$ 不在 $[1,n+1]$ 之间，那么我们就不用管它。

遍历结束后，我们再遍历数组，如果 $i+1$ 不等于 $nums[i]$，那么 $i+1$ 就是我们要找的最小的正整数。

时间复杂度 $O(n)$，其中 $n$ 是数组的长度。空间复杂度 $O(1)$。

Python3

class Solution:def firstMissingPositive(self, nums: List[int]) -> int:def swap(i, j):nums[i], nums[j] = nums[j], nums[i]n = len(nums)for i in range(n):while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:swap(i, nums[i] - 1)for i in range(n):if i + 1 != nums[i]:return i + 1return n + 1

Java

class Solution {public int firstMissingPositive(int[] nums) {int n = nums.length;for (int i = 0; i < n; ++i) {while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {swap(nums, i, nums[i] - 1);}}for (int i = 0; i < n; ++i) {if (i + 1 != nums[i]) {return i + 1;}}return n + 1;}private void swap(int[] nums, int i, int j) {int t = nums[i];nums[i] = nums[j];nums[j] = t;}
}

C++

class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n = nums.size();for (int i = 0; i < n; ++i) {while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {swap(nums[i], nums[nums[i] - 1]);}}for (int i = 0; i < n; ++i) {if (i + 1 != nums[i]) {return i + 1;}}return n + 1;}
};

---

42. 接雨水

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

 

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

 

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

难度：困难

标签：栈,数组,双指针,动态规划,单调栈

解法

方法一：动态规划

我们定义 $left[i]$ 表示下标 $i$ 位置及其左边的最高柱子的高度，定义 $right[i]$ 表示下标 $i$ 位置及其右边的最高柱子的高度。那么下标 $i$ 位置能接的雨水量为 $\min (left[i],right[i])-height[i]$。我们遍历数组，计算出 $left[i]$ 和 $right[i]$，最后答案为 ${\sum }_{i=0}^{n-1}\min (left[i],right[i])-height[i]$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组的长度。

Python3

class Solution:def trap(self, height: List[int]) -> int:n = len(height)left = [height[0]] * nright = [height[-1]] * nfor i in range(1, n):left[i] = max(left[i - 1], height[i])right[n - i - 1] = max(right[n - i], height[n - i - 1])return sum(min(l, r) - h for l, r, h in zip(left, right, height))

Java

class Solution {public int trap(int[] height) {int n = height.length;int[] left = new int[n];int[] right = new int[n];left[0] = height[0];right[n - 1] = height[n - 1];for (int i = 1; i < n; ++i) {left[i] = Math.max(left[i - 1], height[i]);right[n - i - 1] = Math.max(right[n - i], height[n - i - 1]);}int ans = 0;for (int i = 0; i < n; ++i) {ans += Math.min(left[i], right[i]) - height[i];}return ans;}
}

C++

class Solution {
public:int trap(vector<int>& height) {int n = height.size();int left[n], right[n];left[0] = height[0];right[n - 1] = height[n - 1];for (int i = 1; i < n; ++i) {left[i] = max(left[i - 1], height[i]);right[n - i - 1] = max(right[n - i], height[n - i - 1]);}int ans = 0;for (int i = 0; i < n; ++i) {ans += min(left[i], right[i]) - height[i];}return ans;}
};

---

43. 字符串相乘

题目描述

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

 

示例 1:

输入: num1 = “2”, num2 = “3”
输出: “6”

示例 2:

输入: num1 = “123”, num2 = “456”
输出: “56088”

 

提示：

• 1 <= num1.length, num2.length <= 200
• num1 和 num2 只能由数字组成。
• num1 和 num2 都不包含任何前导零，除了数字0本身。

难度：中等

标签：数学,字符串,模拟

解法

方法一：数学乘法模拟

假设 $num1$ 和 $num2$ 的长度分别为 $m$ 和 $n$，则它们的乘积的长度最多为 $m+n$。

证明如下：

• 如果 $num1$ 和 $num2$ 都取最小值，那么它们的乘积为 ${10}^{m-1}\times {10}^{n-1}={10}^{m+n-2}$，长度为 $m+n-1$。
• 如果 $num1$ 和 $num2$ 都取最大值，那么它们的乘积为 $({10}^m-1)\times ({10}^n-1)={10}^{m+n}-{10}^m-{10}^n+1$，长度为 $m+n$。

因此，我们可以申请一个长度为 $m+n$ 的数组，用于存储乘积的每一位。

从低位到高位，依次计算乘积的每一位，最后将数组转换为字符串即可。

注意判断最高位是否为 $0$，如果是，则去掉。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m+n)$。其中 $m$ 和 $n$ 分别为 $num1$ 和 $num2$ 的长度。

Python3

class Solution:def multiply(self, num1: str, num2: str) -> str:if num1 == "0" or num2 == "0":return "0"m, n = len(num1), len(num2)arr = [0] * (m + n)for i in range(m - 1, -1, -1):a = int(num1[i])for j in range(n - 1, -1, -1):b = int(num2[j])arr[i + j + 1] += a * bfor i in range(m + n - 1, 0, -1):arr[i - 1] += arr[i] // 10arr[i] %= 10i = 0 if arr[0] else 1return "".join(str(x) for x in arr[i:])

Java

class Solution {public String multiply(String num1, String num2) {if ("0".equals(num1) || "0".equals(num2)) {return "0";}int m = num1.length(), n = num2.length();int[] arr = new int[m + n];for (int i = m - 1; i >= 0; --i) {int a = num1.charAt(i) - '0';for (int j = n - 1; j >= 0; --j) {int b = num2.charAt(j) - '0';arr[i + j + 1] += a * b;}}for (int i = arr.length - 1; i > 0; --i) {arr[i - 1] += arr[i] / 10;arr[i] %= 10;}int i = arr[0] == 0 ? 1 : 0;StringBuilder ans = new StringBuilder();for (; i < arr.length; ++i) {ans.append(arr[i]);}return ans.toString();}
}

C++

class Solution {
public:string multiply(string num1, string num2) {if (num1 == "0" || num2 == "0") {return "0";}int m = num1.size(), n = num2.size();vector<int> arr(m + n);for (int i = m - 1; i >= 0; --i) {int a = num1[i] - '0';for (int j = n - 1; j >= 0; --j) {int b = num2[j] - '0';arr[i + j + 1] += a * b;}}for (int i = arr.size() - 1; i; --i) {arr[i - 1] += arr[i] / 10;arr[i] %= 10;}int i = arr[0] ? 0 : 1;string ans;for (; i < arr.size(); ++i) {ans += '0' + arr[i];}return ans;}
};

---

44. 通配符匹配

题目描述

• '?' 可以匹配任何单个字符。
• '*' 可以匹配任意字符序列（包括空字符序列）。

 

示例 1：

输入：s = “aa”, p = “a”
输出：false
解释：“a” 无法匹配 “aa” 整个字符串。

示例 2：

输入：s = “aa”, p = ""
输出：true
解释：’’ 可以匹配任意字符串。

示例 3：

输入：s = “cb”, p = “?a”
输出：false
解释：’?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。

 

提示：

• 0 <= s.length, p.length <= 2000
• s 仅由小写英文字母组成
• p 仅由小写英文字母、'?' 或 '*' 组成

难度：困难

标签：贪心,递归,字符串,动态规划

解法

方法一：记忆化搜索

我们设计一个函数 $dfs(i,j)$，表示从字符串 $s$ 的第 $i$ 个字符开始和字符串 $p$ 的第 $j$ 个字符开始是否匹配。那么答案就是 $dfs(0,0)$。

函数 $dfs(i,j)$ 的执行过程如下：

• 如果 $i\ge \text{len}(s)$，那么只有当 $j\ge \text{len}(p)$ 或者 $p[j]{=}^{\prime }{\ast }^{\prime }$ 且 $dfs(i,j+1)$ 为真时，$dfs(i,j)$ 才为真。
• 如果 $j\ge \text{len}(p)$，那么 $dfs(i,j)$ 为假。
• 如果 $p[j]{=}^{\prime }{\ast }^{\prime }$，那么 $dfs(i,j)$ 为真当且仅当 $dfs(i+1,j)$ 或 $dfs(i+1,j+1)$ 或 $dfs(i,j+1)$ 中有一个为真。
• 否则 $dfs(i,j)$ 为真当且仅当 $p[j]{=}^{\prime }{?}^{\prime }$ 或 $s[i]=p[j]$ 且 $dfs(i+1,j+1)$ 为真。

为了避免重复计算，我们使用记忆化搜索的方法，将 $dfs(i,j)$ 的结果存储在一个哈希表中。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别是字符串 $s$ 和 $p$ 的长度。

Python3

class Solution:def isMatch(self, s: str, p: str) -> bool:@cachedef dfs(i: int, j: int) -> bool:if i >= len(s):return j >= len(p) or (p[j] == "*" and dfs(i, j + 1))if j >= len(p):return Falseif p[j] == "*":return dfs(i + 1, j) or dfs(i + 1, j + 1) or dfs(i, j + 1)return (p[j] == "?" or s[i] == p[j]) and dfs(i + 1, j + 1)return dfs(0, 0)

Java

class Solution {private Boolean[][] f;private char[] s;private char[] p;private int m;private int n;public boolean isMatch(String s, String p) {this.s = s.toCharArray();this.p = p.toCharArray();m = s.length();n = p.length();f = new Boolean[m][n];return dfs(0, 0);}private boolean dfs(int i, int j) {if (i >= m) {return j >= n || (p[j] == '*' && dfs(i, j + 1));}if (j >= n) {return false;}if (f[i][j] != null) {return f[i][j];}if (p[j] == '*') {f[i][j] = dfs(i + 1, j) || dfs(i + 1, j + 1) || dfs(i, j + 1);} else {f[i][j] = (p[j] == '?' || s[i] == p[j]) && dfs(i + 1, j + 1);}return f[i][j];}
}

C++

class Solution {
public:bool isMatch(string s, string p) {int m = s.size(), n = p.size();int f[m + 1][n + 1];memset(f, -1, sizeof(f));function<bool(int, int)> dfs = [&](int i, int j) {if (i >= m) {return j >= n || (p[j] == '*' && dfs(i, j + 1));}if (j >= n) {return false;}if (f[i][j] != -1) {return f[i][j] == 1;}if (p[j] == '*') {f[i][j] = dfs(i + 1, j) || dfs(i, j + 1) ? 1 : 0;} else {f[i][j] = (p[j] == '?' || s[i] == p[j]) && dfs(i + 1, j + 1) ? 1 : 0;}return f[i][j] == 1;};return dfs(0, 0);}
};

---

45. 跳跃游戏 II

题目描述

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i] 
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

 

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
  从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

 

提示:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000
• 题目保证可以到达 nums[n-1]

难度：中等

标签：贪心,数组,动态规划

解法

方法一：贪心

我们可以用变量 $mx$ 记录当前位置能够到达的最远位置，用变量 $last$ 记录上一次跳跃到的位置，用变量 $ans$ 记录跳跃的次数。

接下来，我们遍历 $[0,..n-2]$ 的每一个位置 $i$，对于每一个位置 $i$，我们可以通过 $i+nums[i]$ 计算出当前位置能够到达的最远位置，我们用 $mx$ 来记录这个最远位置，即 $mx=max(mx,i+nums[i])$。接下来，判断当前位置是否到达了上一次跳跃的边界，即 $i=last$，如果到达了，那么我们就需要进行一次跳跃，将 $last$ 更新为 $mx$，并且将跳跃次数 $ans$ 增加 $1$。

最后，我们返回跳跃的次数 $ans$ 即可。

时间复杂度 $O(n)$，其中 $n$ 是数组的长度。空间复杂度 $O(1)$。

相似题目：

• 55. 跳跃游戏
• 1024. 视频拼接
• 1326. 灌溉花园的最少水龙头数目

Python3

class Solution:def jump(self, nums: List[int]) -> int:ans = mx = last = 0for i, x in enumerate(nums[:-1]):mx = max(mx, i + x)if last == i:ans += 1last = mxreturn ans

Java

class Solution {public int jump(int[] nums) {int ans = 0, mx = 0, last = 0;for (int i = 0; i < nums.length - 1; ++i) {mx = Math.max(mx, i + nums[i]);if (last == i) {++ans;last = mx;}}return ans;}
}

C++

class Solution {
public:int jump(vector<int>& nums) {int ans = 0, mx = 0, last = 0;for (int i = 0; i < nums.size() - 1; ++i) {mx = max(mx, i + nums[i]);if (last == i) {++ans;last = mx;}}return ans;}
};

---

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 中的所有整数 互不相同

难度：中等

标签：数组,回溯

解法

方法一：DFS（回溯）

我们设计一个函数 $dfs(i)$ 表示已经填完了前 $i$ 个位置，现在需要填第 $i+1$ 个位置。枚举所有可能的数，如果这个数没有被填过，就填入这个数，然后继续填下一个位置，直到填完所有的位置。

时间复杂度 $O(n\times n!)$，其中 $n$ 是数组的长度。一共有 $n!$ 个排列，每个排列需要 $O(n)$ 的时间来构造。

相似题目：

• 47. 全排列 II

Python3

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:return list(permutations(nums))

Python3

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:def dfs(i):if i == n:ans.append(t[:])returnfor j in range(n):if not vis[j]:vis[j] = Truet[i] = nums[j]dfs(i + 1)vis[j] = Falsen = len(nums)vis = [False] * nt = [0] * nans = []dfs(0)return ans

Java

class Solution {private List<List<Integer>> ans = new ArrayList<>();private List<Integer> t = new ArrayList<>();private boolean[] vis;private int[] nums;public List<List<Integer>> permute(int[] nums) {this.nums = nums;vis = new boolean[nums.length];dfs(0);return ans;}private void dfs(int i) {if (i == nums.length) {ans.add(new ArrayList<>(t));return;}for (int j = 0; j < nums.length; ++j) {if (!vis[j]) {vis[j] = true;t.add(nums[j]);dfs(i + 1);t.remove(t.size() - 1);vis[j] = false;}}}
}

C++

class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {int n = nums.size();vector<vector<int>> ans;vector<int> t(n);vector<bool> vis(n);function<void(int)> dfs = [&](int i) {if (i == n) {ans.emplace_back(t);return;}for (int j = 0; j < n; ++j) {if (!vis[j]) {vis[j] = true;t[i] = nums[j];dfs(i + 1);vis[j] = false;}}};dfs(0);return ans;}
};

---

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

难度：中等

标签：数组,回溯

解法

方法一：排序 + 回溯

我们可以先对数组进行排序，这样就可以将重复的数字放在一起，方便我们进行去重。

然后，我们设计一个函数 $dfs(i)$，表示当前需要填写第 $i$ 个位置的数。函数的具体实现如下：

• 如果 $i=n$，说明我们已经填写完毕，将当前排列加入答案数组中，然后返回。
• 否则，我们枚举第 $i$ 个位置的数 $nums[j]$，其中 $j$ 的范围是 $[0,n-1]$。我们需要保证 $nums[j]$ 没有被使用过，并且与前面枚举的数不同，这样才能保证当前排列不重复。如果满足条件，我们就可以填写 $nums[j]$，并继续递归地填写下一个位置，即调用 $dfs(i+1)$。在递归调用结束后，我们需要将 $nums[j]$ 标记为未使用，以便于进行后面的枚举。

在主函数中，我们首先对数组进行排序，然后调用 $dfs(0)$，即从第 0 个位置开始填写，最终返回答案数组即可。

时间复杂度 $O(n\times n!)$，空间复杂度 $O(n)$。其中 $n$ 是数组的长度。需要进行 $n!$ 次枚举，每次枚举需要 $O(n)$ 的时间来判断是否重复。另外，我们需要一个标记数组来标记每个位置是否被使用过，因此空间复杂度为 $O(n)$。

相似题目：

• 46. 全排列

Python3

class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:def dfs(i: int):if i == n:ans.append(t[:])returnfor j in range(n):if vis[j] or (j and nums[j] == nums[j - 1] and not vis[j - 1]):continuet[i] = nums[j]vis[j] = Truedfs(i + 1)vis[j] = Falsen = len(nums)nums.sort()ans = []t = [0] * nvis = [False] * ndfs(0)return ans

Java

class Solution {private List<List<Integer>> ans = new ArrayList<>();private List<Integer> t = new ArrayList<>();private int[] nums;private boolean[] vis;public List<List<Integer>> permuteUnique(int[] nums) {Arrays.sort(nums);this.nums = nums;vis = new boolean[nums.length];dfs(0);return ans;}private void dfs(int i) {if (i == nums.length) {ans.add(new ArrayList<>(t));return;}for (int j = 0; j < nums.length; ++j) {if (vis[j] || (j > 0 && nums[j] == nums[j - 1] && !vis[j - 1])) {continue;}t.add(nums[j]);vis[j] = true;dfs(i + 1);vis[j] = false;t.remove(t.size() - 1);}}
}

C++

class Solution {
public:vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());int n = nums.size();vector<vector<int>> ans;vector<int> t(n);vector<bool> vis(n);function<void(int)> dfs = [&](int i) {if (i == n) {ans.emplace_back(t);return;}for (int j = 0; j < n; ++j) {if (vis[j] || (j && nums[j] == nums[j - 1] && !vis[j - 1])) {continue;}t[i] = nums[j];vis[j] = true;dfs(i + 1);vis[j] = false;}};dfs(0);return ans;}
};

---

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

 

难度：中等

标签：数组,数学,矩阵

解法

方法一：原地翻转

根据题目要求，我们实际上需要将 $matrix[i][j]$ 旋转至 $matrix[j][n-i-1]$。

我们可以先对矩阵进行上下翻转，即 $matrix[i][j]$ 和 $matrix[n-i-1][j]$ 进行交换，然后再对矩阵进行主对角线翻转，即 $matrix[i][j]$ 和 $matrix[j][i]$ 进行交换。这样就能将 $matrix[i][j]$ 旋转至 $matrix[j][n-i-1]$ 了。

时间复杂度 $O(n^2)$，其中 $n$ 是矩阵的边长。空间复杂度 $O(1)$。

Python3

class Solution:def rotate(self, matrix: List[List[int]]) -> None:n = len(matrix)for i in range(n >> 1):for j in range(n):matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j]for i in range(n):for j in range(i):matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

Java

class Solution {public void rotate(int[][] matrix) {int n = matrix.length;for (int i = 0; i < n >> 1; ++i) {for (int j = 0; j < n; ++j) {int t = matrix[i][j];matrix[i][j] = matrix[n - i - 1][j];matrix[n - i - 1][j] = t;}}for (int i = 0; i < n; ++i) {for (int j = 0; j < i; ++j) {int t = matrix[i][j];matrix[i][j] = matrix[j][i];matrix[j][i] = t;}}}
}

C++

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n = matrix.size();for (int i = 0; i < n >> 1; ++i) {for (int j = 0; j < n; ++j) {swap(matrix[i][j], matrix[n - i - 1][j]);}}for (int i = 0; i < n; ++i) {for (int j = 0; j < i; ++j) {swap(matrix[i][j], matrix[j][i]);}}}
};

---

49. 字母异位词分组

题目描述

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

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

 

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = [“a”]
输出: [[“a”]]

 

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

难度：中等

标签：数组,哈希表,字符串,排序

解法

方法一：哈希表

1. 遍历字符串，对每个字符串按照字符字典序排序，得到一个新的字符串。
2. 以新字符串为 key，[str] 为 value，存入哈希表当中（HashMap<String, List<String>>）。
3. 后续遍历得到相同 key 时，将其加入到对应的 value 当中即可。

以 strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 为例，遍历结束时，哈希表的状况：

key	value
"aet"	["eat", "tea", "ate"]
"ant"	["tan", "nat"]
"abt"	["bat"]

最后返回哈希表的 value 列表即可。

时间复杂度 $O(n\times k\times \log k)$。其中 $n$ 和 $k$ 分别是字符串数组的长度和字符串的最大长度。

Python3

class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:d = defaultdict(list)for s in strs:k = ''.join(sorted(s))d[k].append(s)return list(d.values())

Java

class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> d = new HashMap<>();for (String s : strs) {char[] t = s.toCharArray();Arrays.sort(t);String k = String.valueOf(t);d.computeIfAbsent(k, key -> new ArrayList<>()).add(s);}return new ArrayList<>(d.values());}
}

C++

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> d;for (auto& s : strs) {string k = s;sort(k.begin(), k.end());d[k].emplace_back(s);}vector<vector<string>> ans;for (auto& [_, v] : d) ans.emplace_back(v);return ans;}
};

---

50. Pow(x, n)

题目描述

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

 

示例 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
• -231 <= n <= 231-1
• n 是一个整数
• 要么 x 不为零，要么 n > 0 。
• -104 <= xn <= 104

难度：中等

标签：递归,数学

解法

方法一：数学（快速幂）

快速幂算法的核心思想是将幂指数 $n$ 拆分为若干个二进制位上的 $1$ 的和，然后将 $x$ 的 $n$ 次幂转化为 $x$ 的若干个幂的乘积。

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。其中 $n$ 为幂指数。

Python3

class Solution:def myPow(self, x: float, n: int) -> float:def qpow(a: float, n: int) -> float:ans = 1while n:if n & 1:ans *= aa *= an >>= 1return ansreturn qpow(x, n) if n >= 0 else 1 / qpow(x, -n)

Java

class Solution {public double myPow(double x, int n) {return n >= 0 ? qpow(x, n) : 1 / qpow(x, -(long) n);}private double qpow(double a, long n) {double ans = 1;for (; n > 0; n >>= 1) {if ((n & 1) == 1) {ans = ans * a;}a = a * a;}return ans;}
}

C++

class Solution {
public:double myPow(double x, int n) {auto qpow = [](double a, long long n) {double ans = 1;for (; n; n >>= 1) {if (n & 1) {ans *= a;}a *= a;}return ans;};return n >= 0 ? qpow(x, n) : 1 / qpow(x, -(long long) n);}
};

---