LeetCode热题100刷题5：189. 轮转数组、238. 除自身以外数组的乘积、41. 缺失的第一个正数

189. 轮转数组

两次翻转，借助swap实现reverse

class Solution {
public:
    void reverse(vector<int>& nums, int left, int right) {
        int i=left, j = right-1;
        while(i<j) {
            swap(nums[i],nums[j]);
            i++;
            j--;
        }
    }
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums,0,nums.size()-k);
        reverse(nums,nums.size()-k,nums.size());
        reverse(nums,0,nums.size());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

238. 除自身以外数组的乘积

前缀积 * 后缀积

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> preX(nums.size(),1);
        vector<int> postX(nums.size(),1);
        vector<int> res;
        for(int i=1;i<nums.size();i++) {
            preX[i] = preX[i-1] * nums[i-1];
        }
        for(int j=nums.size()-2;j>=0;j--) {
            postX[j] = postX[j+1] * nums[j+1];
        }

        for(int i=0;i<nums.size();i++) {
            res.push_back(preX[i] * postX[i]);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

41. 缺失的第一个正数

需要借助unordered_set，res最好的情况是1，那我就假设答案是1，然后判断，这个res当前出现or曾经出现 就 res++，否则就把nums[i]加入到unordered_set中

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_set<long> uset;
        int res = 1;
        for(int i=0;i<nums.size();i++) {
            if(nums[i] == res || uset.find(res)!=uset.end()) {
                res++;
                while(uset.find(res)!=uset.end()) {
                    res++;
                }
            }
            uset.insert(nums[i]);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17