100215. Number of Changing Keys
给你一个下标从 0 开始的字符串 s ，该字符串由用户输入。按键变更的定义是：使用与上次使用的按键不同的键。例如 s = "ab" 表示按键变更一次，而 s = "bBBb" 不存在按键变更。
返回用户输入过程中按键变更的次数。
注意：shift 或 caps lock 等修饰键不计入按键变更，也就是说，如果用户先输入字母 'a' 然后输入字母 'A' ，不算作按键变更。
测试样例：
输入：s = "aAbBcC"
输出：2
解释：
- 从 s[0] = 'a' 到 s[1] = 'A'，不存在按键变更，因为不计入 caps lock 或 shift 。
- 从 s[1] = 'A' 到 s[2] = 'b'，按键变更。
- 从 s[2] = 'b' 到 s[3] = 'B'，不存在按键变更，因为不计入 caps lock 或 shift 。
- 从 s[3] = 'B' 到 s[4] = 'c'，按键变更。
- 从 s[4] = 'c' 到 s[5] = 'C'，不存在按键变更，因为不计入 caps lock 或 shift 。
解答：将String转成全小写，然后按照题意判断按键变更数。
class Solution {
public int countKeyChanges(String s) {
s = s.toLowerCase();
int res = 0;
for (int i = 1; i < s.length(); ++i) {
if (s.charAt(i) != s.charAt(i - 1)) {
++res;
}
}
return res;
}
}100206. Find the Maximum Number of Elements in Subset
给你一个 正整数 数组 nums 。
你需要从数组中选出一个满足下述条件的子集：
你可以将选中的元素放置在一个下标从 0 开始的数组中，并使其遵循以下模式：[x, x^2, x^4, ..., x^(k/2), x^k, x^(k/2), ..., x^4, x^2, x]（注意，k 可以是任何 非负 的 2 的幂）。例如，[2, 4, 16, 4, 2] 和 [3, 9, 3] 都符合这一模式，而 [2, 4, 8, 4, 2] 则不符合。
返回满足这些条件的子集中，元素数量的 最大值 。测试样例：
输入：nums = [5,4,1,2,2]
输出：3
解释：选择子集 {4,2,2} ，将其放在数组 [2,4,2] 中，它遵循该模式，且 2^2 == 4 。因此答案是 3 。
解答：存在平方关系，又因为1 <= nums[i] <= 10^9。我们首先将数组排序，然后从大到小遍历。记录当前数字最长的长度。由于从大到小遍历，我们只会遇到更小的数字。所以遇到当前数字，只要查看它的平方数最长长度即可。
class Solution {
public int maximumLength(int[] nums) {
HashMap<Long, Integer> count = new HashMap<>();
HashMap<Long, Integer> mem = new HashMap<>();
Arrays.sort(nums);
int res = 0;
for (int i = nums.length - 1; i >= 0; --i) {
if (nums[i] == 1) {
int len = i + 1;
if (len % 2 == 0) {
--len;
}
res = Math.max(res, len);
break;
}
long tmp = nums[i];
count.put(tmp, count.getOrDefault(tmp, 0) + 1);
if (count.get(tmp) == 1) {
res = Math.max(res, 1);
mem.put(tmp, 1);
} else {
long mul = tmp * tmp;
int max = mem.getOrDefault(mul, -1);
res = Math.max(max + 2, res);
mem.put(tmp, max + 2);
}
}
return res;
}
}100195. Alice and Bob Playing Flower Game
Alice 和 Bob 在一个长满鲜花的环形草地玩一个回合制游戏。环形的草地上有一些鲜花，Alice 到 Bob 之间顺时针有 x 朵鲜花，逆时针有 y 朵鲜花。
游戏过程如下：
- Alice 先行动。
- 每一次行动中，当前玩家必须选择顺时针或者逆时针，然后在这个方向上摘一朵鲜花。
- 一次行动结束后，如果所有鲜花都被摘完了，那么 当前 玩家抓住对手并赢得游戏的胜利。
给你两个整数 n 和 m ，你的任务是求出满足以下条件的所有 (x, y) 对：
- 按照上述规则，Alice 必须赢得游戏。
- Alice 顺时针方向上的鲜花数目 x 必须在区间 [1,n] 之间。
- Alice 逆时针方向上的鲜花数目 y 必须在区间 [1,m] 之间。
请你返回满足题目描述的数对 (x, y) 的数目。
测试样例：
输入：n = 3, m = 2
输出：3
解释：以下数对满足题目要求：(1,2) ，(3,2) ，(2,1) 。
解答：主要是保证选择的两个数都大于1，且两数的奇偶情况不同。
class Solution {
public int minimumPushes(String word) {
int[] count = new int[26];
for (int i = 0; i < word.length(); ++i) {
count[word.charAt(i) - 'a'] += 1;
}
Arrays.sort(count);
int res = 0, mul = 1, remain = 8;
for (int i = 25; i >= 0; --i) {
--remain;
if (remain < 0) {
remain = 7;
++mul;
}
res += mul * count[i];
}
return res;
}
}100179. Minimize OR of Remaining Elements Using Operations
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一次操作中，你可以选择 nums 中满足 0 <= i < nums.length - 1 的一个下标 i ，并将 nums[i] 和 nums[i + 1] 替换为数字 nums[i] & nums[i + 1] ，其中 & 表示按位 AND 操作。
请你返回 至多 k 次操作以内，使 nums 中所有剩余元素按位 OR 结果的 最小值 。
测试样例：
输入：nums = [3,5,3,2,7], k = 2
输出：3
解释：执行以下操作：
- 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ，得到 nums 为 [1,3,2,7] 。
- 将 nums[2] 和 nums[3] 替换为 (nums[2] & nums[3]) ，得到 nums 为 [1,3,2] 。
最终数组的按位或值为 3 。3 是 k 次操作以内，可以得到的剩余元素的最小按位或值。
解答：竞赛的时候没想明白。这道题目还是贪婪，首先我们需要从高位到低位遍历，优先让k把高位的数变成0。但是高位变0的过程中，牵涉到一个很麻烦的问题，当前的数是和前一个数还是后一个数取和，这个会影响到最终结果。竞赛的时候卡在了这里。
看了别人的答案，才明白这个问题其实也难。只要将每一位分开查看，且保持数组不变。这样遍历的过程中总会把高位想办法再变0。就能知道当前位能不能和高位合并了。
class Solution {
public int minOrAfterOperations(int[] nums, int k) {
int maxBit = 30;
int mask = (1 << maxBit) - 1;
for(int i = maxBit - 1; i >= 0; i--) {
int t = mask - (1 << i);
int cnt = 0;
int now = -1;
for (int num : nums) {
if (now < 0) {
if ((num | t) > t) {
now = num;
} else {
continue;
}
} else {
now = now & num;
cnt++;
if ((now | t) == t) now = -1;
}
}
if(now > 0) cnt++;
if(cnt <= k) mask = t;
}
return mask;
}
}