19.2.7 [LeetCode 45] Jump Game II - 19.2.7, game, ii, jump, leetcode

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

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

< span style="font-size: 16px; color: #008080;">Your goal is to reach the last index in the minimum number of jumps.

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.

Note:

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

Title meaning

The array represents the maximum number of steps that can be jumped at the numbered position. It is asked that the minimum number of steps from the 0 position can just reach the end point

Problem solution

I made a simple dp at the beginning, very slow

 1 class Solution {

 2 public:

 3 int jump(vector<int>& nums) {

 4 int n = nums.size();

 5 vector<int>dp(n,n);

 6 dp[n-1] = 0;

 7 for (int i = n-2; i >= 0; i--) {

 8 int step = nums[i];

 9 for (int j = i + 1; j <= i + step && j )

10 dp[i] = min(dp[j] + 1 , dp[i]);

11 }

12 return dp[0];

13 }

14 };

View Code < /div>

bfs are exactly the same…

 1 class< span style="color: #000000;"> Solution {

 2 public:

 3 struct node {

 4 int posi, step;

 5 node(int x, int y) :posi(x), step(y) {}

 6  };

 7 int jump(vector<int>& nums) {

 8 queueq;

 9 int n = nums.size();

10 vector<bool>visited(n, < span style="color: #0000ff;">false);

11 q.push(node(0,< span style="color: #800080;">0));

12 visited[0] = true;

13 while (!q.empty()) {

14 node now = q.front(); q.pop( );

15 if (now.posi == n- 1)return now.step ;

16 for (int i = now.posi + 1; i <= now.posi + nums[now.posi] && i < n; i++)

17 if (!visited[i]) {

18 visited[i] = true;

19 q.push(node(i,now.step+1< /span>));

20 }

21 }

22 return -1;

23 }

24 };

View Code < /div>

Afterwards, greedy is still slow, although it is much faster

 1 class Solution {

 2 public:

 3 int jump(vector<int>& nums) {

 4 if (nums.size() == 1)return 0 span>;

 5 int reach = nums[0],prereach=0, cnt = 1 , n = nums.size();

 6 while (reach 1) {

 7 cnt++;

 8 int nextreach = reach;

 9 for (int i = prereach + 1; i <= reach; i++ )

10 nextreach = max(nextreach, i + nums[i]) ;

11 prereach = reach;

12 reach = nextreach;

13 }

14 return cnt;

15 }

16 };

View Code < /div>

Then the comment section tried a lot of solutions called beat 99%, all of which are almost at the speed above… …

share picture

 1 class Solution {

 2 public:

 3 int jump(vector<int>& nums) {

 4 int n = nums.size();

 5 vector<int>dp(n,n);

 6 dp[n-1] = 0;

 7 for (int i = n-2; i >= 0; i--) {

 8 int step = nums[i];

 9 for (int j = i + 1; j <= i + step && j )

10 dp[i] = min(dp[j] + 1 , dp[i]);

11 }

12 return dp[0];

13 }

14 };

View Code< /p>

 1 class Solution {

 2 public:

 3 int jump(vector<int>& nums) {

 4 int n = nums.size();

 5 vector<int>dp(n,n);

 6 dp[n-1] = 0;

 7 for (int i = n-2; i >= 0; i--) {

 8 int step = nums[i];

 9 for (int j = i + 1; j <= i + step && j )

10 dp[i] = min(dp[j] + 1 , dp[i]);

11 }

12 return dp[0];

13 }

14 };

share picture

 1 class Solution {

 2 public:

 3 struct node {

 4 int posi, step;

 5 node(int x, int y) :posi(x), step(y) {}

 6  };

 7 int jump(vector<int>& nums) {

 8 queueq;

 9 int n = nums.size();

10 vector<bool>visited(n, < span style="color: #0000ff;">false);

11 q.push(node(0,< span style="color: #800080;">0));

12 visited[0] = true;

13 while (!q.empty()) {

14 node now = q.front(); q.pop( );

15 if (now.posi == n- 1)return now.step ;

16 for (int i = now.posi + 1; i <= now.posi + nums[now.posi] && i < n; i++)

17 if (!visited[i]) {

18 visited[i] = true;

19 q.push(node(i,now.step+1< /span>));

20 }

21 }

22 return -1;

23 }

24 };

View Code< /p>

 1 class Solution {

 2 public:

 3 struct node {

 4 int posi, step;

 5 node(int x, int y) :posi(x), step(y) {}

 6  };

 7 int jump(vector<int>& nums) {

 8 queueq;

 9 int n = nums.size();

10 vector<bool>visited(n, < span style="color: #0000ff;">false);

11 q.push(node(0,< span style="color: #800080;">0));

12 visited[0] = true;

13 while (!q.empty()) {

14 node now = q.front(); q.pop( );

15 if (now.posi == n- 1)return now.step ;

16 for (int i = now.posi + 1; i <= now.posi + nums[now.posi] && i < n; i++)

17 if (!visited[i]) {

18 visited[i] = true;

19 q.push(node(i,now.step+1< /span>));

20 }

21 }

22 return -1;

23 }

24 };

share picture

 1 class Solution {

 2 public:

 3 int jump(vector<int>& nums) {

 4 if (nums.size() == 1)return 0 span>;

 5 int reach = nums[0],prereach=0, cnt = 1 , n = nums.size();

 6 while (reach 1) {

 7 cnt++;

 8 int nextreach = reach;

 9 for (int i = prereach + 1; i <= reach; i++ )

10 nextreach = max(nextreach, i + nums[i]) ;

11 prereach = reach;

12 reach = nextreach;

13 }

14 return cnt;

15 }

16 };

View Code< /p>

 1 class Solution {

 2 public:

 3 int jump(vector<int>& nums) {

 4 if (nums.size() == 1)return 0 span>;

 5 int reach = nums[0],prereach=0, cnt = 1 , n = nums.size();

 6 while (reach 1) {

 7 cnt++;

 8 int nextreach = reach;

 9 for (int i = prereach + 1; i <= reach; i++ )

10 nextreach = max(nextreach, i + nums[i]) ;

11 prereach = reach;

12 reach = nextreach;

13 }

14 return cnt;

15 }

16 };

19.2.7, game, ii, jump, leetcode

Title meaning

Problem solution

Leave a Comment Cancel reply