Fork me on GitHub

Leetcode-SIX-jumpGame

发表于 | 分类于 | 阅读次数:

Jump Game II

Description

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Note: You can assume that you can always reach the last index.

Example

Input: [2,3,1,1,4]
Output: 2

Explanation:
The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.

Analysis

看起来很有意思的一道题目。题目给出一个数组arr，我们起始站在arr[0]，要沿着数组往前跳，而数组的最后一个元素代表终点。数组每个元素的值arr[i]，代表在当前位置能跳的最远距离(可以选择跳[1, arr[i]]个距离)。问给定的数组，跳动步数最少为多少。其中，题目给出的数组是一定可以到达终点的(这是Jump Game的进阶题，简单版本的题目会让你先判断是否有解)。

Approach One

最短步数，立刻就会想到 BFS。我们的确可以把这个数组抽象成 无权有向图：图的每个节点对应于数组的每个元素arr[i]，节点 i 到节点 j 有边的条件是从 i 能跳到 j，也就是说arr[i] + i >= j。问题就转化成初始节点为arr[0]，寻找到节点arr[n-1]的最短路径。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int jump(vector<int>& nums) {
  if (nums.size() < 2)  return 0;
  
  return BFS(nums);
}

int BFS(vector<int>& nums) {
  int n = nums.size();
  vector<int> graph[n];
  for (int i = 0; i < n; ++i) {
    for (int j = 1; j <= nums[i]; ++j) {
      graph[i].push_back(j + i);
    }
  }
  
  int level = 0;
  queue<int> q;
  set<int> visited;
  q.push(0);
  
  while (!q.empty()) {
    int size = q.size();
    level++;
    for (int i = 0; i < size; ++i) {
      int node = q.front();
      visited.insert(node);
      q.pop();
      for (int j = 0; j < graph[node].size(); ++j) {
        if (visited.count(graph[node][j]) == 0) {
          q.push(graph[node][j]);
          if (graph[node][j] == n - 1)  return level;
        }
      }
    }
  }
  
  return 0;
}

通过了 70% 的 test case，但很不幸 TLE 了。虽然时间复杂度只有$O(V+E)$，但是 E 太大了。

TLE

Approach Two

是不是 BFS 不能用？并不是，只是对于所有的能跳到地方都构造一条边，会让搜索范围扩大。上面 TLE 的例子就是这么一个 case。我们重新考虑一次。

我们的目的是跳到终点。至于跳过，这是可以的，因为能跳过终点，那么必然可以跳到终点，因为没有要求一定要跳最远。那么我们依旧采用 BFS，但维护一个变量，存储每一层能到达的最大距离。如果本层的最大距离比够到终点，那么就抵达终点了。

这个做法还有一个好处，我们没有额外的队列插入删除开销和数组判重开销。因为每一层的节点，由前一层的下一个节点和前一层能跳到的最远节点构成的。这可以保证只需要每个节点遍历一次，只为找出节点所在层能够到的最远距离。这把时间复杂度缩减到$O(V)$(这是一个模仿了 BFS 思想的算法)。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int jump(vector<int>& nums) {
  return BFS(nums);
}

int BFS(vector<int>& nums) {
  int level = 0, levelSize = 0, index = 0, n = nums.size(), temp = 0;
  if (n < 2)  return 0;
  while (levelSize - index + 1 > 0) {
    level++;
    while (index <= levelSize) {
      temp = max(temp, nums[index] + index);
      if (temp >= n - 1) return level;
      index++;
    }
    levelSize = temp;
  }
  
  return 0;
}

AC 截图：
AC

Simple One - Jump Game

我们回过头再来看看前面题目的简化版。

Description

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example

  1. One
    Input: [2,3,1,1,4]
    Output: true
    Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

  2. Two
    Input: [3,2,1,0,4]
    Output: false
    Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Analysis

题目意思是一样的，不过这个简化版比较直接，判断你能不能跳到终点。我们直接利用前面题目的 Approach Two 的模拟 BFS 来判断，如果能够到终点，那就是能跳到(其实应该先做这个，启发你用这个方法的，但我先做了前面的 hard 题，然后才发现有这个 medium 题，23333)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool canJump(vector<int>& nums) {
  return Solve(nums);
}

bool Solve(vector<int>& nums) {
  int levelSize = 0, index = 0, n = nums.size(), temp = 0;
  while (levelSize - index + 1 > 0) {
    while (index <= levelSize) {
      temp = max(temp, nums[index] + index);
      if (temp >= n - 1) return true;
      index++;
    }
    levelSize = temp;
  }
  
  return false;
}

AC