I went to bed late last night. I went to bed at 4 o'clock and got up at 10 o'clock to play the game
Question 1: 5759 Find the XOR sum of all subsets and then sum
Title Link
5759. Find the XOR sum of all subsets and sum again
Topic introduction
Topic idea
- Directly find the number of subsets, and then XOR each subset, and finally sum.
Title code
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);
}
}
}
Question 2: 5760 The minimum number of swaps required to form an alternating string
Title Link
5760. Minimum number of exchanges required to form an alternating string
Title Introduction:
Topic idea
- We can think that there are only two ways to express the alternating substring we need to transform into
- First type: 101010101
- Second type: 010101010
- There are three situations:
- First: the number of '0' in the current string is greater than the number of '1':
- In this case, the converted string must be in the form of '010101010', that is, the odd digit is' 1 'and the even digit is' 0'
- We compare the original string with this kind of string to get the number of misplaced '0' and '1'. If the number of errors (cnt) is equal, the alternating string can be obtained after cnt exchange.
- If not equal: it is impossible to form alternating strings
- Second: the number of '1' in the current string is greater than the number of '0': the idea is as follows
- Third: the number of '0' in the current string is equal to the number of '1':
- In this case, you need to traverse both, and finally find the minimum value.
- First: the number of '0' in the current string is greater than the number of '1':
Title code
/*
The game code is a little rough
*/
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++;
}
}
// Suppose the number of 0 is greater than the number of 1
// 01010
// Even number is 0 and odd number is 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;
}
}
// Suppose the number of 1 is greater than the number of 0
// 1010101
// Even number is 1 and odd number is 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;
}
}
// Both are possible
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;
}
Question 3: 5761 Find the subscript pair for the specified value
Title Link
5761. Find and the subscript pair for the specified value
Topic introduction
Topic idea
- The topic is a simulation problem with three operations:
- Instantiate array: assign value directly
- add: increase the value of our nums2 array
- count: find the pair of values in num1 and num2 that add up to tot
- When calculating numerical pairs, we can solve them violently. Using the double-layer for loop, we will find timeout when submitting. The data range we see is:
- 1 <= nums1.length <= 1000
- 1 <= nums2.length <= 10^5
- Up to 1000 calls to the add and count functions
- If we are simply violent, the time complexity is: 1000 * 1000 * 10 ^ 5, direct timeout
- Let's consider optimization. num1 + num2 = tot. We need to find num1 and num2. We might as well change our thinking. When num1, we can find whether there is a number equal to 'tot - num1'.
- We store the elements in num2 into the HashMap and directly traverse num1 to find whether there is a number of tot-num1 in the map.
- Time complexity: 1000 * 1000
Title code
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);
*/