贪心【ing】

455. 分发饼干

尺寸小的先给胃口小的或者尺寸大的先给胃口大的

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        int childenIndex = 0;
        for(int i=0; i<s.size();i++) {
            // 尺寸小的先满足胃口小的
            if(childenIndex< g.size() &&s[i]>=g[childenIndex]) childenIndex++;
        }

        return childenIndex;
    }
};

376. 摆动序列

  • 贪心,有曲折的一个趋势就++

    class Solution
    {
    public:
      int wiggleMaxLength(vector &nums)
      {
          if (nums.size() <= 1)
              return nums.size();
    
          int count = 1;   //最右节点算1个峰值
          int preDiff = 0; //默认最左边节点的preDiff为0,假设最左边节点旁也有个相等的节点
          for (int i = 0; i < nums.size() - 1; i++)
          {
              int lastDiff = nums[i + 1] - nums[i];
              if ((preDiff <= 0 && lastDiff > 0) || (preDiff >= 0 && lastDiff < 0))
              {
                  count++;
                  preDiff = lastDiff;
              }
          }
          return count;
      }
    };
  • 动态规划

53. 最大子数组和

  • 贪心

    局部最优:当前“连续和”为负数的时候立刻放弃,从下一个元素重新计算“连续和”,因为负数加上下一个元素 “连续和”只会越来越小。

    全局最优:选取最大“连续和”

    选取所有得到正数过程中最大的值

    class Solution {
    public:
      int maxSubArray(vector& nums) {
          int ans = INT_MIN;
          int curSum = 0;
          for(int i=0;i
  • 动态规划

122. 买卖股票的最佳时机 II

  • 贪心:把每天的利润得出,是正利润就加入

    class Solution {
    public:
      int maxProfit(vector& prices) {
          int ans = 0;
          for(int i=1;i0) ans+=profit;
          }
          return ans;
      }
    };
  • 动态规划

55. 跳跃游戏

每次取最大的跳跃步数,这个就是可以跳跃的覆盖范围。那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点!

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;
        for(int i=0;i<=cover;i++) {
            cover = max(cover, i+nums[i]);
            if(cover>=nums.size()-1) return true;
        }
        return false;
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇