Leetcode 45&55 - 跳跃游戏

题目1 (Leetcode 55)：

给定一个非负整数数组 nums ，你最初位于数组的第一个下标。

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

判断你是否能够到达最后一个下标。

示例 1：

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

输出：true

解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

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

输出：false

解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ，所以永远不可能到达最后一个下标。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game/

分析：此题是判断能否到达。

思路1：从后往前跑一边数组，判断当前位置加权值能否大于最大数组下标，若能将问题缩小化。

法1：

 1 class Solution {
 2 public:
 3     bool canJump(vector<int>& nums) {
 4         int temp =nums.size()-1-1; //temp 下标 从倒数第二个开始
 5         if (nums.size()==1)
 6             return 1;
 7         else
 8         {
 9             int last = nums.size()-1;
10             for(int i=temp;i>=0;i--) //从后往前
11             {
12                 if(nums[i]+i >= last)
13                     last = i; //更新最后标志，问题缩小
14             }
15 
16             if(last==0)
17                 return 1;
18             else
19                 return 0;
20         }
21     }
22 };

思路2：从头开始，贪心算法，每个位置都计算自己能达到的最远距离，同时每个位置要判断自己是否可达，也就是本位置需要在当前最远能到达的距离中。最终计算出来能到达的最远距离，与数组长度比较即可。

法2：

 1 class Solution {
 2 public:
 3     bool canJump(vector<int>& nums) {
 4         int len = nums.size();
 5         if (len <= 1) return true;
 6 
 7         int maxDis = nums[0];
 8 
 9         for (int i = 1; i < len - 1; i++) {
10             if (i <= maxDis) {
11                 maxDis = max(maxDis, nums[i]+i);
12             }
13         }
14 
15         return maxDis >= len - 1;
16     }
17 };

题目2 (Leetcode 45)：

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

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

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game-ii

分析：此问题区别于上述问题，此题肯定能到达，取最短。类似于Dijkstra算法的变形，BFS广度优先算法

例：以【2,3,1,1,4】数组为例

此题就只找从开始下标为0-->n-1的最少边数显然0-->1-->4 输出为 2

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include<vector>
 4 using namespace std;
 5 class Solution {
 6 public:
 7     int jump(vector<int>& nums) {
 8         int end=0;
 9         int start=0;
10         int max;    // 最大逾越
11         int i;      //记录最大值，和下标
12         int time=0;//跳跃次数
13         while(end < nums.size()-1)  //当end 下标大于数组下标退出
14         {
15             max = end;          
16             for(i=start;i<=end;i++)  //相当于图的BFS搜索 取与父节点相邻子节点中 下标与值和的最大者
17             {
18                 if(nums[i]+i>max)    
19                 {
20                     max = nums[i]+i;
21                 }
22             }
23             start = end+1;   //更新起点
24             end = max;       //更新尾点
25             time++;
26         }
27         return time;
28     }
29 
30 };
31 int main(){
32     int n,i,x;
33     Solution b;
34     cin>>n;
35     vector<int> a;
36     for(i=0;i<n;i++)
37     {
38         cin>>x;
39         a.push_back(x);
40     }
41     cout<<b.jump(a);
42 }

另外补充 vector 类用法

详细见：https://blog.csdn.net/Linux_bin/article/details/81942152?utm_term=vector%E7%B1%BB&utm_medium=distribute.pc_aggpage_search_result.none-task-blog-2~all~sobaiduweb~default-0-81942152&spm=3001.4430

它是一种顺序容器，支持随机访问。vector是一块连续分配的内存，从数据安排的角度来讲，和数组极其相似，不同的地方就是：数组是静态分配空间，一旦分配了空间的大小，就不可再改变了；而vector是动态分配空间，随着元素的不断插入，它会按照自身的一套机制不断扩充自身的容量。

vector的扩充机制：按照容器现在容量的一倍进行增长。vector容器分配的是一块连续的内存空间，每次容器的增长，并不是在原有连续的内存空间后再进行简单的叠加，而是重新申请一块更大的新内存，并把现有容器中的元素逐个复制过去，然后销毁旧的内存。这时原有指向旧内存空间的迭代器已经失效，所以当操作容器时，迭代器要及时更新。

1.push_back   在数组的最后添加一个数据
2.pop_back    去掉数组的最后一个数据
3.at                得到编号位置的数据
4.begin           得到数组头的指针
5.end             得到数组的最后一个单元+1的指针
6．front        得到数组头的引用
7.back            得到数组的最后一个单元的引用
8.max_size     得到vector最大可以是多大
9.capacity       当前vector分配的大小
10.size           当前使用数据的大小
11.resize         改变当前使用数据的大小，如果它比当前使用的大，者填充默认值
12.reserve      改变当前vecotr所分配空间的大小
13.erase         删除指针指向的数据项
14.clear          清空当前的vector
15.rbegin        将vector反转后的开始指针返回(其实就是原来的end-1)
16.rend          将vector反转构的结束指针返回(其实就是原来的begin-1)
17.empty        判断vector是否为空
18.swap         与另一个vector交换数据

Leetcode 45&55 - 跳跃游戏

推荐阅读