53. 最大子数组和❌

贪心：不能让“连续和”为负数的时候加上下一个元素（因为直接把前面这一堆和为负数的子串抛弃就回来，后面怎么也会比加上个负数更大），而不是不让“连续和”加上一个负数（加上负数也没事，只要整体还算大）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = 0;
        int res = INT32_MIN;
        for(int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            if(sum > res) res = sum;
            if(sum <= 0) sum = 0;
        }

        return res;
    }
};

ps：回头看一下dp的解法（https://leetcode.cn/problems/maximum-subarray/solutions/9058/dong-tai-gui-hua-fen-zhi-fa-python-dai-ma-java-dai/?envType=study-plan-v2&envId=top-100-liked）

---

56. 合并区间✅

简单模拟 注意右边界如何更新

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        ranges::sort(intervals);

        // for(const auto &interval : intervals) {
        //     for(const auto &num : interval) {
        //         cout << num << " ";
        //     }
        //     cout << endl;
        // }

        int left = intervals[0][0];
        int right = intervals[0][1];
        for(int i = 1; i < intervals.size(); i++) {
            if(intervals[i][0] <= right) { //如果连续
                right = max(right, intervals[i][1]);
            } else {
                res.push_back({left, right});   
                left = intervals[i][0];       
                right = intervals[i][1];
            }
        }
        res.push_back({left, right});

        return res;
    }
};

---

189. 轮转数组✅

简单模拟 稍微算一下

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        vector<int> v(nums);

        for(int i = 0; i < nums.size(); i++) {
            //由化简得到：nums.size() + i - k  < nums.size()
            if(i < k) {
                nums[i] = v[nums.size() + i - k];
            } else {
                nums[i] = v[i - k];
            }
        }

        return ;
    }
};

---

238. 除自身以外数组的乘积✅

本来很简单 可惜题目不让用除法

类比前缀和

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> pre_prod(nums), post_prod(nums), res(nums);
        for(int i = 1; i < nums.size(); i++) { //前缀积
            pre_prod[i] *= pre_prod[i-1];
        }
        for(int i = nums.size() - 2; i >= 0; i--) { //后缀积
            post_prod[i] *= post_prod[i+1];
        }
        // for(const auto &i : pre_prod) {
        //     cout << i << " ";
        // }
        // cout << endl;
        // for(const auto &i : post_prod) {
        //     cout << i << " ";
        // }
        // cout << endl;
        res[0] = post_prod[1];
        res[nums.size() - 1] = pre_prod[nums.size() - 2];
        for(int i = 1; i < nums.size() - 1; i++) {
            res[i] = pre_prod[i-1] * post_prod[i+1];
        }
        // for(const auto &i : res) {
        //     cout << i << " ";
        // }

        return res;
    }
};

---

41. 缺失的第一个正数✅

不合理Solution1：二分 + 细节（不过题意应该是不让直接调用排序函数的）

合理Solution2：飞机对号入座问题 原地哈希桶排序（https://leetcode.cn/problems/first-missing-positive/solutions/304894/zhao-zuo-wei-de-gu-shi-onyuan-di-jie-fa-by-java_le/?envType=study-plan-v2&envId=top-100-liked）

class Solution1 {
public:
    int firstMissingPositive(vector<int>& nums) {
        ranges::sort(nums);

        int left = 0, right = nums.size() - 1;
        int mid = 0;
        while(left <= right) { //二分查找第一个正数索引
            mid = (left + right) / 2;
            if(nums[mid] > 0) {
                right = mid - 1;
            }
            else if(nums[mid] < 0) {
                left = mid + 1;
            }
            else {
                break;
            }
        }

        int p = mid;
        while(nums[p] <= 0 && p < nums.size() - 1) p++;

        if(nums[p] != 1) return 1;
        for(int i = p; i < nums.size() - 1; i++) {
            if(nums[i] == nums[i+1]) continue;
            if(nums[i] + 1 != nums[i+1]) return nums[i] + 1;
        }
        return nums[nums.size() - 1] + 1;
    }
};

class Solution2 {
public:
    int firstMissingPositive(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] < 0 || nums[i] > nums.size()) nums[i] = 0;
        }

        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] && nums[i] != i + 1) { //如果坐错了位置
                int tmp = nums[i]; //坐错的人先站一边去
                nums[i] = 0; //那么位置就空了
                while(nums[tmp - 1] != tmp) { //去找属于自己的位置
                    if(!nums[tmp - 1]) {
                        nums[tmp - 1] = tmp; //正确的位置是空的 直接坐下
                    } else { //已经有人了
                        int ta = nums[tmp - 1]; //让他离开
                        nums[tmp - 1] = tmp; //tmp坐下
                        tmp = ta; //ta变成新的tmp 去找正确的座位
                    }
                }
            }
        }
        int i = 0;
        for(i = 0; i < nums.size() && nums[i]; i++);  
        //i号位置是空的 说明i+1号乘客不在
        //如果每个人都坐对了 那么返回nums.size()+1 符合题意
        return i + 1;
    }
};