LeetCode刷题之数组复习

由于以后会从事嵌入式，所以这些题打算全部用C语言来完成。

第一题：从排序数组中删除重复项。

示例：

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。

来源：点击这里

做数组题一定优先考虑双指针法

答案：这里虽然没使用指针，但是思想是一样的，使用的是数值下标

int removeDuplicates(int* nums, int numsSize){
    if (numsSize==0) return 0;
    int length =0;
    for (int i=0;i<numsSize;i++){
        if (nums[i]!=nums[length]){
            nums[++length]=nums[i];
        }
    }
    return length+1;
}

第二题：买卖股票的最佳时机 II

示例：

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

来源：点击这里

答案：这道题要重点要理解：当明天的价格高于今天就今天买明天卖，这样就能获得最高利润，理解了这点，就能顺利写出代码

int maxProfit(int* prices, int pricesSize){
    int profit = 0;
   
    for (int i=0; i<pricesSize-1;i++){
        if (prices[i]<prices[i+1]){
            profit += prices[i+1]-prices[i];
        }
    }
    return profit;

}

第三题：旋转数组

示例：

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

来源：点击这里

答案：

第一种解法，暴力求解，这道题其实跟冒泡排序很相似，每次都把最后一个数移动到第一个位置，所以我先用暴力求解。但是时间复杂度为O(kn)，超出LeetCode时间限制。

void rotate(int* nums, int numsSize, int k){
    for (int i=0;i<k;i++){
        for (int j=numsSize-1; j>0;j--){
            int temp = nums[j];
            nums[j] = nums[j-1];
            nums[j-1] = temp;
        }
    }
    return 0;
}

第二种解法,三次反转法，该方法较为实用需掌握。经过三次反转后，即可得到目的数组

原始数组                  : 1 2 3 4 5 6 7
反转所有数字后             : 7 6 5 4 3 2 1
反转前 k 个数字后          : 5 6 7 4 3 2 1
反转后 n-k 个数字后        : 5 6 7 1 2 3 4 --> 结果

答案：此处采用C语言过于繁琐，因此采用C++,直接调用反转函数即可

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int length=size(nums);
        k%=size(nums);
        reverse(&nums[0],&nums[length]);
        reverse(&nums[0],&nums[k]);
        reverse(&nums[k],&nums[length]);
    }
};

第四题：存在重复

示例：

输入: [1,2,3,1]
输出: true

输入: [1,2,3,4]
输出: false

来源：点击这里

答案：这道题首先用C语言想到的是暴力求解，一个两层循环，但是LeetCode上超出时间限制。后面想到先将数组排序，然后挨个比较，于是采用C++，使用sort()函数排序

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;
    }
};

第五题：只出现一次的数字

示例：

输入: [4,1,2,1,2]
输出: 4

来源：点击这里

答案：这道题我的第一反应就是将其排序，因为一定有一个非重复元素，而其他均只出现两次。因此可以让下标每次都跳两格。如果i和i+1相等就跳两格。如果不相等，那肯定i就是那个单独的数。一直循环到数组中倒数第三个元素（倒数第三个会和倒数第二个进行比较）如果还是没找到。则数组中最后那个值一定是单独数。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        for (int i=0;i<nums.size()-1;){
            if (nums[i]==nums[i+1]){
                i=i+2;               
            }else return nums[i];
        }
        return nums.back();
    }
};

第六题：两个数组的交集 II

示例：

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]

来源：点击这里

答案:这道题比较简单，排序后两两比较，小的那个往后移动，如果相等就都往下移，并且把数值存入数组中

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
         vector<int> sum;
        int i=0,j=0;
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());while (i<nums1.size() && j<nums2.size()){
            if (nums1[i] > nums2[j]){
            j++;
        }else if (nums1[i] < nums2[j]){
            i++;
        }else {
            sum.push_back(nums1[i]);
            i++;
            j++;
        }   
        }
        return sum;
    }
};

第七题：移动零

示例：

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

来源：点击这里

答案：简单，使用双指针法即可

void moveZeroes(int* nums, int numsSize){
    int j=0;
    for (int i=0;i<numsSize;i++){
            if (nums[i] != 0){
                nums[j] = nums[i];
                if(i!=j) nums[i]=0;
                j++;
            }
        }
}

第八题：两数之和

示例：

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

来源：点击这里

答案：暴力遍历，简单；

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
         int i,j;
        for(i=0;i<nums.size();++i){
            for(j=i+1;j<nums.size();++j){
                if(nums[i]+nums[j]==target){
                    return {i,j};
                }
            }
        }
        return {i,j};
    }
};

第九题：

示例：

来源：点击这里

答案

第十题：

示例：

来源：点击这里

答案

LeetCode刷题之数组复习

推荐阅读