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 。
一次操作中，你可以执行以下四种操作之一：
- 如果 x 是 11 的倍数，将 x 除以 11 。
- 如果 x 是 5 的倍数，将 x 除以 5 。
- 将 x 减 1 。
- 将 x 加 1 。
请你返回让 x 和 y 相等的 最少 操作次数。
测试样例：
输入：x = 26, y = 1
输出：3
解释：我们可以通过以下操作将 26 变为 1 ：
- 将 x 减 1
- 将 x 除以 5
- 将 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;
}
}