Biweekly Contest 121

100157. Smallest Missing Integer Greater Than Sequential Prefix Sum

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

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

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

测试样例：

输入：nums = [1,2,3,2,5]

输出：6

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

解答：搜索最长满足要求的前缀，然后暴力枚举查看第一个缺少的数据。（题目的范围很小，暴力是可以的）

class Solution {
    public int missingInteger(int[] nums) {
        int prefixSum = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] == nums[i - 1] + 1) {
                prefixSum += nums[i];
            } else {
                break;
            }
        }

        Set<Integer> set = new HashSet<>();
        for (int n : nums) {
            set.add(n);
        }
        while (set.contains(prefixSum)) {
            ++prefixSum;
        }
        return prefixSum;
    }
}

100168. Minimum Number of Operations to Make Array XOR Equal to K

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

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

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

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

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

测试样例：

输入：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 。

解答：这道题目需要稍微脑经急转弯一下。因为只是选择一个数，然后反转一个位数，所以知道当前数组的XOR结果，然后对比k查看那些位对不上即可。对不上的位，找任意一个数，对应位反转。

class Solution {
    public int minOperations(int[] nums, int k) {
        int xor = k;
        for (int n : nums) {
            xor ^= n;
        }

        int res = 0;
        while (xor != 0) {
            res += (xor) % 2;
            xor /= 2;
        }
        return res;
    }
}

100159. Minimum Number of Operations to Make X and Y Equal

给你两个正整数 x 和 y 。

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

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

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

测试样例：

输入：x = 26, y = 1

输出：3

解释：我们可以通过以下操作将 26 变为 1 ：

1. 将 x 减 1
2. 将 x 除以 5
3. 将 x 除以 5

将 26 变为 1 最少需要 3 次操作。

解答：感恩，这道题目范围很小。最大值是10000，因为最多是除以11这个操作，所以数组需要遍历的最大值就是10010（如果遍历到10021，然后除以11，不如从10010除以11，再加1）。最后利用BFS+DP暴力计算即可。

class Solution {
    private static final int max = 10010;

    public int minimumOperationsToMakeEqual(int x, int y) {
        if (x == y) {
            return 0;
        }
        Queue<Integer> queue = new LinkedList<Integer>();
        boolean[] isVisit = new boolean[max + 1];
        isVisit[x] = true;
        queue.add(x);
        queue.add(null);

        int res = 1;
        while (queue.size() > 1) {
            Integer tmp = queue.poll();
            if (tmp == null) {
                ++res;
                queue.add(null);
            } else {
                if (tmp + 1 <= max && !isVisit[tmp + 1]) {
                    queue.add(tmp + 1);
                    isVisit[tmp + 1] = true;
                }
                if (tmp - 1 >= 1 && !isVisit[tmp - 1]) {
                    queue.add(tmp - 1);
                    isVisit[tmp - 1] = true;
                }
                if (tmp % 5 == 0 && !isVisit[tmp / 5]) {
                    queue.add(tmp / 5);
                    isVisit[tmp / 5] = true;
                }
                if (tmp % 11 == 0 && !isVisit[tmp / 11]) {
                    queue.add(tmp / 11);
                    isVisit[tmp / 11] = true;
                }
                if (isVisit[y]) {
                    return res;
                }
            }
        }
        return res;
    }
}

100163. Count the Number of Powerful Integers

给你三个整数 start ，finish 和 limit 。同时给你一个下标从 0 开始的字符串 s ，表示一个 正 整数。

如果一个 正 整数 x 末尾部分是 s （换句话说，s 是 x 的 后缀），且 x 中的每个数位至多是 limit ，那么我们称 x 是 强大的 。

请你返回区间 [start..finish] 内强大整数的 总数目 。

如果一个字符串 x 是 y 中某个下标开始（包括 0 ），到下标为 y.length - 1 结束的子字符串，那么我们称 x 是 y 的一个后缀。比方说，25 是 5125 的一个后缀，但不是 512 的后缀。

测试样例：

输入：start = 1, finish = 6000, limit = 4, s = "124"

输出：5

解释：区间 [1..6000] 内的强大数字为 124 ，1124 ，2124 ，3124 和 4124 。这些整数的各个数位都 <= 4 且 "124" 是它们的后缀。注意 5124 不是强大整数，因为第一个数位 5 大于 4 。这个区间内总共只有这 5 个强大整数。

解答：其实没啥难度的板子题目，主要需要细心。WA了好多次，心累。

class Solution {
    public long numberOfPowerfulInt(long start, long finish, int limit, String s) {
        return cal(finish, limit, s) - cal(start - 1, limit, s);
    }

    private long cal(long num, int limit, String s) {
        long suf = Long.parseLong(s);
        if (suf > num) {
            return 0;
        }
        String numStr = String.valueOf(num);
        int lenDiff = numStr.length() - s.length();
        long res = 0;
        long[] mulArr = mul(lenDiff, limit);

        for (int i = 0; i < lenDiff; ++i) {
            res += mulArr[i];
        }
        for (int i = 0, j = lenDiff - 1; i <= lenDiff; ++i, --j) {
            if (i < lenDiff) {
                if (i == 0) {
                    if (numStr.charAt(i) - '0' > limit) {
                        res += limit * (mulArr[j] / limit + mulArr[j]);
                        break;
                    } else {
                        res += (numStr.charAt(i) - '0' - 1) * (mulArr[j] / limit + mulArr[j]);
                    }
                } else {
                    if (numStr.charAt(i) - '0' > limit) {
                        res += (limit + 1) * (mulArr[j] / limit + mulArr[j]);
                        break;
                    } else {
                        res += (numStr.charAt(i) - '0') * (mulArr[j] / limit + mulArr[j]);
                    }
                }
            } else {
                res += Long.parseLong(numStr.substring(i)) >= suf ? 1 : 0;
            }
        }
        return res;
    }

    private long[] mul(int len, int limit) {
        long[] mem = new long[len + 1];
        mem[0] = 1;
        for (int i = 1; i < len; ++i) {
            if (i == 1) {
                mem[i] = limit * mem[i - 1];
            } else {
                mem[i] = (limit + 1) * (limit * mem[i - 1] / limit);
            }
        }
        return mem;
    }
}