【力扣篇一】数组30道题汇总(1)-阿里云开发者社区

前言

（12月5日）突然想起了很久以前别人（具体来源已经记不清了）传给我的一套题单。网上的题单不少，光收藏可不行，关键还得下手。

这套题单的题目数量为300出头，什么时候刷完我还没有明确计划，但我必定会持续更新（刷题）！小伙伴们如果一起，也可以交流。本文是题单的第一部分——数组，有30道题。

刚开始刷的时候，我的策略是“速度为上”，尽量快点通过避免过多优化代码的质量 （可读性、效率等），打算后面会对代码进行重构。为了快点刷，这次代码基本没写注释（但这可能不是个好习惯）。

先从简单的题目开始刷，积累信心，养成刷题的习惯，然后再慢慢地向难题突破。

小结

12月8日刷完了第一部分——数组，算是成功踏出了第一步。这三十道题大多是力扣中的“简单”和“中等”难度，想不出来时还可以看力扣的题解（独立思考很重要，同时也要兼顾效率，做好平衡），刷题体验较好。第一部分的成功完成也确实给我自己积累了一些信心，觉得自己可以继续走下去了。

令我印象比较深刻的一点是，力扣老喜欢 “原地算法”，即要求仅使用常量级的额外空间完成对数组的操作，这样的要求会给题目带来一些额外的难度。常用的一个方法是对输入或输出数组进行改造，给我们提供操作空间。

题单简介

是不是有许多小伙伴在刷力扣的时候感觉无从下手？从头按顺序开始刷的童鞋们可能会比较有感触，为什么才第四题就感觉很难了?没关系，本文将对力扣的 1-700 题中不需要会员的数据结构与算法题目(数据库与 shell 除外)进行分类，并推荐一个刷题的顺序。

完全零基础可以刷题吗？

不能，至少要基本掌握一门计算机语言的语法。但现在在网上随便搜一下就能搜到许多关于计算机语言的教程。当然，最好还是上一下正规的课程。

刷题顺序很重要吗？

重要。按照题目类别结构化地刷题的速度不仅更快，而且可以在刷完一类题之后进行总结。对于水平较高的小伙伴们来说，按照推荐的顺序刷，可以在 200 小时内刷完 500 多题。对于萌新们来说，按照推荐顺序刷，能更好地掌握数据结构与算法基础。

题单

分类	题目列表
数组的遍历	485，495，41，628
统计数组中的元素	645、697、448、442、41、274

数组的改变、移动	453、665、283
二维数组及滚动数组	118、119、661、598、419
数组的旋转	189、396

特定顺序遍历二维数组	54、59、498
二维数组变换	566、48、73、289
前缀和数组	303、304、238

数组的遍历

485. 最大连续 1 的个数 | 很久以前

//首次通过
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int count = 0;
        int countMax = 0;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] == 1) {
                count ++;
            }
            else {
                count = 0;
            }
            if(count > countMax){
                countMax = count;
            }
        }
        return countMax;
    }
};

495. 提莫攻击 | 很久以前

//首次通过
#include<cstdio>
class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int tLast = timeSeries[timeSeries.size() - 1] + duration;
        int len = timeSeries.size();
        int count = 0;
        int iTS = 0;
        for(int i = 0; i < len - 1; i++){
            int mid = timeSeries[i+1] - timeSeries[i];
            int addT = duration < mid ? duration : mid;
            count += addT;
        }
        count += duration;
        return count;
    }
};

414. 第三大的数 | 2022-12-5

//首次通过
#include<climits>
class Solution {
public:
    int thirdMax(vector<int>& nums) {
        int limitMin = INT_MIN;
        int maxs[3] = {limitMin, limitMin, limitMin};
        int count = 0;
        bool showMin = 0;
        for(auto num : nums){
            if(num == limitMin){
                showMin = 1;
            }
            bool equl = 0;
            for(int i = 0; i < 3; i++){
                if(num == maxs[i]){
                    equl = 1;
                }
            }
            if(equl == 1){
                continue;
            }
            if(num > maxs[2]){
                maxs[2] = num;
                count += 1;
            }
            int t = 0;
            if(maxs[0] < maxs[1]){
                t = maxs[0];  maxs[0] = maxs[1];  maxs[1] = t;
            }
            if(maxs[1] < maxs[2]){
                t = maxs[1];  maxs[1] = maxs[2];  maxs[2] = t;
            }
            if(maxs[0] < maxs[1]){
                t = maxs[0];  maxs[0] = maxs[1];  maxs[1] = t;
            }
        }
        int result = 0;
        if(showMin == 1 && count == 2){
            result = maxs[2];
        }
        else if(maxs[2] == limitMin){
            result = maxs[0];
        }
        else {
            result = maxs[2];
        }
        return result;
    }
};

628. 三个数的最大乘积 | 2022-12-6

想起了我们高数老师讲求函数的最值的时候，把所有可能的位置（极值和端点值）都列出来再进行比较就好了。

//首次通过
//56ms, 击败7.60%
#include<algorithm>
#include<cstdio>
using namespace std;
class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        int numsSize = nums.size();
        int result = 0;
        int indexMid = -1;  //正负数交界处
        bool zeroShow = false;
        sort(nums.rbegin(), nums.rend());
        if(numsSize == 3){
            result = nums[0] * nums[1] * nums[2];
        }
        else{
            for(int i = 0; i <= numsSize-2; i++){
                if(nums[i] >= 0 && nums[i+1] < 0){
                    indexMid = i;
                    cout << nums[i] << endl;
                    break;
                }
            }
            vector<int> ts;
            if(nums[2] > 0){
                int t1 = nums[0] * nums[1] * nums[2];
                ts.push_back(t1);
            }
            if(nums[0] > 0 && nums[numsSize-2] < 0){
                int t2 = nums[0] * nums[numsSize-2] * nums[numsSize-1];
                ts.push_back(t2);
            }
            if(nums[1] > 0 && nums[numsSize-1] < 0){
                int t3 = nums[0] * nums[1] * nums[indexMid+1];
                ts.push_back(t3);
            }
            if(nums[numsSize-3] < 0){
                int t4 = nums[indexMid+1] * nums[indexMid+2] * nums[indexMid+3]; 
                ts.push_back(t4);
            }
            for(auto num : nums){
                if(num == 0){
                    zeroShow = true;
                }
            }
            if(zeroShow){
                ts.push_back(0);
            }
            result = *max_element(ts.begin(),ts.end()); 
        }
        return result;
    }
};

统计数组中的元素

645. 错误的集合 | 2022-12-6

借用了“桶排序”时的思路。

//首次通过
//28ms，击败71.37%
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int nSize = nums.size();
        vector<int> result;
        vector<bool> a(nSize+1, false);
        for(auto num : nums){
            if(a[num] == false){
                a[num] = true;
            }
            else{
                result.push_back(num);
            }
        }
        for(int i = 1; i <= nSize; i++){
            if(a[i] == false){
                result.push_back(i);
            }
        }
        return result;
    }
};

697. 数组的度 | 2022-12-6

对C++的语法不熟，写这个题时百度了好多次。此外，发现哈希表确实挺好用的。

//首次通过
//124ms，击败13.23%
#include<unordered_map>
using namespace std;
class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        int nSize = nums.size();
        unordered_map<int, int> hash;  //统计频数
        for(auto num : nums){
            if(hash.count(num) == 0){
                hash[num] = 0;
            }
            hash[num] += 1;
        }
        int maxCount = 0;  //最大频数
        for(auto p : hash){
            if(p.second > maxCount){
                maxCount = p.second;
            }
        }
        vector<int> maxNum;  //频数最大的数
        for(auto p: hash){
            if(p.second == maxCount){
                maxNum.push_back(p.first);
            }
        }
        vector<int> diff;  //可能的子数组长度
        for(auto n : maxNum){
            int lIndex = find(nums.begin(), nums.end(), n) - nums.begin();  //find()的返回值不是int，但相减之后是
            int rIndex = nSize - 1 - (find(nums.rbegin(), nums.rend(), n) - nums.rbegin());
            cout << lIndex << ' ' << rIndex << endl;
            diff.push_back(rIndex - lIndex + 1);
        }
        int result = *min_element(diff.begin(), diff.end());
        return result;
    }
};

448. 找到所有数组中消失的数字 | 2022-12-6

力扣题解中一招“原地修改”确实秀到我了，不得不说差距客观存在，而且很大。

//首次通过
//96ms，击败12.45%
#include<unordered_map>
using namespace std;
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int nSize = nums.size();
        unordered_map<int, bool> hash;
        for(auto num : nums){
            if(hash.count(num) == 0){
                hash[num] = true;
            }
        }
        vector<int> result;
        for(int i = 1; i <= nSize; i++){
            if(hash[i] == 0){
                result.push_back(i);
            }
        }
        return result;
    }
};

442. 数组中重复的数据 | 2022-12-6

这题套用了第448题中官方题解中的原地修改法，在进行移植的时候也清晰了自己的理解。

//首次通过
//48ms，击败51.67%
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        int n = nums.size();
        for(auto& num : nums){
            int x = (num - 1) % n;
            nums[x] += n;
        }
        vector<int> ret;
        for(int i = 0; i < n; i++) {
            if(nums[i] > 2 * n){
                ret.push_back(i + 1);
            }
        }
        return ret;
    }
};

41. 缺失的第一个正数 | 2022-12-6

题目要求时间复杂度O ( n ) O(n)O(n)，空间复杂度O ( 1 ) O(1)O(1)。下面的代码因为新建了一个哈希表，所以空间复杂度为O ( n ) O(n)O(n)，不满足要求。本题中− 2 31 < = n u m s [ i ] < = 2 31 − 1 -2^{31}

屏幕截图 2023-12-28 171623.png

//首次通过
//76ms，击败10.85%
#include<climits>
using namespace std;
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int nSize = nums.size();
        unordered_map<int, bool> hash;
        for(auto num : nums){
            if(hash.count(num) == 0){
                hash[num] = true;
            }
        }
        if(hash.count(1) == 0){
            return 1;
        }
        int minNum = INT_MAX;
        for(auto num : nums){
            int t1 = num;
            int t2 = num;
            if(t1 < INT_MAX){
                t1 += 1;
            }
            if(t2 > INT_MIN){
                t2 -= 1;
            }
            if(t1 > 0 && hash.count(t1) == 0){
                if(t1 < minNum){
                    minNum = t1;
                }
            }
            if(t2 > 0 && hash.count(t2) == 0){
                if(t2 < minNum){
                    minNum = t2;
                }
            }
        }
        return minNum;
    }
};

274. H 指数 | 2022-12-6

//首次通过
//0ms，击败100%
#include<algorithm>
using namespace std;
class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.rbegin(), citations.rend());
        int cSize = citations.size();
        int result = 0;
        if(cSize == 1 && citations[0] >= 1){
            result = 1;
        }
        for(int i = 0; i <= cSize - 1; i++){
            if(i + 1 <= citations[i] && (i + 1 >= cSize || i + 1 >= citations[i+1])){
                result = i + 1;
                break;
            }
        }
        return result;
    }
};

数组的改变、移动

453. 最小操作次数使数组元素相等 | 2022-12-6

一开始我真没思路，看了题解才写出来。这题就非常体现了相对的思想，目标是相等，那么 n - 1 个数加一就相当于 1 个数减一。

//首次通过
//36ms，击败41.12%
class Solution {
public:
    int minMoves(vector<int>& nums) {
        int minNum = 1000000000;
        int count = 0;
        for(auto num : nums){
            if(num < minNum){
                minNum = num;
            }
        }
        for(auto num : nums){
            count += num - minNum;
        }
        return count;
    }
};

665. 非递减数列 | 2022-12-6

这段代码修修补补才终于通过，写得逻辑不太清晰，缩进数太多。有两种情况应该返回 false，

有多次下降（一次下降指出现一次n u m s [ i ] > n u m s [ i + 1 ] nums[i]>nums[i+1]nums[i]>nums[i+1]）

仅一次下降，但是处于特殊情况如下图，a 点高于下虚线，且 b 点低于上虚线。

这题花时间较多，不太擅长分情况讨论。发现这个击败率是不稳定的，我刷新了几次，有一次击败了 98%，但是代码没改。

//首次通过
//20ms，击败79.55%
class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int nSize = nums.size();
        int countDown = 0;
        bool result = true;
        if(nSize >= 3){
            for(int i = 0; i <= nSize - 3; i++){
                if(nums[i] > nums[i + 1]){
                    countDown += 1;
                    if(nums[i + 1] > nums[i + 2]){
                        result = false;
                    }
                    else if(i - 1 >= 0 && nums[i + 1] < nums[i - 1] && nums[i + 2] < nums[i]){
                        result = false;
                    }
                }
            }
            if(nums[nSize-2] > nums[nSize-1]){
                countDown += 1;
            }
            if(countDown > 1){
                result = false;
            }
        }
        return result;
    }
};

283. 移动零 | 2022-12-7

最初用的冒泡排序的思路，时间复杂度 O(n^2) 超时了，看了题解才写出来，时间复杂度变成了O ( n ) O(n)O(n)。

//首次通过
//16ms，击败88.55%
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int nSize = nums.size();
        int firstZero = -1;  //第一个0的位置
        int firstNum = -1;  //firstZero后面的第一个非零数的位置
        for(int i = 0; i < nSize; i++){
            if(firstZero == -1 && nums[i] == 0){
                firstZero = i;  
            }
            if(firstNum == -1 && firstZero != -1 && nums[i] != 0){
                firstNum = i;
                break;
            }
        }
        if(firstZero == -1 || firstNum == -1){
            return;
        }
        while(firstNum < nSize){
            if(nums[firstZero] == 0 && nums[firstNum] != 0){
                int t = nums[firstZero];  
                nums[firstZero] = nums[firstNum]; 
                nums[firstNum] = t;
            }
            firstZero += 1;
            while(firstNum < nSize && nums[firstNum] == 0){
                firstNum += 1;
            }
        }
        return;
    }
};