Leetcode(Final 前700 免费题)

2024-03-13 18:57:57

目录

数组

数组的遍历

LeetCode 485. 最大连续1的个数

class Solution {
public:
/*
双指针算法，从头遍历数组中每一个元素，如果是0的话跳过，如果是1的话，从它开始探索它后面有多少个连续的1，更新答案
*/
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < nums.size(); i ++ ) {
            if (nums[i] == 0) continue;
            int j = i + 1;
            while (j < nums.size() && nums[j] == 1) j ++ ;
            res = max(res, j - i);
            i = j;
        }
        return res;
    }
};

LeetCode 495. 提莫攻击

class Solution {
public:
/*
要判断每一次攻击在实际中所能维持的中毒时间，这个需要比较中毒持续时间 与 当前攻击时刻与下一个攻击时刻的差值 两者取较小值。
所以从第二个时刻开始遍历，每次遍历时确定的是前一时刻实际上所维持的中毒时间
最后加上最后一个时刻的中毒时间(如果需要加的话)
*/
    int findPoisonedDuration(vector<int>& w, int d) {
        int res = 0;
        for (int i = 1; i < w.size(); i ++ ) res += min(w[i] - w[i - 1], d);
        if (w.size()) res += d;//最后加上最后中毒持续时间
        return res;
    }
};

LeetCode 414. 第三大的数

class Solution {
public:
    int thirdMax(vector<int>& nums) {
/*
注意第三大的数是指第三大且唯一出现的数 输入：[2, 2, 3, 1] 输出：1
本质上分情况讨论
从三个数记录前三大的值，遍历数组，更新三个变量，另外用一个变量记录整个数组一共有多少个最大值
另外这道题数据会出现负无穷，为了不处理边界情况，用long long
*/
        long long INF = 1e10, a = -INF, b = -INF, c = -INF, s = 0;
        for (auto x: nums) {
            if (x > a) s ++, c = b, b = a, a = x;//注意更新顺序
            else if (x < a && x > b) s ++, c = b, b = x;
            else if (x < b && x > c) s ++, c = x;
            //对于等于abc以及小于c的情况都没有处理，s记录的就是有几个最大值
        }
        if (s < 3) return a;
        return c;
    }
};

LeetCode 628. 三个数的最大乘积

/*
根据正负数个数分类讨论：
正正正：最大的三个正数
正正负：说明数组长度为3，否则但凡还有一个数，无法正负或为0都不可能出现这个情况
正负负：最大的正数和最小的两个负数
负负负：数组全负，否则但凡有一个正数或0都不会出现这种情况，选最大的三个数
所以三个数的最大乘积，必然是三个最大的数的乘积或者两个最小的（负）数与最大数的乘积
*/
class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        int n = nums.size();
        if(n<3) return 0;
        sort(nums.begin(), nums.end());
        return max(nums[n - 1] * nums[n - 2] * nums[n - 3], nums[0] * nums[1] * nums[n - 1]);
    }
};

/*
三个数的最大乘积，必然是三个最大的数的乘积或者两个最小的（负）数与最大数的乘积。
线性扫描或者排序找出最大的三个数和最小的两个数即可。
*/
class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        //假设max1 > max2 > max3
        int max1 = INT_MIN;
        int max2 = INT_MIN;
        int max3 = INT_MIN;
        //假设min1 < min2
        int min1 = INT_MAX;
        int min2 = INT_MAX;        
        for (int a : nums) {
            if (a > max1) {
                max3 = max2;
                max2 = max1;
                max1 = a;
            } else if (a > max2) {
                max3 = max2;
                max2 = a;
            } else if (a > max3) {
                max3 = a;
            }
            
            if (a < min1) {
                min2 = min1;
                min1 = a;
            } else if (a < min2) {
                min2 = a;    
            }            
        }
        return max(min1 * min2 * max1, max1 * max2 * max3);
    }
};

统计数组中的元素

LeetCode 41. 缺失的第一个正数

/*
这道题可用先排序，然后从前往后扫描 但是这样时间复杂度O(nlogn) C++最多1e8
也可以用哈希表，先把所有数放入哈希表中，之后再去从小到大枚举所有正整数(1-n)，直到找到第一个没有出现过的正整数为止，这样时间空间复杂度都是O(n)
这道题让我们找到没有出现的最小的正整数，可能是1,2,....
遍历每一个元素，如果当前遍历元素可以放到它该在的位置，并且不在它该在的位置的话，就一直交换，直到最后每一个可以放到该在的位置的元素放入该在的位置
说的具体一点就是如果数组中有元素1的话，把它放到第一个位置(下标为0)，如果有2的话，把它放到第二个位置(下标为1)...如果有元素i的话，把它放到i-1这个位置
时间复杂度看着是两层循环，但每个元素最多执行一次，所以时间复杂度是O(n)
*/
class Solution{
public:
    int firstMissingPositive(vector<int>& nums) 
    {
//哈希表做法
        // unordered_set<int> h;
        // for(auto x:nums) h.insert(x);

        // int res=1;
        // while(h.count(res)) res++;

        // return res;
        int n = nums.size();

        for(int i = 0; i < n; ++ i)
            while(nums[i] > 0 && nums[i] <= n
                    && nums[nums[i] - 1] != nums[i])
                swap(nums[i], nums[nums[i] - 1]);

        for(int i = 0; i < n; ++ i)
            if(nums[i] != i + 1)
                return i + 1;//这里nums[i]不一定是重复的数，因为它可能不在1到n这个范围内

        return n + 1;
    }
};

LeetCode 274. H 指数

/*
计数排序
如果一篇文章的引用次数超过论文的总数 n，那么将它的引用次数降低为 n 也不会改变hh 指数的值，因为 h 指数一定小于等于 n
*/
class Solution {
public:
    int hIndex(vector<int>& c) {
        int n = citations.size();
        vector<int> buckets(n + 1);

        for (int citation: citations)
            ++buckets[min(citation, n)];//buckets[i]表示引用i次的论文有多少篇

        int sum = 0;
        for (int i = n; i >= 0; --i){
            sum += buckets[i];//有sum篇论文引用了至少i次
            if (sum >= i) return i;//刚开始出现sum>=i时就return
        }

        return -1;
    }
};

class Solution {
public:
    int hIndex(vector<int>& c) {
        /*
        找到最大的h使得有h个数大于等于h
        先将数组从大到小排好序，h从大到小枚举，如果h个数大于等于h，则必然第h个数大于等于h
        只需要判断是否刚好第h个数大于等于h，这样必然前面所有数都大于等于h
        */
        sort(c.begin(), c.end(), greater<int>());
        for (int h = c.size(); h; h -- )
            if (c[h - 1] >= h)//第h个数大于等于h
                return h;
        return 0;
    }
};

LeetCode 442. 数组中重复的数据

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        for (auto x: nums) {
            int k = abs(x);
            nums[k-1] *= -1;
            if (nums[k-1] > 0) res.push_back(k);
        }
        return res;
    }
};

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < nums.size(); ++i){
            while (nums[nums[i] - 1] != nums[i])
                swap(nums[nums[i] - 1], nums[i]);
        }

        vector<int> res;
        for (int i = 0; i < nums.size(); ++i){
            if (nums[i] != i + 1)
            //nums[i]这个在数组中出现过的数还没有在正确的位置说明nums[i]本身重复，i+1是没出现过的数
                res.push_back(nums[i]);
        }

        return res;
    }
};

LeetCode 448. 找到所有数组中消失的数字

/*
利用下标，把每个数都放在正确的位置上，也就是下标与数字一一对应，因为这道题的数据范围数1到n，所以数字i对应的第i个数的下标是i-1
让数组中出现的数都在正确的位置上
最后只要不在正确的位置上的数就是没出现过的
*/
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i){//遍历，只有当前遍历的数不在正确的位置上，就交换使得在正确的位置上
            while (nums[nums[i] - 1] != nums[i])//while循环是尽可能的交换
                swap(nums[nums[i] - 1], nums[i]);//数字nums[i]对应的第nums[i]个数的下标是nums[i]-1
        }

        vector<int> res;
        for (int i = 0; i < n; ++i)
            if (nums[i] != i + 1)//此时是i+1没出现过
                res.push_back(i + 1);

        return res;
    }
};

/*
如果不考虑空间限制的话，可以开一个长度是n的数组标记每个数是否出现，然后遍历原数组记录每个数的出现次数，然后再遍历新开数组即可
要求不开额外空间的话可以原地修改原数组，使得原数组帮我们记录每个数是否出现过
由于所有数的范围都是1到n之间，所有只有数字x出现过，就把数组中第x个数(对应下标为x-1)变成负数即可
最后数组中的正数对应的数是没有出现过的
*/
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        for (auto x: nums) {
            x = abs(x);
            if (nums[x - 1] > 0) nums[x - 1] *= -1;
//这里是大于0的时候才变为负数，所以出现一次或两次的数最后都是负数
        }
        vector<int> res;
        for (int i = 0; i < nums.size(); i ++ )
            if (nums[i] > 0)
                res.push_back(i + 1);
        return res;
    }
};

LeetCode 645. 错误的集合

class Solution {
public:
/*
数组中1个数出现了0次，1个数出现了两次，其他均只出现1次，且范围在1到n之间
注意要先返回重复的，再返回缺失的
(线性扫描) O(n)
利用原数组进行线性扫描。扫描过程中，将 nums[abs(nums[i]) - 1] 取相反数。若扫描过程中发现 nums[abs(nums[i]) - 1] 已经是负数了，就不再将其置负数，同时说明 abs(nums[i]) - 1 是重复的。
最后再扫描数组中，若发现 nums[i] 是正数，则说明 i + 1 是丢失的数。
注意数组中第i个数的下标是i-1
*/
    vector<int> findErrorNums(vector<int>& nums) {
        vector<int> res(2);
        for (auto x: nums) {
            int k = abs(x);//取绝对值是因为当前遍历到的这个数可能已经被取反了
            if (nums[k - 1] < 0)//如果第k个数以及取反，说明第数字k是重复的那个数
                res[0] = k;
            nums[k - 1] *= -1;
        }
//循环结束后，数组中只有两个数为正数，一个是重复数k对于的第k个数，它被取反两次，一个数缺失的数，被取反0次
        for (int i = 0; i < nums.size(); i ++ ) {
            if (nums[i] > 0 && i + 1 != res[0]) {//下标i对应的数是i+1
                res[1] = i + 1;
            }
        }

        return res;
    }
};

/*
异或位运算 timeO(n)
1.
将原数组和辅助数组[1, 2, ...n]所有元素进行异或，可知其中等于dup的有3个，mis有1个（在辅助数组中），其余元素各有2个。在异或运算过程中，成对出现的都会抵消为0（异或运算的先后顺序不影响，故可当做相等元素各自运算）。最后的结果就是 dup ^ mis
2.
根据dup和mis最后不同的那一位去把两个数组分类，其中一类中3个dup，其余元素成对出现；另一部分有1个mis，其余元素成对出现。对于这两部分，各自将自身所有元素按位异或^，发现结果正好一个是dup，一个是mis。
3.
区分谁重复，谁缺失，先返回重复的
*/
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int xorr = 0, n = nums.size();//0与任何数异或都为数自身，所以以0为基元素
        for (int num: nums)
            xorr ^= num;

        for (int i = 1; i <= n; ++i)
            xorr ^= i;
        //循环结束后，xorr为dup^mis

        //lowbit操作得到最后xorr最后一位1，遍历所有元素，将各自类中的数全部异或
        int lowbit = xorr & -xorr, a = 0, b = 0;
        for (int num: nums)
            if (num & lowbit)
                a ^= num;
            else 
                b ^= num;

        for (int i = 1; i <= n; ++i)
            if (i & lowbit)
                a ^= i;
            else 
                b ^= i;
        //上面两个循环结束后，a和b中一个数dup，一个是mis

        //然后再区别谁是dup，谁是mis，先返回dup
        for (int num: nums)
            if (num == a)
                return {a, b};
            else if (num == b)
                return {b, a};
        return {-1, -1};
    }
};

LeetCode 697. 数组的度(待做)
上一篇：Codeforces Round #700 (Div. 2) D2. Painting the Array I


下一篇：Codeforces Round #700 (Div. 2)