Day2 用两个栈实现队列+连续子数组的最大和+数组中的逆序对

剑指 Offer 09. 用两个栈实现队列（简单）

简单但没做对，下次需要仔细想一下细节

class CQueue {
    stack<int> stack1,stack2;
public:
    CQueue() {
        while (!stack1.empty()) {
            stack1.pop();
        }
        while (!stack2.empty()) {
            stack2.pop();
        }
    }
    
    void appendTail(int value) {
        stack1.push(value);
    }
    
    int deleteHead() {
        // 如果第二个栈为空
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        } 
        if (stack2.empty()) {
            return -1;
        } else {
            int deleteItem = stack2.top();
            stack2.pop();
            return deleteItem;
        }
    }
};

剑指 Offer 42. 连续子数组的最大和（简单）

简单但没一下想出来

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int sum = 0;
        for(auto it:nums){
            sum = sum > 0?sum+it:it;
            res = max(res,sum);
        }
        return res;

    }
};

剑指 Offer 51. 数组中的逆序对（困难）

不会不会不会 ❗ 这次就只学归并的方法
求逆序对，和数组的大小有关，所以可以边排序边计算个数

class Solution {
public:
    int chat(vector<int>&nums, vector<int>& temp,int l,int r){
        if(l >= r) return 0;
        int mid = l + (r-l)/2;
        int res = chat(nums,temp,l,mid) + chat(nums,temp,mid+1,r);
        for(int k = l; k <= r; k++){
            temp[k] = nums[k]; 
        }
        int i = l;
        int j = mid+1;
        for(int k = l; k <= r; k++){
            if(i == mid+1){nums[k] = temp[j++];}
            else if(j == r+1){nums[k] = temp[i++];}
            else{
                if(temp[i] > temp[j]){
                    nums[k] = temp[j++];
                    res += mid-i+1;
                }else{
                    nums[k] = temp[i++];
                }
            }
        }
        return res;
    }
    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        if(n <= 0) return 0;
        vector<int> temp(n);
        return chat(nums,temp,0,n-1);

    }
};