力扣100题——贪默算法
概述贪默算法(Greedy Algorithm)是一种在办理问题时,按照某种尺度在每一步都选择当前最优解(局部最优解)的算法。它期望通过一系列局部最优解的选择,终极可以或许得到全局最优解。
贪默算法的核心思想
贪默算法的核心思想是每一步都采取最优选择,即所谓的“贪心选择”。算法会根据某种贪心计谋,渐渐做出局部最优的选择,并渴望通过这些局部最优的选择可以或许得到终极的全局最优解。
贪默算法的一样平常步骤
[*]问题分解:将问题分解为多少个子问题。
[*]选择贪心计谋:为每个子问题选取局部最优解(通常是通过某种评价尺度,选择当前最有利的选择)。
[*]合并子问题的解:将每次的选择累积起来,直到办理完所有子问题,得到终极的全局解。
贪默算法的应用场景
贪默算法实用于那些通过选择局部最优解,终极可以或许得到全局最优解的问题。一样平常来说,贪默算法并不总是能找到全局最优解,但在某些特定问题中,它可以得到最优解。常见的贪默算法应用场景包罗:
[*]最小天生树问题:Kruskal 和 Prim 算法都是基于贪心计谋的,可以或许找到加权连通图的最小天生树。
[*]活动选择问题:用于选择最多的不重叠活动,典型的贪心选择是选择结束时间最早的活动。
[*]背包问题(贪心版的 0-1 背包问题):按物品的单位代价从高到低举行选择,直到装满背包。
贪默算法的优缺点
优点:
[*]简单、高效:由于只关注局部最优,贪默算法通常比较简单,运行速度较快。
[*]直接、可实现性强:贪默算法容易实现,对于某些问题是最佳办理方案。
缺点:
[*]不实用于所有问题:贪默算法无法保证在所有问题中都能找到全局最优解,尤其是当局部最优解无法组合玉成局最优解时。
[*]必要问题具备“贪心选择性质”:即从局部最优可以或许推导出全局最优。
刷题
买卖股票的最佳时机
标题
121. 买卖股票的最佳时机 - 力扣(LeetCode)
思路
初始思路:以每一个数组元素为买入点,找出利润的最大值,时间复杂度是O(n)
优化思路:在遍历的过程中,我们始终选择当前最小的买入价格,并盘算卖出的最大大概利润。
代码
初始代码
public int maxProfit(int[] prices) {
int n = prices.length;
int max = 0;
for (int i = 0; i < n; i++) {
for(int j=i+1;j<n;j++){
if(prices>prices){
max = Math.max(max,prices-prices);
}
}
}
return max;
} 优化后的代码
public int maxProfit(int[] prices) {
int n = prices.length;
int max = 0;
int min = prices;
for (int i = 0; i < n; i++) {
if(prices < min)
min = prices;
max = Math.max(max, prices - min);
}
return max;
} 跳跃游戏
标题
55. 跳跃游戏 - 力扣(LeetCode)
思路
[*]初始化一个变量 maxReach,表现当前可以或许到达的最远位置。
[*]遍历数组的每一个元素,对于每个元素 nums,查抄是否可以从当前位置到达更远的位置,即 maxReach 是否大于或即是当前下标 i。
[*]在遍历的过程中,不断更新可以或许到达的最远位置 maxReach 为 i + nums。
[*]假如在遍历过程中,某个位置的 maxReach 大于或即是末了一个下标,则返回 true;否则,假如遍历结束仍未达到末了一个下标,则返回 false。
代码
public boolean canJump(int[] nums) {
int n = nums.length;
int max = 0;
for(int i = 0; i < n; i++) {
if(i>max){
return false;
}
max = Math.max(max, nums + i);
if(max>=n-1){
return true;
}
}
return false;
} 跳跃游戏Ⅱ
标题
45. 跳跃游戏 II - 力扣(LeetCode)
思路
1.定义状态:
[*]维护两个变量 curEnd 和 curFarthest:
[*]curEnd 表现当前跳跃范围的最远边界。
[*]curFarthest 表现通过当前步可以或许到达的最远位置。
2.遍历数组:
[*]遍历 nums,在每次遍历时,我们会更新 curMax,表现通过当前跳跃可以到达的最远位置。
[*]当遍历到 curEnd 时,表现当前跳跃已经完成,必须举行下一次跳跃,并更新 max 为 curMax,跳跃次数加1。
[*]末了,假如遍历到了数组的末了一个位置,返回跳跃次数即可。
贪心计谋:
[*]在每一次跳跃中,我们尽大概向前跳得最远,如许才能保证在最少的跳跃次数内到达数组末端。
代码
public int jump(int[] nums) {
int n = nums.length;
int max = 0;
int curMax = 0;
int sum =0;
for(int i = 0; i < n; i++) {
if(i==n-1){
break;
}
curMax = Math.max(curMax, nums + i);
if(i==max){
max = curMax;
sum++;
}
}
return sum;
} 划分字母区间
标题
763. 划分字母区间 - 力扣(LeetCode)
思路
[*]用一个last数组,记录每个字母出现的最远位置
[*]遍历数组,使用start和end记录当前划分字符串的开头和结尾
[*]每次不断的更新当前字符串的最远位置
[*]当i和end相称,即代表当前字符串划分结束
代码
public List<Integer> partitionLabels(String s) {
List<Integer> res = new ArrayList<Integer>();
int[] last = new int;
for(int i=0;i<s.length();i++){
last=i;
}
int end = 0,start = 0;
for(int i=0;i<s.length();i++){
end = Math.max(end, last);
if(i==end){
res.add(end-start+1);
start=i+1;
}
}
return res;
}
结语
每次做贪心都以为自己智商低
https://i-blog.csdnimg.cn/direct/25ad1ac8cb6b417fa9e08b2f6fc5f19c.jpeghttps://i-blog.csdnimg.cn/direct/697b7c6a136b4f4c89ff68bc1b8905d0.jpeg
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。
页:
[1]