第一题：5759. 找出所有子集的异或总和再求和
题目链接
题目简介
题目思路
- 直接爆搜出子集的个数，然后对每一个子集进行异或操作，最终进行求和。
题目代码
class Solution { public int subsetXORSum(int[] nums) { List<List<Integer>> list = new ArrayList<>(); List<Integer> path = new ArrayList<>(); dfs(path, list, 0, nums); int sum = 0; for(int i = 0; i < list.size(); i++){ int num = 0; List<Integer> list1 = list.get(i); if(list1.size() == 0){ sum += num; }else{ for(int j = 0; j < list1.size(); j++){ num = num ^ list1.get(j); } } sum = sum + num; } return sum; } public void dfs(List<Integer> path, List<List<Integer>> list, int index, int[] nums){ list.add(new ArrayList<>(path)); if(index == nums.length){ return; } for(int i = index; i < nums.length; i++){ path.add(nums[i]); dfs(path, list, i + 1, nums); path.remove(path.size() - 1); } } }
第二题：5760. 构成交替字符串需要的最小交换次数
题目链接
题目简介：
题目思路
- 我们可以想一下，最终我们需要转化成的
交替子串，只有两种表达方式
- 第一种：101010101
- 第二种：010101010
- 我们分三种情况：
- 第一种：当前字符串中
'0'的个数大于'1'的个数： - 这种情况的话，说明转化成的字符串必定是
'010101010'这种形式，也就是奇数位是'1'，偶数位是'0' - 我们将原来的字符串与
- 这种字符串进行比较，得出错位的
'0'和'1'的个数，假如错误的个数(cnt)相等，那经过cnt次交换即可得到交替字符串。 - 若是不相等：则不可能组成交替字符串
- 第二种：当前字符串中
'1'的个数大于'0'的个数：思路如上
- 第三种：当前字符串中
'0'的个数等于'1'的个数：
- 这样的话，需要对两种都进行遍历，最后求一下最小值。
题目代码
/* 比赛代码，有点粗糙 */ public int minSwaps(String s) { int size = s.length(); int res0 = 0; int res1 = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '0') { res0++; } else { res1++; } } // 假设0的数量大于1的数量 // 01010 // 偶数为0，奇数为1 if (res0 > res1) { int num1 = 0; int num2 = 0; for (int i = 0; i < s.length(); i++) { if (i % 2 == 0 && s.charAt(i) == '1') { num1++; } else if (i % 2 == 1 && s.charAt(i) == '0') { num2++; } } if (num1 == num2) { return num2; } else { return -1; } } // 假设1的数量大于0的数量 // 1010101 // 偶数为1，奇数为0 if (res1 > res0) { int num1 = 0; int num2 = 0; for (int i = 0; i < s.length(); i++) { if (i % 2 == 0 && s.charAt(i) == '0') { num1++; } else if (i % 2 == 1 && s.charAt(i) == '1') { num2++; } } if (num1 == num2) { return num2; } else { return -1; } } // 两种都有可能 if (res0 == res1) { int num1 = 0; int num2 = 0; for (int i = 0; i < s.length(); i++) { if (i % 2 == 0 && s.charAt(i) == '1') { num1++; } else if (i % 2 == 1 && s.charAt(i) == '0') { num2++; } } int num3 = 0; int num4 = 0; for (int i = 0; i < s.length(); i++) { if (i % 2 == 0 && s.charAt(i) == '0') { num3++; } else if (i % 2 == 1 && s.charAt(i) == '1') { num4++; } } if (num1 == num2 && num3 == num4) { return Math.min(num1, num3); } else if (num1 == num2) { return num1; } else if (num3 == num4) { return num3; } else { return -1; } } return -1; }
第三题：5761. 找出和为指定值的下标对
题目链接
题目简介
题目思路
- 题目是一个模拟题，有三种操作：
- 实例化数组：直接赋值即可
- add：将我们
nums2数组的值增加 - count：求
num1和num2中，加起来等于tot的数值对
- 在求数值对的时候，我们可以暴力求解，利用双层for循环，提交的时候会发现超时，我们看给的数据范围：
- 1 <= nums1.length <= 1000
- 1 <= nums2.length <= 10^5
- 最多调用 add 和 count 函数各 1000 次
- 如果我们单纯暴力的话，时间复杂度为：1000 * 1000 * 10^5，直接超时
- 我们来考虑优化，
num1 + num2 = tot，我们要找到num1和num2这两个数，我们不妨换一种思路，当num1时，我们去找有没有等于'tot - num1'的数字。
- 我们将
num2中的元素存入到HashMap中，直接遍历num1寻找map中有没有tot-num1的数字。 - 时间复杂度为：1000 * 1000
题目代码
class FindSumPairs { ArrayList<Integer> list1; ArrayList<Integer> list2; HashMap<Integer, Integer> map; public FindSumPairs(int[] nums1, int[] nums2) { list1 = new ArrayList<>(); list2 = new ArrayList<>(); map = new HashMap(); for(int i = 0; i < nums1.length; i++){ list1.add(nums1[i]); } for(int i = 0; i < nums2.length; i++){ list2.add(nums2[i]); if(map.containsKey(nums2[i])){ int val = map.get(nums2[i]); val++; map.put(nums2[i], val); }else{ map.put(nums2[i], 1); } } } public void add (int index, int val){ int num= list2.get(index); int val2 = map.get(num); val2--; map.put(num, val2); int sum = num + val; list2.set(index, sum); if (map.containsKey(sum)) { int val1= map.get(sum); val1++; map.put(sum, val1); } else { map.put(sum, 1); } } public int count(int tot) { int sum = 0; for(int i = 0; i < list1.size(); i++){ if(map.containsKey(tot - list1.get(i))){ sum += map.get(tot -list1.get(i)); } } return sum; } } /** * Your FindSumPairs object will be instantiated and called as such: * FindSumPairs obj = new FindSumPairs(nums1, nums2); * obj.add(index,val); * int param_2 = obj.count(tot); */
