力扣第241场周赛
题一 找出所有子集的异或总和再求和
描述«
一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。
例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。 给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。
注意：在本题中，元素 相同 的不同子集应 多次 计数。
数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。
示例 1：
输入：nums = [1,3] 输出：6 解释：[1,3] 共有 4 个子集： - 空子集的异或总和是 0 。 - [1] 的异或总和为 1 。 - [3] 的异或总和为 3 。 - [1,3] 的异或总和为 1 XOR 3 = 2 。 0 + 1 + 3 + 2 = 6 示例 2：
输入：nums = [5,1,6] 输出：28 解释：[5,1,6] 共有 8 个子集： - 空子集的异或总和是 0 。 - [5] 的异或总和为 5 。 - [1] 的异或总和为 1 。 - [6] 的异或总和为 6 。 - [5,1] 的异或总和为 5 XOR 1 = 4 。 - [5,6] 的异或总和为 5 XOR 6 = 3 。 - [1,6] 的异或总和为 1 XOR 6 = 7 。 - [5,1,6] 的异或总和为 5 XOR 1 XOR 6 = 2 。 0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28 示例 3：
输入：nums = [3,4,5,6,7,8] 输出：480 解释：每个子集的全部异或总和值之和为 480 。
提示：
1 <= nums.length <= 12 1 <= nums[i] <= 20
思路
DFS 遍历所有可能。
代码
public class N1 {
private int sum;
public int subsetXORSum(int[] nums) {
sum=0;
dfs(0,nums,0);
return sum;
}
private void dfs(int pre, int[] nums, int idx) {
if(idx>= nums.length)return;
final int next = pre ^ nums[idx];
sum+=next;
dfs(next,nums,idx+1);
dfs(pre,nums,idx+1);
}
}
题二 构成交替字符串需要的最小交换次数
描述
给你一个二进制字符串 s ，现需要将其转化为一个 交替字符串 。请你计算并返回转化所需的 最小 字符交换次数，如果无法完成转化，返回 -1 。
交替字符串 是指：相邻字符之间不存在相等情况的字符串。例如，字符串 "010" 和 "1010" 属于交替字符串，但 "0100" 不是。
任意两个字符都可以进行交换，不必相邻 。
示例 1：
输入：s = "111000" 输出：1 解释：交换位置 1 和 4："111000" -> "101010" ，字符串变为交替字符串。 示例 2：
输入：s = "010" 输出：0 解释：字符串已经是交替字符串了，不需要交换。 示例 3：
输入：s = "1110" 输出：-1
提示：
1 <= s.length <= 1000 s[i] 的值为 '0' 或 '1'
思路
- 统计出1和0的个数
- 如果1和0的个数差距大于1 则无法构成交替字符串
- 如果1和0的个数相等：
- 统计偶数位是1需要交替的次数。
- 统计偶数位是0需要交替的次数。
- 取上面的最小值。
- 如果1的个数大于0的个数，则说明偶数位一定是1
- 如果1的个数小于0的个数，则说明偶数位一定是0。
代码
public class N2 {
public int minSwaps(String s) {
final char[] strs = s.toCharArray();
int cnt0,cnt1;
cnt0=cnt1=0;
for (char c:strs){
if(c=='0')cnt0++;
else cnt1++;
}
if(Math.abs(cnt0-cnt1)!=1&&cnt0!=cnt1)return -1;
int res=0;
if(cnt0>cnt1){
for (int i=0;i<strs.length;i+=2){
if(strs[i]=='1')res++;
}
}
else if(cnt0==cnt1){
int res1=0;
int res2=0;
for (int i=0;i<strs.length;i+=2){
if(strs[i]=='0')res1++;
else res2++;
}
res=Math.min(res1,res2);
}
else {
for (int i=0;i<strs.length;i+=2){
if(strs[i]=='0')res++;
}
}
return res;
}
}
题三 找出和为指定值的下标对
描述
给你两个整数数组 nums1 和 nums2 ，请你实现一个支持下述两类查询的数据结构：
累加 ，将一个正整数加到 nums2 中指定下标对应元素上。 计数 ，统计满足 nums1[i] + nums2[j] 等于指定值的下标对 (i, j) 数目（0 <= i < nums1.length 且 0 <= j < nums2.length）。 实现 FindSumPairs 类：
FindSumPairs(int[] nums1, int[] nums2) 使用整数数组 nums1 和 nums2 初始化 FindSumPairs 对象。 void add(int index, int val) 将 val 加到 nums2[index] 上，即，执行 nums2[index] += val 。 int count(int tot) 返回满足 nums1[i] + nums2[j] == tot 的下标对 (i, j) 数目。
示例：
输入： ["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"] [[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]] 输出： [null, 8, null, 2, 1, null, null, 11]
解释： FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]); findSumPairs.count(7); // 返回 8 ; 下标对 (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) 满足 2 + 5 = 7 ，下标对 (5,1), (5,5) 满足 3 + 4 = 7 findSumPairs.add(3, 2); // 此时 nums2 = [1,4,5,4,5,4] findSumPairs.count(8); // 返回 2 ；下标对 (5,2), (5,4) 满足 3 + 5 = 8 findSumPairs.count(4); // 返回 1 ；下标对 (5,0) 满足 3 + 1 = 4 findSumPairs.add(0, 1); // 此时 nums2 = [2,4,5,4,5,4] findSumPairs.add(1, 1); // 此时 nums2 = [2,5,5,4,5,4] findSumPairs.count(7); // 返回 11 ；下标对 (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) 满足 2 + 5 = 7 ，下标对 (5,3), (5,5) 满足 3 + 4 = 7
提示：
1 <= nums1.length <= 1000 1 <= nums2.length <= 10^5 1 <= nums1[i] <= 10^9 1 <= nums2[i] <= 10^5 0 <= index < nums2.length 1 <= val <= 10^5 1 <= tot <= 10^9 最多调用 add 和 count 函数各 1000 次
思路
- 将数据分别额外存储在两个Map中。key是值，value是个数
- add操作的同时更新map2相关KV对
- 求count的是遍历size小的map找出对应map的value，对数相当于两个value相乘。
代码
class FindSumPairs {
private int[] nums2;
private Map<Integer,Integer> map1;
private Map<Integer,Integer> map2;
public FindSumPairs(int[] nums1, int[] nums2) {
this.nums2=nums2;
map1=new HashMap<>();
map2=new HashMap<>();
for (int i:nums1)map1.put(i,map1.getOrDefault(i,0)+1);
for (int i:nums2)map2.put(i,map2.getOrDefault(i,0)+1);
}
public void add(int index, int val) {
final int cnt = map2.getOrDefault(nums2[index], 0) - 1;
if(cnt==0)map2.remove(nums2[index]);
else map2.put(nums2[index],cnt);
nums2[index]+=val;
map2.put(nums2[index],map2.getOrDefault(nums2[index],0)+1);
}
public int count(int tot) {
Map<Integer,Integer> m1;
Map<Integer,Integer> m2;
if(map1.size()<=map2.size()){
m1=map1;
m2=map2;
}else {
m1=map2;
m2=map1;
}
int res=0;
for (Map.Entry<Integer,Integer> e:m1.entrySet()){
res+=e.getValue()*m2.getOrDefault(tot-e.getKey(),0);
}
return res;
}
}
题四 恰有 K 根木棍可以看到的排列数目
描述
有 n 根长度互不相同的木棍，长度为从 1 到 n 的整数。请你将这些木棍排成一排，并满足从左侧 可以看到 恰好 k 根木棍。从左侧 可以看到 木棍的前提是这个木棍的 左侧 不存在比它 更长的 木棍。
例如，如果木棍排列为 [1,3,2,5,4] ，那么从左侧可以看到的就是长度分别为 1、3 、5 的木棍。 给你 n 和 k ，返回符合题目要求的排列 数目 。由于答案可能很大，请返回对 109 + 7 取余 的结果。
示例 1：
输入：n = 3, k = 2 输出：3 解释：[1,3,2], [2,3,1] 和 [2,1,3] 是仅有的能满足恰好 2 根木棍可以看到的排列。 可以看到的木棍已经用粗体+斜体标识。 示例 2：
输入：n = 5, k = 5 输出：1 解释：[1,2,3,4,5] 是唯一一种能满足全部 5 根木棍可以看到的排列。 可以看到的木棍已经用粗体+斜体标识。 示例 3：
输入：n = 20, k = 11 输出：647427950 解释：总共有 647427950 (mod 10^9 + 7) 种能满足恰好有 11 根木棍可以看到的排列。
提示：
1 <= n <= 1000 1 <= k <= n
思路
可以将题转换成n根木棍划分成K个部分。对于每个长为 mm 的部分，对于其任意排列，我们总是可以将排列中最大的元素当作可以看到的木棍，移到该部分的开头，则剩余的木棍可以任意排列，因此每个部分的方案数为 (m-1)!(m−1)!，即为一个长为 mm 的圆排列的方案数。也就是说这是斯特林数。
代码
public class N4 {
private final static int MOD= (int) (Math.pow(10,9)+7);
public int rearrangeSticks(int n, int k) {
long[][] dp=new long[n+1][k+1];
dp[0][0]=1;
for (int i=1;i<=n;i++){
for (int j=1;j<=k;j++){
dp[i][j]=(dp[i-1][j-1]+(i-1)*dp[i-1][j])%MOD;
}
}
return (int) dp[n][k];
}
}