贪心算法leetcode专栏
leetcode 455 分法饼干leetcode 376 摆动序列leetcode 53 最大子数组和leetcode 122 买卖股票的最佳时机 IIleetcode 55 跳跃游戏leetcode 45 跳跃游戏 IIleetcode 1005 K次取反后最大化的数组和leetcode 134 加油站leetcode 135 分发糖果leetcode 860 柠檬水找零leetcode 406 根据身高重建队列leetcode 452 用最少数量的箭引爆气球leetcode 435 无重叠区间leetcode 763 划分字母区间leetcode 56 合并区间leetcode 738 单调递增的数字leetcode 968 监控二叉树
贪心算法leetcode专栏 leetcode 455 分法饼干class Solution {
public:
int findContentChildren(vector& g, vector& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int child = 0;
int cookie = 0;
while(child < g.size() && cookie < s.size())
{
if(g[child] <= s[cookie])
child++;
cookie++;
}
return child;
}
};
class Solution {
public:
int findContentChildren(vector& g, vector& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int child = 0;
int cookie = s.size()-1;
for(int i = g.size()-1; i >= 0; i--)
{
if(cookie >= 0 && s[cookie] >= g[i])
{
child++; //一个饼干用来满足一个孩子
cookie--;
}
}
return child;
}
};
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;
}
};
class Solution {
public:
int wiggleMaxLength(vector& nums) {
if (nums.size() <= 1) return nums.size();
static const int BEGIN = 0;
static const int UP = 1;
static const int DOWN = 2;
int STATE = BEGIN;
int maxLen = 1;
int i = 0;
for(int i = 0; i < nums.size()-1; i++)
{
switch(STATE)
{
case BEGIN:
if(nums[i+1] > nums[i])
{
maxLen++;
STATE = UP;
}
if(nums[i+1] < nums[i])
{
maxLen++;
STATE = DOWN;
}
break;
case UP:
if(nums[i+1] < nums[i])
{
maxLen++;
STATE = DOWN;
}
break;
case DOWN:
if(nums[i+1] > nums[i])
{
maxLen++;
STATE = UP;
}
break;
}
}
return maxLen;
}
};
leetcode 53 最大子数组和
暴力搜索的结果会超时的
class Solution {
public:
int maxSubArray(vector& nums) {
int max = INT_MIN;
int sum;
for(int i = 0; i < nums.size(); i++)
{
sum = 0;
for(int j = i; j < nums.size(); j++)
{
sum = sum + nums[j];
max = sum > max ? sum : max;
}
}
return max;
}
};
局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”
局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。
从代码角度上来讲：遍历nums，从头开始用count累积，如果sum一旦加上nums[i]变为负数，那么就应该从nums[i+1]开始从0累积sum了，因为已经变为负数的sum，只会拖累总和。
这相当于是暴力解法中的不断调整最大子序和区间的起始位置。
class Solution {
public:
int maxSubArray(vector& nums) {
int max = INT_MIN;
int sum = 0;
for(int i = 0; i < nums.size(); i++)
{
sum = sum + nums[i];
max = sum > max ? sum : max;
if(sum <= 0) sum = 0;
}
return max;
}
};
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;
}
};
leetcode 55 跳跃游戏
class Solution {
public:
bool canJump(vector& nums) {
int loc = 0;
int range = 0;
bool flag = false;
if(nums.size() <= 1) return true;
while(loc < nums.size())
{
range = nums[loc];
if(loc + range >= nums.size() - 1) //可以跳到终点 terminate
{
flag = true;
break;
}
if(range == 0 && loc < nums.size() - 1) //不可能跳到终点
{
break;
}
int max = INT_MIN;
int next;
for(int i = loc+1; i <= loc + range; i++)
{
if (i + nums[i] >= max) //{ 4,2,0,0,1,1,4,4,4,0,4,0 }
{ //next loc必须在当前loc+range范围内选取loc+range(i + nums[i])最大的那个记录,也就是下次站在loc = i位置时，是局部范围内可以跳的最远的选择。
max = i + nums[i];
next = i;
}
}
loc = next;
}
return flag;
}
};
class Solution {
public:
bool canJump(vector& nums) {
int cover = 0; //cover是可以跳跃的最远的覆盖范围
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;
}
};
leetcode 45 跳跃游戏 II
class Solution {
public:
int jump(vector& nums) {
int loc = 0;
int range = 0;
bool flag = false;
if(nums.size() == 1) return 0;
int count = 0;
while(loc < nums.size())
{
range = nums[loc];
if(loc + range >= nums.size() - 1) //可以跳到终点 terminate
{
count++;
flag = true;
break;
}
int max = INT_MIN;
int next;
for(int i = loc+1; i <= loc + range; i++)
{
if (i + nums[i] >= max) //{ 4,2,0,0,1,1,4,4,4,0,4,0 }
{
max = i + nums[i];
next = i;
}
}
loc = next;
count++;
}
return count;
}
};
leetcode 1005 K次取反后最大化的数组和
按逻辑写通过的
class Solution {
public:
int largestSumAfterKNegations(vector& nums, int k) {
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size() || k > 0; i++)
{
if(k == 0)
{
break;
}
if(i >= nums.size() && k > 0)
{
goto Label;
}
if(nums[i] <= 0)
{
nums[i] = -nums[i];
k--;
}
else
{
Label:
sort(nums.begin(), nums.end());
nums[0] = -nums[0];
k--;
}
}
int sum = 0;
for(int i = 0; i < nums.size(); i++)
{
sum += nums[i];
}
return sum;
}
};
class Solution {
public:
static bool cmp(int a, int b)
{
return abs(a) > abs(b);
}
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] = -nums[i];
k--;
}
}
while(k)
{
nums[nums.size()-1] *= -1;
k--;
}
int sum = 0;
for(int i = 0; i < nums.size(); i++)
{
sum += nums[i];
}
return sum;
}
};
leetcode 134 加油站
//情况一：如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的 //情况二：rest[i] = gas[i]-cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。 //情况三：如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能这个负数填平，能把这个负数填平的节点就是出发节点。 class Solution { public: int canCompleteCircuit(vector& gas, vector & cost) { int minDiff = INT_MAX; int totalDiff = 0; for(int i = 0; i < gas.size(); i++) { int rest = gas[i] - cost[i]; totalDiff += rest; if(totalDiff < minDiff) { minDiff = totalDiff; } } if(totalDiff < 0) return -1; if(minDiff >= 0) return 0; for(int i = gas.size()-1; i >=0; i--) { int rest = gas[i] - cost[i]; minDiff += rest; if(minDiff >= 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;
}
};
leetcode 135 分发糖果
class Solution {
public:
int candy(vector& ratings) {
vector 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);
}
int result = 0;
for(auto ele : candyVec) result += ele;
return result;
}
};
leetcode 860 柠檬水找零
class Solution {
public:
bool lemonadeChange(vector& bills) {
int hashVec[21] = {0};
for(int i = 0; i < bills.size(); i++) {
if(bills[i] == 5) {
hashVec[5]++;
}
else if(bills[i] == 10) {
hashVec[10]++;
if(hashVec[5] > 0) {
hashVec[5]--;
}
else {
return false;
}
}
else {
hashVec[20]++;
bool flag = false;
if(hashVec[10] > 0) {
hashVec[10]--;
flag = true;
}
if(hashVec[5] > 0 && flag == true) {
hashVec[5]--;
}
else {
if(hashVec[5] == 0)
return false;
}
if(hashVec[5] > 0 && flag == false) {
hashVec[5] = hashVec[5] - 3;
if(hashVec[5] < 0) {
return false;
}
}
}
}
return true;
}
};
class Solution {
public:
bool lemonadeChange(vector& bills) {
int five = 0, ten = 0, twenty = 0;
for(auto bill : bills) {
if(bill == 5) {
five++;
}
else if(bill == 10) {
if(five <= 0) {
return false;
}
ten++;
five--;
}
else {
if(ten > 0 && five > 0) {
ten--;
five--;
}
else if (five >= 3) {
five -= 3;
}
else {
return false;
}
}
}
return true;
}
};
leetcode 406 根据身高重建队列
class Solution {
static bool cmp(const vector& a, const vector& b) {
if(a[0] == b[0]) return a[1] < b[1];
else return a[0] > b[0];
}
public:
vector> reconstructQueue(vector>& people) {
sort(people.begin(), people.end(), cmp);
vector> queue;
for(int i = 0; i < people.size(); i++) {
int pos = people[i][1];
queue.insert(queue.begin()+pos, people[i]);
}
return queue;
}
};
class Solution {
static bool cmp(const vector& a, const vector& b) {
if(a[0] == b[0]) return a[1] < b[1];
else return a[0] > b[0];
}
public:
vector> reconstructQueue(vector>& people) {
sort(people.begin(), people.end(), cmp);
list> queue;
for(int i = 0; i < people.size(); i++) {
int pos = people[i][1];
auto it = queue.begin();
while(pos) {
it++;
pos--;
}
queue.insert(it, people[i]);
}
return vector>(queue.begin(), queue.end());
}
};
leetcode 452 用最少数量的箭引爆气球
class Solution {
static bool cmp(const vector& a, const vector& b) {
return a[0] < b[0];
}
public:
int findMinArrowShots(vector>& points) {
sort(points.begin(), points.end(), cmp);
int start = points[0][0];
int end = points[0][1];
int shootNum = 1;
for(int i = 1; i < points.size(); i++) {
if(points[i][0] <= end) {
start = points[i][0];
if(points[i][1] <= end) {
end = points[i][1];
}
}
else {
shootNum++;
start = points[i][0];
end = points[i][1];
}
}
return shootNum;
}
};
leetcode 435 无重叠区间
class Solution {
static bool cmp(const vector& a, const vector& b) {
return a[1] < b[1];
}
public:
int eraseOverlapIntervals(vector>& intervals) {
sort(intervals.begin(), intervals.end(), cmp);
int rightBound = intervals[0][1];
int overlap = 0;
for(int i = 1; i < intervals.size(); i++) {
if(intervals[i][0] < rightBound) {
overlap++;
continue;
}
else {
rightBound = intervals[i][1];
}
}
return overlap;
}
};
leetcode 763 划分字母区间
class Solution {
public:
vector partitionLabels(string s) {
int hashVec[27] = {0};
for(int i = 0; i < s.size(); i++) {
hashVec[s[i]-'a'] = i; //统计每个字母最后出现的下标
}
int right = 0;
int left = 0;
vector result;
for(int i = 0; i < s.size(); i++) {
right = max(right, hashVec[s[i]-'a']); //不断更新该片段中字母最后出现的下标
if(right == i) { //片段分割点
result.push_back(right - left + 1);
left = i + 1;
}
}
return result;
}
};
leetcode 56 合并区间
按照左边界排序，排序之后局部最优：每次合并都取最大的右边界，这样就可以合并更多的区间了，整体最优：合并所有重叠的区间。
class Solution {
static bool cmp(const vector& a, const vector& b) { //按左边界进行从小到大排序
if(a[0] == b[0]) return a[1] < b[1];
return a[0] < b[0];
}
public:
vector> merge(vector>& intervals) {
sort(intervals.begin(), intervals.end(), cmp);
int left = intervals[0][0];
int right = intervals[0][1];
vector> result;
for(int i = 1; i < intervals.size(); i++) {
if(intervals[i][0] <= right) { //如果当前区间的left小于前面区间的right,说明区间重叠可以合并
if(intervals[i][1] > right) //如果当前区间的right大于前面区间的right,更新一下right最大值,扩大可以合并区间范围
right = intervals[i][1];
}
else {
result.push_back(vector{left, right}); //说明区间不重叠，更新新的left和right值
left = intervals[i][0];
right = intervals[i][1];
}
}
result.push_back(vector{left, right});
return result;
}
};
leetcode 738 单调递增的数字
遍历过程中，要用之前处理的结果推导以后的内容，首先想到从后往前遍历
//向前遍历，前一项大于后一项，前一项就减 1，后面所有都变成 9
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string str = to_string(n);
int flag = str.size();
for(int i = str.size()-1; i >= 1; i--) {
if(str[i-1] > str[i]) {
str[i-1]--;
flag = i;
}
}
for(int i = flag; i < str.size(); i++) {
str[i] = '9';
}
return stoi(str);
}
};
leetcode 968 监控二叉树
//0：该节点无覆盖
//1：本节点有摄像头
//2：本节点有覆盖
class Solution {
public:
int minCameraCover(TreeNode* root) {
int result = 0;
if(recursiveFunc(root, result) == 0) { //最后处理头节点状态
result++;
}
return result;
}
int recursiveFunc(TreeNode* node, int& result) {
if(node == NULL) {
return 2;
}
int left = recursiveFunc(node->left, result);
int right = recursiveFunc(node->right, result);
if(left == 2 && right == 2) {
return 0;
}
if(left == 0 || right == 0) {
result++;
return 1;
}
if(left == 1 || right == 1) {
return 2;
}
return -1;
}
};
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）