【蓝湖专场】力扣第 241 场周赛(1262 / 4490)

深碍√TFBOYSˉ_ 2023-01-21 13:22 8阅读 0赞

> 昨天晚上睡晚了，4点睡的，10点爬起来晕乎乎的打比赛

### 文章目录 ###

*   *   *  第一题：5759. 找出所有子集的异或总和再求和
         *   *  题目链接
             *  题目简介
             *  题目思路
             *  题目代码
         *  第二题：5760. 构成交替字符串需要的最小交换次数
         *   *  题目链接
             *  题目简介：
             *  题目思路
             *  题目代码
         *  第三题：5761. 找出和为指定值的下标对
         *   *  题目链接
             *  题目简介
             *  题目思路
             *  题目代码

### 第一题：5759. 找出所有子集的异或总和再求和 ###

#### 题目链接 ####

[5759. 找出所有子集的异或总和再求和][5759.]

#### 题目简介 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]

#### 题目思路 ####

*  直接爆搜出子集的个数，然后对每一个子集进行异或操作，最终进行求和。

#### 题目代码 ####

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. 构成交替字符串需要的最小交换次数 ###

#### 题目链接 ####

[5760. 构成交替字符串需要的最小交换次数][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. 找出和为指定值的下标对 ###

#### 题目链接 ####

[5761. 找出和为指定值的下标对][5761.]

#### 题目简介 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 1]

#### 题目思路 ####

*  题目是一个模拟题，有三种操作：
    
     *  实例化数组：直接赋值即可
     *  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);
     */

[5759.]: https://leetcode-cn.com/problems/sum-of-all-subset-xor-totals/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]: /images/20221020/ad978422fe5f4f37a4871235cfa64958.png
[5760.]: https://leetcode-cn.com/problems/minimum-number-of-swaps-to-make-the-binary-string-alternating/
[-]: /images/20221020/3c320566c4344d45b577442be9c21e6f.png
[5761.]: https://leetcode-cn.com/problems/finding-pairs-with-a-certain-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 1]: /images/20221020/afaf14e51d2b49be88bd87d0de3ec720.png