LC 455.分发饼干：https://leetcode.cn/problems/assign-cookies/
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
if (!s.size()) return 0;
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int res = 0;
for (int i = 0; i < g.size(); ++ i){
for(int j = 0; j < s.size(); ++ j){
if (g[i] <= s[j] && s[j]){
s[j] = 0;
res ++;
break;
}
}
}
return res;
}
};LC 376. 摆动序列：https://leetcode.cn/problems/wiggle-subsequence/
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int len = nums.size();
if (len == 1) return len;
else if (len == 2 && nums[0] != nums[1]) return len;
else if (len == 2 && nums[0] == nums[1]) return 1;
int res = 1,preDiff = 0,curDiff = 0;
for (int i = 0; i < len - 1; ++ i){
curDiff = nums[i + 1] - nums[i];
// 从0开始（此时prediff和curdiff重叠只想一个delta）,让i 在走一步才会开始计算prediff（才会有prediff）
if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)){
res ++;
preDiff = curDiff;
}
}
return res;
}
};LC 53. 最大子序和：https://leetcode.cn/problems/maximum-subarray/
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if (nums.size() == 1) return nums[0];
int sum = 0,maxSumSeq = INT32_MIN;
for (int i = 0; i < nums.size(); ++ i){
sum += nums[i];
if (maxSumSeq < sum) maxSumSeq = sum;
if (sum <= 0) sum = 0;
}
return maxSumSeq;
}
};LC 122.买卖股票的最佳时机II：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
122. 买卖股票的最佳时机 II - 力扣（LeetCode）
greedy
class Solution {
public:
// greedy
int maxProfit(vector<int>& prices) {
int Purchase = prices[0], Profit = 0, i = 1, size = prices.size();
for(;i < size; ++ i)
{
if (prices[i - 1] < prices[i])
{
Purchase = prices[i - 1];
Profit += (prices[i] - prices[i - 1]);
}
}
return Profit;
}
};dp
class Solution {
public:
int maxProfit(vector<int>& prices) {
int maxTotal = 0;
for(int i = 0; i < prices.size() - 1; ++ i){
maxTotal += max(prices[i + 1] - prices[i],0);
}
return maxTotal;
}
};LC 55. 跳跃游戏：https://leetcode.cn/problems/jump-game/
class Solution {
public:
bool canJump(vector<int>& nums) {
if (nums.size() == 1) return true;
int cover = 0;
for(int i = 0; i <= cover; ++ i){
cover = max(i + nums[i],cover);
if (cover >= nums.size() - 1) return true;
}
return false;
}
};LC 45. 跳跃游戏 II：https://leetcode.cn/problems/jump-game-ii/
class Solution {
public:
int jump(vector<int>& nums) {
int curDistance = 0,nextDistance = 0,res = 0;
for (int i = 0; i < nums.size() - 1; ++ i){
nextDistance = max(i + nums[i], nextDistance);
if (i == curDistance){
curDistance = nextDistance;
res ++;
}
}
return res;
}
};LC 1005.K次取反后最大化的数组和：https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/
1005. K 次取反后最大化的数组和 - 力扣（LeetCode）
class Solution {
public:
static bool cmp(const int a, const int b){
return abs(a) > abs(b);
}
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(),nums.end(),cmp);
for (int i = 0; i < nums.size(); ++ i)
if (k && nums[i] < 0){
nums[i] *= -1;
-- k;
}
if (k % 2) nums[nums.size() - 1] *= -1;
return accumulate(nums.begin(), nums.end(),0);
}
};LC 134. 加油站：https://leetcode.cn/problems/gas-station/
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int startPos = 0,curSum = 0,totalSum = 0;
for(int i = 0; i < gas.size(); ++ i){
curSum += (gas[i] - cost[i]);
totalSum += (gas[i] - cost[i]);
if (curSum < 0){
startPos = i + 1;
curSum = 0;
}
}
if (totalSum < 0) return -1;
return startPos;
}
};LC 135. 分发糖果
class Solution {
public:
int candy(vector<int>& ratings) {
int len = ratings.size(),res = 0;
if (!len) return 0;
else if (len == 1) return 1;
vector<int> resVec(len,1);
for (int i = 1; i < len; ++ i)
if (ratings[i] > ratings[i - 1]) resVec[i] = resVec[i - 1] + 1;
for (int i = len - 2; i >= 0; -- i)
if (ratings[i] > ratings[i + 1])
resVec[i] = max(resVec[i],resVec[i + 1] + 1);
return accumulate(resVec.begin(),resVec.end(),0);
}
};LC 860.柠檬水找零
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
if (bills[0] != 5) return false;
int five = 0, ten = 0;
for (int val : bills){
switch (val){
case 5 : ++ five;
break;
case 10 :{
if (five){
-- five;
++ ten;
}
else return false;
}
break;
case 20 : {
if (ten && five) {
-- ten;
-- five;
}
else if(five >= 3) five -= 3;
else return false;
}
break;
}
}
return true;
}
};LC 406.根据身高重建队列：https://leetcode.cn/problems/queue-reconstruction-by-height/
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>> reconstructQueue(vector<vector<int>>& people) {
vector<vector<int>> que;
if (people.size() == 1) {
que.emplace_back(people[0]);
return que;
}
sort(people.begin(),people.end(),cmp);
for(int i = 0; i < people.size(); ++i)
que.insert(que.begin() + people[i][1],people[i]);
que.shrink_to_fit();
return que;
}
};LC 452. 用最少数量的箭引爆气球：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/
452. 用最少数量的箭引爆气球 - 力扣（LeetCode）
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() == 1 || !points.size()) return points.size();
sort(points.begin(),points.end(),cmp);
int res = 1;
for (int i = 1; i < points.size(); ++ i){
if (points[i][0] > points[i - 1][1])
++ res;
else
points[i][1] = min(points[i - 1][1],points[i][1]);
}
return res;
}
};LC 435. 无重叠区间：https://leetcode.cn/problems/non-overlapping-intervals/
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 cnt = 0,end = intervals[0][0];
for (int i = 1; i < intervals.size(); ++ i){
if (intervals[i][0] < intervals[i - 1][1]){
++ cnt;
intervals[i][1] = min(intervals[i - 1][1],intervals[i][1]);
}
}
return cnt;
}
};LC 763.划分字母区间：https://leetcode.cn/problems/partition-labels/
class Solution {
public:
vector<int> partitionLabels(string s) {
if (s.size() == 1) return vector<int>{1};
vector<int> res;
int hash[27] = {0};
for(int i = 0; i < s.size(); ++ i)
hash[s[i] - 'a'] = i;
int right = 0, left = 0;
for (int i = 0; i < s.size(); ++ i){
right = max(right,hash[s[i] - 'a']);
if (right == i){
res.emplace_back(right - left + 1);
left = i + 1;
}
}
res.shrink_to_fit();
return res;
}
};LC 56. 合并区间：https://leetcode.cn/problems/merge-intervals/
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.size() == 1) return intervals;
vector<vector<int>> res;
sort(intervals.begin(), intervals.end(),
[](const vector<int>& a,const vector<int> &b){ return a[0] < b[0];});
res.emplace_back(intervals[0]);
for (int i = 1; i < intervals.size(); ++ i){
if (res.back()[1] >= intervals[i][0])
res.back()[1] = max(res.back()[1],intervals[i][1]);
else
res.emplace_back(intervals[i]);
}
res.shrink_to_fit();
return res;
}
};LC 738.单调递增的数字：https://leetcode.cn/problems/monotone-increasing-digits/
class Solution {
public:
int monotoneIncreasingDigits(int n) {
if (n < 0 && n <= 10) return n - 1;
else if (!n) return 0;
string strNum = to_string(n);
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);
}
};LC 968.监控二叉树：https://leetcode.cn/problems/binary-tree-cameras/
/**
* 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:
// 0：该节点无覆盖
// 1：本节点有摄像头
// 2：本节点有覆盖
int res = 0;
int traversal(const TreeNode* node){
if (!node) return 2;
int left = traversal(node->left);
int right = traversal(node->right);
if (left == 0 || right == 0){
res ++;
return 1;
} else if (left == 1 || right == 1) return 2;
else if (right == 2 && right == 2) return 0;
return -1;
}
int minCameraCover(TreeNode* root) {
if (!traversal(root)) res ++;
return res;
}
};