LeetCode第121场双周赛

​ 每次这么晚打比赛脑子都要抽风，这次周赛疯狂WA，第一道简单题更是WA了4次，受不了了。每次打比赛我都是能AC三题就是胜利，第四题看一眼题干，能看懂就做，看不懂就不做了，这次确实是A掉三题，只不过罚时了很久就是了…

第一题

给你一个下标从 0 开始的整数数组 nums 。

如果一个前缀 nums[0..i] 满足对于 1 <= j <= i 的所有元素都有 nums[j] = nums[j - 1] + 1 ，那么我们称这个前缀是一个 顺序前缀 。特殊情况是，只包含 nums[0] 的前缀也是一个 顺序前缀 。

请你返回 nums 中没有出现过的 最小 整数 x ，满足 x 大于等于 最长 顺序前缀的和。

示例 1：

输入：nums = [1,2,3,2,5]
输出：6
解释：nums 的最长顺序前缀是 [1,2,3] ，和为 6 ，6 不在数组中，所以 6 是大于等于最长顺序前缀和的最小整数。

示例 2：

输入：nums = [3,4,5,1,12,14,13]
输出：15
解释：nums 的最长顺序前缀是 [3,4,5] ，和为 12 ，12、13 和 14 都在数组中，但 15 不在，所以 15 是大于等于最长顺序前缀和的最小整数。

提示：

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 50

思路分析

纯纯阅读理解题，我就是因为没理解到位WA了三次。

1. 必须1 <= j <= i之间的所有元素全都满足才算一个顺序前缀。并且**nums[0]**也算一个顺序前缀。

2. 需要返回的是最长顺序前缀的和，并且这个和在数组中没出现过，如果出现过，就一直+1直到满足条件。

明白了以上几点，再看数据范围：50，啥都不用想了，直接n^2暴力解。

代码

class Solution {
public:
    int missingInteger(vector<int>& nums) {
        int ans = 0, s = 0, n = nums.size();
        set<int> hashSet;
        for (int num: nums){
            hashSet.insert(num);
        }
        for(int i = 0; i < n; i++){
            int tmp = 1, ts = nums[0];
            for (int j = 1; j <= i; j++){
                if(nums[j] == nums[j - 1] + 1){
                    tmp ++;
                    ts += nums[j];
                }
                else break;		// 如果不满足条件直接break
            }
            ans = max(ans, tmp);
            if(ans == tmp){		// 只有确定这次是最长前缀的时候才更新s，避免s大但是ans小的情况
                s = max(s, ts);
            }
        }
        if(s > 50) return s;
        for(int i = s; i <= 51; i++){
            if (hashSet.find(i) == hashSet.end()){
                return i;
            }
        }
        return -1;
    }
};

class Solution {
    public int missingInteger(int[] nums) {
        int n = nums.length;
        int ans = 0, s = 0;
        HashSet<Integer> set = new HashSet<>();
        for (int i: nums){
            set.add(i);
        }
        for (int i = 0; i < n; i++){
            int tmp = 1, ts = nums[0];
            for (int j = 1; j <= i; j++){
                if(nums[j] == nums[j - 1] + 1){
                    tmp ++;
                    ts += nums[j];
                }
                else break;		// 如果不满足条件直接break
            }
            ans = Math.max(ans, tmp);
            if(ans == tmp) s = Math.max(s, ts);		// 只有确定这次是最长前缀的时候才更新s，避免s大但是ans小的情况
        }
        if(s > 50) return s;
        for(int i = s; i <= 51; i++){
            if (!set.contains(i)) return i;
        }
        return -1;
    }
}

class Solution:
    def missingInteger(self, nums: List[int]) -> int:
        n, ans, s = len(nums), 0, 0
        hashSet = set(nums)
        for i in range(n):
            tmp, ts = 1, nums[0]
            for j in range(1, i + 1):
                if nums[j] == nums[j - 1] + 1:
                    tmp += 1
                    ts += nums[j]
                else:
                    break
            ans = max(ans, tmp)
            if ans == tmp:		# 只有确定这次是最长前缀的时候才更新s，避免s大但是ans小的情况
                s = max(s, ts)
        if s > 50:
            return s
        for i in range(s, 52):
            if i not in hashSet:
                return i
        return -1

复杂度分析

• 时间复杂度：O(n^2)，n为数组长度。
• 空间复杂度：O(n)，定义了一个哈希集合，最坏情况下有n个数。

第二题

给你一个下标从 0 开始的整数数组 nums 和一个正整数 k 。

你可以对数组执行以下操作 任意次 ：

• 选择数组里的 任意 一个元素，并将它的 二进制 表示 翻转 一个数位，翻转数位表示将 0 变成 1 或者将 1 变成 0 。

你的目标是让数组里 所有 元素的按位异或和得到 k ，请你返回达成这一目标的 最少 操作次数。

注意，你也可以将一个数的前导 0 翻转。比方说，数字 (101)2 翻转第四个数位，得到 (1101)2 。

示例 1：

输入：nums = [2,1,3,4], k = 1
输出：2
解释：我们可以执行以下操作：

• 选择下标为 2 的元素，也就是 3 == (011)2 ，我们翻转第一个数位得到 (010)2 == 2 。数组变为 [2,1,2,4] 。
• 选择下标为 0 的元素，也就是 2 == (010)2 ，我们翻转第三个数位得到 (110)2 == 6 。数组变为 [6,1,2,4] 。
  最终数组的所有元素异或和为 (6 XOR 1 XOR 2 XOR 4) == 1 == k 。
  无法用少于 2 次操作得到异或和等于 k 。

示例 2：

输入：nums = [2,0,2,0], k = 0
输出：0
解释：数组所有元素的异或和为 (2 XOR 0 XOR 2 XOR 0) == 0 == k 。所以不需要进行任何操作。

提示：

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^6
• 0 <= k <= 10^6

思路分析

这道题看似很唬人，其实是纸老虎。

设nums的异或和为s。

令s=k就等于s⊕k=0。也就是把数组中所有数全部异或，令其为x，只需要比较x和k有多少位不一样即可。

代码

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        int s = 0;
        for(int i: nums){
            s ^= i;
        }
        s ^= k;		// 想知道s和k有几位数不一样只需要异或一次后数1的个数即可
        int ans = 0;
        while(s){
            ans += s & 1;
            s >>= 1;
        }
        return ans;
    }
};

class Solution {
    public int minOperations(int[] nums, int k) {
        int s = 0;
        for (int i: nums){
            s ^= i;
        }
        return Integer.bitCount(s ^ k);		// 想知道s和k有几位数不一样只需要异或一次后数1的个数即可,bitCount方法可以直接获取
    }
}

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        s = 0
        for i in nums:
            s ^= i
        return (s ^ k).bit_count()

复杂度分析

• 时间复杂度：O(n)，n为数组长度。
• 空间复杂度：O(1)。

第三题

给你两个正整数 x 和 y 。

一次操作中，你可以执行以下四种操作之一：

1. 如果 x 是 11 的倍数，将 x 除以 11 。
2. 如果 x 是 5 的倍数，将 x 除以 5 。
3. 将 x 减 1 。
4. 将 x 加 1 。

请你返回让 x 和 y 相等的 最少 操作次数。

示例 1：

输入：x = 26, y = 1
输出：3
解释：我们可以通过以下操作将 26 变为 1 ：

1. 将 x 减 1
2. 将 x 除以 5
3. 将 x 除以 5
   将 26 变为 1 最少需要 3 次操作。

示例 2：

输入：x = 54, y = 2
输出：4
解释：我们可以通过以下操作将 54 变为 2 ：

1. 将 x 加 1
2. 将 x 除以 11
3. 将 x 除以 5
4. 将 x 加 1
   将 54 变为 2 最少需要 4 次操作。

示例 3：

输入：x = 25, y = 30
输出：5
解释：我们可以通过以下操作将 25 变为 30 ：

1. 将 x 加 1
2. 将 x 加 1
3. 将 x 加 1
4. 将 x 加 1
5. 将 x 加 1
   将 25 变为 30 最少需要 5 次操作。

提示：

• 1 <= x, y <= 10^4

思路分析

这题我第一眼看以为是模拟，仔细看了一下样例发现没有这么复杂，可以抽象成最短路问题，直接BFS即可。

这里有一点可以优化的方法：注意x想要增加只有+1这种方法，所有如果y >= x时，直接返回y - x即可。

代码

class Solution {
public:
    int minimumOperationsToMakeEqual(int x, int y) {
        deque<tuple<int, int>> q;
        set<int> visited;
        q.push_back(make_tuple(x, 0));
        visited.insert(x);
        while(!q.empty()){
            tuple<int, int> now = q.front();
            q.pop_front();
            int tmp = get<0>(now);
            int cnt = get<1>(now);
            if (tmp == y){
                return cnt;
            }
            if(tmp % 11 == 0 && visited.find(tmp / 11) == visited.end()){
                visited.insert(tmp / 11);
                q.push_back(make_tuple(tmp / 11, cnt + 1));
            }
            if(tmp % 5 == 0 && visited.find(tmp / 5) == visited.end()){
                visited.insert(tmp / 5);
                q.push_back(make_tuple(tmp / 5, cnt + 1));
            }
            if(tmp > 0 && visited.find(tmp - 1) == visited.end()){
                visited.insert(tmp - 1);
                q.push_back(make_tuple(tmp - 1, cnt + 1));
            }
            if(visited.find(tmp + 1) == visited.end()){
                visited.insert(tmp + 1);
                q.push_back(make_tuple(tmp + 1, cnt + 1));
            }
        }

        return -1;
    }
};

class Solution {
    public int minimumOperationsToMakeEqual(int x, int y) {
        ArrayDeque<int[]> q = new ArrayDeque<>();
        HashSet<Integer> set = new HashSet<>();
        q.addLast(new int[]{x, 0});
        set.add(x);
        while(!q.isEmpty()){
            int[] now = q.pollFirst();
            int tmp = now[0], cnt = now[1];
            if(tmp == y) return cnt;
            if(tmp % 11 == 0 && !set.contains(tmp / 11)){
                set.add(tmp / 11);
                q.addLast(new int[]{tmp / 11, cnt + 1});
            }
            if(tmp % 5 == 0 && !set.contains(tmp / 5)){
                set.add(tmp / 5);
                q.addLast(new int[]{tmp / 5, cnt + 1});
            }
            if(tmp > 0 && !set.contains(tmp - 1)){
                set.add(tmp - 1);
                q.addLast(new int[]{tmp - 1, cnt + 1});
            }
            if(!set.contains(tmp + 1)){
                set.add(tmp + 1);
                q.addLast(new int[]{tmp + 1, cnt + 1});
            }
        }
        return -1;
    }
}

class Solution:
    def minimumOperationsToMakeEqual(self, x: int, y: int) -> int:
        if y >= x:
            return y - x
        ans = 0
        q = collections.deque()
        visited = set()
        q.append((x, 0))
        visited.add(x)

        while q:
            tmp, cnt = q.popleft()
            if tmp == y:
                return cnt
            if tmp % 11 == 0 and tmp // 11 not in visited:
                q.append((tmp // 11, cnt + 1))
                visited.add(tmp // 11)
            if tmp % 5 == 0 and tmp // 5 not in visited:
                q.append((tmp // 5, cnt + 1))
                visited.add(tmp // 5)
            if tmp > 0 and tmp - 1 not in visited:
                q.append((tmp - 1, cnt + 1))
                visited.add(tmp - 1)
            if tmp + 1 not in visited:
                q.append((tmp + 1, cnt + 1))
                visited.add(tmp + 1)
        return -1

复杂度分析

• 时间复杂度：O(x)。
• 空间复杂度：O(x)，定义了一个哈希集合。