1. 数组

LeetCode.704.二分查找

// 左边界匹配由int/2的性质确保
// 右边界的匹配需要由 l <= r确保
// 更新左右的时候都需要移动
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        while(l <= r){
            int m = (l + r)/2;
            if(target < nums[m]) r = m - 1;
            if(target > nums[m]) l = m + 1;
            if(target == nums[m]) return m;
        }
        return -1;
    }
};

LeetCode.27.移除元素

// 题解用双指针原地交换
// 我直接从后向前删了
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        for(int i = nums.size()-1;i >= 0;i--){
            if(nums[i] == val){
                nums.erase(nums.begin()+i);
            }
        }
        return nums.size();
    }
};

// 原地交换
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int l = 0, r = 0;
        while(r < nums.size()){
            if(nums[l] == val){
                if(nums[r] == val){
                    r++;
                }else{
                    int t = nums[l];
                    nums[l] = nums[r];
                    nums[r] = t;
                    r++;
                    l++;
                }
            }else{
                l++;
                r++;
            }
        }
        return l;
    }
};

LeetCode.209.长度最小的子数组

// 区间问题
// 先统计答案
// 再更新当前和
// 最后变更边界
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int l = 0, r = 0, summ = 0, anss = INT_MAX;
        while(r < nums.size()){
            summ += nums[r];
            while(summ >= target){
                anss = min(anss, r-l+1);
                summ -= nums[l];
                l++;
            }
            r++;
        }
        return anss == INT_MAX?0:anss;
    }
};

LeetCode.59.螺旋数组

// 纯模拟
// 第四步的时候记得x,y都到迭代
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> v(n, vector<int>(n));
        int summ = 0;
        int x = 0,y = 0;
        for(int i = 1;i <= 2*n-1;i++) {
            int m = i % 4;
            int t_now = i/4;
            if(m == 1) {    // 左到右
                for(int j = y;j <= n-t_now-2;j++) v[x][j] = ++summ;
                y = n-t_now-1;
            }else if(m == 2) {  // 上到下
                for(int j = x;j<=n-t_now-2;j++) v[j][y] = ++summ;
                x = n-t_now-1;
            }else if (m == 3) { // 右到左
                for(int j = n-t_now-1;j>=t_now+1;j--) v[x][j] = ++summ;
                y = t_now;
            }else { // 下到上
                for(int j = n-t_now;j>=t_now;j--) v[j][y] = ++summ;
                x = t_now;
                y = t_now;
            }
        }
        v[x][y] = ++summ;
        return v;
        }
};

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int sx = 0, sy = 0, cnt = 0;
        vector<vector<int>> matrix(n, vector<int>(n));
        int now = 0;
        while(cnt < n/2+1){
            cnt++;
            for(int i = 1;i <= 4;i++){
                int m = i%4;
                if(m == 1){
                    int x = sx;
                    for(int y = sy;y < n-cnt;y++){
                        matrix[x][y] = ++now;
                    }
                    sy = n-cnt;
                }
                if(m == 2){
                    int y = sy;
                    for(int x = sx;x < n-cnt;x++){
                        matrix[x][y] = ++now;
                    }
                    sx = n-cnt;
                }
                if(m == 3){
                    int x = sx;
                    for(int y = sy;y > cnt-1;y--){
                        matrix[x][y] = ++now;
                    }
                    sy = cnt-1;
                }
                if(m == 0){
                    int y = sy;
                    for(int x = sx;x > cnt-1;x--){
                        matrix[x][y] = ++now;
                    }
                    sx = cnt;
                    sy = cnt;
                }
            }
        }
        if(n%2 == 1){
            matrix[n/2][n/2] = ++now;
        }
        return matrix;
    }
};