【LeetCode算法系列题解】第46~50题

LeetCode 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]]
1
2

【示例2】

输入：nums = [0,1]
输出：[[0,1],[1,0]]
1
2

【示例3】

输入：nums = [1]
输出：[[1]]
1
2

【提示】

$1\le nums.length\le 6$
$-10\le nums[i]\le 10$
nums 中的所有整数互不相同

【分析】

---

全排列的裸题，DFS 入门题，不需要过多讲解了，由于题目保证每个数互不相同，因此可以用一个整数的二进制中的每一位表示某个数是否已被使用，省去开标记数组的额外空间开销。

当然，用 next_permutation 函数也是可以秒杀的，不过面试肯定还是要会手搓~

---

【代码】

【next_permutation 函数实现】

class Solution {
public:
    vector<vector<int>> res;

    vector<vector<int>> permute(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        do {
            res.push_back(nums);
        } while (next_permutation(nums.begin(), nums.end()));
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

【DFS 实现】

class Solution {
public:
    vector<vector<int>> res;
    vector<int> v;

    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums, 0, 0);
        return res;
    }

    void dfs(vector<int>& nums, int u, int state)  // state二进制的第i位表示i是否已被使用
    {
        if (u == nums.size()) { res.push_back(v); return; }
        for (int i = 0; i < nums.size(); i++)
            if (!(state >> nums[i] + 10 & 1))  // 判断state的第i位是否为1，注意将nums[i]映射成0~20
            {
                v.push_back(nums[i]);
                dfs(nums, u + 1, state | 1 << nums[i] + 10);
                v.pop_back();
            }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

LeetCode 47. 全排列 II（中等）

【题目描述】

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

【示例1】

输入：nums = [1,1,2]
输出：[[1,1,2],[1,2,1],[2,1,1]]
1
2

【示例2】

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
1
2

【提示】

$1\le nums.length\le 8$
$-10\le nums[i]\le 10$

【分析】

---

这一题和上一题的差别在于数字可能有重复，因此需要考虑如何控制搜索出来的序列不会重复。对于相同的数，我们应该规定他们的顺序，比如统一按升序排列或者降序排列，这样相同的数的排列就只会有一种对应关系。

如何实现这一操作呢？我们先对数组进行排序，我们要保证答案中相同数的相对位置和原始数组一样，因此我们在枚举每个数 nums[i] 的时候，如果 nums[i] == nums[i - 1]，且 nums[i - 1] 还没有被使用，那么 nums[i] 也不能使用。我们在这题中使用 state 二进制的第 $i$ 位表示 nums[i] 是否被使用。

---

【代码】

class Solution {
public:
    vector<vector<int>> res;
    vector<int> v;

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());  // 先排好序
        dfs(nums, 0, 0);
        return res;
    }

    void dfs(vector<int>& nums, int u, int state)
    {
        if (u == nums.size()) { res.push_back(v); return; }
        for (int i = 0; i < nums.size(); i++)
            // 如果当前数和前一个数相等但是前一个数没被用过那么当前数也不能用
            if (i && nums[i] == nums[i - 1] && !(state >> i - 1 & 1)) continue;
            else if (!(state >> i & 1))  // 判断第i个数是否被使用
            {
                v.push_back(nums[i]);
                dfs(nums, u + 1, state | 1 << i);
                v.pop_back();
            }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

LeetCode 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]]
1
2

【示例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]]
1
2

【提示】

$n==matrix.length==matrix[i].length$
$1\le n\le 20$
$-1000\le matrix[i][j]\le 1000$

【分析】

---

我们先给出一个变换过程的例子：

1 2 3      1 4 7      7 4 1
4 5 6  =>  2 5 8  =>  8 5 2
7 8 9      3 6 9      9 6 3
1
2
3

该过程很简单，但是没有接触过类似题目的话确实很难想出来，首先沿着主对角线进行翻转，然后沿着列的中轴进行翻转即可。

---

【代码】

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 沿对角线翻转
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                swap(matrix[i][j], matrix[j][i]);
        // 沿列中轴线翻转
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n >> 1; j++)
                swap(matrix[i][j], matrix[i][n - 1 - j]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode 49. 字母异位词分组（中等）

【题目描述】

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。
字母异位词是由重新排列源单词的所有字母得到的一个新单词。

【示例1】

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
1
2

【示例2】

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

【示例3】

输入: strs = ["a"]
输出: [["a"]]
1
2

【提示】

$1\le strs.length\le 10^4$
$0\le strs[i].length\le 100$
strs[i] 仅包含小写字母

【分析】

---

我们可以将每个字符串按字典序排序，这样如果两个字符串所含的字符相同那么排序后的字符串一定也相同，然后我们再用一个哈希表记录每类字符串即可。

---

【代码】

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string, int> st;  // 记录每一类的下标
        int idx = 0;
        for (auto s: strs)
        {
            string t = s;
            sort(t.begin(), t.end());
            if (!st[t]) st[t] = ++idx, res.push_back(vector<string> { s });
            else res[st[t] - 1].push_back(s);  // 注意vector中下标从0开始
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

LeetCode 50. Pow(x, n)（中等）

【题目描述】

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

【示例1】

输入：x = 2.00000, n = 10
输出：1024.00000
1
2

【示例2】

输入：x = 2.10000, n = 3
输出：9.26100
1
2

【示例3】

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
1
2
3

【提示】

$-100.0<x<100.0$
$-2^{31}\le n\le 2^{31}-1$
n 是一个整数
要么 x 不为零，要么 n > 0。
$-10^4\le x^n\le 10^4$

【分析】

---

快速幂裸题，统一将 $n$ 转为非负数再求解，最后再根据 $n$ 的正负修改结果即可（$x^{-n}=\frac{1}{x^n}$）。注意如果 $n$ 为 INT_MIN 直接转换为正数会溢出，因此需要开 long long。

---

【代码】

class Solution {
public:
    double myPow(double x, int n) {
        double res = 1;
        for (long long k = abs((long long)n); k; k >>= 1)
        {
            if (k & 1) res *= x;
            x *= x;
        }
        if (n < 0) res = 1 / res;
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13