LeetCode第235场周赛

周赛地址：https://leetcode-cn.com/contest/weekly-contest-235/

第一题：截断句子

题目保证k的取值范围是[1, s 中单词的数目]，所以，split分隔后，取前k个用空格拼接起来即可。

class Solution {
    public String truncateSentence(String s, int k) {
        StringJoiner stringJoiner = new StringJoiner(" ");
        String[] ss = s.split(" ");
        for (int i = 0; i < k; i++) {
            stringJoiner.add(ss[i]);
        }
        return stringJoiner.toString();
    }
}
           

第二题：查找用户活跃分钟数

看懂题意，根据题目描述操作即可。

class Solution {
    public int[] findingUsersActiveMinutes(int[][] logs, int k) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        int[] active = new int[k];
        for (int[] log : logs) {
            Set<Integer> set = map.get(log[0]);
            if (set == null) {
                set = new HashSet<>();
            }
            set.add(log[1]);
            map.put(log[0], set);
        }
        for (Map.Entry<Integer, Set<Integer>> entry : map.entrySet()) {
            active[entry.getValue().size() - 1]++;
        }
        return active;
    }
}
           

第三题：绝对差值和

根据差值直接贪心做替换是错误的思路，题目数据水了，当时用差值直接贪心AC的，是错误的做法，提供一组测试数据并介绍正确的做法，正确的做法是用二分查找+贪心。

Hack数据：nums1=[95,1,2,3,4]，nums2=[100,2,3,4,5]。

已知 S = ∑ i = 0 n − 1 ∣ n u m s 1 [ i ] − n u m s 2 [ i ] ∣ S=\sum\limits_{i=0}^{n-1}|nums1[i]-nums2[i]| S=i=0∑n−1​∣nums1[i]−nums2[i]∣，假设我们任意操作一次，把nums1中的的值a变成nums1中的值b可以使得 S S S变小，原来nums2中和a同下标的值是c，可以知道 ∣ b − c ∣ |b-c| ∣b−c∣是小于 ∣ a − c ∣ |a-c| ∣a−c∣的，那么变化后 S ′ = S − ( ∣ a − c ∣ − ∣ b − c ∣ ) S'=S-(|a-c|-|b-c|) S′=S−(∣a−c∣−∣b−c∣)，要想使得操作后的 S ′ S' S′最小，就要 ∣ a − c ∣ − ∣ b − c ∣ |a-c|-|b-c| ∣a−c∣−∣b−c∣最大，对于某个确定的 i i i，因为 ∣ a − c ∣ |a-c| ∣a−c∣是固定的，就要让 ∣ b − c ∣ |b-c| ∣b−c∣最小，b取自nums1中和c最接近的数字，对每个nums2[i]，在nums1的副本中进行二分查找，查找大于等于nums2[i]的最小值min和小于等于nums2[i]的最大值max，再取 M a t h . m a x ( ∣ a − c ∣ − ∣ n u m s 2 [ i ] − m i n ∣ , ∣ a − c ∣ − ∣ n u m s 2 [ i ] − m a x ∣ ) Math.max(|a-c|-|nums2[i]-min|, |a-c|-|nums2[i]-max|) Math.max(∣a−c∣−∣nums2[i]−min∣,∣a−c∣−∣nums2[i]−max∣)，这就是nums2[i]对应的最大变化代价，对nums2[i]中的所有代价取最大值，让之前的 S S S减去这个最大值，即是答案。

class Solution {
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int length = nums1.length, MOD = 1000000007;
        long cost = 0, result = 0;
        int[] temp = nums1.clone();// 用于排序和二分查找
        Arrays.sort(temp);
        for (int i = 0; i < length; i++) {
            result += Math.abs(nums1[i] - nums2[i]);
        }
        // 找cost的最大值
        for (int i = 0; i < length; i++) {
            int leftBound = left_bound(temp, nums2[i], length), rightBound = right_bound(temp, nums2[i], length);
            if (leftBound != -1) {
                cost = Math.max(cost, Math.abs(nums1[i] - nums2[i]) - Math.abs(temp[leftBound] - nums2[i]));
            }
            if (rightBound != -1) {
                cost = Math.max(cost, Math.abs(nums1[i] - nums2[i]) - Math.abs(temp[rightBound] - nums2[i]));
            }
        }
        return (int) ((result - cost) % MOD);
    }

    private int left_bound(int[] array, int key, int length) {
        int left = 0, right = length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (array[mid] > key) {
                right = mid - 1;
            } else if (array[mid] < key) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left == length ? -1 : left;
    }

    private int right_bound(int[] array, int key, int length) {
        int left = 0, right = length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (array[mid] > key) {
                right = mid - 1;
            } else if (array[mid] < key) {
                left = mid + 1;
            } else {
                left = mid + 1;
            }
        }
        return right == -1 ? -1 : right;
    }
}
           

第四题：序列中不同最大公约数的数目

根据题目描述，最直观，最暴力的解法就是把所有的子序列都找出来，求每个子序列的GCD，然后过一遍set，求set.size()，然而是行不通的。求子序列就是一个指数规模的时间复杂度了，需要换一个角度考虑。

对于原数组中的所有子序列，无论怎么组合，GCD都不会超过数组中的最大值，于是，可以反向考虑，对[1, max]中的每个数字k，试图构造一个子序列，让子序列的GCD=k，如果能找到，计数器累计，继续判断下一个数字，如果找不到，说明不存在这样的子序列，继续判断下一个数字。

那么，什么样的序列，有可能GCD=k呢？子序列中的每个值一定是k的倍数，才有可能GCD=k，当然，也有可能大于k，比如：2k和4k的GCD=2k。所以，要找GCD=k的子序列就找一遍k的倍数，如果能构造出来GCD=k就可以了判断下一个k了。

class Solution {
    public int countDifferentSubsequenceGCDs(int[] nums) {
        BitSet bitSet = new BitSet(200000);
        int max = 0, result = 0;
        // 用于标记nums里有哪些数
        for (int i : nums) {
            bitSet.set(i);
            max = Math.max(i, max);
        }
        // 判断[1, max]范围内每个值，试图找到一个序列，满足GCD==i
        for (int i = 1; i <= max; i++) {
            int gcd = 0;
            // 类似筛法，只有i的整数倍数字的组合，才有可能使得GCD=i，有目的性的查找，缩小查找范围
            for (int j = i; j <= max; j += i) {// j是i的整数倍
                if (bitSet.get(j)) {// j是nums中的元素
                    gcd = gcd(j, gcd);
                    if (gcd == i) {// 已经找到一个GCD==i的组合了
                        result++;
                        break;
                    }
                }
            }
        }
        return result;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}