首页

力扣连着刷到了几个贪心，而且另一篇笔记字数要爆了，决定先按大类慢慢分一下。
🤟参考链接
规律特征就是更加注重当前的状态,通常用于组合优化问题。即每一次都做出当前看起来最好的选择。每次只需要考虑一个问题，并通常是自底向上求解。即局部最优→全局最优。

455.分发饼干

解题思路

完整代码

976.三角形的最大周长

给定由一些正数（代表长度）组成的数组 nums ，返回 由其中三个长度组成的、面积不为零的三角形的最大周长 。如果不能形成任何面积不为零的三角形，返回 0。

  • 3 <= nums.length <= 104
  • 1 <= nums[i] <= 106

解题思路

因为题目需要的是最大的三角形周长，所以不需要暴力列举所有的情况再一一对比，而是直接奔着“最大”这个目标求解就行:
三条边a,b,c（假设从小到大已排好），当a+b>c时满足三角形。如果不满足，必须换更大的a,b。
贪心优化策略：

  • nums排序
  • 从最大的三个数开始 尝试是否满足
  • 若无法满足，往前找更小的a,b
  • 一旦找到符合条件的三边，直接返回

完整代码

class Solution {
public:
    int largestPerimeter(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        for(int i=nums.size()-1;i>=2;i++){
            if(nums[i-1]+nums[i-2]>nums[i])
        }
        return 0;
    }
};

860.柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

  • 1 <= bills.length <= 105
  • bills[i] 不是 5 就是 10 或是 20

解题思路

**找零时，尽量先用大额。**并且只记录5美元、10美元的数量（因为这题目的情况不可能找20块）那么

  • 收到5美元 直接收
  • 收到10美元 10-5=5 找5美元（如果有）
  • 收到20美元 贪心来了~20-5=15优先使用10+5找零，否则用5+5+5（如果有）

完整代码

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five=0,ten=0;
        for(int bill:bills){
            if(bill==5){
                five++;
            }
            else if(bill==10){
                if(five!=0){
                    five--;
                    ten++;
                }
                else{
                    return false;
                }
            }
            else if(bill==20){
                if(ten>0 && five>0){
                    ten--;
                    five--;
                }
                else if(five>=3){
                    five-=3;
                }
                else{
                    return false;
                }
                
            }
        }
        return true;
    }
};

2680.最大或值

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k 。每一次操作中，你可以选择一个数并将它乘 2 。
你最多可以进行 k 次操作，请你返回 nums[0] | nums[1] | … | nums[n - 1] 的最大值。
a | b 表示两个整数 a 和 b 的 按位或 运算。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 15

解题思路

做了这么几道中等题，发现很多难就难在变量大的时候怎么才能不超时的问题上😂

因此要注意：
👉️按位或（|）的特性（二进制数）某一位只要有一个是1，按位或的结果该位就是1。
题目需要按位或的最大值，那么也就意味着尽量让高位变成1。

👉️不能直接暴力枚举否则会超时。

🔍️按位运算总结

运算 运算符 描述 示例
按位与 & 两位都是1，结果才是1 5 & 3 = 1
按位或 一竖杠 只要有一个是1，结果就是1 5 或 3 = 7
按位异或 ^ 相同为0，不同为1 5 ^ 3 = 6
按位取反 ~ 0变1，1变0 ~5 = -6（补码）
左移 << 乘2^k 5 << 1 = 10
右移 >> 除2^k 5 >> 1 = 2

解决方案：
1️⃣预计算最初的或值

  • orsum|=num

2️⃣按位或最大化

  • 遍历nums，对每个num[i]进行优化
  • 假设nums[i]被选中，*2^k，计算新的或值
  • 对于已经选定的nums[i]，0~i-1的或值设为leftor;i+1~n-1的或值设为rightor。那么新的或值只需要让leftor | nums[i]*2^k | rightor即可。
  • nums[i]*2^k用nums[i] * (1LL << k)。表示位运算中的左移操作，让nums[i]的二进制向左移动k位右侧补零，等价于*2^k（这里可以自己试一试：5<<3等价于40=5*8。）；LL防止溢出。

🆗其他问题

  • 为什么 left[i+1] = left[i] | nums[i]，right[i] = right[i+1] | nums[i]？
    按位或计算有个特点：计算或值具有单调性，也就是a|b|c的结果一定不会比a|b小。
    left[i]存的是nums[0]~nums[1]的或值，又因为left[i+1]相比left[i]需要加入nums[i]进行或值运算，所以left[i+1] = left[i] | nums[i]；right[i]同理。

完整代码

class Solution {
public:
    long long maximumOr(vector<int>& nums, int k) {
        int n=nums.size();
        vector<long long> left(n+1,0),right(n+1,0);
        for(int i=0;i<n;i++){
            left[i+1]=left[i]|nums[i];
        }
        for(int i=n-1;i>=0;i--){
            right[i]=right[i+1]|nums[i];
        }
        long long maxor=0;
        for(int i=0;i<n;i++){
            long long newor;
            newor=left[i]|(nums[i]*(1LL<<k))|right[i+1];
            maxor=max(maxor,newor);
        }
        return maxor;
    }
};

2829.k-avoiding数组的最小总和

给你两个整数 n 和 k 。
对于一个由 不同 正整数组成的数组，如果其中不存在任何求和等于 k 的不同元素对，则称其为 k-avoiding 数组。
返回长度为 n 的 k-avoiding 数组的可能的最小总和。

提示：

  • 1 <= n, k <= 50

解题思路

  1. 数组总和最小
    从1开始逐步添加符合条件的数字，直到数组长度达到n
  2. 避免和为k
    尝试加入x时，确保数组中不存在k-x

完整代码

class Solution {
public:
    int minimumSum(int n, int k) {
        vector<int> ans;
        unordered_set<int> used;
        int num=1;
        while(ans.size()<n){
            if(used.find(k-num)==used.end()){
                ans.push_back(num);
                used.insert(num);
            }
            num++;
        }
        return accumulate(ans.begin(),ans.end(),0);
    }
};

2712.使所有字符相等的最小成本

给你一个下标从 0 开始、长度为 n 的二进制字符串 s ，你可以对其执行两种操作：

  • 选中一个下标 i 并且反转从下标 0 到下标 i（包括下标 0 和下标 i ）的所有字符，成本为 i + 1 。
  • 选中一个下标 i 并且反转从下标 i 到下标 n - 1（包括下标 i 和下标 n - 1 ）的所有字符，成本为 n - i 。
    返回使字符串内所有字符 相等 需要的 最小成本 。
    反转字符意味着：如果原来的值是 ‘0’ ，则反转后值变为 ‘1’ ，反之亦然。

提示：

  • 1 <= s.length == n <= 105
  • s[i] 为 ‘0’ 或 ‘1’

解题思路

  1. 所有字符相等
  • 全1
  • 全0
  1. 对于i，反转的成本
  • 反转前缀[0,i]，成本i+1
  • 反转后缀[i,n-1]，成本n-i
  1. 核心问题
    对每个i，求出 min（s全1）和min（s全0），再对二者求min。
    说人话就是：从0开始遍历，如果s[i] ≠ s[i+1]，那么我们此时有两种选择：反转前缀[0,i] 或 反转后缀[i,n-1]。对于每一个这样需要反转的i，我们选择反转前缀还是后缀的原则就是哪个成本小选哪个。最后得到的总成本也必然最小。

👉️难理解的部分：min(i,n-i) 或 min(i+1,n-i-1)。
个人理解是因为对于此算法，实际上的分界点在s[i]和s[i+1]之间。也就是说：修正分界点需要做的是

  • 反转0~i
  • 反转i+1~n-1
    这样求得的min才能保证达到我们“最小成本”的目标。

👉️这里学到一个小知识：s.size()返回的类型为无符号整数（unsigned int）

  • size_t无符号整型 (unsigned)
  1. 是C++标准库中专门用于表示数组、容器的大小或索引的类型
  2. 不能表示负数
  3. 在 64 位系统上，size_t通常是unsigned long，比int更大，可表示更大的范围。
  • int有符号整型 (signed)
  1. 是C++默认的整数类型，可以存储正数、负数和 0。
  2. 取值范围一般是 [-2³¹, 2³¹ - 1]（32位系统） 或 [-2⁶³, 2⁶³ - 1]（64位系统）
    更适合存储一般的计数、索引、数学运算，而size_t主要用于数组大小和内存管理。

完整代码

class Solution {
public:
    long long minimumCost(string s) {
        long long int sum=0;
        int n=s.size();
        for(int i=0;i<n-1;i++){
            if(s[i]!=s[i+1]){
                sum+=min(i+1,n-i-1);
            }
        }
        return sum;
    }
};

11.盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

提示：

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104

解题思路

莫名想起接雨水（？😅一眼做不出来，上题解。

  1. 哪里贪心？
    评论佬的解释：永远找最高和最远的柱子，局部最优推出全局最优。双指针的解法存在遗漏，但对全局最优解无影响。
  2. 双指针的解法本质：缩减搜索空间。
  3. 排除i/j的配对可能性：
  • i和j相遇算法结束；
  • 对于两边指针i、j，如果移动其中一边，那么新的容器h一定 不大于 另一边的柱子高度；
  • 收缩过程中，配对的h较低一方的柱子必定被舍弃所有可能，该位置指针向中间收缩。

完整代码

单看代码理解应该也没问题，这道题知道思路后写起来是无压力的。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left,right;
        left=0;
        right=height.size()-1;
        int ans=0;
        while(left<right){
            int h=height[left]<height[right]?height[left]:height[right];
            ans=max(ans,(right-left)*h);
            if(height[left]<height[right]){
                left++;
            }
            else{
                right--;
            }           
        }
        return ans;
    }
};