2021-05-16周赛题解

题目一：找出所有子集的异或总和再求和

方法一：枚举子集

数据范围有限，直接枚举子集计算异或和。

时间复杂度 O(mn)
空间复杂度 O(1)

public int subsetXORSum(int[] nums) {
    int len = nums.length;
    int res = 0;
    for(int i=0;i<(1<<len);i++){
        res += getXOR(nums,i);
    }
    return res;
}
public int getXOR(int[] nums,int i){
    int sum = 0;
    if(i==0) return 0;
    for(int k=0;k<31;k++){
        if((i&k)!=0) sum^= nums[k];
    }
    return sum;
}

题目二：构成交替字符串需要的最小交换次数

方法一：模拟

可以交换：abs(OneN-ZeroN)<=1 否则返回-1

交换次数：字符串只有0，1,最少交换次数一定是最终字符串和当前字符串差异/2

时间复杂度 O(n)
空间复杂度 O(1)

public int minSwaps(String s) {
    int OneN = count(s,'1'),ZeorN = count(s,'0');
    if(Math.abs(OneN-ZeorN)>1) return -1;
    int cnt1 = 0,cnt2 = 0;
    char c;
    for(int i=0;i<s.length();i++){
        if(i%2==0) c = '1';
        else c = '0';
        if(s.charAt(i)!=c) cnt1++;
    }
    for(int i=0;i<s.length();i++){
        if(i%2==0) c = '0';
        else c = '1';
        if(s.charAt(i)!=c) cnt2++;
    }
    if(OneN==ZeorN) return Math.min(cnt1,cnt2)/2;
    if(OneN >ZeorN) return cnt1/2;
    return cnt2/2;
}
public int count(String s,char c){
    int res = 0;
    for(char ch : s.toCharArray()){
        if(ch==c) res++;
    }
    return res;
}

题目三：找出和为指定值的下标对

方法一： hash

设计题，寻找两数之和可以用Map优化查询时间，本题依然可以采用Map优化，关于Add修改数组，只需要修改map即可；

class FindSumPairs {
    int[] nums1;
    int[] nums2;
    Map<Integer,Integer> map;
    public FindSumPairs(int[] nums1, int[] nums2) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        this.map = new HashMap<>();
        for(int i: nums2){
            map.put(i, map.getOrDefault(i,0)+1);
        }
    }

    public void add(int index, int val) {
        int newVal = nums2[index]+val;
        map.put(newVal, map.getOrDefault(newVal,0)+1);
        map.put(nums2[index], map.getOrDefault(nums2[index],0)-1);
    }

    public int count(int tot) {
        int res = 0;
        for(int i:nums1){
            if(map.containsKey(tot-i)){
                res += map.get(tot-i);
            }
        }
        return res;
    }
}

题目四：恰有 K 根木棍可以看到的排列数目

方法一：DP

看大佬题解，应该是常见板子题。思路是：由于数组1-n,选择恰好可以看到k个，就是将n个数分成m个集合，有几种分配方式。

定义：dp[i][j] 为i个数分为j个集合的方案数，dp[i][j] = dp[i-1][j-1] + (i-1)dp[i-1][j], 即：若i-1个数分成了m-1个集合，那么第i个数自己独立成集合，如果i-1个数分配成了m个集合，第i个数任意插入i-1的集合中。

class Solution {
    int MOD = 1000000000+7;
    public int rearrangeSticks(int n, int k) {
        long[][] dp = new long[n+1][n+1];
        dp[0][0] = 1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=Math.min(i,k);j++){
                dp[i][j] = dp[i-1][j-1];
                if(i-1>=j) dp[i][j] += (i-1)*dp[i-1][j];
                dp[i][j] %= MOD; 
            }
        }
        return (int)dp[n][k];
    }
}

Enplee's blog