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

下面是这两个题的解法：

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

自己写的第一题（TLE）：

 #include<iostream>

 #include<vector>

 using namespace std;

 bool canJump(vector<int>& nums)

 {

     int L = nums.size();

     bool *flag = new bool[L];

     for (int i = L - ; i >= ; i--)

     {

         int right = i + nums[i];

         if (right >= L - )

             flag[i] = true;

         else

         {

             flag[i] = false;

             for (int j = i + ;j<L&& j < i + nums[i]; j++)

             {

                 if (flag[j] == true)

                 {

                     flag[i] = true;

                     break;

                 }

             }

         }

     }

     return flag[];

 }

 int main()

 {

     vector<int> a = { , , , ,  };

     cout << canJump(a) << endl;

 }

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

代码：

 #include<iostream>

 #include<vector>

 using namespace std;

 bool canJump(vector<int>& nums)

 {

     int L = nums.size();

     int step = ;

     for (int i = ; i <= step; i++)

     {

         if (nums[i] + i > step)

             step = nums[i] + i;

         if (step >= L - )

             return true;

     }

     return false;

 }

 int main()

 {

     int a[] = { , , , ,  };

     cout << canJump(vector<int>(a, a+)) << endl;

 }

第二题：

BFS解法（MLE）：

 #include<vector>

 #include<iostream>

 #include<queue>

 using namespace std;

 typedef struct Node

 {

     int index;

     int jumpNo;

     Node(int index, int jumpNo) :index(index), jumpNo(jumpNo){};

 }Node;

 //    BFS

 int jump(vector<int>& nums)

 {

     int i = ;

     int L = nums.size();

     queue<Node> que;

     que.push(Node(i,));

     while (!que.empty())

     {

         Node now = que.front();

         que.pop();

         for (i = now.index + ; i <= nums[now.index] + now.index; i++)

         {

             if (nums[i]+now.index >= L - )

             {

                 return now.jumpNo+;

             }

             else

                 que.push(Node(i,now.jumpNo+));

         }

     }

     return -;

 }

 int main()

 {

     vector<int> a = { , , , ,  };

     cout << jump(a) << endl;

 }

自己写的也是MLE：

 #include<iostream>

 #include<vector>

 #include<queue>

 using namespace std;

 typedef struct Node

 {

     int val;    //从该节点能调到哪儿

     int len;    //该节点在第len跳被访问

     int index;  //当前节点的下标

     Node(int val,int index,  int len) :val(val), index(index),len(len){};

     Node(){};

 }Node;

 int jump(vector<int>& nums)

 {

     int L = nums.size();

     Node* nodeArray = new Node[L];

     for (int i = ; i < L; i++)

     {

         nodeArray[i].val = nums[i];

         nodeArray[i].index = i;

         nodeArray[i].len = ;

     }

     //vector<bool> visited(L,false);

     queue<Node> visiteQueue;

     nodeArray[].len = ;

     visiteQueue.push(nodeArray[]);

     while (!visiteQueue.empty())

     {

         Node temp = visiteQueue.front();

         int index = temp.index;

         int canStep = temp.val;

         for (int i = index + ; i <= index + canStep; i++)

         {

             if (nodeArray[i].index+nodeArray[i].val>=L-)

             {

                 return temp.len + ;

             }

             Node nextNode(nodeArray[i].val,nodeArray[i].index, temp.len + );

             visiteQueue.push(nextNode);

         }

         visiteQueue.pop();

     }

     return false;

 }

 int main()

 {

     vector<int> a = { ,,, , , ,,,,};

     cout << jump(a) << endl;

 }

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

动态规划解法（TLE）：

 #include<iostream>

 #include<vector>

 using namespace std;

 int jump(vector<int>& nums)

 {

     int L = nums.size();

     int *dp = new int[L];

     dp[] = ;

     for (int i = ; i < L; i++)

     {

         int min = INT_MAX;

         for (int j = ; j < i; j++)

         {

             if (nums[j] + j >= i&&dp[j]+<min)

             {

                 min = dp[j] + ;

             }

         }

         dp[i] = min;

     }

     for (int i = ; i < L; i++)

         cout << dp[i] << endl;

     return dp[L - ];

 }

 int main()

 {

     vector<int> a = { , , , ,  };

     cout << jump(a) << endl;

 }

贪心解法：

巴特西

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

最新文章

热门文章

巴特西

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

最新文章

热门文章

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