本文共 1278 字,大约阅读时间需要 4 分钟。
给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]输出: true解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4]输出: false解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。
解题思路:
倒数第二个位置开始往前寻找一个能够跳到末尾的点pos,如果没找到,那么返回fasle;如果找到了,将终点改为pos,继续往前搜索能跳到终点的值,如果到数组开始找不到当前的终点,那么返回false,如果能则返回true。
class Solution { public: bool canJump(vector<int>& nums) { int size = nums.size(); if (size == 1) return true; int pos = size - 1; bool sgn = false; for (int i = size - 2; i >= 0; i--) { if (nums[i] + i >= pos) { pos = i; sgn = true; } else { sgn = false; } } return sgn; } }; |
深入思考:如果要找最小次数(路径)的话,显然用DFS才能做出来,需要将下列的代码加以改造。
class Solution { public: bool canJump(vector<int>& nums) { int size = nums.size(); data = nums; visit = vector<bool>(size, false); return DFS(0); } bool DFS(int pos) { //返回从pos位置起跳能否到末尾 visit[pos] = true; if (pos == int(data.size())-1) return true; if (data[pos] == 0) return false; int left = pos - data[pos], right = pos + data[pos]; if (left < 0) left = 0; if (right >= int(data.size()) - 1) return true; //调到任何一个没有访问的点 for (int i = right; i <= left; i--) { if (visit[i] == false) { bool sgn=DFS(i); if (sgn == true) return true; } } return false; } private: vector<int> data; vector<bool> visit; }; |
转载地址:http://frfjn.baihongyu.com/