1. 数组

LeetCode.704.二分查找

二分问题，在单调的序列上找值，不断与中间值nums[m]比较，更新区间。target在nums[m]右侧，左区间更新；target在nums[m]左侧, 右区间更新。

// 左边界匹配由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.移除元素

区间内删除target，如果不需要交换的话，就直接扫一遍统计就可以了。交换的情况下，需要在右侧不断找到nums[i] != target的点来交换。

双指针

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int l = 0, r = n-1;
        while(l <= r){
            if(nums[l] == val && nums[r] != val){
                int t = nums[l]; nums[l] = nums[r]; nums[r] = t;
            }
            if(nums[l] != val) l++;
            if(nums[r] == val) r--;
        }
        return l;
    }
};

从后向前删除

// 题解用双指针原地交换
// 我直接从后向前删了
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.977.有序数组的平方

双指针，谁的平方大就谁先插入到数组尾。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> anss(nums.size());
        int a = nums.size()-1;
        int l = 0, r = nums.size()-1;
        while(l <= r){
            if(nums[l] * nums[l] > nums[r] * nums[r]){
                anss[a--] = nums[l] * nums[l];
                l++;
            }else{
                anss[a--] = nums[r] * nums[r];
                r--;
            }
        }
        return anss;

    }
};

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

这里的每个值都>0，所以左边界向右一定会减小总和，右边界向右一定会增大总和，扫描一遍即可。

// 区间问题
// 先统计答案
// 再更新当前和
// 最后变更边界
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;
    }
};