【LeetCode Solutions】LeetCode 热题 100 题解（16 ~ 20）

普通数组 - LeetCode 238. 除自身以外数组的乘积（中等）

【题目描述】

给你一个整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。

请不要使用除法，且在 $O(n)$ 时间复杂度内完成此题。

【示例 1】

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

【示例 2】

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

【提示】

$2<=nums.length<=10^5$
$-30<=nums[i]<=30$
输入保证数组 answer[i] 在 32 位整数范围内

进阶：你可以在 $O(1)$ 的额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间）

【分析】

本题是前缀和的思想，不考虑空间要求的情况下我们可以预处理出两个数组 $p[i]$ 和 $s[i]$ 分别表示 $i$ 之前所有数的乘积（$nums[0]\ast nums[1]\ast \cdots \ast nums[i-1]$）以及 $i$ 之后所有数的乘积（$nums[i+1]\ast nums[i+2]\ast \cdots \ast nums[n-1]$）。

题目要求我们只能开一个额外的答案数组，那么我们可以将数组 $s$ 省去，先在输出数组中预处理出前缀乘积 $p$，然后我们再倒序遍历数组，遍历的过程中用一个变量记录当前的后缀乘积即可。

【代码】

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);
        res[0] = 1;  // 边界初始化
        for (int i = 1; i < n; i++)
            res[i] = res[i - 1] * nums[i - 1];  // res[i] 表示 [0, i - 1] 区间中所有元素的乘积
        for (int i = n - 1, mul = 1; ~i; i--)
            res[i] *= mul, mul *= nums[i];  // mul 表示 [i + 1, n - 1] 区间中所有元素的乘积
        return res;
    }
};

普通数组 - LeetCode 41. 缺失的第一个正数（困难）

【题目描述】

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

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

【示例 1】

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

【示例 2】

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

【示例 3】

输入：nums = [7,8,9,11,12]
输出：1

【提示】

$1\le nums.length\le 5\ast 10^5$
$-2^{31}\le nums[i]\le 2^{31}-1$

【分析】

注意本题的时空复杂度，不能用排序以及哈希表之类的做法。

我们可以用置换的方法求解，我们记 $n$ 为 $nums$ 的长度，因此答案一定在 $1\sim n+1$ 之间（因为最完美的情况是 $num$ 中有 $1\sim n$）。

我们利用两两交换的方法将 $num$ 中在 $1\sim n$ 范围内的数放置到其对应的位置上，也就是 nums[i] = i + 1。但其中有若干个位置上的数是错误的，每一个错误的位置就代表了一个缺失的正数。以 [3, 4, -1, 1] 为例，置换后的数组应当为 [1, -1, 3, 4]，我们就可以知道缺失的数为 $2$。

注意在交换的过程中应判断两数是否相等防止死循环。

【代码】

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++)
            // 将当前数置换到其对应的位置 num[i] - 1
            while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1])
                swap(nums[i], nums[nums[i] - 1]);
        for (int i = 0; i < n; i++)
            if (nums[i] != i + 1) return i + 1;  // 该位置上没有对应的正整数说明缺失了
        return n + 1;  // 1 ~ n 全部没有缺失
    }
};

矩阵 - LeetCode 73. 矩阵置零（中等）

【题目描述】

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

【示例 1】

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

【示例 2】

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

【提示】

$m==matrix.length$
$n==matrix[0].length$
$1\le m,n\le 200$
$-2^{31}\le matrix[i][j]\le 2^{31}-1$

【分析】

我们需要用原矩阵的第一行来记录每一列是否有 0，用第一列来记录每一行是否有 0。但是第一行与第一列是否有 0 的信息无法保存，因此还需要使用两个额外的变量来记录第一行与第一列是否有 0。

【代码】

class Solution {
public:
    void setZeroes(vector<vector<int>>& g) {
        bool r0 = false, c0 = false;  // 第一行或者第一列是否有 0
        for (int i = 0; i < g[0].size(); i++)  // 判断第一行是否有 0
            if (!g[0][i]) { r0 = true; break; }
        for (int i = 0; i < g.size(); i++)  // 判断第一列是否有 0
            if (!g[i][0]) { c0 = true; break; }
        for (int i = 1; i < g.size(); i++)  // 判断其余行是否有 0
            for (int j = 1; j < g[0].size(); j++)
                if (!g[i][j]) { g[i][0] = 0; break; }
        for (int i = 1; i < g[0].size(); i++)  // 判断其余列是否有 0
            for (int j = 1; j < g.size(); j++)
                if (!g[j][i]) { g[0][i] = 0; break; }
        for (int i = 1; i < g[0].size(); i++)  // 遍历第一行，将为 0 的元素所在的列置零
            if (!g[0][i])
                for (int j = 1; j < g.size(); j++)
                    g[j][i] = 0;
        for (int i = 1; i < g.size(); i++)  // 遍历第一列，将为 0 的元素所在的行置零
            if (!g[i][0])
                for (int j = 1; j < g[0].size(); j++)
                    g[i][j] = 0;
        if (r0) for (int i = 0; i < g[0].size(); i++) g[0][i] = 0;  // 第一行置零
        if (c0) for (int i = 0; i < g.size(); i++) g[i][0] = 0;  // 第一列置零
    }
};

矩阵 - LeetCode 54. 螺旋矩阵（中等）

【题目描述】

给你一个 m 行 n 列的矩阵 matrix，请按照顺时针螺旋顺序，返回矩阵中的所有元素。

【示例 1】

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

【示例 2】

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

【提示】

$m==matrix.length$
$n==matrix[i].length$
$1\le m,n\le 10$
$-100\le matrix[i][j]\le 100$

【分析】

分别设置向右、向下、向左、向上四个方向向量，然后模拟一遍即可，走出界或是已经遍历过了改变一下方向即可。

【代码】

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        int dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 };  // 分别表示右、下、左、上的方向向量
        vector<int> res;
        for (int i = 0, x = 0, y = 0, d = 0; i < n * m; i++) {  // 总共遍历 n * m 个点
            res.push_back(matrix[x][y]);
            matrix[x][y] = INT_MIN;  // 遍历过的数修改为 INT_MIN
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || matrix[nx][ny] == INT_MIN) d = (d + 1) % 4;
            x += dx[d], y += dy[d];
        }
        return res;
    }
};

矩阵 - 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]]

【示例 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\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

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

【代码】

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