【记录】 T2. LeetCode第241场周赛

【记录】 T2. LeetCode第241场周赛

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+bc ,此时只要遍历 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没花时间看,是图相关的,因为分值最高肯定难度也最高吧

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

上一篇:双周赛 52,单周赛 241 题解


下一篇:【蓝湖专场】力扣第 241 场周赛