标题说明了一切，话不多说，开始正文吧！
跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 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
提交结果还算不错
网友评论