leetcode Jump Game I II 待续贪心看不懂啊！！！！

下面是这两个题的解法：

参考博客：http://blog.csdn.net/loverooney/article/details/38455475

自己写的第一题（TLE）：

 1 #include<iostream>
 2 #include<vector>
 3 
 4 using namespace std;
 5 
 6 bool canJump(vector<int>& nums) 
 7 {
 8     int L = nums.size();
 9     bool *flag = new bool[L];
10     for (int i = L - 2; i >= 0; i--)
11     {
12         int right = i + nums[i];
13         if (right >= L - 1)
14             flag[i] = true;
15         else
16         {
17             flag[i] = false;
18             for (int j = i + 1;j<L&& j < i + nums[i]; j++)
19             {
20                 if (flag[j] == true)
21                 {
22                     flag[i] = true;
23                     break;
24                 }
25             }
26         }
27     }
28     return flag[0];
29 }
30 
31 int main()
32 {
33     vector<int> a = { 3, 2, 1, 0, 4 };
34     cout << canJump(a) << endl;
35 }

View Code

贪心用step维护当前可到达的最远位置，每次的i必须在这个最远位置以内，假如不在就表明不能前进了return false。

代码：

 1 #include<iostream>
 2 #include<vector>
 3 
 4 using namespace std;
 5 
 6 bool canJump(vector<int>& nums) 
 7 {
 8     int L = nums.size();
 9     int step = 0;
10     for (int i = 0; i <= step; i++)
11     {
12         if (nums[i] + i > step)
13             step = nums[i] + i;
14         if (step >= L - 1)
15             return true;
16     }
17     return false;
18 }
19 
20 int main()
21 {
22     int a[] = { 3, 2, 1, 0, 4 };
23     cout << canJump(vector<int>(a, a+5)) << endl;
24 }

View Code

第二题：

BFS解法（MLE）：

 1 #include<vector>
 2 #include<iostream>
 3 #include<queue>
 4 
 5 using namespace std;
 6 
 7 typedef struct Node
 8 {
 9     int index;
10     int jumpNo;
11     Node(int index, int jumpNo) :index(index), jumpNo(jumpNo){};
12 }Node;
13 
14 //    BFS
15 int jump(vector<int>& nums) 
16 {
17     int i = 0; 
18     int L = nums.size();
19     queue<Node> que;
20     que.push(Node(i,0));
21     while (!que.empty())
22     {
23         Node now = que.front();
24         que.pop();
25         for (i = now.index + 1; i <= nums[now.index] + now.index; i++)
26         {
27             if (nums[i]+now.index >= L - 1)
28             {
29                 return now.jumpNo+1;
30             }
31             else
32                 que.push(Node(i,now.jumpNo+1));
33         }
34     }
35     return -1;
36 }
37 
38 int main()
39 {
40     vector<int> a = { 8, 3, 1, 1, 4 };
41     cout << jump(a) << endl;
42 }

View Code

自己写的也是MLE：

 1 #include<iostream>
 2 #include<vector>
 3 #include<queue>
 4 
 5 using namespace std;
 6 
 7 typedef struct Node
 8 {
 9     int val;    //从该节点能调到哪儿
10     int len;    //该节点在第len跳被访问
11     int index;  //当前节点的下标
12     Node(int val,int index,  int len) :val(val), index(index),len(len){};
13     Node(){};
14 }Node;
15 
16 int jump(vector<int>& nums) 
17 {
18     int L = nums.size();
19     Node* nodeArray = new Node[L];
20     for (int i = 0; i < L; i++)
21     {
22         nodeArray[i].val = nums[i];
23         nodeArray[i].index = i;
24         nodeArray[i].len = 0;
25     }
26     //vector<bool> visited(L,false);
27     queue<Node> visiteQueue;
28     nodeArray[0].len = 0;
29     visiteQueue.push(nodeArray[0]);
30     while (!visiteQueue.empty())
31     {
32         Node temp = visiteQueue.front();
33         int index = temp.index;
34         int canStep = temp.val;
35         for (int i = index + 1; i <= index + canStep; i++)
36         {
37             if (nodeArray[i].index+nodeArray[i].val>=L-1)
38             {
39                 return temp.len + 2;
40             }
41             Node nextNode(nodeArray[i].val,nodeArray[i].index, temp.len + 1);
42             visiteQueue.push(nextNode);
43         }
44         visiteQueue.pop();
45     }
46     return false;
47 }
48 
49 int main()
50 {
51     vector<int> a = { 2,1,3, 1, 1, 4,1,1,1,1};
52     cout << jump(a) << endl;
53 }

内存不超的BFS：http://www.myext.cn/c/a_4468.html

动态规划解法（TLE）：

 1 #include<iostream>
 2 #include<vector>
 3 
 4 using namespace std;
 5 
 6 int jump(vector<int>& nums) 
 7 {
 8     int L = nums.size();
 9     int *dp = new int[L];
10     dp[0] = 0;
11     for (int i = 1; i < L; i++)
12     {
13         int min = INT_MAX;
14         for (int j = 0; j < i; j++)
15         {
16             if (nums[j] + j >= i&&dp[j]+1<min)
17             {
18                 min = dp[j] + 1;
19             }
20         }
21         dp[i] = min;
22     }
23     for (int i = 0; i < L; i++)
24         cout << dp[i] << endl;
25     return dp[L - 1];
26 }
27 
28 int main()
29 {
30     vector<int> a = { 2, 3, 1, 1, 4 };
31     cout << jump(a) << endl;
32 }

贪心解法：

leetcode Jump Game I II 待续 贪心看不懂啊！！！！

leetcode Jump Game I II 待续贪心看不懂啊！！！！