石碣镇做网站,php网站伪静态,海口 做网站,杭州百度公司在哪里文章目录 前置知识122.买卖股票的最佳时机II题目描述贪心-直观写法贪心-优化代码更简洁 55. 跳跃游戏题目描述贪心-借助ability数组贪心-只用int far记录最远距离 45.跳跃游戏II题目描述回溯算法贪心算法 总结 前置知识
参考前文 参考文章#xff1a; LeetCode刷题笔记【23】… 文章目录 前置知识122.买卖股票的最佳时机II题目描述贪心-直观写法贪心-优化代码更简洁 55. 跳跃游戏题目描述贪心-借助ability数组贪心-只用int far记录最远距离 45.跳跃游戏II题目描述回溯算法贪心算法 总结 前置知识
参考前文 参考文章 LeetCode刷题笔记【23】贪心算法专题-1分发饼干、摆动序列、最大子序和 122.买卖股票的最佳时机II
题目描述 LeetCode链接https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/ 贪心-直观写法
思路: 贪心算法 假设这个股票交易员有预知明天股票价格的能力; 当明天的价格大于今天的时候, 就买入/持有; 当明天价格下跌时, 就在今天抛售/不购买; 最后一天的时候如果手里还有, 就售出;
class Solution {
public:int maxProfit(vectorint prices) {int ans0;if(prices.size()1)return ans;bool holdingfalse;for(int i0; iprices.size(); i){if(iprices.size()-1){//最后一天, 手里还有股票if(holding)ans prices.back();//卖出break;//不管咋样都要break了}if(prices[i1] prices[i] !holding){//明天升值, 并且手里没有股票ans - prices[i];//买入holding true;}else if(prices[i1] prices[i] holding){//明天贬值, 并且手里有股票ans prices[i];//卖出holding false;}}return ans;}
};贪心-优化代码更简洁
以上过程可以抽象为以下操作: 遍历整个prices序列, 只记录其中升序的部分的差值
class Solution {
public:int maxProfit(vectorint prices) {int ans0;for(int i0; iprices.size()-1; i){ans max(0, prices[i1]-prices[i]);}return ans;}
};55. 跳跃游戏
题目描述 LeetCode链接https://leetcode.cn/problems/jump-game/description/ 贪心-借助ability数组
创建并维护一个vectorbool ability数组 从头开始遍历nums, 最开始ability[0]true 然后如果ability[i]true, 那么将ability[i]~ability[inums[i]]都为true 过程中发现某个ability[i]false, 那么就为false
class Solution {
public:bool canJump(vectorint nums) {vectorbool ability(nums.size(), false);ability[0] true;for(int i0; inums.size(); i){if(ability[i]){for(int ji1; jinums[i]; j){if(jnums.size())return true;;ability[j] true;}}else{return false;}}return true;}
};贪心-只用int far记录最远距离
用不到一个数组, 用一个far表示最远能到达的点就可以了
class Solution {
public:bool canJump(vectorint nums) {int far0;for(int i0; inums.size(); i){if(far nums.size()-1)return true;if(fari){far max(far, inums[i]);}else{return false;}}return true;}
};核心思想是: 不要纠结这次跳几步, 而是关注最远能跳到哪里
45.跳跃游戏II
题目描述 LeetCode链接https://leetcode.cn/problems/jump-game-ii/description/ 回溯算法
思路: 回溯算法 每一层的回溯过程就是在遍历自己从这一步跳出去, 可以跳的距离的所有可能性 终止条件是indexnums.size()-1, 或者nums[index]0
class Solution {
private:int ans INT_MAX;int cur 0;void backtrack(vectorint nums, int index){if(indexnums.size()-1){ans min(ans, cur);return;}if(nums[index]0)return;for(int inums[index]; i0; --i){cur;backtrack(nums, indexi);cur--;}return;}
public:int jump(vectorint nums) {backtrack(nums, 0);return ans;}
};贪心算法
回溯法肯定是可以解决问题的, 但是奈何回溯的本质是遍历, 时间复杂度过高, 超出时间限制 所以老老实实用贪心吧: 和55. 跳跃游戏的核心思路是一样的, 都是尽量往远了跳, 但是这个又不能乱跳, 因为涉及到要不要ans的问题
所以贪心的思路是: 先看一下这一步能跳多远, 如果可以满足要求, 就结束, 如果不能, 那么就再跳一步 具体的实现是: 用nextDistence记录在当前范围内, 再跳一步可以达到的最远结果; 当遍历达到了curDistence处时, 如果还没有到最后一位, 那么就转nextDistence
class Solution {
public:int jump(vectorint nums) {int ans 0;if(nums.size()1)return ans;int nextDistence0, curDistence0;for(int i0; inums.size(); i){nextDistence max(nextDistence, inums[i]);if(icurDistence){ans;curDistence nextDistence;if(nextDistencenums.size()-1)break;}}return ans;}
};总结
贪心算法大概率就是没法把握, 甚至看起来是千题千解, 尽量熟悉吧只能说, 如果之后遇到类似的题目了, 可以想起来最好. 实在不行的话或许只能用回溯和动态规划尝试了.
刚才的第二题, 说到不要纠结这次跳几步, 而是关注最远能跳到哪里, 或许也是某种人生哲学呢哈哈哈. 本质上我们或多或少的都在用贪心算法规划自己的人生. (用贪心还算好了, 至少是当下和未来一部分时间内的最优, 还有不知道多少人是在后视镜开车呢) 本文参考 买卖股票的最佳时机II 跳跃游戏 跳跃游戏II
