贪心算法笔记
发布时间
阅读量：
阅读量
贪心
-
1.序列问题
-
- 1.1摆动序列
- 1.2单调递增的数字
-
2.多维度权衡
-
- 2.1分发糖果
- 2.2根据身高重构队列
-
区间相关问题
-
第三章中的区间相关问题
- 第三章中的第一个区间相关子问题（I）
- 第三章中的第二个区间相关子问题（II）
- 使用最少数量的箭击中气球的问题
- 不重叠区间的划分方法
- 字母区间的划分技巧
-
4.其他
-
- 4.1最大子数组和
- 4.2加油站
- 4.3监控二叉树
-
如其名称所示，在解决问题的过程中运用了一种贪心的思想。例如，在选择钞票时我们的目标是尽可能多地选取面值较高的钞票，在遍历这些钞票的过程中我们优先选择了高面额的钞票以获得最大的总和结果。贪心算法的核心在于每一步都做出局部最优的选择从而最终达到了全局最优的目标。下面列举了一些可以通过贪心算法解决的经典问题列表参考来源：代码随想录[https://www.programmercarl.com]
1.序列问题
1.1摆动序列
解法一：贪心
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if(nums.size() <= 1) return nums.size();
int curDiff = 0; //当前一对差值
int preDiff = 0; //前一对差值
int result = 1; //记录峰值个数，序列默认序列最右边有一个峰值
for(int i = 0; i < nums.size() - 1; i++){
curDiff =nums[i + 1] - nums[i];
//出现峰值
if((preDiff <= 0 && curDiff > 0) || (preDiff >=0 && curDiff < 0)){
result++;
preDiff = curDiff;
}
}
return result;
}
};
cpp
解法二：动态规划
class Solution {
public:
//动态规划实现：dp[i][0]表示第i个数作为山峰的摆动子序列的最长长度
//动态规划实现：dp[i][1]表示第i个数作为山谷的摆动子序列的最长长度
int dp[1005][2];//这个大小是根据题目给出数值的范围来定义的
int wiggleMaxLength(vector<int>& nums) {
memset(dp, 0, sizeof dp);
dp[0][0] = dp[0][1] = 1;
for(int i = 1; i < nums.size(); i++){
dp[i][0] = dp[i][1] = 1;
for(int j = 0; j < i; j++){
if(nums[j] > nums[i]) dp[i][1] = max(dp[i][1], dp[j][0] + 1);
}
for(int j = 0; j < i; j++){
if(nums[j] < nums[i]) dp[i][0] = max(dp[i][0], dp[j][1] + 1);
}
}
return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);
}
};
cpp
1.2单调递增的数字
当我们采用暴力循环方法时，在处理较大的数值可能会导致超时报错。因此我们转而采用一种基于以下两个关键条件的构造方法：数字必须单调递增且尽可能大以满足要求。为了保证生成的数字尽可能大且满足单调递增的要求，在此我们采用了基于这两个关键条件的构造方法
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string strNum = to_string(n);
//flag用来标记赋值9从哪开始
//设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行
int flag = strNum.size();
for(int i = strNum.size() - 1; i > 0; i--){
if(strNum[i - 1] > strNum[i]){
flag = i;
strNum[i - 1]--;
}
}
for(int i = flag; i < strNum.size(); i++){
strNum[i] = '9';
}
return stoi(strNum);
}
};
cpp
2.多维度权衡
在某些情况下，我们在处理数据时并非仅局限于单一指标。可能会涉及一个以上指标的情形更为普遍。举例而言，在排序任务中若涉及两个指标，则需综合权衡这两个指标的影响。
2.1分发糖果
在本题中,每个孩子能获得的糖果数量要考虑左右手的人得分情况（涉及两个维度）。
这个题目通过两次遍历的方式得以解决。在第一次遍历时是从前往后进行操作：每位参与者会关注左手相邻的人的评分情况，在左手评分较低的情况下会相应提高自己的糖果数量；反之，则维持原有水平。经过第一次遍历后进行第二次遍历：这次是从右往左依次处理每位参与者的情况：每位参与者只需比较右手相邻人的评分高低，在右手评分较低时会根据自身当前糖果数量与右手侧邻居对应的数量进行比较取其较大值作为新的糖果分配结果。最终完成两次遍历计算后所得出的结果即为最少需要分配出的糖果总数
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> candyVec(ratings.size(), 1);
//从前向后
for(int i = 1; i < ratings.size(); i++){
if(ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
}
//从后向前
for(int i = ratings.size() - 2; i >= 0; i--){
if(ratings[i] > ratings[i + 1]){
candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
}
}
return accumulate(candyVec.begin(), candyVec.end(), 0);
}
};
cpp
2.2根据身高重构队列
这个题目中无需考虑增加h同时还需关注k值即当前的人前面有k个更高的
class Solution {
public:
//自定义排序规则：按照身高从大到小排，如果身高相同就让k小的在前面
static bool cmp(const vector<int>& a, const vector<int>& b){
if(a[0] == b[0]) return a[1] < b[1];
return a[0] > b[0];
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), cmp);
vector<vector<int>> que;
for(int i = 0; i < people.size(); i++){
int position = people[i][1];
que.insert(que.begin() + position, people[i]);
}
return que;
}
};
cpp
3.区间问题
处理区间问题通常会遇到需要解决的去重挑战以及类似的问题类型。具体案例可以通过下面的练习来巩固理解。
3.1跳跃问题
class Solution {
public:
bool canJump(vector<int>& nums) {
int maxJump = nums[0];
int i = 1;
while(i < nums.size() && maxJump > 0){
maxJump = max(maxJump - 1, nums[i]);
i++;
}
if(i == nums.size()) return true;
return false;
}
};
cpp
3.2跳跃问题 II
class Solution {
public:
int jump(vector<int>& nums) {
int curDistance = 0; //当前覆盖的最远距离下标
int ans = 0;
int nextDistance = 0; //下一步覆盖的最远距离下标
for(int i = 0; i < nums.size() - 1; i++){//注意i的取值范围
nextDistance = max(nums[i] + i, nextDistance);//更新下一步覆盖的最远距离下标
if(i == curDistance){
curDistance = nextDistance;//更新当前的最远覆盖距离下标
ans++;
}
}
return ans;
}
};
cpp
3.3用最小数量的箭引爆气球
class Solution {
public:
static bool cmp(const vector<int>& a, const vector<int>& b){
return a[0] < b[0];
}
int findMinArrowShots(vector<vector<int>>& points) {
if(points.size() == 0) return 0;
sort(points.begin(), points.end(), cmp);
int result = 1; //points不为空至少需要一支箭
for(int i = 1; i < points.size(); i++){
if(points[i][0] > points[i - 1][1]){
//区间无重叠，需要一支箭
result++;
}else{
//气球i和气球i - 1挨着
points[i][1] = min(points[i - 1][1], points[i][1]);
}
}
return result;
}
};
cpp
3.4无重叠区间
解法一：区间右边界排序
class Solution {
public:
//按照区间右边界排序
static bool cmp(const vector<int>& a, const vector<int>& b){
return a[1] < b[1];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if(intervals.size() <= 1) return 0;
sort(intervals.begin(), intervals.end(), cmp);
int count = 1; //记录非交叉区间的个数
int end = intervals[0][1]; //记录区间分割点
for(int i = 1; i < intervals.size(); i++){
if(end <= intervals[i][0]){
end = intervals[i][1];
count++;
}
}
return intervals.size() - count;
}
};
cpp
解法二：区间左边界排序
class Solution {
public:
//按照区间左端值从小到大排列
static bool cmp(const vector<int>& a, const vector<int>& b){
return a[0] < b[0];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if(intervals.size() <= 1) return 0;
sort(intervals.begin(), intervals.end(), cmp);
int ans = 0;
int end = intervals[0][1];
for(int i = 1; i < intervals.size(); i++){
if(intervals[i][0] < end){
ans++;
//注意这里不是max而是min，因为要把更大右边界的那个区间给去除（因为它更可能和别的区间有交集）
end = min(end, intervals[i][1]);
}else{
end = intervals[i][1];
}
}
return ans;
}
};
cpp
3.5划分字母区间
该题目中我们首先找出每个字母最后一次出现的位置即其索引值随后依次遍历整个字符串当当前字符的位置i等于相应字母最后一次出现的索引值时我们就进行一次分割操作此时分割出来的子串满足题目的条件
class Solution {
public:
vector<int> partitionLabels(string s) {
vector<int> hash(26, 0);
for(int i = 0; i < s.size();i++){
hash[s[i] - 'a'] = i;
}
vector<int> result;
int left = 0;
int right = 0;
for(int i = 0; i < s.size(); i++){
//找到字符出现的最远边界
right = max(right, hash[s[i] - 'a']);
if(i == right){
result.push_back(right - left + 1);
left = i + 1;
}
}
return result;
}
};
cpp
3.6合并区间
学习这个题目巧妙合并区间！！
class Solution {
public:
static bool cmp(const vector<int>& a, const vector<int>& b){
if(a[0] == b[0]) return a[1] < b[1];
return a[0] < b[0];
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size() <= 1) return intervals;
sort(intervals.begin(), intervals.end(), cmp);
vector<vector<int>> result;
//第一个区间就可以放进结果集里，后面如果重叠，再result上直接合并
result.push_back(intervals[0]);
for(int i = 1; i < intervals.size(); i++){
if(result.back()[1] >= intervals[i][0]){//区间重叠
//合并区间
result.back()[1] = max(result.back()[1], intervals[i][1]);
}else{
result.push_back(intervals[i]);
}
}
return result;
}
};
cpp
4.其他
4.1最大子数组和
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res =nums[0];
for(int i = 1; i < nums.size(); i++){
nums[i] += max(nums[i - 1], 0);
res = max(res, nums[i]);
}
return res;
}
};
cpp
4.2加油站
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int curSum = 0;
int totalSum = 0;
int start = 0;
for(int i = 0; i < gas.size(); i++){
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
if(curSum < 0){
start = i + 1;//起始位置更新
curSum = 0;
}
}
if(totalSum < 0) return -1;
return start;
}
};
cpp
4.3监控二叉树
/** * Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int result;
//后序遍历：左右根
int travel(TreeNode* cur){
//空节点，为有覆盖状态
if(cur == NULL) return 2;
int left = travel(cur -> left);
int right = travel(cur -> right);
//情况1：左右节点都有覆盖
if(left == 2 && right == 2) return 0;
//情况2
if(left == 0 || right == 0){
result++;
return 1;
}
//情况3
if(left == 1 || right == 1) return 2;
//下面这个return -1 永远都不会执行
return -1;
}
int minCameraCover(TreeNode* root) {
result = 0;
//情况4：root未被覆盖
if(travel(root) == 0){
result++;
}
return result;
}
};
cpp
全部评论 (0)
还没有任何评论哟~