欢迎大家加QQ群：623375442，可以方便群里面交流。
100372. Number of Bit Changes to Make Two Integers Equal
给你两个正整数 n 和 k。
你可以选择 n 的 二进制表示 中任意一个值为 1 的位，并将其改为 0。
返回使得 n 等于 k 所需要的更改次数。如果无法实现，返回 -1。
测试样例：
输入：n = 13, k = 4
输出：2
解释：
最初，n 和 k 的二进制表示分别为 n = (1101)2 和 k = (0100)2，我们可以改变 n 的第一位和第四位。结果整数为 n = (0100)2 = k。
解答：位运算暴力即可。
class Solution {
public int minChanges(int n, int k) {
int res = 0;
for (int i = 30; i >= 0; --i) {
if (isOcc(n, i) && !isOcc(k, i)) {
++res;
} else if (!isOcc(n, i) && isOcc(k, i)) {
return -1;
}
}
return res;
}
private boolean isOcc(int n, int offset) {
int tmp = (n >> offset) & 1;
return tmp == 1;
}
}100335. Vowels Game in a String
小红和小明在玩一个字符串元音游戏。
给你一个字符串 s，小红和小明将轮流参与游戏，小红 先 开始：
- 在小红的回合，她必须移除 s 中包含 奇数 个元音的任意 非空 子字符串。
- 在小明的回合，他必须移除 s 中包含 偶数 个元音的任意 非空 子字符串。
第一个无法在其回合内进行移除操作的玩家输掉游戏。假设小红和小明都采取 最优策略 。
如果小红赢得游戏，返回 true，否则返回 false。
英文元音字母包括：a, e, i, o, 和 u。
测试样例：
输入：s = "leetcoder"
输出：true
解释：小红可以执行如下移除操作来赢得游戏：
- 小红先手，她可以移除加下划线的子字符串 s = "leetcoder"，其中包含 3 个元音。结果字符串为 s = "der"。
- 小明接着，他可以移除加下划线的子字符串 s = "der"，其中包含 0 个元音。结果字符串为 s = "er"。
- 小红再次操作，她可以移除整个字符串 s = "er"，其中包含 1 个元音。
- 又轮到小明，由于字符串为空，无法执行移除操作，因此小红赢得游戏。
解答：其实只要有一个元音字母出现，Alice就必然获胜。
class Solution {
private static final char[] vowels = {'a','e','i','o','u'};
public boolean doesAliceWin(String s) {
int count = 0;
for (int i = 0; i < s.length(); ++i) {
if (isVowel(s.charAt(i))) ++count;
}
if (count == 0) {
return false;
}
return true;
}
private boolean isVowel(char c) {
for (char v : vowels) {
if (v == c) {
return true;
}
}
return false;
}
}100360. Maximum Number of Operations to Move Ones to the End
给你一个 二进制字符串 s。
你可以对这个字符串执行 任意次 下述操作：
- 选择字符串中的任一下标 i（ i + 1 < s.length ），该下标满足 s[i] == '1' 且 s[i + 1] == '0'。
- 将字符 s[i] 向 右移 直到它到达字符串的末端或另一个 '1'。例如，对于 s = "010010"，如果我们选择 i = 1，结果字符串将会是 s = "000110"。
返回你能执行的 最大 操作次数。
测试样例：
输入：s = "1001101"
输出：4
解释：可以执行以下操作：
- 选择下标 i = 0。结果字符串为 s = "0011101"。
- 选择下标 i = 4。结果字符串为 s = "0011011"。
- 选择下标 i = 3。结果字符串为 s = "0010111"。
- 选择下标 i = 2。结果字符串为 s = "0001111"。
解答：遍历数组，然后22之间的1逐渐融合。
class Solution {
public int maxOperations(String s) {
List<Integer> arr = new ArrayList<>();
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == '1') {
arr.add(i);
}
}
arr.add(s.length());
int res = 0;
for (int i = 1; i < arr.size(); ++i) {
if (arr.get(i) > arr.get(i - 1) + 1) {
res += i;
}
}
return res;
}
}100329. Minimum Operations to Make Array Equal to Target
给你两个长度相同的正整数数组 nums 和 target。
在一次操作中，你可以选择 nums 的任何子数组，并将该子数组内的每个元素的值增加或减少 1。
返回使 nums 数组变为 target 数组所需的 最少 操作次数。
测试样例：
输入：nums = [3,5,1,2], target = [4,6,2,4]
输出：2
解释：执行以下操作可以使 nums 等于 target：
- nums[0..3] 增加 1，nums = [4,6,2,3]。
- nums[3..3] 增加 1，nums = [4,6,2,4]。
解答：竞赛的时候没想明白，有点脑经急转弯了。一个子数组，连续区间的正负情况是必然相同的。
- 如果我们选择把整个子数组+1，虽然正数节省了k-1次操作，但是每一段非正数增加了至少一次操作，所以总的操作没有变好。
- 如果我们选择把整个子数组-1，虽然非正数节省了k-1次操作，但是每一段正数增加了至少一次操作，所以总的操作没有变好。
class Solution {
public long minimumOperations(int[] nums, int[] target) {
long res = 0;
long totalDiff = 0;
for (int i = 0; i < nums.length; i++){
long curDiff = nums[i] - target[i];
if (curDiff == 0) {
totalDiff = 0;
} else if (curDiff > 0 ) {
totalDiff = Math.max(0, totalDiff);
if (curDiff <= totalDiff){
totalDiff = curDiff;
} else {
res += (curDiff - totalDiff);
totalDiff = curDiff;
}
} else {
totalDiff = Math.min(0, totalDiff);
if (curDiff >= totalDiff){
totalDiff = curDiff;
} else {
res += (totalDiff - curDiff);
totalDiff = curDiff;
}
}
}
return res;
}
}