周赛通过情况总结
本次周赛通过题目2个，第三个有了思路能看懂题目，说明还是有进步的。
周赛题目
按键变更的次数
给你一个下标从0开始的字符串s，该字符串由用户输入。按键变更的定义是：使用与上次使用的按键不同的键。例如s="ab"表示按键变更一次，而s="bBBb"不存在按键变更。
返回用户输入过程中按键变更的次数。
注意：shift或capslock等修饰键不计入按键变更，也就是说，如果用户先输入字母’a’然后输入字母’A’，不算作按键变更。
- 解题思法
- 只需要依次判断，如果有变更时就result++。
class Solution {
public int countKeyChanges(String s) {
char[] ar=s.toCharArray();
int len=ar.length;
int result=0;
int mid=ar[0]>='A'&&ar[0]<='Z'?ar[0]-'A':ar[0]-'a';
for(int i=1;i<len;i++){
int tem=ar[i]>='A'&&ar[i]<='Z'?ar[i]-'A':ar[i]-'a';
if (tem==mid){
continue;
}
result++;
mid=tem;
}
return result;
}
}
子集中元素的最大数量
给你一个正整数数组nums。
你需要从数组中选出一个满足下述条件的子集，你可以将选中的元素放置在一个下标从0开始的数组中，并使其遵循以下模式：[x,x2,x4,…,xk/2,xk,xk/2,…,x4,x2,x]（注意，k可以是任何非负的2的幂）。例如，[2,4,16,4,2]和[3,9,3]都符合这一模式，而[2,4,8,4,2]则不符合。
返回满足这些条件的子集中，元素数量的最大值。
- 解题思路
- 主要是通过map记录每个数字出现的次数，然后依次轮询判断
class Solution {
public int maximumLength(int[] nums) {
// Map<数字,总数>
HashMap<Integer,Integer>map=new HashMap<>();
// 处理每个数字
for(Integer tem:nums){
map.put(tem,map.getOrDefault(tem,0)+1);
}
int result=1;
// 选择一个数字为开头数字，然后依次^2判断有无值，如果有值且数字数量大于2，则继续判断下一个数字，否则退出
for(int i=0;i<nums.length;i++){
if (i!=0&&nums[i]==nums[i-1]){
continue;
}
if (nums[i]<=1){
result=Math.max(result,map.get(nums[i])%2==0?map.get(nums[i])-1:map.get(nums[i]));
continue;
}
if (map.get(nums[i])>=2&&map.get(nums[i]*nums[i])!=null){
int mid=1;
int tem=nums[i]*nums[i];
while(map.get(tem)!=null){
System.out.println(tem);
mid++;
if (map.get(tem)<2){
break;
}
tem=tem*tem;
}
mid=mid>1?(mid-1)*2+1:mid;
result=Math.max(mid,result);
}
}
return result;
}
}
Alice 和 Bob 玩鲜花游戏
Alice和Bob在一个长满鲜花的环形草地玩一个回合制游戏。环形的草地上有一些鲜花，Alice到Bob之间顺时针有x朵鲜花，逆时针有y朵鲜花。
游戏过程如下：
Alice先行动。
每一次行动中，当前玩家必须选择顺时针或者逆时针，然后在这个方向上摘一朵鲜花。
一次行动结束后，如果所有鲜花都被摘完了，那么当前玩家抓住对手并赢得游戏的胜利。
给你两个整数n和m，你的任务是求出满足以下条件的所有(x,y)对：
按照上述规则，Alice必须赢得游戏。
Alice顺时针方向上的鲜花数目x必须在区间[1,n]之间。
Alice逆时针方向上的鲜花数目y必须在区间[1,m]之间。
请你返回满足题目描述的数对(x,y)的数目。
- 解题思路
- Alice 必须要赢，如果x是奇数，y必须是偶数；x是偶数，y必须是奇数。1-n中，奇数个数是n/2，偶数也是n/2，对于m同理。所以计算公式为n/2m/2+n/2m/2
class Solution {
public long flowerGame(int n, int m) {
return (long) n * m / 2;
}
}
给定操作次数内使剩余元素的或值最小
给你一个下标从0开始的整数数组nums和一个整数k。
一次操作中，你可以选择nums中满足0<=i<nums.length-1的一个下标i，并将nums[i]和nums[i+1]替换为数字nums[i]&nums[i+1]，其中&表示按位AND操作。
请你返回至多k次操作以内，使nums中所有剩余元素按位OR结果的最小值。
- 解题思路
- 多次操作，相当于把一段连续子数组合并成0。 尝试从左到右合并（忽略低位和必须是111的位），如果合并出000，就开始合并下一段。
class Solution {
public int minOrAfterOperations(int[] nums, int k) {
int ans = 0;
int mask = 0;
for (int b = 29; b >= 0; b--) {
mask |= 1 << b;
int cnt = 0; // 操作次数
int and = -1; // -1 的二进制全为 1
for (int x : nums) {
and &= x & mask;
if (and != 0) {
cnt++; // 合并 x
} else {
and = -1; // 准备合并下一段
}
}
if (cnt > k) {
ans |= 1 << b; // 答案的这个比特位必须是 1
mask ^= 1 << b; // 后面不考虑这个比特位
}
}
return ans;
}
}
总结
- Leetcode周赛第三题基本偏推导性题目，不能从数据结构方面去硬解。
