首页 / 算法 / 力扣算法题—045跳跃游戏二
力扣算法题—045跳跃游戏二
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了力扣算法题—045跳跃游戏二,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2277字,纯文字阅读大概需要4分钟。
内容图文
1 #include "000库函数.h" 2 3 4 //考虑当前最远能到什么地方,例如2, 3, 1, 1, 4, 5 //首先只考虑a[0] = 2,即最远可以到a[2],然后从1到2中找下一个可到的最远点, 6 //即a[1]可以到达a[4],此时找到结果,步数记录为2。若接着考虑, 7 //下一次应该从3 - 4里面找一个最远即a[4]可达a[8](4 + 4), 8 //再下一次从5 - 8中找最远 9 //20ms 10 class Solution { 11 public: 12 int jump(vector<int>& nums) { 13 if (nums.size() < 2)return 0; 14 int min = 0; 15 int a = 0, b = 0 + nums[0];//第一步和下一步的坐标 16 while (a < nums.size() - 1) { 17 min++; 18 int s = MAX(nums, a + 1, b); //在a,b中找到最远距离 19 a = b; 20 b = s; 21 } 22 return min; 23 } 24 int MAX(vector<int>& nums, int s, int t) { 25 int max = s + nums[s]; 26 for (; s < nums.size() && s <= t; ++s) { 27 if (max < s + nums[s]) 28 max = s + nums[s]; 29 } 30 return max; 31 } 32 }; 33 34 //博客解法 20ms 35 //解法的思想一样,找到跳的最远的那个 36 class Solution { 37 public: 38 int jump(vector<int>& nums) { 39 int res = 0, n = nums.size(), i = 0, cur = 0; 40 while (cur < n - 1) { 41 ++res; 42 int pre = cur; 43 for (; i <= pre; ++i) { 44 cur = max(cur, i + nums[i]); 45 } 46 if (pre == cur) return -1; // May not need this 47 } 48 return res; 49 } 50 }; 51 52 53 class Solution { 54 public: 55 int jump(vector<int>& nums) { 56 int res = 0, n = nums.size(), last = 0, cur = 0; 57 for (int i = 0; i < n - 1; ++i) { 58 cur = max(cur, i + nums[i]); 59 if (i == last) { 60 last = cur; 61 ++res; 62 if (cur >= n - 1) break; 63 } 64 } 65 return res; 66 } 67 }; 68 void T045() { 69 Solution s; 70 vector<int>v; 71 v = { 5,5,3,2,1,0,2,3,3,10,0,0 }; 72 cout << s.jump(v) << endl << "**************" << endl; 73 v = { 2,0,2,4,6,0,0,3}; 74 cout << s.jump(v) << endl << "**************" << endl; 75 v = { 2,3,0,1,4 }; 76 cout << s.jump(v) << endl << "**************" << endl; 77 v = { 2,3,1,1,4 }; 78 cout << s.jump(v) << endl << "**************" << endl; 79 }
内容总结
以上是互联网集市为您收集整理的力扣算法题—045跳跃游戏二全部内容,希望文章能够帮你解决力扣算法题—045跳跃游戏二所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。