力扣初级算法(数组篇)_力扣 初级算法 答案

个人觉得这个模块还是很不错的，适合像我一样初学算法的童鞋入门，我一般使用c++做题的(c和java也会 )
下面会简单介绍一下我的对每个题目的想法，之后可能会录制讲解视频放到B站供童鞋们参考！

• 删除排序数组中的重复项
  给出一个升序数组，用O(1)的空间复杂度实现求得数组去重后数组，数组去重的话时间复杂度比较高，代价太大，因此需要换一种思考方向，那么我们可以从前往后覆盖这个数组，看下面的例子：

给定 nums = [0,0,1,1,1,2,2,3,3,4]
首先我们需要设定一个变量用来记录去重后数组的长度，我们从下标为1处开始，比较前一个数是否与当前的数相等，如果相等的话，就判断下一个，直到找到不相等的时候，然后让去重的数组的长度加1，并且把这个未出现过的值添加到去重的数组里

对于下标为0的值首先添加到去重数组，长度加1，然后再往后判断，0与0相等，然后判断下一个，1与0不相等，那么将1添加到去重数组…依次类推就可以得到正确答案：0 1 2 3 4

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int sum = 0;
        for(int i = 0; i < nums.size(); i++)
            if(i == 0 || nums[i] != nums[i-1]) nums[sum++]=nums[i];
        return sum;
    }
};
1
2
3
4
5
6
7
8
9

• 买卖股票的最佳时机 II
  直接比较相邻两个数大小即可，如果后面的值大于前面的值，那么就是累加差值，这个有点贪心的思想在里面，看下面的例子：
  [7,1,5,3,6,4]
  第一天与第二天比较发现第二天跌价了，那第一天就肯定不能买入呀。第二天与第三天比较发现可以盈利，那么就第二天买入，第三天卖出。第三天再与第四天进行比较，跌价了，不能购买…依次类推，得到正确答案：7

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sum = 0;
        for(int i = 1; i < prices.size(); i++)
            if(prices[i] > prices[i-1]) sum += prices[i] - prices[i-1];
        return sum;
    }
};
1
2
3
4
5
6
7
8
9

• 旋转数组
  这道题目的做法也是挺多的，我推荐一种就是直接使用stl中的reverse函数，直接进行三次反转即可！看具体例子：
  [1,2,3,4,5,6,7] 和 k = 3
  先把整个数组反转得到：
  [7,6,5,4,3,2,1]
  然后再把前k个再进行反转得到：
  [5,6,7,4,3,2,1]
  最后再把剩下的再反转一下就可以得到正确答案：
  [5,6,7,1,2,3,4]

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums.begin(),nums.end());
        reverse(nums.begin(),nums.begin()+k);
        reverse(nums.begin()+k,nums.end());
    }
};
1
2
3
4
5
6
7
8
9

• 存在重复元素
  使用sort函数排序(c的童鞋可以用qsort，java可以使用ArrayList中的sort，或者可以参考我之前写过的快排)，然后判断相邻元素是否相等，如果相等的话，直接返回true，如果遍历完都没有相等的元素，那么则返回false

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
       sort(nums.begin(),nums.end());
       for(int i = 1; i < nums.size(); i++){
           if(nums[i-1] == nums[i]) return true;
       }
       return false;
    }
};
1
2
3
4
5
6
7
8
9
10

• 只出现一次的数字
  这道题目我当时想的是sort(虽然看到了线性时间！！！)之后进行加减运算，果然RE了…思考良久呀，位运算中的异或的话可以让相等的元素为0，而且还具有交换律(那么做这个题目就很舒服)，所以！！！直接用一个初值为0的遍历与每个元素进行异或运算即可，得到的最后结果就是唯一的那个元素。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int num=0;
        for(int i : nums) num ^= i;
        return num;
    }
};
1
2
3
4
5
6
7
8

• 两个数组的交集 II
  很明显需要先排序，不然只能暴力遍历了，先给两个数组从小到大排序，然后双指针同时遍历两个数组，将相等的数值找出来即可。

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> nums3;
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        for(int i=0,j=0;i<nums1.size()&&j<nums2.size();){
            if(nums1[i]==nums2[j]){
                nums3.push_back(nums1[i]);
                i++;
                j++;
            }else if(nums1[i]>nums2[j]){
                j++;
            }else{
                i++;
            }
        }
        return nums3;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 加一
  这个题目可以看做就是大数相加的简单版本，这里是一个大正整数加1，为了防止进位带来的影响，我们先让数组反转，然后让下标为0的数与1相加，设置一个变量记录是否发生进位。最后将数组再反转一下即可~

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        reverse(digits.begin(),digits.end());
        int tmp=0;
        digits[0]++;
        for(int i=0;i<digits.size();i++){
            digits[i] += tmp;
            tmp = digits[i] /10;
            digits[i] %= 10;
        }
        if(tmp) digits.push_back(tmp);
        reverse(digits.begin(),digits.end());
        return digits;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 移动零
  利用双指针，一个j记录最前面0的位置，一个i用来遍历数组，如果当前位置的数值是0的话，那么j不做处理，然后i++；如果数值不是0的话，那么就与之前的0进行位置交换，如果之前没有0的话，那么指针j就会与i相等，不需要进行位置交换,这里也要记得移动指针j哦。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
       for(int i=0,j=0;i<nums.size();i++){
           if(nums[i]){
               if(i!=j) swap(nums[j],nums[i]);
               j++;
           }
       }
    }
};
1
2
3
4
5
6
7
8
9
10
11

• 两数之和
  这个题目使用双指针肯定快一点，先把数组从小到大排序，一个指针从前往后指，一个指针从后往前指。如果当前数值和大于给定的数值，那么后面的指针往前移动，相反则前面的指针往后移动，当两个指针重合时结束查找或者给定的值和两个数值的和相等。还有需要注意一点的就是：排序之后下标就乱了，因此我们需要复制一个未排序的数组，找到等值的数值后，遍历复制出来的数组，查找下标。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        vector<int> temp;
        temp=nums;
        int n=temp.size();
       sort(temp.begin(),temp.end());
       int i=0,j=n-1;
       while(i<j){  
           if(temp[i]+temp[j]>target)j--;
          else if(temp[i]+temp[j]<target)i++;
          else break; 
       }
       if(i<j){
             for(int k=0;k<n;k++){
                if(i<n&&nums[k]==temp[i]){
                    ans.push_back(k);
                    i=n;
                }
                else if(j<n&&nums[k]==temp[j]){
                    ans.push_back(k);
                    j=n;
                }
                 if(i==n&&j==n)return ans;
            }
         }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

• 有效的数独
  这题目直接模拟就行，看着简单，但是如果思路不明确的话，会写到让人奔溃的，我认为最简单的方式就是设置3个二维数组，然后记录9对应9个点出现的次数，如果有一个点在规定范围出现了2次，那么直接返回false,遍历完图之后，直接返回true即可。

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int row[9][9] ={};
        int col[9][9] ={};
        int block[9][9] ={};
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] != '.'){
                    if(row[i][board[i][j]-'1']++) return false;
                    else if(col[j][board[i][j]-'1']++) return false;
                    else if(block[(i/3)*3+j/3][board[i][j]-'1']++) return false;
                }
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 旋转图像
  好多童鞋之前肯定接触过这个题目，但是我估计大多数的人一般都是借助另一个数组做的，但是这个题目要求了不能借助其他数组，所以，我们只能在这个数组上进行操作。对于n*n的矩阵，先来看外层，外层的话就是由4个（n-1）个数组组合而成的。顺时针旋转的话，只需要更改（n-1）个数组的位置即可，我们设置一个变量用来存放一个点，然后让其他三个点一次覆盖，最后一个点的话就是变量存的值，然后直接赋值的话就完成了4个方向一个点的变化，然后我们再旋转其他的点，旋转（n-1）次就完成了外层的旋转，相邻的内层比外层的层数少2，根据这个规律的话添加一层循环既可以完成整个矩阵的旋转！

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int cycle = matrix.size() / 2, len = matrix.size(), tmp,t;
        for(int i = 0; i < cycle; i++){
            for(int j = i; j < len - 1 - i; j++){
                tmp = matrix[i][j];
                matrix[i][j] = matrix[len - 1 -j][i];
                t = matrix[j][len - 1 - i];
                matrix[j][len - 1 - i] = tmp;
                tmp = matrix[len - 1 - i][len - 1 -j];
                matrix[len - 1 - i][len - 1 - j] = t;
                matrix[len - 1 - j][i] = tmp;
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

总结

这些题目看着简单，但是题目给出了一些限制条件，我们平时使用的方法可能就被限制了，需要我们拓展思维，思考其他的方法来解决问题！