博客

所有的题型目录在下面的链接


LeetCode相关典型题解合集（两百多道题）

一、283. 移动零

思路就是若有0，则就交换相邻两个元素

void moveZeroes(vector<int>& nums) {
        //思路就是两个相邻的元素一次交换
        int j=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]!=0){
                //只有碰到0的时候才有操作
                if(i>j){
                    nums[j]=nums[i];
                    nums[i]=0;
                }
                //碰到0的时候j不加
                j++;
            }
        }
    }

二、566. 重塑矩阵

记住一个重要的知识点：


第x个元素在nums中对应的下标为(x/n, x%n)，n为列数

而在新的重塑矩阵中对应的下标为(x/c,x%c)。c为列数

vector<vector> temp_vector(r,vector ©);

再用vector定义确定行列数的二位数组时，就是这种方式

 vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
        //获取二维数组的行列数
        int raw=nums.size();
        int col=nums[0].size();
        if((raw*col)!=r*c){
            return nums;
        }else{
           //第一种方法：用一个一维数组存储二维数组的映射，这个方法开销有点大
           //第二种方法：第x个元素在nums中对应的下标为(x/n, x%n)，n为列数
           //而在新的重塑矩阵中对应的下标为(x/c,x%c)。c为列数
           vector<vector<int>> temp_vector(r,vector<int> (c));
           for(int i=0;i<raw*col;i++){
               temp_vector[i/c][i%c]=nums[i/col][i%col];
           }
           return temp_vector;
        }
        
    }

三、485. 最大连续 1 的个数

这道题有个陷阱或者说一个隐晦的难点

当数组没有0或者最后没有0的时候的判断

应当计数1次就做一次最大值的判断

 int findMaxConsecutiveOnes(vector<int>& nums) {
        int max=0;
        int count=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==0){
                count=0;
            }else{
                count++;
            }
             max=count>max?count:max;
        }
        return max;
    }

四、240. 搜索二维矩阵 II

//思路：尽可能多的排除掉无关紧要的行和列

//这里从nums[行首][列尾]开始

//当矩阵值大于target的时候，列要–

//当矩阵值小于target的时候，行要++

//注意若没有匹配的情况，返回false

bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int raw=matrix.size();
        int col=matrix[0].size();
        int temp_raw=0;
        int temp_col=col-1;
        while(matrix[temp_raw][temp_col]!=target){
            matrix[temp_raw][temp_col]<target?temp_raw++:temp_col--;
            if(temp_raw>=raw||temp_col<0){
                return false;
            }
        }
        return true;
    }

五、378. 有序矩阵中第 K 小的元素

思路：借鉴二分法

1、 首先找出矩阵中的最大和最小值，在这道题目中最小值是左上角left，最大值是右上角right

2、计算mid=（left+right）/2

3、找到矩阵中小于等于mid的个数记为count

4、判断如果count<k，则说明在left到mid之间的元素少了，这时候需要left=mid+1

5、如果count>=k，则说明在mid到right之间的元素多了，这个时候right=mid

6、循环结束的条件是left=right，返回right

int kthSmallest(vector<vector<int>>& matrix, int k) {
        int raw=matrix.size();
        int col=matrix[0].size();
        int left=matrix[0][0];
        int right=matrix[raw-1][col-1];
        while(left<right){
            int mid=(left+right)/2;
            int count=binary_search(matrix,mid,raw,col);
            if(count<k){
                left=mid+1;
            }else{
                right=mid;
            }
        }
        return right;
    }

    int binary_search(vector<vector<int>>& matrix,int mid,int raw,int col){
        int count=0;
        for(int i=0;i<raw*col;i++){
            if(matrix[i/col][i%col]<=mid){
                count++;
            }
        }
        return count;
    }

六、287. 寻找重复数

这道题目目前有三种方法，代码分别如下


第一种方法：

对数组排序，然后若相邻的又相同的立刻返回就好


第二种方法：

二分法。这道题能用二分就是因为题目中给了n+1个整数的数组，根据抽屉原理（一个萝卜一个坑）。二分法的思路是先猜一个数（有效范围 [left, right]里的中间数 mid），然后统计原始数组中小于等于这个中间数的元素的个数 cnt，如果 cnt 严格大于 mid，分「小于等于」、「严格大于」）。根据抽屉原理，重复元素就在区间 [left, mid] 里；


第三种方法：

快慢指针。可以思考

 int findDuplicate(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int temp;
        for(int i=0;i<nums.size()-1;i++){
            if(nums[i]==nums[i+1]){
                temp=nums[i];
            }
        }
        return temp;
    }

int findDuplicate(vector<int>& nums) {
        //二分法
        int left=1;
        int right=nums.size()-1;
        int count=0;
        while(left<right){
            //每次循环都必须保证count为0
            count=0;
            int mid=(left+right)/2;
            for(int i=0;i<nums.size();i++){
                if(nums[i]<=mid){
                    count++;
                }
            }
            if(count>mid){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return left;
    }

七、645. 错误的集合

注意！本题目有一个非常大的坑，坑了我好久

有一个报错用例是这样的：给了个用例[2,2]

正确输出：[2,1]

错误输出：[1,2]，我之前一直输出的是这个，找半天毛病

注意题目的一句话：

请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回


这句话如果不注意，会出错

解题思路：其实就是数学问题

重复的数字=原数组的和-去掉重复的数据的数组和

重复的数字也可以将数组排序，然后比较相邻两个是否重复来判断

缺失的数字=从1到数组的长度length的数据的和-去掉重复的数据的数组和

vector<int> findErrorNums(vector<int>& nums) {
        vector<int> errorArr;
        sort(nums.begin(),nums.end());
        //找重复的
        for(int i=0;i<nums.size()-1;i++){
            if(nums[i]==nums[i+1]){
               errorArr.push_back(nums[i]);
               nums[i]=0;
               break;
            }
        }
        //找错误的
        //错误的数据=正常数组所有元素的和-去掉重复元素所有数组的和
        int normal_sum=0;
        int error_sum=0;
        for(int i=0;i<nums.size();i++){
            normal_sum+=i+1;
            error_sum+=nums[i];
        } 
        errorArr.push_back(normal_sum-error_sum);
        return errorArr;
    }

八、667. 优美的排列 II

思路一：

反转序列就完事儿了

比如若n=8，有12345678

k=1，不反转

k=2， 1| 8765432

k=3， 18|234567

思路二：

当考虑特殊情况，k=n-1时是有规律的

即有效的构造是[1, n, 2, n-1, 3, n-2, …],k为奇数

有效构造是[n, 1, n-1, 2, n-2, 3, …]，k为偶数

自己写一些就清楚了

 vector<int> constructArray(int n, int k) {
        //创建一个初始数组
        vector<int> arr;
        for(int i=1;i<=n;i++){
            arr.push_back(i);
        }
        //反转数组,注意不仅仅是反转一次
        if(k==1){
            return arr;
        }
        //需要反转k-1次
        for(int i=1;i<k;i++){
            //这一个错误看了半个小时，注意m是i不是k！
            int m=i;
            int n=arr.size()-1;
            while(m<n){
                int temp=arr[m];
                arr[m]=arr[n];
                arr[n]=temp;
                m++;
                n--;
            }
        }
        return arr;
    }

 vector<int> constructArray(int n, int k) {
        vector<int> arr;
        int i=1;
        int j=n;
        while(i<=j){
            if(k==1){
                arr.push_back(i);
                i++;
            }else{
                //当k是偶数的时候，先加大的
                if(k%2==0){
                    arr.push_back(j);
                    j--;
                }else{
                    arr.push_back(i);
                    i++;
                }
                k--;
            }
        }
        return arr;
    }

九、697数组的度

思路：首先用一个哈希表来存储一个数组中出现次数最多的那个元素

其次这道题中的度由出现次数最多的元素 第一次和最后一次出现的位置确定

特例：[1, 2, 2, 3, 1]，由于有这种情况的出现，所以要求第一次和最后一次出现的位置的最小值

int findShortestSubArray(vector<int>& nums) {
        //这道题的思路就是①找频数最大的那个数
        //②找到之后，这个数a的第一个和最后一个相隔的距离
        //一、找频数最大的那个，用hash表实现
        unordered_map<int,int> res;
        int max_count=0;
        for(int i=0;i<nums.size();i++){
            //若key相同则++
            res[nums[i]]++;
            max_count=max_count>res[nums[i]]?max_count:res[nums[i]];
        }
        //二、第一次出现和最后一次出现的距离的最小值
        int min=nums.size();
        for(int i=0;i<nums.size();i++){
            if(res[nums[i]]==max_count){
                for(int j=i;j<nums.size();j++){
                    //这一步的目的是找到第一个重复的元素和最后一个重复的元素，自己思考一下
                    if(nums[i]==nums[j]){
                        res[nums[i]]--;
                    }
                    if(res[nums[i]]==0){
                        min=min<(j-i+1)?min:(j-i+1);
                    }
                }
            }
        }
        return min;
    }

十、766. 托普利茨矩阵

方法一：依次遍历，然后判断其左上角和本身是否相等

 bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        int raw=matrix.size();
        int col=matrix[0].size();
        //注意，是从第二行第二列开始比较的
        for(int i=1;i<raw;i++){
            for(int j=1;j<col;j++){
                if(matrix[i][j]!=matrix[i-1][j-1]){
                    return false;
                }
            }
        }
        return true;
    }

十一、565. Array Nesting

这道题的思路：首先数组中没有重复的元素，所以一直嵌套，结束的条件就是又访问到相同元素时就结束了，然后找到最大的集合

所以说，每个数组的元素只会被访问到一遍，因此我们可以对数组中的元素做标记，当访问到相同的标记时就跳过

int arrayNesting(vector<int>& nums) {
        int max=0;
        for(int i=0;i<nums.size();i++){
            //数组的元素不等于-1说明还没有被访问
            if(nums[i]!=-1){
                int tempA=nums[i];
                int count=0;  //每一次循环都要重新计数
                while(nums[tempA]!=-1){
                    //其实就是双指针的思路
                    count++; //计数一次
                    int tempB=tempA;
                    tempA=nums[tempA];
                    nums[tempB]=-1; //标记访问过的

                }
                max=max>count?max:count;
            }
        }
        return max;
    }

十二、Max Chunks To Make Sorted

思路：这道题看着比较难，但是只要有方法就很简单

当遍历到第i个位置时，如果可以切分为块，那前i个位置的最大值一定等于i。

int maxChunksToSorted(vector<int>& arr) {
        int max=0;
        int count=0;
        for(int i=0;i<arr.size();i++){
            //当遍历到第i个位置时，如果可以切分为块，那前i个位置的最大值一定等于i。
            max=max>arr[i]?max:arr[i];
            if(max==i){
                count++;
            }
        }
        return count;
    }