贪心算法
1. leetcode 455 分发饼干
//1. leetcode 455 分发饼干
class Solution {
public:
int findContentChildren(vector& g, vector& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int result = 0;
int index = s.size() - 1; //饼干数组的下标
for (int i = g.size() - 1; i >= 0; i--) { //倒序
if (index >= 0 && s[index] >= g[i]) {
result++;
index--;
}
}
return result;
}
};
// 从小到大
class Solution {
public:
int findContentChildren(vector& g, vector& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int result = 0;
for (int i =0; i < s.size(); i++) {
if (result < g.size() && g[result] <= s[i]) {
result++;
}
}
return result;
}
};
2. leetcode 376 摆动序列
//2. leetcode 376 摆动序列
class Solution {
public:
int wiggleMaxLength(vector& 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 ((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0)) {
result++;
preDiff = curDiff;
}
}
return result;
}
};
3. leetcode 53 最大子数组和
//3. leetcode 53. 最大子数组和
//暴力解法
class Solution {
public:
int maxSubArray(vector& nums) {
int result = INT32_MIN;
int count = 0;
for (int i = 0; i < nums.size(); i++) {
count = 0;
for (int j = i; j < nums.size(); j++) {
count += nums[j];
result = count > result ? count : result;
}
}
return result;
}
};
//贪心
class Solution {
public:
int maxSubArray(vector& nums) {
int result = INT_MIN;
int count = 0;
for (int i = 0; i < nums.size(); i++) {
count += nums[i];
//取区间累计的最大值
if (count > result) {
result = count;
}
//重置最大子序起始位置
if (count <= 0) count = 0;
}
return result;
}
};
//动态规划
class Solution {
public:
int maxSubArray(vector& nums) {
if (nums.size() == 0) return 0;
vector dp(nums.size(), 0);
dp[0] = nums[0];
int result = dp[0];
for (int i = 1; i < nums.size(); i++) {
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
if (dp[i] > result) result = dp[i];
}
return result;
}
};
4. leetcode 122 买卖股票的最佳时机 II
//4. leetcode 122 买卖股票的最佳时机 II
//贪心
class Solution {
public:
int maxProfit(vector& prices) {
int result = 0;
for (int i = 1; i < prices.size(); i++) {
result += max(prices[i] - prices[i - 1], 0);
}
return result;
}
};
//动态规划
class Solution {
public:
int maxProfit(vector& prices) {
//dp[i][0] 第i天持有的最多现金
//dp[i][1] 第i天持有股票后的最多现金
int n = prices.size();
vector> dp(n, vector(2, 0));
dp[0][0] -= prices[0];
for (int i = 1; i < n; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
}
return max(dp[n - 1][0], dp[n - 1][1]);
}
};
5. leetcode 55 跳跃游戏
//5. leetcode 55 跳跃游戏
class Solution {
public:
bool canJump(vector& nums) {
int cover = 0;
if (nums.size() == 1) return true;
for (int i = 0; i <= cover; i++) {
cover = max(i + nums[i], cover);
if (cover >= nums.size() - 1) return true;
}
return false;
}
};
6. leetcode 45 跳跃游戏 II
//6. leetcode 45 跳跃游戏 II
class Solution {
public:
int jump(vector& nums) {
if (nums.size() == 1) return 0;
int curDistance = 0; //当前覆盖最远距离下标
int ans = 0;
int nextDistance = 0; //下一步覆盖最远距离下标
for (int i = 0; i < nums.size(); i++) {
//更新下一步覆盖最远距离下标
nextDistance = max(nums[i] + i, nextDistance);
//遇到当前覆盖最远距离下标=
if (i == curDistance) {
//遇到当前覆盖最远距离下标不是终点
if (curDistance != nums.size() - 1) {
ans++;
curDistance = nextDistance;
if (nextDistance >= nums.size() - 1) break;
} else break; //当前覆盖最远距离下标是集合终点，不用做ans++操作，直接结束
}
}
return ans;
}
};
class Solution {
public:
int jump(vector& nums) {
int curDistance = 0;
int ans = 0;
int nextDistance = 0;
for (int i = 0; i < nums.size() - 1; i++) {
nextDistance = max(nums[i] + i, nextDistance);
if (i == curDistance) {
curDistance = nextDistance;
ans++;
}
}
return ans;
}
};
7. leetcode 1005 K次取反后最大化的数组和
//7. leetcode 1005 K 次取反后最大化的数组和
class Solution {
static bool cmp(int a, int b) {
return abs(a) > abs(b);
}
public:
int largestSumAfterKNegations(vector& nums, int k) {
sort(nums.begin(), nums.end(), cmp);
for (int i = 0; i < nums.size(); i++) {
if (nums[i] < 0 && k > 0) {
nums[i] *= -1;
k--;
}
}
if (k % 2 == 1) nums[nums.size() - 1] *= -1;
int result = 0;
for (int num : nums) result += num;
return result;
}
};
8. leetcode 134 加油站
//8. leetcode 134 加油站
//暴力解法
class Solution {
public:
int canCompleteCircuit(vector& gas, vector& cost) {
for (int i = 0; i < cost.size(); i++) {
int rest = gas[i] - cost[i];
int index = (i + 1) % cost.size();
while (rest > 0 && index != i) {
rest += gas[index] - cost[index];
index = (index + 1) % cost.size();
}
if (rest >= 0 && index == i) return i;
}
return -1;
}
};
//贪心
class Solution {
public:
int canCompleteCircuit(vector& gas, vector& cost) {
int curSum = 0;
int min = INT_MAX;
for (int i = 0; i < gas.size(); i++) {
int rest = gas[i] - cost[i];
curSum += rest;
if (curSum < min) {
min = curSum;
}
}
if (curSum < 0) return -1;
if (min >= 0) return 0;
for (int i = gas.size() - 1; i >= 0; i--) {
int rest = gas[i] - cost[i];
min += rest;
if (min >= 0) {
return i;
}
}
return -1;
}
};
//贪心
class Solution {
public:
int canCompleteCircuit(vector& gas, vector& 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;
}
};
9.leetcode 135 分发糖果
//9.leetcode 135 分发糖果
class Solution {
public:
int candy(vector& ratings) {
vector result(ratings.size(), 1);
//从前向后 右比左大
for (int i = 1; i < ratings.size(); i++) {
if (ratings[i] > ratings[i - 1]) result[i] = result[i - 1] + 1;
}
//从后向前 左比右大
for (int i = ratings.size() - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) result[i] = max(result[i], result[i + 1] + 1);
}
//统计结果
int res = 0;
for (int i = 0; i < result.size(); i++) res += result[i];
return res;
}
};
10.leetcode 860 柠檬水找零
//10.leetcode 860. 柠檬水找零
class Solution {
public:
bool lemonadeChange(vector& bills) {
int five = 0, ten = 0;
for (int bill : bills) {
if (bill == 5) five++;
if (bill == 10) {
if (five <= 0) return false;
ten++;
five--;
}
if (bill == 20) {
if (five > 0 && ten > 0) {
five--;
ten--;
} else if (five >= 3) {
five -= 3;
} else return false;
}
}
return true;
}
};
11.leetcode 406 根据身高重建队列
//11.leetcode 406.根据身高重建队列
//数组
class Solution {
public:
static bool cmp(const vector a, const vector b) {
if (a[0] == b[0]) return a[1] < b[1];
return a[0] > b[0];
}
vector> reconstructQueue(vector>& people) {
sort(people.begin(), people.end(), cmp);
vector> que;
for (int i = 0; i < people.size(); i++) {
int position = people[i][1];
que.insert(que.begin() + position, people[i]);
}
return que;
}
};
//链表
class Solution {
public:
static bool cmp(const vector a, const vector b) {
if (a[0] == b[0]) return a[1] < b[1];
return a[0] > b[0];
}
vector> reconstructQueue(vector>& people) {
sort(people.begin(), people.end(), cmp);
//list底层是链表，插入效率比vector高
list> que;
for(int i = 0; i < people.size(); i++) {
int position = people[i][1];
std::list>::iterator it = que.begin();
while (position--) {
it++;
}
que.insert(it, people[i]);
}
return vector>(que.begin(), que.end());
}
};
12.leetcode 452 用最少数量的箭引爆气球
//12.leetcode 452. 用最少数量的箭引爆气球
class Solution {
private:
static bool cmp(const vector& a, const vector& b) {
return a[0] < b[0];
}
public:
int findMinArrowShots(vector>& points) {
if (points.size() == 0) return 0;
sort(points.begin(), points.end(), cmp);
int result = 1;
for (int i = 1; i < points.size(); i++) {
if (points[i][0] > points[ i - 1][1]) { // 气球i与气球i - 1不相邻
result++;
} else { //气球i和气球i - 1挨着
//更新重叠气球最小右边界
points[i][1] = min(points[i - 1][1], points[i][1]);
}
}
return result;
}
};
13.leetcode 435 无重叠区间
//13.leetcode 435. 无重叠区间
class Solution {
public:
//按区间右边界进行排序
static bool cmp(const vector& a, const vector& b) {
return a[1] < b[1];
}
int eraseOverlapIntervals(vector>& intervals) {
if (intervals.size() == 0) 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;
}
};
14.leetcode 763 划分字母区间
//14.leetcode 763 划分字母区间
class Solution {
public:
vector partitionLabels(string s) {
int hash[27] = {0}; //i为字符，hash[i]为字符出现的最后位置
//统计没一个字符最后出现的位置
for (int i = 0; i < s.size(); i++) {
hash[s[i] - 'a'] = i;
}
vector result;
int left = 0, 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;
}
};
15.leetcode 56 合并区间
//15.leetcode 56. 合并区间
class Solution {
public:
static bool cmp(const vector& a, const vector& b) {
return a[0] < b[0];
}
vector> merge(vector>& intervals) {
vector> result;
if (intervals.size() == 0) return result;
sort(intervals.begin(), intervals.end(), cmp);
bool flag = false;
int length = intervals.size();
for (int i = 1; i < length; i++) {
int start = intervals[i - 1][0];
int end = intervals[i - 1][1];
while (i < length && intervals[i][0] <= end) {
end = max(end, intervals[i][1]);
if (i == length - 1) flag = true;
i++;
}
result.push_back({start, end});
}
if (flag == false) {
result.push_back({intervals[length - 1][0], intervals[length - 1][1]});
}
return result;
}
};
16.leetcode 738 单调递增的数字
//16.leetcode 738. 单调递增的数字
//暴力循环
class Solution {
private:
bool checkNum(int num) {
int max = 10;
while (num) {
int t = num % 10;
if (max >= t) max = t;
else return false;
num = num / 10;
}
return true;
}
public:
int monotoneIncreasingDigits(int n) {
for (int i = n; i > 0; i--) {
if (checkNum(i)) return i;
}
return 0;
}
};
//贪心
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string strNum = to_string(n);
//flag 用来标记赋值9从哪里开始
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);
}
};
17.leetcode 714 买卖股票的最佳时机含手续费
//17. leetcode 714. 买卖股票的最佳时机含手续费
//贪心算法
class Solution {
public:
int maxProfit(vector& prices, int fee) {
int result = 0;
//记录最低的价格
int minPrice = prices[0];
for (int i = 1; i < prices.size(); i++) {
//买入
if (prices[i] < minPrice) minPrice = prices[i];
//保持原有的状态
if (prices[i] >= minPrice && prices[i] <= minPrice + fee) {
continue;
}
//计算利润 可能有多次利润计算，最后一次才是卖出
if (prices[i] > minPrice + fee) {
result += prices[i] - minPrice - fee;
minPrice = prices[i] - fee; //情况一 持有股票
}
}
return result;
}
};
//动态规划
class Solution {
public:
int maxProfit(vector& prices, int fee) {
int n = prices.size();
vector> dp(n, vector(2, 0));
dp[0][0] -= prices[0];
for (int i = 1; i < n; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
}
return max(dp[n - 1][0], dp[n - 1][1]);
}
};
18.leetcode 968 监控二叉树
//18.leetcode 968 监控二叉树
class Solution {
private:
int result;
int traversal(TreeNode* cur) {
//空节点 该节点有覆盖
if (cur == nullptr) return 2;
int left = traversal(cur->left);
int right = traversal(cur->right);
//左右节点都覆盖
if (left == 2 && right == 2) return 0;
//left == 0 && right == 0 左右节点无覆盖
//left == 1 && right == 0 左节点有摄像头，右节点无覆盖
//left == 0 && right == 1 左节点无覆盖，右节点有摄像头
//left == 0 && right == 2 左节点无覆盖 有节点覆盖
//left == 2 && right == 0 左节点覆盖 右节点无覆盖
if (left == 0 || right == 0) {
result++;
return 1;
}
//left == 1 && right == 2 左节点有摄像头 右节点有覆盖
//left == 2 && right == 1 左节点有覆盖 右节点有摄像头
//left == 1 && right == 1 左右节点有摄像头
if (left == 1 || right == 1) return 2;
return -1;
}
public:
int minCameraCover(TreeNode* root) {
result = 0;
if (traversal(root) == 0) {
result++;
}
return result;
}
};
