leetcode Jump Game I II待续贪心看不懂啊!!!
25629 ワード
次はこの2つの問題の解法です.
参考ブログ:http://blog.csdn.net/loverooney/article/details/38455475
自分で書いた第一題(TLE):
View Code
欲張りはstepで現在到達可能な最も遠い位置を維持し、毎回のiはこの最も遠い位置以内にいなければならず、いなければreturn falseを前進できないことを示す.
コード:
View Code
2番目の問題:
BFS解法(MLE):
View Code
自分で書いたのもMLE:
メモリが超過しないBFS:http://www.myext.cn/c/a_4468.html
動的計画解法(TLE):
貪欲な解法:
参考ブログ: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
2番目の問題:
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 }貪欲な解法: