在对问题求解时,总是做出在当前看来是最好的选择.
从局部最优解 ==> 全局最优解
LeetCode 455 : 分发饼干
描述:
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。
对每个孩子i
,都有一个胃口值 g[i]
,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干j
,都有一个尺寸 s[j]
。如果 s[j] >= g[i]
,我们可以将这个饼干 j
分配给孩子 i
,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
局部最优->全局最优
局部最优:让尺寸小的饼干满足胃口小的孩子
全局最优:优先满足胃口小的孩子
class Solution {
public int findContentChildren(int[] g, int[] s) {
// 先进行排序
Arrays.sort(g);
Arrays.sort(s);
// 让胃口最小的孩子 吃 最小尺寸的饼干
int child = 0;
int cookies = 0;
int count = 0;
while(child < g.length && cookies < s.length){
// 这里的饼干回复度 >= 孩子饥饿度 才能满足
if(g[child] <= s[cookies]){
count++;
child++;
}
cookies++;
}
return count;
}
}
LeetCode 435 : 无重叠区间
描述:
给定一个区间的集合intervals
,其中 intervals[i] = [starti, endi]
。返回 需要移除区间的最小数量,使剩余区间互不重叠 。
局部最优 -> 全局最优
局部最优: 优先选右边界最小的区间,避免交叉
全局最优: 保留最多的不相交区间
i
区间的右边界 <``i+1
区间的左边界,则需要移除i+1
区间class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
// 贪心思路 : 每次都保留区间结尾最小的且不相交的区间
// 排序 根据每组最后一个数排序
Arrays.sort(intervals,(o1,o2)->o1[1]-o2[1]);
int count = 0;
// 让 pre 指向第一个区间的右边界 如果下一个区间的左边界 小于 这个pre 就是需要移除的
int pre = intervals[0][1];
// 因为第一组肯定是不需要移除的 所以让i == 1
for (int i = 1; i < intervals.length; i++){
// 下一组左边界 < pre 移除
if (intervals[i][0] < pre){
count++;
}else{
// 不需要移除 就让pre 指向下一组的右边界
pre = intervals[i][1];
}
}
return count;
}
}
LeetCode 122: 买卖股票的最佳时机 II
描述:
给定一个数组 prices
,其中 prices[i]
表示股票第 i
天的价格。
在每一天,你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它,然后在 同一天 出售。
返回 你能获得的 最大 利润 。
局部最优 -> 全局最优
局部最优: 只要明天卖能赚钱就卖
全局最优: 总是能获得利润
class Solution {
public int maxProfit(int[] prices) {
int profit = 0;
// 这里假设 如果当天买,明天卖了能赚钱,就今天买了,明天卖。
for(int i = 0; i < prices.length - 1; i ++){
if(prices[i] < prices[i + 1]){
profit += prices[i+1] - prices[i];
}
}
return profit;
}
}
LeetCode 55: 跳跃游戏
描述:
给定一个非负整数数组 nums
,你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
局部最优 -> 全局最优
局部最优: 每次跨越都跨最远的距离
全局最优: 跳跃的总长度最远
mostLength
记录可以跳跃到的下标i
下的值nums[i]+i
> mostLength
就更新mostLength
nums[i]+i
表示.能到达的下标.mostLength >= nums.length-1
就返回true
;false
;class Solution {
public boolean canJump(int[] nums) {
// 贪心思路 每次都跳跃最大的距离
// mostLength 记录 跳跃的最远距离的下标
int mostLength = 0;
for(int i = 0;i < nums.length;i++){
// 如果 下标是小于等于mostLength,就代表可以跳跃
if(i <=mostLength){
// 更新最大跳跃距离
// 最大距离为 历史最大距离 或者 当前数据跳跃距离+下标
// nums[i] + i 表示最远可以达到的下标
mostLength = Math.max(mostLength,nums[i]+i);
// 如果最大距离可到的下标 为 数组最后一个数的下标则返回true
if(mostLength >= nums.length -1){
return true;
}
}
}
// 遍历完不能到达最后就是false
return false;
}
}
LeetCode 45: 跳跃游戏 II
描述:
给你一个非负整数数组 nums
,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
局部最优 -> 全局最优
局部最优: 每次跳跃都移动最大距离
全局最优: 那么所用的次数就最少
mostLength
记录最远可达的下标flg
记录是否遍历到了最远的下标
i = flg
表示跳跃到了最远记录记录下 次数,并更新flg
等于最远下标
mostLength
和nums[i]+i
比较,确保mostLength 永远指向最远的下标.class Solution {
public int jump(int[] nums) {
// 贪心: 每次跳最远 -> 步数就最少
int mostLength = 0;// 指向能跳跃到的最远下标
int count = 0;// 记录跳跃次数
int flg = 0;// 标记是否经过最远距离下标
for (int i = 0; i < nums.length-1; i++){
// 始终让mostLength指向最远能跳到的下标
mostLength = Math.max(mostLength,nums[i]+i);
// 如果i=flg 表示跳跃了一次
if(i == flg){
// 更新flg能到的位置
flg = mostLength;
// 记录次数
count++;
}
}
return count;
}
}
LeetCode 561: 数组拆分 I
描述:
给定长度为 2n
的整数数组 nums
,你的任务是将这些数分成 n
对, 例如 (a1, b1), (a2, b2), ..., (an, bn)
,使得从 1
到 n
的 min(ai, bi)
总和最大。
返回该 最大总和 。
局部最优 -> 全局最优
局部最优: 优先让最大的和第二大的数分组
全局最优: 总是拿到最大可保留的值
right
下标指向数组最后一个元素.right-=2
,其中nums[right-1]
就是第二大的数,sum
记录下每次遍历到的第二大的值class Solution {
public int arrayPairSum(int[] nums) {
// 贪心: 总是让第二大和最大的值分到一组.
// 排序
Arrays.sort(nums);
// right 指向数组最后一个元素
int right = nums.length - 1;
// sum 记录总和
int sum = 0;
while(right >= 1){
sum += nums[right - 1];// 始终加第二大的数
right -= 2;
}
return sum;
}
}
LeetCode 1833: 雪糕的最大数量
描述:
夏日炎炎,小男孩 Tony
想买一些雪糕消消暑。
商店中新到n
支雪糕,用长度为 n
的数组costs
表示雪糕的定价,其中 costs[i]
表示第 i
支雪糕的现金价格。Tony
一共有 coins
现金可以用于消费,他想要买尽可能多的雪糕。
给你价格数组 costs
和现金量 coins
,请你计算并返回 Tony
用 coins
现金能够买到的雪糕的 最大数量 。
注意:Tony 可以按任意顺序购买雪糕。
局部最优 -> 全局最优
局部最优: 每次都去买最小价格的雪糕
全局最优: 购买的雪糕数量最多
coins
小于数组i
下标下的元素,表示没法购买了count++
,让coins = coins - cost[i]
class Solution {
public int maxIceCream(int[] costs, int coins) {
// 贪心思想: 每次都买最小的
// 先排序
Arrays.sort(costs);
// 如果第一个价格都大于conis 那么就一个买不了
if(costs[0] > coins) return 0;
int count = 0;
// 遍历数组
for(int i = 0; i < costs.length; i++){
// 只要costs[i] <= coins 就代表可以买,否则就买不起了就跳出循环
if(costs[i] <= coins){
coins -= costs[i];
count++;
}else{
break;
}
}
return count;
}
}
LeetCode 1877: 数组中最大数对和的最小值
描述:
一个数对 (a,b) 的 数对和 等于 a + b 。最大数对和 是一个数对数组中最大的 数对和 。
(1,5) ,(2,3) 和 (4,4)
,最大数对和 为 max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8
。给你一个长度为 偶数n
的数组 nums
,请你将 nums
中的元素分成 n / 2
个数对,使得:
nums
中每个元素 恰好 在 一个 数对中,请你在最优数对划分的方案下,返回最小的 最大数对和 。
局部最优 -> 全局最优
局部最优: 总是让最大的和最小的组队
全局最优: 最大数对和最小
left
和right
指向0
下标和nums.length-1
下标class Solution {
public int minPairSum(int[] nums) {
// 贪心思想: 每次让最大和最小的组队
// 最大数对和就最小
// 先排序
Arrays.sort(nums);
int left = 0;
int right = nums.length-1;
int maxTotal = nums[left] + nums[right];
// 遍历 让 最大和最小最队,并记录每队的和,返回最大和
while(left < right){
maxTotal = Math.max(maxTotal,nums[left]+nums[right]);
left++;
right--;
}
return maxTotal;
}
}
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://wangzhi430.blog.csdn.net/article/details/123891904
内容来源于网络,如有侵权,请联系作者删除!