Time: 16, May, 2021. 10:30 — 12:00

Score: 1 / 4 & 3’ / 18’
Rank: 2256 / 4490

P1 : 找出所有子集的异或总和再求和【链接】

输入：

一个普通数组

输出：

数组中所有子集异或的和

思路：

1. 思考子集的概念
   只要满足所有元素都存在于数组中，且个数要大于1， 小于等于数组的长度，那么对于每个元素来说、取或不取都会产生一个新的子集。

2. 递归求解

class Solution {
    int res = 0;
    public int subsetXORSum(int[] nums) {
        for(int i = 0; i < nums.length; ++i)
            dfs(nums, i, -1);
        return res;
    }
    public void dfs(int []nums, int i, int v){
        if(i == nums.length){
            res += v;
            return;
        }
        // 为 0 必须取
        if(v == -1)
            dfs(nums, i + 1, 0 ^ nums[i]);
        else{
            dfs(nums, i + 1, v);            //不取
            dfs(nums, i + 1, v ^ nums[i]);   //取
        }
    }
}

---

P3: 找出和为指定值的下标对【链接】

输入：

构造方法，传入两个数组a和b O r Or Or add方法 O r Or Or count方法

输出:

针对三种不同输入.

1. 类——构造方法 ——构造一个带add方法、count方法的类
2. null ——add方法， 实现add(int b_index, int val) 即 b[b_index] += val
3. 出现次数cnt——count方法，实现count(int val)，即两数组任意两元素和为 v a l val val 的统计个数

思路：

1. 空间溢出待优化思路

定义HashMap， 记录每个 a + b a+b a+b 即 c c c 值出现的次数

a d d add add 时，更新map表，原来的值出现次数减一，更新后的值出现次数加一

c o u n t count count 时，直接返回 m a p map map 的 g e t get get值

优: c o u n t count count 的时候很方便，直接return get的值就行
缺: 太耗空间，没必要将所有的和都存入哈希表

class FindSumPairs {
    int [] a, b;
    int na, nb;
    Map<Integer, Integer> times = new HashMap<>(); // 记录 和为Integer 的出现次数. 
    int [][] ab;
    public FindSumPairs(int[] nums1, int[] nums2) {
        a = nums1; b = nums2;
        na = nums1.length; nb = nums2.length;
        ab = new int[na+1][nb+1];
        for(int i = 0; i < na; ++i)
            for(int j = 0; j < nb; ++j)
                times.put(a[i] + b[j], times.getOrDefault(a[i]+b[j], 0) + 1);
    }
    
    public void add(int index, int val) {
        int pre, now;
        for(int i = 0; i < na; ++i){
            pre = b[index] + a[i]; 
            now = pre + val;
            times.put(pre, times.get(pre) - 1);
            times.put(now, times.getOrDefault(now, 0) + 1);
        }
        b[index] += val;
    }
    
    public int count(int tot) {
        return times.getOrDefault(tot, 0);
    }
}

2. 哈希表存取

在思路1的基础上，更改哈希表存储的k, v。

v 同样是出现次数，而 k 改成 b数组中某个元素的值

key1：

为什么 k e y key key 改成不取 a + b 呢？ 这样 c o u n t count count 的时候不会更麻烦吗？

因为， a + b 的最大可能数为 a.length * b. length ，这样显然是浪费空间而且会空间溢出。

只保存 b 可以省去 a.length 倍的空间，而且在count 的时候，已给出a+b 即 c ，此时只要遍历 a ， 统计 c-b 即 a 出现的次数

key2:

add 该怎么操作？ 只是更改数组b的值就行了吗？

add 是让数组 b b b 的某个元素加上一个数 v a l val val

故要先让 b b b 对应哈希值减去1，再让 b + v a l b + val b+val 后的哈希值 加 1 1 1

class FindSumPairs {
    int [] a, b;
    Map<Integer, Integer> times = new HashMap(); // 记录 值 的出现次数.
    public FindSumPairs(int[] nums1, int[] nums2) {
        a = nums1; b = nums2;
        for(int x : b) 
            times.put(x, times.getOrDefault(x, 0) + 1);
    }
    
    public void add(int index, int val) {
        times.put(b[index], times.get(b[index]) - 1);
        b[index] += val;
        times.put(b[index], times.getOrDefault(b[index], 0) + 1);
    }
    public int count(int tot) {
        int res = 0;
        for(int i = 0; i < a.length; ++i)
            res += times.getOrDefault(tot - a[i], 0);
        return res;
                
    }
}

心得

P3 有点可惜，最后没想到优化空间，直到看了rank全国榜一大佬的ac代码才恍然大悟…

P2是字符串 + 数学排列 操作…目前还没系统化学习，就没A出来，根本就想不到思路，P4没花时间看，是图相关的，因为分值最高肯定难度也最高吧

目前在刷的栈、队列、二叉树 都没涉及到其中，太难啦，希望在以后的日子里能越来越好吧。