0简介
0.1什么是贪心算法
贪心算法是用贪婪(鼠目寸光)的角度，找到解决问题的最优解
贪心策略：(从局部最优 --> 整体最优)
1把解决问题的过程分为若干步；
2解决每一个问题时，都选择当前“看上去”最优的解法；
3“希望”得到全局最优解
0.2贪心算法特点
1贪心策略的提出
a.没有任何模板和标准
b.可能每道题的贪心标准是不同的
2贪心策略的正确性
a有可能贪心策略是错误的（例二和例三）
b也就是正确的贪心策略是需要证明的！
0.3证明找零问题
1柠檬水找零
oj链接：柠檬水找零
class Solution
{
public:
bool lemonadeChange(vector<int> &bills)
{
int five = 0, ten = 0;
for (auto &bill : bills)
{
if (bill == 5)
five++;
else if (bill == 10)
{
if (five == 0)
return false;
else
ten++, five--;
}
else
{
if (ten == 0)
{
if (five >= 3)
five -= 3;
else
return false;
}
else
{
ten--;
if (five >= 1)
five -= 1;
else
return false;
}
}
}
return true;
}
};
//简化版
class Solution
{
public:
bool lemonadeChange(vector<int> &bills)
{
int five = 0, ten = 0;
for (int i = 0; i < bills.size(); i++)
{
if (bills[i] == 5)
five++;
else if (bills[i] == 10)
{
five--;
ten++;
}
else
{
if (ten)
ten--, five--;
else
five -= 3;
}
if (five < 0)
return false;
}
return true;
}
}; 
2将数组和减半的最小操作次数
oj链接：将数组和减半的最少操作次数
class Solution
{
public:
int halveArray(vector<int> &nums)
{
priority_queue<double> qe;
double sum = 0; // 不能用int！
for (auto &num : nums)
{
qe.push(num);
sum += num;
}
int cnt = 0;
double aim = sum / 2;
while (true)
{
double maxval = qe.top();
qe.pop();
sum -= maxval;
cnt++;
maxval /= 2;
sum += maxval;
if (sum <= aim)
return cnt;
qe.push(maxval);
}
}
};
class Solution
{
public:
int halveArray(vector<int> &nums)
{
priority_queue<double> qe;
double sum = 0.0;
for (auto &num : nums)
{
qe.push(num);
sum += num;
}
sum /= 2.0;
int cnt = 0;
while (sum > 0)
{
double t = qe.top() / 2.0;
qe.pop();
sum -= t;
cnt++;
qe.push(t);
}
return cnt;
}
};
3最大数
oj链接：最大数
class Solution
{
public:
class cmp
{
public:
bool operator()(const string &s1, const string &s2)
{
return s1 + s2 > s2 + s1;
}
};
string largestNumber(vector<int> &nums)
{
vector<string> str;
for (auto &e : nums)
str.push_back(to_string(e));
sort(str.begin(), str.end(), cmp());
string ret;
for (auto &e : str)
ret += e;
if (ret[0] == '0')
return "0";
return ret;
}
};
4摆动序列
oj链接：摆动序列
class Solution
{
public:
int left = 0, ret = 0;
int wiggleMaxLength(vector<int> &nums)
{
for (int i = 0; i < nums.size() - 1; i++)
{
int right = nums[i + 1] - nums[i];
if (right == 0)
continue; // 有连续相等的情况
if (left * right <= 0)
ret++; // left=0 -> 开始处于第一个位置也要加
left = right;
}
return ret + 1; // 加上最后一个位置
}
};
5最长递增子序列
oj链接：最长递增子序列
class Solution
{
public:
int lengthOfLIS(vector<int> &nums)
{
vector<int> ret;
ret.push_back(nums[0]);
for (int i = 1; i < nums.size(); i++)
{
int x = nums[i];
if (x > ret.back())
ret.push_back(x);
else
{
// 二分插入位置
int left = 0, right = ret.size() - 1;
while (left < right)
{
int mid = left + (right - left) / 2;
if (ret[mid] < x)
left = mid + 1;
else
right = mid;
}
ret[left] = x;
}
}
return ret.size();
}
};6递增的三元子序列
oj链接：递增的三元子序列
思路：与上题类似！
class Solution
{
public:
bool increasingTriplet(vector<int> &nums)
{
vector<int> ret;
ret.push_back(nums[0]);
for (int i = 1; i < nums.size(); i++)
{
int x = nums[i];
if (x > ret.back())
ret.push_back(x);
else
{
int left = 0, right = ret.size() - 1;
while (left < right)
{
int mid = left + (right - left) / 2;
if (ret[mid] < x)
left = mid + 1;
else
right = mid;
}
ret[left] = x;
}
}
return ret.size() >= 3;
}
};7最长连续递增序列
oj链接：最长连续递增序列
该方法是从暴力解法（两层for循环）优化来的，所以暴力解法对，这个贪心一定对！
class Solution
{
public:
int findLengthOfLCIS(vector<int> &nums)
{
int n = nums.size(), ret = 1;
for (int i = 0; i < n; i++)
{
int j = i;
while (j + 1 < n && nums[j] < nums[j + 1])
j++;
ret = max(j - i + 1, ret);
i = j;
}
return ret;
}
};8买卖股票的最佳时机
oj链接：买卖股票的最佳时机
该方法是从暴力解法（两层for循环）优化来的，所以暴力解法对，这个贪心一定对！
class Solution
{
public:
int maxProfit(vector<int> &prices)
{
int n = prices.size(), ret = 0;
int MinPrice = INT_MAX;
for (int i = 0; i < n; i++)
{
int profit = prices[i] - MinPrice;
MinPrice = min(MinPrice, prices[i]);
ret = max(profit, ret);
}
return ret;
}
};此题也可以采用 动态规划58道算法题 中的买卖股票的最佳时机Ⅲ的思路来解决~
9买卖股票的最佳时机Ⅱ
oj链接：买卖股票的最佳时机 II
//双指针
class Solution
{
public:
int maxProfit(vector<int> &prices)
{
int n = prices.size(), ret = 0;
for (int i = 0; i < n; i++)
{
int j = i;
while (j + 1 < n && prices[j] < prices[j + 1])
j++;
ret += prices[j] - prices[i];
i = j;
}
return ret;
}
};
//一天一天拆分
class Solution
{
public:
int maxProfit(vector<int> &prices)
{
int n = prices.size(), ret = 0;
for (int i = 0, right = 0; i < n - 1; i++)
{
right = prices[i + 1] - prices[i];
if (right > 0)
ret += right;
}
return ret;
}
};10K次取反后最大化的数组和
oj链接：K 次取反后最大化的数组和
//解法1：原始分类讨论
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
int m = 0, minElem = INT_MAX, n = nums.size();
for (auto x : nums) {
if (x < 0)
m++;
minElem = min(minElem, abs(x)); // 求绝对值最⼩的那个数
}
// 分类讨论
int ret = 0;
if (m > k) {
sort(nums.begin(), nums.end());
for (int i = 0; i < k; i++) // 前 k ⼩个负数，变成正数
{
ret += -nums[i];
}
for (int i = k; i < n; i++) // 后⾯的数不变
{
ret += nums[i];
}
} else {
// 把所有的负数变成正数
for (auto x : nums)
ret += abs(x);
if ((k - m) % 2) // 判断是否处理最⼩的正数
{
ret -= minElem * 2;
}
}
return ret;
}
};
//解法2：利用小堆
class Solution
{
public:
int largestSumAfterKNegations(vector<int> &nums, int k)
{
priority_queue<int, vector<int>, greater<int>> qe;
for (auto &num : nums)
qe.push(num);
while (k)
{
int tmp = qe.top();
qe.pop();
tmp = -tmp;
qe.push(tmp);
k--;
}
int ret = 0;
while (!qe.empty())
{
ret += qe.top();
qe.pop();
}
return ret;
}
};11按身高排序
oj链接：按身高排序
// 解法1
class Solution
{
public:
vector<string> sortPeople(vector<string> &names, vector<int> &heights)
{
int n = names.size();
pair<int, string> pr[n];
for (int i = 0; i < n; i++)
{
pr[i].first = heights[i];
pr[i].second = names[i];
}
sort(pr, pr + n, greater());
vector<string> ret(n);
for (int i = 0; i < n; i++)
ret[i] = pr[i].second;
return ret;
}
};
// 解法2
class Solution
{
public:
vector<string> sortPeople(vector<string> &names, vector<int> &heights)
{
int n = names.size();
map<int, string> hash;
for (int i = 0; i < n; i++)
hash[heights[i]] = names[i];
vector<string> ret;
for (auto &[a, b] : hash)
ret.push_back(b);
reverse(ret.begin(), ret.end());
return ret;
}
};
// 解法3
class Solution
{
public:
vector<string> sortPeople(vector<string> &names, vector<int> &heights)
{
int n = names.size();
vector<int> index(n);
for (int i = 0; i < n; i++)
index[i] = i;
sort(index.begin(), index.end(), [&](int i, int j)
{ return heights[i] > heights[j]; });
vector<string> ret(n);
for (int i = 0; i < n; i++)
ret[i] = names[index[i]];
return ret;
}
};12优势洗牌
oj链接：优势洗牌
class Solution
{
public:
vector<int> advantageCount(vector<int> &nums1, vector<int> &nums2)
{
int n = nums2.size();
vector<int> index2(n);
for (int i = 0; i < n; i++)
index2[i] = i;
sort(index2.begin(), index2.end(), [&](int i, int j)
{ return nums2[i] < nums2[j]; });
sort(nums1.begin(), nums1.end());
vector<int> ret(n);
// 田忌赛马
int left = 0, right = n - 1;
for (int i = 0; i < n; i++)
{
if (nums1[i] > nums2[index2[left]])
ret[index2[left++]] = nums1[i]; // 比你大
else
ret[index2[right--]] = nums1[i]; // 比你小/相等 取对付你最大的数: nums2[index[right]]
}
return ret;
}
};
13最长回文串
oj链接：最长回文串
class Solution
{
public:
int longestPalindrome(string s)
{
unordered_map<char, int> hash;
for (auto &a : s)
hash[a]++;
int ret = 0, tmp = 0;
for (auto &[a, b] : hash)
{
// if(b%2==0) ret+=b;
// else ret+=b-1;
ret += b / 2 * 2;
}
if (ret < s.size())
ret++;
return ret;
}
};14增减字符串匹配
oj链接：增减字符串匹配
class Solution
{
public:
vector<int> diStringMatch(string s)
{
vector<int> ret;
int l = 0, r = s.size();
for (auto &ch : s)
{
if (ch == 'I')
ret.push_back(l++);
else
ret.push_back(r--);
}
ret.push_back(l /*r*/);
return ret;
}
};15分发饼干
oj链接：分发饼干
class Solution
{
public:
int findContentChildren(vector<int> &g, vector<int> &s)
{
if (s.size() == 0)
return 0;
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int i = 0, j = 0;
while (i < g.size() && j < s.size())
{
if (g[i] <= s[j])
{
i++;
j++;
}
else
j++;
}
return i;
}
};
16最优除法
oj链接：最优除法
class Solution
{
public:
string optimalDivision(vector<int> &nums)
{
if (nums.size() == 1)
{
return to_string(nums[0]);
}
else if (nums.size() == 2)
{
return to_string(nums[0]) + "/" + to_string(nums[1]);
}
string ret = to_string(nums[0]) + "/(" + to_string(nums[1]);
for (int i = 2; i < nums.size(); i++)
{
ret += "/" + to_string(nums[i]);
}
ret += ")";
return ret;
}
};17跳跃游戏Ⅱ
oj链接：跳跃游戏 II
// 解法1
class Solution
{
public:
int jump(vector<int> &nums)
{
int n = nums.size();
vector<int> dp(n, INT_MAX);
dp[0] = 0;
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (nums[j] >= i - j)
dp[i] = min(dp[i], dp[j] + 1);
}
}
return dp[n - 1];
}
};
// 解法2
class Solution
{
public:
int jump(vector<int> &nums)
{
int n = nums.size();
int left = 0, right = 0, ret = 0, maxpos = 0;
while (left < n && right < n)
{
if (maxpos >= n - 1)
return ret;
ret++;
for (int i = left; i <= right; i++)
maxpos = max(maxpos, nums[i] + i);
left = right + 1;
right = maxpos;
}
return ret;
}
};18跳跃游戏
oj链接：跳跃游戏
与上面的思路一致，只不过在while循环更换判断条件即可！
class Solution {
public:
bool canJump(vector<int>& nums) {
int n=nums.size(),left=0,right=0,maxpos=0;
while(left<=right)//如果到不了n-1:left>right
{
if(maxpos>=n-1) return true;
for(int i=left;i<=right;i++) maxpos=max(maxpos,nums[i]+i);
left=right+1;
right=maxpos;
}
return false;
}
};19加油站
oj链接：加油站
class Solution
{
public:
int canCompleteCircuit(vector<int> &gas, vector<int> &cost)
{
int n = gas.size();
for (int i = 0; i < n; i++)
{
int pos = 0, cnt = 0;
for (; pos < n; pos++)
{
int index = (pos + i) % n;
cnt += gas[index] - cost[index];
if (cnt < 0)
break;
}
if (cnt >= 0)
return i;
i = i + pos;
}
return -1;
}
};20单调递增的数字
oj链接：单调递增的数字
class Solution
{
public:
int monotoneIncreasingDigits(int n)
{
string s = to_string(n);
int i = 0, m = s.size();
// 找递减位置
while (i + 1 < m && s[i] <= s[i + 1])
i++;
if (i == m - 1)
return n;
cout << i << endl;
// 回退找相等数的第一个
while (i - 1 >= 0 && s[i - 1] == s[i])
i--;
s[i] -= 1;
for (int j = i + 1; j < m; j++)
s[j] = '9';
return stoi(s);
}
};
21坏了的计算器
oj链接：坏了的计算器
class Solution
{
public:
int brokenCalc(int startValue, int target)
{
// 第一种情况
// if(target<=startValue) return startValue-target;
// 第二种情况
int cnt = 0;
while (target > startValue)
{
if (target % 2 != 0)
target += 1;
else
target /= 2;
cnt++;
}
return cnt + startValue - target;
}
};22合并区间
oj链接：合并区间
class Solution
{
public:
vector<vector<int>> merge(vector<vector<int>> &intervals)
{
if (intervals.size() == 1)
return intervals;
sort(intervals.begin(), intervals.end()); // 左端点排序
vector<vector<int>> ret;
int n = intervals.size(), left = intervals[0][0], right = intervals[0][1];
for (int i = 1; i < n; i++)
{
int next_left = intervals[i][0], next_right = intervals[i][1];
if (right >= next_left)
right = max(right, next_right);
else
{
ret.push_back({left, right});
left = next_left;
right = next_right;
}
if (i == n - 1)
ret.push_back({left, right}); // 最后一组区间放到ret中
}
return ret;
}
};
23无重叠区间
oj链接：无重叠区间
class Solution
{
public:
int eraseOverlapIntervals(vector<vector<int>> &intervals)
{
if (intervals.size() == 1)
return 0;
sort(intervals.begin(), intervals.end());
int n = intervals.size(), ret = 0, left = intervals[0][0], right = intervals[0][1];
for (int i = 1; i < n; i++)
{
int next_left = intervals[i][0], next_right = intervals[i][1];
if (right > next_left)
{
ret++;
right = min(right, next_right); // 删除最大的right区间
}
else
{
left = next_left;
right = next_right;
}
}
return ret;
}
};
24用最少量的箭引爆气球
oj链接：用最少数量的箭引爆气球
class Solution
{
public:
int findMinArrowShots(vector<vector<int>> &points)
{
if (points.size() == 1)
return 1;
sort(points.begin(), points.end());
int left = points[0][0], right = points[0][1];
int n = points.size(), ret = 1;
for (int i = 1; i < n; i++)
{
int next_left = points[i][0], next_right = points[i][1];
if (right >= next_left)
{
// 相交的区间去与下一个比
// left=max(left,next_left);
right = min(right, next_right);
}
else
{
// left=next_left;
right = next_right;
ret++;
}
}
return ret;
}
};
25整数替换
oj链接：整数替换
//解法1
class Solution
{
public:
unordered_map<int, int> memo; // 不用vector:存不下
int integerReplacement(int n)
{
return MinCount(n);
}
int MinCount(long long n) // n越界处理
{
// 记忆化
if (memo.count(n))
return memo[n];
if (n == 1)
{
memo[n] = 0;
return memo[n];
}
int ret = 0;
if (n % 2 != 0)
ret = min(MinCount(n + 1), MinCount(n - 1)) + 1;
else
ret = MinCount(n / 2) + 1;
// 记忆化
memo[n] = ret;
return memo[n];
}
};
//解法2
class Solution
{
public:
int integerReplacement(long long n)
{
int ret = 0;
while (n != 1)
{
if (n % 2 == 0)
n /= 2;
else
{
if (n % 4 == 1 || n == 3)
n -= 1;
else
n += 1;
}
ret++;
}
return ret;
}
};26俄罗斯套娃信封问题
oj链接：俄罗斯套娃信封问题
class Solution
{
public:
int maxEnvelopes(vector<vector<int>> &envelopes)
{
int ret = 0, n = envelopes.size();
sort(envelopes.begin(), envelopes.end());
vector<int> dp(n, 1);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (envelopes[j][1] < envelopes[i][1] && envelopes[j][0] < envelopes[i][0])
dp[i] = max(dp[i], dp[j] + 1);
}
ret = max(ret, dp[i]);
}
return ret;
}
};
class Solution
{
public:
int maxEnvelopes(vector<vector<int>> &envelopes)
{
sort(envelopes.begin(), envelopes.end(), [](vector<int> &v1, vector<int> &v2)
{ return v1[0] == v2[0] ? v1[1] > v2[1] : v1[0] < v2[0]; });
// 重排完序后就变成了最长递增子序列的问题(以每个区间的第二个数为基准)
vector<int> ret;
ret.push_back(envelopes[0][1]);
int n = envelopes.size();
for (int i = 1; i < n; i++)
{
int t = envelopes[i][1];
if (ret.back() < t)
ret.push_back(t);
else
{
int left = 0, right = ret.size() - 1;
while (left < right)
{
int middle = left + (right - left) / 2;
if (ret[middle] >= t)
right = middle;
else
left = middle + 1;
}
ret[left] = t;
}
}
return ret.size();
}
};27可被三整除的最大和
oj链接：可被三整除的最大和
class Solution
{
public:
int maxSumDivThree(vector<int> &nums)
{
int sum = 0, ret = 0;
for (auto &e : nums)
sum += e;
if (sum % 3 == 0)
return sum;
else if (sum % 3 == 1)
{
// 定义y1和y2来求最小值和次小值 注意数据溢出问题
int x = 0x3f3f3f3f3f, y1 = 0x3f3f3f3f3f, y2 = 0x3f3f3f3f3f;
for (auto &e : nums)
{
if (e % 3 == 1)
x = min(x, e);
else if (e % 3 == 2)
{
if (e < y1)
{
y2 = y1;
y1 = e;
}
else if (y1 <= e && e <= y2)
y2 = e;
}
}
ret = max(sum - x, sum - y1 - y2);
}
else
{
int y = 0x3f3f3f3f3f, x1 = 0x3f3f3f3f3f, x2 = 0x3f3f3f3f3f;
for (auto &e : nums)
{
if (e % 3 == 1)
{
if (e < x1)
{
x2 = x1;
x1 = e;
}
else if (x1 <= e && e <= x2)
x2 = e;
}
else if (e % 3 == 2)
y = min(y, e);
}
ret = max(sum - y, sum - x1 - x2);
}
return ret;
}
};
