Leetcode: 0041-0050题速览-EW帮帮网

微信交流群：https://732903.hlcode.cn/?id=NK1fWUR

Leetcode: 0041-0050题速览

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

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

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

Leetcode: 0041-0050题速览
- [41. 缺失的第一个正数](https://leetcode.cn/problems/first-missing-positive)
- - 题目描述
  - 解法
  - - 方法一：原地交换
    - - Python3
      - Java
      - C++
- [42. 接雨水](https://leetcode.cn/problems/trapping-rain-water)
- - 题目描述
  - 解法
  - - 方法一：动态规划
    - - Python3
      - Java
      - C++
- [43. 字符串相乘](https://leetcode.cn/problems/multiply-strings)
- - 题目描述
  - 解法
  - - 方法一：数学乘法模拟
    - - Python3
      - Java
      - C++
- [44. 通配符匹配](https://leetcode.cn/problems/wildcard-matching)
- - 题目描述
  - 解法
  - - 方法一：记忆化搜索
    - - Python3
      - Java
      - C++
- [45. 跳跃游戏 II](https://leetcode.cn/problems/jump-game-ii)
- - 题目描述
  - 解法
  - - 方法一：贪心
    - - Python3
      - Java
      - C++
- [46. 全排列](https://leetcode.cn/problems/permutations)
- - 题目描述
  - 解法
  - - 方法一：DFS（回溯）
    - - Python3
      - Python3
      - Java
      - C++
- [47. 全排列 II](https://leetcode.cn/problems/permutations-ii)
- - 题目描述
  - 解法
  - - 方法一：排序 + 回溯
    - - Python3
      - Java
      - C++
- [48. 旋转图像](https://leetcode.cn/problems/rotate-image)
- - 题目描述
  - 解法
  - - 方法一：原地翻转
    - - Python3
      - Java
      - C++
- [49. 字母异位词分组](https://leetcode.cn/problems/group-anagrams)
- - 题目描述
  - 解法
  - - 方法一：哈希表
    - - Python3
      - Java
      - C++
- [50. Pow(x, n)](https://leetcode.cn/problems/powx-n)
- - 题目描述
  - 解法
  - - 方法一：数学（快速幂）
    - - Python3
      - Java
      - C++

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 <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1

难度：困难

标签：数组,哈希表

解法

方法一：原地交换

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

遍历结束后，我们再遍历数组，如果 $i + 1$ 不等于 $n u m s [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 + 1
        return 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 * 10⁴
0 <= height[i] <= 10⁵

难度：困难

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

解法

方法一：动态规划

我们定义 $l e f t [i]$ 表示下标 $i$ 位置及其左边的最高柱子的高度，定义 $r i g h t [i]$ 表示下标 $i$ 位置及其右边的最高柱子的高度。那么下标 $i$ 位置能接的雨水量为 $\min(left[i], right[i]) - height[i]$ 。我们遍历数组，计算出 $l e f t [i]$ 和 $r i g h t [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]] * n
        right = [height[-1]] * n
        for 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本身。

难度：中等

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

解法

方法一：数学乘法模拟

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

证明如下：

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

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

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

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

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

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 * b
        for i in range(m + n - 1, 0, -1):
            arr[i - 1] += arr[i] // 10
            arr[i] %= 10
        i = 0 if arr[0] else 1
        return "".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. 通配符匹配

题目描述

给你一个输入字符串 ( s) 和一个字符模式 ( p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：

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

判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

示例 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 仅由小写英文字母、'?' 或 '*' 组成

难度：困难

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

解法

方法一：记忆化搜索

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

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

如果 $\geq \textit{len}(s)$ ，那么只有当 $\geq \textit{len}(p)$ 或者 $p [j] =^{'} *^{'}$ 且 $d f s (i, j + 1)$ 为真时， $d f s (i, j)$ 才为真。
如果 $\geq \textit{len}(p)$ ，那么 $d f s (i, j)$ 为假。
如果 $p [j] =^{'} *^{'}$ ，那么 $d f s (i, j)$ 为真当且仅当 $d f s (i + 1, j)$ 或 $d f s (i + 1, j + 1)$ 或 $d f s (i, j + 1)$ 中有一个为真。
否则 $d f s (i, j)$ 为真当且仅当 $p [j] =^{'} ?^{'}$ 或 $s [i] = p [j]$ 且 $d f s (i + 1, j + 1)$ 为真。

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

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

Python3

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        @cache
        def 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 False
            if 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 <= 10⁴
0 <= nums[i] <= 1000
题目保证可以到达 nums[n-1]

难度：中等

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

解法

方法一：贪心

我们可以用变量 $m x$ 记录当前位置能够到达的最远位置，用变量 $l a s t$ 记录上一次跳跃到的位置，用变量 $a n s$ 记录跳跃的次数。

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

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

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

相似题目：

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

Python3

class Solution:
    def jump(self, nums: List[int]) -> int:
        ans = mx = last = 0
        for i, x in enumerate(nums[:-1]):
            mx = max(mx, i + x)
            if last == i:
                ans += 1
                last = mx
        return 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（回溯）

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

时间复杂度 $\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[:])
                return
            for j in range(n):
                if not vis[j]:
                    vis[j] = True
                    t[i] = nums[j]
                    dfs(i + 1)
                    vis[j] = False

        n = len(nums)
        vis = [False] * n
        t = [0] * n
        ans = []
        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

难度：中等

标签：数组,回溯

解法

方法一：排序 + 回溯

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

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

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

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

时间复杂度 $\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[:])
                return
            for j in range(n):
                if vis[j] or (j and nums[j] == nums[j - 1] and not vis[j - 1]):
                    continue
                t[i] = nums[j]
                vis[j] = True
                dfs(i + 1)
                vis[j] = False

        n = len(nums)
        nums.sort()
        ans = []
        t = [0] * n
        vis = [False] * n
        dfs(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

难度：中等

标签：数组,数学,矩阵

解法

方法一：原地翻转

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

我们可以先对矩阵进行上下翻转，即 $m a t r i x [i] [j]$ 和 $m a t r i x [n - i - 1] [j]$ 进行交换，然后再对矩阵进行主对角线翻转，即 $m a t r i x [i] [j]$ 和 $m a t r i x [j] [i]$ 进行交换。这样就能将 $m a t r i x [i] [j]$ 旋转至 $m a t r i x [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 <= 10⁴
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

难度：中等

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

解法

方法一：哈希表

遍历字符串，对每个字符串按照字符字典序排序，得到一个新的字符串。
以新字符串为 key，[str] 为 value，存入哈希表当中（HashMap<String, List<String>>）。
后续遍历得到相同 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 次幂函数（即，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⁴

难度：中等

标签：递归,数学

解法

方法一：数学（快速幂）

快速幂算法的核心思想是将幂指数 $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 = 1
            while n:
                if n & 1:
                    ans *= a
                a *= a
                n >>= 1
            return ans

        return 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);
    }
};

Leetcode: 0041-0050题速览