关键词：
（学习参考书：LeetCode101）
贪心算法
贪心算法采用贪心的策略，保证每次操作都是局部最优的，从而使最后得到是全局最优的。
解题步骤：
- 将问题分解为若干个子问题，寻找合适的贪心策略
- 求解每一个子集的最优解
- 将局部最优解迭代成全局最优解
力扣例题
455.分发饼干
分析：
因为饥饿度最小的孩子最容易吃饱，所以优先考虑这个孩子。为了使剩下的饼干尽可能的满足饥饿度更大的孩子，所以应该把大于等于这个孩子饥饿度的且最小的饼干给这个孩子。然后采取同样的策略，直到没有满足的饼干为止。
题解：
class Solution
public:
int findContentChildren(vector<int>& g, vector<int>& s)
//将饼干和孩子从小到大排序
sort(g.begin(),g.end());
sort(s.begin(),s.end());
//初始化辅助变量
int cnt = 0;
int j = 0;
//循环至一方没有剩余
while(cnt<g.size()&&j<s.size())
//当孩子能吃饱时，同时++进行下一组比对
//当孩子不能吃饱时，这个孩子继续和下一个饼干匹配
if(g[cnt]<=s[j])
++cnt;
++j;
return cnt;
;
class Solution
public int findContentChildren(int[] g, int[] s)
Arrays.sort(g);
Arrays.sort(s);
int cnt = 0,j = 0;
while(cnt<g.length&&j<s.length)
if(g[cnt]<=s[j])
++cnt;
++j;
return cnt;
135.分发糖果
分析：
只需要两次遍历，把所有孩子糖果数初始化为1；先从左到右遍历一遍，如果右边孩子的评分比左边的高，则右边更新为左边的糖果数+1；再从右往左遍历，如果左边的右边高，且左边孩子的糖果数不大于右边孩子的糖果数，则左边更新为右边的+1。
题解：
class Solution
public:
int candy(vector<int>& ratings)
int size = ratings.size();
//如果只有一个孩子返回1即可
if(size==1)
return size;
//创建一个数组，表示每个孩子对应的糖果数，初始值都为1
vector<int> v(size,1);
//从左往右遍历
for(int i=1;i<size;++i)
if(ratings[i-1]<ratings[i])
v[i] = v[i-1]+1;
//从右往左遍历
for(int i=size-1;i>0;--i)
if(ratings[i-1]>ratings[i])
//需要判断是否左边已经大于右边
v[i-1] = max(v[i-1],v[i]+1);
//求和得出需要的总糖果数
return accumulate(v.begin(),v.end(),0);
;
class Solution
public int candy(int[] ratings)
int[] candys = new int[ratings.length];
for(int i=0;i<candys.length;++i)
candys[i] = 1;
for(int i=0;i<ratings.length-1;++i)
if (ratings[i+1]>ratings[i])
candys[i+1] = candys[i]+1;
for(int i=ratings.length-1;i>=1;--i)
if (ratings[i-1]>ratings[i])
if (candys[i-1]<=candys[i])
candys[i-1] = candys[i]+1;
return IntStream.of(candys).sum();
435.无重叠区间
分析：
选择的区间结尾越小，余留给其他区间的空间就越大，就能保留更多的区间。因此采取的贪心策略是，优先保留结尾笑且不相交的区间。先把区间按照结尾大小排序，每次选择结尾最小且与前一个选择的区间不重叠的区间。
题解：
class Solution
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals)
//无区间直接返回0
if(intervals.empty())
return 0;
//使用自定义规则的sort函数对区间按照结尾大小排序
//这里定义规则的vector<int> a用法没错，但是在力扣上超时
//应该替换为const auto& a
sort(intervals.begin(),intervals.end(),
[](vector<int> a,vector<int> b)
return a[1]<b[1];
);
int cnt = 0;//计数器
int start = intervals[0][1];//初始设置为第一个区间的结尾
for(int i=1;i<intervals.size();++i)
if(intervals[i][0]<start)
//当下一个区间的开始与上一个区间的结尾重合时，应该删除该区间
++cnt;
else
//当不重合时，更新需要比较的区间的结尾
start = intervals[i][1];
return cnt;
;
class Solution
public int eraseOverlapIntervals(int[][] intervals)
Arrays.sort(intervals, new Comparator<int[]>()
@Override
public int compare(int[] o1, int[] o2)
return o1[1]-o2[1];
);
int cnt = 0;
int start = intervals[0][1];
for(int i=1;i<intervals.length;++i)
if (start>intervals[i][0])
++cnt;
else
start = intervals[i][1];
return cnt;
122.买卖股票的最佳时机2
分析：
由于买卖股票没有限制，因此只需要后一天比前一天价格高就买入，即所有的正值利润都交易。
题解：
class Solution
public:
int maxProfit(vector<int>& prices)
if(prices.size()<=1)
return 0;
int cnt = 0;
for(int i=1;i<prices.size();++i)
if(prices[i]-prices[i-1]>0)
cnt+=prices[i]-prices[i-1];
return cnt;
;
class Solution
public int maxProfit(int[] prices)
int profit = 0;
for(int i=0;i<prices.length-1;++i)
if(prices[i+1]>prices[i])
profit += prices[i+1]-prices[i];
return profit;
leetcode刷题之位运算（java）(代码片段)
位运算是算法题中比较特殊的一种类型，它们利用二进制位运算的特性进行一些奇妙的优化和计算。常用的位运算符号包括：^按位异或&按位与|按位或~取反<<左移位>>右移位力扣例题461.汉明距离分析：异... 查看详情
[leetcode刷题]——贪心思想(代码片段)
此篇博客主要记录力扣中的贪心思想。 一、分配饼干455.分发饼干 easy 2021-06-10 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子i，都有一个胃... 查看详情
leetcode刷题之位运算（java）(代码片段)
位运算是算法题中比较特殊的一种类型，它们利用二进制位运算的特性进行一些奇妙的优化和计算。常用的位运算符号包括：^按位异或&按位与|按位或~取反<<左移位>>右移位力扣例题461.汉明距离分析：异... 查看详情
leetcode刷题题单记录
...ff01;！算法基础差，变做题巩固！！！LeetCode刷题，搞起来！由于我只会C++和Python，所以题解只有C++和Python版本，记录思路方便回顾！！！使用博客园来写题解，CSDN做... 查看详情
力扣刷题之双指针（c++&java）(代码片段)
（学习参考书：LeetCode101）双指针双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。也可以延申多个数组的多个指针。若两个指针指向同一数组，遍历方向相同且不会相交，则... 查看详情
leetcode刷题之双指针（c++&java）(代码片段)
（学习参考书：LeetCode101）双指针双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。也可以延申多个数组的多个指针。若两个指针指向同一数组，遍历方向相同且不会相交，则... 查看详情
leetcode面试刷题技巧-贪心算法题习题集(代码片段)
...贪心策略或者字典排序的题目的通用解题方法。第一题，leetcode中等难度题目先来一道简单的字典序排列的问题，这个题目我这里不会用最优解来解决这个问题，这个是leetcode的中等难度的题目，最优解还是需要再思考一下的，... 查看详情
leetcode刷题之回溯法(代码片段)
掌握回溯法模板leetcode17电话号码的字母组合leetcode78子集leetcode17电话号码的字母组合classSolutionpublicList<String>letterCombinations(Stringdigits)HashMap<Character,String>map=newHashMap<>();map.put(' 查看详情
leetcode刷题之动态规划（java）(代码片段)
算法解释可以用局部最优解来推到全局最优解，即动态规划。动态规划在查找有很多重叠子区间问题的最优解时最有效。它将问题重新组合成子问题，为避免多次解决这些子问题，结果都逐渐被计算并保存，从简... 查看详情
《leetcode零基础指南》(第七讲)贪心(代码片段)
...己手写输入输出函数（例如C语言中的scanf和printf），而在LeetCode这个平台，只需要实现它提供的函数即可。函数的传入参数就代表了的算法的输入&# 查看详情
刷题之implementstrstr()
1publicclassSolution{2publicintstrStr(Stringhaystack,Stringneedle){3intbig=haystack.length();4intsub=needle.length();5if(big==0&&sub==0)return0;6if(big==0&&sub!=0)return-1;7intindex=bi 查看详情
leetcode刷题笔记-动态规划-day4(代码片段)
文章目录LeetCode刷题笔记-动态规划-day455.跳跃游戏1.题目2.解题思路3.代码45.跳跃游戏II1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day455.跳跃游戏1.题目原题链接：55.跳跃游戏2.解题思路算法：贪心我们用变量j表示从前... 查看详情
leetcode刷题笔记-动态规划-day4(代码片段)
文章目录LeetCode刷题笔记-动态规划-day455.跳跃游戏1.题目2.解题思路3.代码45.跳跃游戏II1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day455.跳跃游戏1.题目原题链接：55.跳跃游戏2.解题思路算法：贪心我们用变量j表示从前... 查看详情
leetcode刷题之搜索（java）(代码片段)
一、深度优先搜索基本模型：基于栈的递归voiddfs(step) 判断边界 尝试每一种可能for(inti=0;i<n;++i) 继续下一步dfs(step+1); 返回DFS力扣例题695.岛屿的最大面积分析：对是陆地的位置向四个方向进行深度优... 查看详情
[javascript刷题]贪心-分配饼干,leetcode455
[JavaScript刷题]贪心-分配饼干,leetcode455题目地址：455.AssignCookies题目Assumeyouareanawesomeparentandwanttogiveyourchildrensomecookies.But,youshouldgiveeachchildatmostonecookie.Eachchildihasagreedfactorg[i], 查看详情
leetcode刷题计划
一、刷题内容：数组字符串深度优先搜索广度优先搜索栈哈希表递归滑动窗口链表堆队列动态规划贪心算法并查集分治算法数学二分查找排序图字典树极小化极大回溯算法二、刷题要求：1、举一反三、尽可能给出多种解... 查看详情
算法刷题-数组排序(图算法算法高阶)螺旋矩阵(数组矩阵)分发糖果(贪心数组)(代码片段)
数组排序(图算法、算法高阶)编写一个JavaApplication程序,将随机生成的无序数组使用冒泡排序,将这个混乱的数组变成一个从小到大排列的有序的数组并输出。classdemo_sortpublicstaticvoidmain(String[]args)int[]numbers=newint[]1,5,8,2,3,9,4;for(inti=0;i... 查看详情
算法刷题-数组排序(图算法算法高阶)螺旋矩阵(数组矩阵)分发糖果(贪心数组)(代码片段)
数组排序(图算法、算法高阶)编写一个JavaApplication程序,将随机生成的无序数组使用冒泡排序,将这个混乱的数组变成一个从小到大排列的有序的数组并输出。classdemo_sortpublicstaticvoidmain(String[]args)int[]numbers=newint[]1,5,8,2,3,9,4;for(inti=0;i... 查看详情