2024/11/30 刷题记录

3232. 判断是否可以赢得数字游戏

class Solution {
public:
    bool canAliceWin(vector<int>& nums) {
        int a = 0, b = 0;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] < 10) a+=nums[i];
            else b+=nums[i];
        }
        return a != b;
    }
};

53. 最大子数组和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size());
        int ans = nums[0]; dp[0] = nums[0];
        for(int i = 1; i < nums.size(); i++){
            dp[i] = max(dp[i - 1], 0) + nums[i];
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

56. 合并区间

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int> > ans;
        sort(intervals.begin(), intervals.end());
        for(int i = 0; i < intervals.size(); i++){
            int j = i + 1;
            int now_max = intervals[i][1];
            while(j < intervals.size() && intervals[j][0] <= now_max){
                now_max = max(now_max, intervals[j][1]);
                j++;
            }
            ans.push_back({intervals[i][0], now_max});
            i = j - 1;
        }
        return ans;
    }
};

189. 轮转数组

class Solution {
public:
    oid reverse(vector<int>& nums, int start, int end) {
        while (start < end) {
            swap(nums[start], nums[end]);
            start += 1;
            end -= 1;
        }
    }

    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }
};

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

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> front(nums.size()); front[0] = nums[0];
        vector<int> back(nums.size()); back[nums.size() - 1] = nums[nums.size() - 1];
        for(int i = 1; i < nums.size(); i++){
            front[i] = front[i - 1] * nums[i];
            back[nums.size() - 1 - i] = back[nums.size() - i] * nums[nums.size() - i - 1];
        }
        vector<int> ans;
        for(int i = 0; i < nums.size(); i++){
            int t = 1;
            if(i != 0) t *= front[i - 1];
            if(i != nums.size() - 1) t *= back[i + 1];
            ans.push_back(t);
        }
        return ans;
    }
};