LeetCode Contest 399

欢迎大家加QQ群：623375442，可以方便群里面交流。

100326. String Compression III

给你一个字符串 word，请你使用以下算法进行压缩：

• 从空字符串 comp 开始。当 word 不为空 时，执行以下操作：
  • 移除 word 的最长单字符前缀，该前缀由单一字符 c 重复多次组成，且该前缀长度 最多 为 9 。
  • 将前缀的长度和字符 c 追加到 comp 。
    返回字符串 comp 。

测试样例：

输入：word = "abcde"

输出："1a1b1c1d1e"

解释：初始时，comp = "" 。进行 5 次操作，每次操作分别选择 "a"、"b"、"c"、"d" 和 "e" 作为前缀。对每个前缀，将 "1" 和对应的字符追加到 comp。

解答：按照题意hard code。

class Solution {
    public String compressedString(String word) {
        StringBuilder sb = new StringBuilder();
        int pos = 0;
        while (pos < word.length()) {
            char c = word.charAt(pos);
            int count = 0, remain = 9;
            while (pos < word.length() && word.charAt(pos) == c && remain > 0) {
                ++pos;
                ++count;
                remain -= 1;
            }
            sb.append(count);
            sb.append(c);
        }
        return sb.toString();
    }
}

100321. Find the Number of Good Pairs II

给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。

如果 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为 优质数对（0 <= i <= n - 1, 0 <= j <= m - 1）。

返回 优质数对 的总数。

测试样例：

输入：nums1 = [1,3,4], nums2 = [1,3,4], k = 1

输出：5

解释：5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。

解答：需要逆向思维，对nums1的数字进行质因数分解，并查看哪些数字可以通过这些质因数组合出来。最后查表加上在nums2中的数字出现个数。

class Solution {
    public long numberOfPairs(int[] nums1, int[] nums2, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int n : nums2) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }
        long res = 0;
        for (int n : nums1) {
            if (n % k != 0) {
                continue;
            }
            n /= k;
            // 质因数分解
            HashMap<Integer, Integer> mul = new HashMap<>();
            for (int i = 2; i * i <= n; ++i) {
                while (n % i == 0) {
                    n /= i;
                    mul.put(i, mul.getOrDefault(i, 0) + 1);
                }
            }
            if (n != 1) {
                mul.put(n, mul.getOrDefault(n, 0) + 1);
            }
            List<Integer> distinct = new ArrayList<>(mul.keySet());
            res += dfs(mul, distinct, 0, 1, new HashSet<>(), map);
        }
        return res;
    }

    // 查看所有可以用这些质数产出的数字
    private int dfs(HashMap<Integer, Integer> mul, List<Integer> list, int pos, int path, Set<Integer> set, HashMap<Integer, Integer> map) {
        if (pos == list.size()) {
            if (!set.contains(path)) {
                set.add(path);
                return map.getOrDefault(path, 0);
            } else {
                return 0;
            }
        } else {
            int res = 0;
            for (int i = 0; i <= mul.get(list.get(pos)); ++i) {
                res += dfs(mul, list, pos + 1, path, set, map);
                path *= list.get(pos);
            }
            return  res;
        }
    }
}

100306. Maximum Sum of Subsequence With Non-adjacent Elements

给你一个整数数组 nums 和一个二维数组 queries，其中 queries[i] = [posi, xi]。

对于每个查询 i，首先将 nums[posi] 设置为 xi，然后计算查询 i 的答案，该答案为 nums 中 不包含相邻元素 的子序列的 最大 和。

返回所有查询的答案之和。

由于最终答案可能非常大，返回其对 10^9 + 7 取余 的结果。

子序列 是指从另一个数组中删除一些或不删除元素而不改变剩余元素顺序得到的数组。

测试样例：

输入：nums = [3,5,9], queries = [[1,-2],[0,-3]]

输出：21

解释：执行第 1 个查询后，nums = [3,-2,9]，不包含相邻元素的子序列的最大和为 3 + 9 = 12。执行第 2 个查询后，nums = [-3,-2,9]，不包含相邻元素的子序列的最大和为 9 。

解答：能AC，但是应该是不对的。等看看更好的算法吧。

class Solution {
    private static final int mod = 1_000_000_007;

    public int maximumSumSubsequence(int[] nums, int[][] queries) {
        long res = 0;
        for (int[] q : queries) {
            nums[q[0]] = q[1];
            res = (res + findResult(nums)) % mod;
        }
        return (int) res;
    }

    private long findResult(int[] nums) {
        int l1 = 0, l2 = 0;
        for (int n : nums) {
            int tmp = l2;
            l2 = Math.max(Math.max(n, 0) + l1, l2);
            l1 = tmp;
        }
        return l2;
    }
}