10.数组

88. 合并两个有序数组

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
       int left = m-1,right = n-1;
       int sum = m + n - 1;
       while(left >= 0 || right >= 0){
           if(left < 0){
               nums1[sum--]=nums2[right--];
           }else if(right < 0){
               nums1[sum--]=nums1[left--];
           }else if(nums1[left]>nums2[right]){
               nums1[sum--]=nums1[left--];
           }else {
               nums1[sum--]=nums2[right--];
           }
       }
    }
};

26. 删除排序数组中的重复项

题解

class Solution {
public:
        int removeDuplicates(vector<int> &nums) {
        if (nums.empty()) { return 0; }
        int k = 0;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] != nums[k]) {
                k++;
                nums[k] = nums[i];
            }
        }
        return k + 1;
    }
};

303. 区域和检索 - 数组不可变

class NumArray {
public:
    vector<int> sum;
    NumArray(vector<int> &nums) {
        sum = vector<int>(nums.size() + 1);
        for (int i = 0; i < nums.size(); i++) {
            //前缀和 预处理 都计算出来。
            sum[i + 1] = sum[i] + nums[i];
        }
    }
    int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
};

304. 二维区域和检索 - 矩阵不可变

class NumMatrix {
public:
    vector<vector<int>> sum;
    NumMatrix(vector<vector<int>> &matrix) {
        if(matrix.size()==0){
            return;
        }
        int M = matrix.size();
        // if(M > 0){
        int N = matrix[0].size();
        sum = vector<vector<int>>(M, vector<int>(N + 1));
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                sum[i][j + 1] = sum[i][j] + matrix[i][j];
            }
        }
      }
    // }
    int sumRegion(int row1, int col1, int row2, int col2) {
        int ans = 0;
        for (int row = row1; row <= row2; row++) {
            ans += sum[row][col2 + 1] - sum[row][col1];
        }
        return ans;
    }
};