美文网首页刷题总结
谈两道LeetCode——跳跃游戏,矩阵置零

谈两道LeetCode——跳跃游戏,矩阵置零

作者: 思想永不平凡 | 来源:发表于2019-11-24 17:53 被阅读0次

标题说明了一切,话不多说,开始正文吧!


跳跃游戏

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/jump-game

题目分析与解题

一开始看错题目了,以为数组中的元素就表示当前跳跃的固定距离了,结果发现写错了。。。
后来发现是最大长度。
其实解法有很多了,很多大佬给出了各式各样的解题思路,让人叹为观止,这里介绍一种比较简单的方法吧

需要注意到:
当我们到达一个地方时i,下一步可以到达的最远的地方是i+nums[i]。
同时需要注意的是,并不是跳得越远就可以到达终点的(这里的意思是,不能当到达某一点后就以当前点可到的最大长度进行下一次跳跃)。
下一步最远可以到达的最远地方i+nums[i]之前的点都是可达的。
在正确的路径下,到达终点前的一个点i,有i+nums[i] >= nums.size()-1,返回true。
在没有正确的路径下,最后一个可以到达的点,有i+nums[i] < nums.size()-1,返回false。

在进行一番分析后,我们大致有了思路,虽然要注意的东西有很多,但是程序可以多多精简一些
程序如下:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int index=0;
        for(int i=0;i<nums.size();i++){
            if(i>index)
                return false;
            if(index>=nums.size()-1)
                return true;
            index=max(index,i+nums[i]);
        }
        return true;
    }
};

结果如下:

图片.png 图片.png

值得说明的是
index=max(index,i+nums[i]);
始终表示可以到达的最大位置,同时在此之前的位置都是可达的
直到到达的位置大于终点

这个提交的结果还不错

下一题!!!

矩阵置零

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

示例 1:

输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]

示例 2:

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

进阶:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/set-matrix-zeroes

题目分析与解题

鉴于进阶处的提示,不妨就使用常数空间来解决吧

个人觉得,本题很重要的一点应该是标志位了,使用O(mn)或者O(m + n)来做都不难,用常数空间来解决,还是有不少需要注意的地方

这里介绍下本人的思路吧

应该需要先遍历一遍矩阵,记住那些行列是需要置零的,绝对不是边扫描边置零的

行列都需要标志,而我们却只使用常数空间,用什么来标志呢?

当然是矩阵的原有空间啦,那放在哪呢?

为了不影响遍历,我们可以使用第一行,第一列,如何标志呢?

遍历的时候,如果某一个元素 matrix[i][j] 为0,那么 matrix[i][0],matrix[0][j]赋值为0,在遍历为完成后,扫描第一行,将为0的元素所在的所有列置零。扫描第一列时,将为0的元素所在的所有行置零。那这样似乎就大功告成了,是吗?

不是,还有坑呢,试想下,这个方法确实很好,但是,对矩阵所有元素都是可以的吗?不是,我们用第一行,列作为标志位,对除第一行,列的所有元素都能处理,但是,第一行,列有0的元素,那么它所在的行,列是不是忘了置零呢?

那么我们可以额外设置两个标志位来标志第一行,列是否含有0元素,如果有,第一行的所有元素都要置零,第一列也是如此

经过上面这些理性分析(胡乱分析),这个题基本上差不多了,虽然题不算难,但是在常数空间下完成,需要注意的东西还是有不少的。

程序如下:

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int lines=matrix.size();
        int lists=matrix[0].size();
        bool line=false;
        bool list=false;
        for(int i=0;i<lines;i++){
            for(int j=0;j<lists;j++){
                if(matrix[i][j]==0&&i!=0&&j!=0){
                    matrix[0][j]=0;
                    matrix[i][0]=0;
                }
                if(i==0&&matrix[0][j]==0){
                    line=true;
                }
                if(j==0&&matrix[i][0]==0){
                    list=true;
                }
            }
        }
        //将第1至最后一列含0的列所在的行赋值为0
        //若这些列有0,行置零
        for(int j=1;j<lists;j++){
            if(matrix[0][j]==0){
                for(int i=0;i<lines;i++){
                    matrix[i][j]=0;
                }
            }
        }
        //将第1至最后一行含0的列所在的行赋值为0
        //若这些行有0,列置零
        for(int i=1;i<lines;i++){
            if(matrix[i][0]==0){
                for(int j=0;j<lists;j++){
                    matrix[i][j]=0;
                }
            }
        }
        if(line){
            for(int j=0;j<lists;j++){
                matrix[0][j]=0;
            }
        }
        if(list){
            for(int i=0;i<lines;i++){
                matrix[i][0]=0;
            }
        }
    }
};

结果如下:

图片.png 图片.png

提交结果还算不错

相关文章

  • 谈两道LeetCode——跳跃游戏,矩阵置零

    标题说明了一切,话不多说,开始正文吧! 跳跃游戏 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个...

  • Leetcode 矩阵置零

    题目描述(中等难度) 给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。...

  • 73 矩阵清零

    73. 矩阵置零[https://leetcode-cn.com/problems/set-matrix-zero...

  • Python小白 Leetcode刷题历程 No.71-N

    Python小白 Leetcode刷题历程 No.71-No.75 简化路径、编辑距离、矩阵置零、搜索...

  • leetcode 73 矩阵置零

    先扫描二维矩阵,如果出现 0 元素,将首行对应列和首列对应行置 0,并记录首行和首列是否有自身出现过的 0 元素。...

  • LeetCode - #73 矩阵置零

    前言 我们社区陆续会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。)的 Swi...

  • 矩阵置零

    矩阵置零 [https://imgtu.com/i/64W7Uf] https://leetcode-cn.com...

  • leetcode73 矩阵置零

    要点在于分成两部分标记,负责第一行和第一列的标记/其余部分的标记,注意(0,0)是特殊位置,应该特殊处理

  • 【leetcode-数组】矩阵置零

    【leetcode-数组】矩阵置零 给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都...

  • leetcode 73. 矩阵置零

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

网友评论

    本文标题:谈两道LeetCode——跳跃游戏,矩阵置零

    本文链接:https://www.haomeiwen.com/subject/krglwctx.html