当前位置：首页 > article >正文

【HOT100第四天】除自身以外数组的乘积,矩阵置零,螺旋矩阵,旋转图像

article 2024/11/23 12:03:51

今天感觉是边界值练习专场。。。整体难度不大但是细节还是需要多动手写一写。

238. 除自身以外的数组的乘积

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

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

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

没看提示前隐隐约约感觉应该用前缀法，但是没想清楚到底要如何下手。原来这道题是要把前缀和后缀结合着一起用！

稍微回顾一下前缀法吧！上一次使用前缀法是在 560.和为K的子数组 这里用的，主要思路就是借助 $a_{n}=S_{n}-S_{n-1}$ 来推导出一个子串中元素的和如何用前缀和来表示和计算。

这里思路也差不多，不过既然要算的是数组的乘积，就暂且叫它前缀积数组 pre(n,1) 吧！【后面n和1的意思就是长度为n，每一项默认值为1】然后后缀积数组 suf(n,1) 。

思考一下 ans 数组的每一项是怎么计算出来的，以{1,2,3,4}为例，ans[0]=2x3x4，ans[1]=1x3x4。。。。如果把乘进去的数字分类，不就可以分成 i 之前的数字和 i 之后的数字吗？这不就是（前缀积x后缀积）吗。这样代码就可以写出来了👇【三个for循环可以写成两个，后两个可以合并在一起写】

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> ans(n,1),pre(n,1),suf(n,1);
        for(int i=1;i<n;i++){
            pre[i]=pre[i-1]*nums[i-1];
        }
        for(int i=n-2;i>=0;i--){
            suf[i]=suf[i+1]*nums[i+1];
        }
        for(int i=0;i<n;i++){
            ans[i]=pre[i]*suf[i];
        }
        return ans;
    }
};

因为考虑到只要数组中有一个数字是0，那么ans中除了0这个位置的乘积以外，其他地方一定为零，那可以尝试剪枝。

但写完比较了一下执行用时并没有显著提升，还不如从把第二个和第三个for循环写在一起的方法出发来改进。因为思路还是一样的所以就不写了。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size(),flag=-1;
        vector<int> ans(n),pre(n,1),suf(n,1);
        for(int i=1;i<n;i++){
            pre[i]=pre[i-1]*nums[i-1];
            if(nums[i]==0){
                flag=i;
                break;
            }
        }
        for(int i=n-2;i>=0;i--){
            suf[i]=suf[i+1]*nums[i+1];
            if(flag>0&&i==flag) break;
        }
        if(flag>0){
            ans[flag]=pre[flag]*suf[flag];
            return ans;
        }
        for(int i=0;i<n;i++){
            ans[i]=pre[i]*suf[i];
        }
        return ans;
    }
};

一点点小感想：以后做算法题，如果看到 “数组” “元素之间的计算” “无序” 这几个属性，多半就可以考虑一下是不是应该用前缀法做了。

73. 矩阵置零

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

进阶：

一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？

定睛一看专业对口，之前做数独游戏的时候，高亮选中数字的行和列时也用过相似的算法，只要保存好要处理的行和列，最后修改一下就行了。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<bool> zeroRows(rows, false);
        vector<bool> zeroCols(cols, false);

        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (matrix[i][j] == 0) {
                    zeroRows[i] = true;
                    zeroCols[j] = true;
                }
            }
        }
        for (int i = 0; i < rows; ++i) {
            if (zeroRows[i]) {
                for (int j = 0; j < cols; ++j) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int j = 0; j < cols; ++j) {
            if (zeroCols[j]) {
                for (int i = 0; i < rows; ++i) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
};

结果一看进阶要求，居然可以仅用一个常量空间解决吗？？

先挖个坑改天看看。。。太困了。。。

54. 螺旋矩阵

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

第一眼：有点意思

第二眼：纯折磨（。。。）

主要就是找到应该如何循环，然后划分成四个方向（也就是四个for循环），还有四个边界（top、bottom、left、right），上下左右，每次遍历完一个方向，就通过减小边界值来缩小边界。

注意while循环的边界值，如果只有一行数了，将会出现top=bottom和left=right的情况，所以要带上等于。

【如果一直内存地址溢出，就多看看边界值是不是设错了，m和n是不是设反了】

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        if (m == 0 || n == 0)
            return {};
        int top = 0, bottom = m - 1, left = 0, right = n - 1;
        vector<int> ans;
        while (top <= bottom && left <= right) {
            for (int i = left; i <= right; i++) ans.emplace_back(matrix[top][i]);
            top++;
            if (top > bottom) break;
            for (int i = top; i <= bottom; i++) ans.emplace_back(matrix[i][right]);
            right--;
            if (left > right) break;
            for (int i = right; i >= left; i--) ans.emplace_back(matrix[bottom][i]);
            bottom--;
            if (top > bottom) break;
            for (int i = bottom; i >= top; i--) ans.emplace_back(matrix[i][left]);
            left++;
            if (left > right) break;
        }
        return ans;
    }
};

48.旋转图像

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

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

想学线性代数的有福了。思考一下可不可以通过简单的矩阵变换，让当前矩阵变成旋转90度的样子？

有的，先延水平轴翻转一下，再延对角线翻转，像这样：

$\begin{bmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7& 8& 9 \end{bmatrix}$ 水平向下翻转👉 $\begin{bmatrix} 7 & 8 &9 \\ 4& 5& 6\\ 1 & 2 & 3 \end{bmatrix}$ 最后延对角翻转👉 $\begin{bmatrix} 7 & 4 &1 \\ 8& 5& 2\\ 9 & 6 & 3 \end{bmatrix}$

注意，代码中想要实现翻转，只需要遍历一半的数组，不是全部（不然就翻转回来了）。

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();
        for(int i=0;i<n/2;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]);
            }
        }
    }
};

查看全文

http://www.kler.cn/a/403678.html