代码随想录题单|数组

数组理论基础 | 代码随想录

一、暴力

顺序查找/多层循环/简单模拟/快速排序

二、二分查找

704. 二分查找 – 力扣（LeetCode）

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.size()<=0) return nums.size();
        // 二分查找
        int left=0;
        int right=nums.size()-1;
        while(left<=right){
            int mid=left+((right-left)>>1);
            if(nums[mid]==target) return mid;
            else if(nums[mid]<target) left=mid+1;
            else right=mid-1;
        }
        return -1;
    }
};

35. 搜索插入位置 – 力扣（LeetCode）

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if(nums.size()<=0) return nums.size();
        // 二分查找
        int left=0;
        int right=nums.size()-1;
        while(left<=right){
            int mid=left+((right-left)>>1);
            if(nums[mid]==target) return mid;
            else if(nums[mid]<target) left=mid+1;
            else right=mid-1;
        }
        return left;
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置 – 力扣（LeetCode）

69. x 的平方根 – 力扣（LeetCode）

367. 有效的完全平方数 – 力扣（LeetCode）

三、双指针

27. 移除元素 – 力扣（LeetCode）

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        if(nums.size()<=0) return nums.size();
        // 前后双指针
        int left=0;
        int right=0;
        while(right<nums.size()){
            if(nums[right]!=val){
                nums[left++]=nums[right];
            }
            ++right;
        }
        return left;
    }
};

26. 删除有序数组中的重复项 – 力扣（LeetCode）

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()<=1) return nums.size();
        // 前后双指针
        int left=0;
        int right=1;
        while(right<nums.size()){
            if(nums[left]!=nums[right]){
                nums[++left]=nums[right];
            }
            ++right;
        }
        return left+1;
    }
};

283. 移动零 – 力扣（LeetCode）

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        if(nums.size()<=1) return;
        // 将非0元素前移
        // 前后双指针
        int left=0;
        int right=0;
        while(right<nums.size()){
            if(nums[right]!=0){
                nums[left++]=nums[right];
            }
            ++right;
        }
        // 后续元素置为0
        while(left<nums.size()){
            nums[left++]=0;
        }
        return;
    }
};

844. 比较含退格的字符串 – 力扣（LeetCode）

977. 有序数组的平方 – 力扣（LeetCode）

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        if(nums.size()==0) return nums;
        vector<int> result(nums.size());
        // 相向双指针
        int left=0;
        int right=nums.size()-1;
        for(int i=nums.size()-1;i>=0;--i){
            int leftSq=pow(nums[left],2);
            int rightSq=pow(nums[right],2);
            if(leftSq>rightSq){
                result[i]=leftSq;
                ++left;
            }else{
                result[i]=rightSq;
                --right;
            }
        }
        return result;
    }
};

四、滑动窗口

209. 长度最小的子数组 – 力扣（LeetCode）

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int minLen=INT_MAX;
        // 滑动窗口双指针
        int left=0;
        int right=0;
        int curSum=0;
        while(right<nums.size()){
            curSum+=nums[right];
            while(curSum>=target){
                minLen=min(minLen,right-left+1);
                curSum-=nums[left++];
            }
            ++right;
        }
        return minLen==INT_MAX?0:minLen;
    }
};

904. 水果成篮 – 力扣（LeetCode）

76. 最小覆盖子串 – 力扣（LeetCode）

五、矩阵

59. 螺旋矩阵 II – 力扣（LeetCode）

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> result(n,vector<int>(n));
        // 模拟
        int north=0,south=n-1;
        int west=0,east=n-1;
        int elem=1;
        while(elem<=n*n){
            // 北边界 自西向东
            for(int j=west;j<=east && elem<=n*n;++j){
                result[north][j]=elem++;
            }
            ++north;
            // 东边界 自北向南
            for(int i=north;i<=south && elem<=n*n;++i){
                result[i][east]=elem++;
            }
            --east;
            // 南边界 自东向西
            for(int j=east;j>=west && elem<=n*n;--j){
                result[south][j]=elem++;
            }
            --south;
            // 西边界 自南向北
            for(int i=south;i>=north && elem<=n*n;--i){
                result[i][west]=elem++;
            }
            ++west;
        }
        return result;
    }
};

54. 螺旋矩阵 – 力扣（LeetCode）

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int row=matrix.size();
        int col=matrix[0].size();
        vector<int> result(row*col);
        // 模拟
        int north=0,south=row-1;
        int west=0,east=col-1;
        int idx=0;
        while(idx<=result.size()-1){
            // 北边界 自西向东
            for(int j=west;j<=east 
            && idx<=result.size()-1;++j){
                result[idx++]=matrix[north][j];
            }
            ++north;
            // 东边界 自北向南
            for(int i=north;i<=south
            && idx<=result.size()-1;++i){
                result[idx++]=matrix[i][east];
            }
            --east;
            // 南边界 自东向西
            for(int j=east;j>=west
            && idx<=result.size()-1;--j){
                result[idx++]=matrix[south][j];
            }
            --south;
            // 西边界 自南向北
            for(int i=south;i>=north
            && idx<=result.size()-1;--i){
                result[idx++]=matrix[i][west];
            }
            ++west;
        }
        return result;
    }
};

六、预处理

58. 区间和（第九期模拟笔试）

44. 开发商购买土地（第五期模拟笔试）