欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 健康 > 养生 > 贪心算法 力扣hot100热门面试算法题 面试基础 核心思路 背题

贪心算法 力扣hot100热门面试算法题 面试基础 核心思路 背题

2025/3/30 0:12:43 来源:https://blog.csdn.net/2402_82958989/article/details/146479283  浏览:    关键词:贪心算法 力扣hot100热门面试算法题 面试基础 核心思路 背题

贪心算法

买卖股票的最佳时机

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

核心思路

如果假设今日买入,未来最高点是未知的,需要遍历后续数组,所以时间复杂度变成n^2;
那么如果假设今日卖出,遍历到此处时历史最低价是已知晓的信息,就降低了时间复杂度,只需要遍历一遍并记录实时最小值和实时最大利润即可;

示例代码

class Solution {public int maxProfit(int[] prices) {int min = 10010;int max = 0;for(int num : prices){if(num<min) min = num;if(max < num - min)max = num - min;}return max;}
}

跳跃游戏

https://leetcode.cn/problems/jump-game/

核心思路

倒序 可达性分析

示例代码

class Solution {public boolean canJump(int[] nums) {//i表示可到达的下标int i = nums.length - 1;//j表示需要确定的下标//若倒二可到达倒一,则计算倒三是否可以到达倒二,否则计算到三是否可以到达倒一;for (int j = nums.length - 2; j >= 0; j--) {if (nums[j] >= i - j) {i = j;}}//若i==0,代表可到达if (i == 0) return true;return false;}
}

跳跃游戏II

https://leetcode.cn/problems/jump-game-ii/

返回到达 nums[n - 1] 的最小跳跃次数

核心思路

贪心策略:在当前位置所能跳到的区间内,找下一次能跳到更远的位置。

示例代码

class Solution {public int jump(int[] nums) {int p = nums.length - 1;//每一步的开始int start = 0;int cnt = 0;while (start < p) {int end = -1;//在start位置,[s,e]闭区间即能跳到的的范围int s = start + 1;int e = start + nums[start];//e没跳到最后的话,就找一下:跳到区间的哪个位置可以下一次跳的更远if (e < p) {for (int i = s; i <= e && i <= p; i++) {if (end <= i + nums[i]) {end = i + nums[i];start = i;}}}else{cnt++;break;}cnt++;}return cnt;}
}

划分字母区间

https://leetcode.cn/problems/partition-labels/

核心思路

本质是合并区间:

​ 遍历,记录下每个字母最后出现的下标;
​ 再次遍历,合并区间,计算长度

示例代码

class Solution {public List<Integer> partitionLabels(String S) {char[] s = S.toCharArray();int n = s.length;int[] last = new int[26];for (int i = 0; i < n; i++) {last[s[i] - 'a'] = i; // 每个字母最后出现的下标}List<Integer> ans = new ArrayList<>();int start = 0, end = 0;for (int i = 0; i < n; i++) {end = Math.max(end, last[s[i] - 'a']); // 更新当前区间 右端点的最大值if (end == i) { // 当前区间合并完毕ans.add(end - start + 1); // 区间长度加入答案start = i + 1; // 下一个区间的左端点}}return ans;}
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词