LeetCode Contest 355

6921. Split Strings by Separator

给你一个字符串数组 words 和一个字符 separator ，请你按 separator 拆分 words 中的每个字符串。

返回一个由拆分后的新字符串组成的字符串数组，不包括空字符串 。

注意

• separator 用于决定拆分发生的位置，但它不包含在结果字符串中。
• 拆分可能形成两个以上的字符串。
• 结果字符串必须保持初始相同的先后顺序。

测试样例：

输入：words = ["one.two.three","four.five","six"], separator = "."

输出：["one","two","three","four","five","six"

解释：
"one.two.three" 拆分为 "one", "two", "three"

因此，结果数组为 ["one","two","three","four","five","six"] 。

解答：注意Java的spilt存在正则的问题。

class Solution {
    public List<String> splitWordsBySeparator(List<String> words, char separator) {
        List<String> res = new ArrayList<>();
        for (String w : words) {
            StringBuilder tmp = new StringBuilder();
            String s = w + separator;
            for (int i = 0; i < s.length(); ++i) {
                if (s.charAt(i) == separator) {
                    String add = tmp.toString();
                    if (add.length() > 0) {
                        res.add(add);
                    }
                    tmp = new StringBuilder();
                } else {
                    tmp.append(s.charAt(i));
                }
            }
        }
        return res;
    }
}

6915. Largest Element in an Array after Merge Operations

给你一个下标从 0 开始、由正整数组成的数组 nums 。

你可以在数组上执行下述操作 任意 次：

• 选中一个同时满足 0 <= i < nums.length - 1 和 nums[i] <= nums[i + 1] 的整数 i 。将元素 nums[i + 1] 替换为 nums[i] + nums[i + 1] ，并从数组中删除元素 nums[i] 。

返回你可以从最终数组中获得的 最大 元素的值。

测试样例：

输入：nums = [2,3,7,9,3]

输出：21

解释：
我们可以在数组上执行下述操作：

• 选中 i = 0 ，得到数组 nums = [5,7,9,3] 。
• 选中 i = 1 ，得到数组 nums = [5,16,3] 。
• 选中 i = 0 ，得到数组 nums = [21,3] 。

最终数组中的最大元素是 21 。可以证明我们无法获得更大的元素。

解答：按照题意暴力运算就行了

class Solution {
    public long maxArrayValue(int[] nums) {
        long last = 0, max = 0;
        for (int i = nums.length - 1; i >= 0; --i) {
            if (nums[i] <= last) {
                last += nums[i];
            } else {
                last = nums[i];
            }
            max = Math.max(max, last);
        }
        return max;
    }
}

6955. Maximum Number of Groups With Increasing Length

给你一个下标从 0 开始、长度为 n 的数组 usageLimits 。

你的任务是使用从 0 到 n - 1 的数字创建若干组，并确保每个数字 i 在 所有组 中使用的次数总共不超过 usageLimits[i] 次。此外，还必须满足以下条件：

• 每个组必须由 不同 的数字组成，也就是说，单个组内不能存在重复的数字。
• 每个组（除了第一个）的长度必须 严格大于 前一个组。

在满足所有条件的情况下，以整数形式返回可以创建的最大组数。

测试样例

输入：usageLimits = [1,2,5]

输出：3

解释：
在这个示例中，我们可以使用 0 至多一次，使用 1 至多 2 次，使用 2 至多 5 次。一种既能满足所有条件，又能创建最多组的方式是：

1. 组 1 包含数字 [2] 。
2. 组 2 包含数字 [1,2] 。
3. 组 3 包含数字 [0,1,2] 。

可以证明能够创建的最大组数是 3 。
所以，输出是 3 。

解答：这道题目需要利用到排序，二分查找还有一点脑经急转弯。首先利用二分查找来寻找第一个无法满足要求的组数。那么接下来主要难点就是二分查找时候，如何判断当前的组数可以计算出结果。我们先将usageLimits排序一下，然后自后向前遍历。将当前允许的加入的座位数放入，然后依次填入数字就可以了。（如果当前的组数比较小，就会有额外的空位，又因为我们是排序的情况，不会出现同一个组出现2次的情况。）

class Solution {
    public int maxIncreasingGroups(List<Integer> usageLimits) {
        Collections.sort(usageLimits);
        int left = 1, right = usageLimits.size();
        while (left < right) {
            int mid = (left + right + 1) / 2, count = 0;
            for (int i = 0; i < usageLimits.size(); i++) {
                count += Math.max(0, mid - i);
                count -= Math.min(count, usageLimits.get(usageLimits.size() - i - 1));
            }
            if (count == 0) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

6942. Count Paths That Can Form a Palindrome in a Tree

给你一棵 树（即，一个连通、无向且无环的图），根 节点为 0 ，由编号从 0 到 n - 1 的 n 个节点组成。这棵树用一个长度为 n 、下标从 0 开始的数组 parent 表示，其中 parent[i] 为节点 i 的父节点，由于节点 0 为根节点，所以 parent[0] == -1 。

另给你一个长度为 n 的字符串 s ，其中 s[i] 是分配给 i 和 parent[i] 之间的边的字符。s[0] 可以忽略。

找出满足 u < v ，且从 u 到 v 的路径上分配的字符可以 重新排列 形成 回文 的所有节点对 (u, v) ，并返回节点对的数目。

如果一个字符串正着读和反着读都相同，那么这个字符串就是一个 回文 。

测试样例

输入：parent = [-1,0,0,1,1,2], s = "acaabc"

输出：8

解释：符合题目要求的节点对分别是：

• (0,1)、(0,2)、(1,3)、(1,4) 和 (2,5) ，路径上只有一个字符，满足回文定义。
• (2,3)，路径上字符形成的字符串是 "aca" ，满足回文定义。
• (1,5)，路径上字符形成的字符串是 "cac" ，满足回文定义。
• (3,5)，路径上字符形成的字符串是 "acac" ，可以重排形成回文 "acca" 。

解答：回文字符串一般可以利用状态压缩来判断（一个Int，每一位就是当前字符出现的奇偶情况）。然后遍历树，将每个节点的奇偶情况计算出来，最后计算对数就行了。

class Solution {
    public long countPalindromePaths(List<Integer> parent, String s) {
        HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
        for (int i = 0; i < parent.size(); i++) {
            int p = parent.get(i);
            if (!graph.containsKey(p)) {
                graph.put(p, new ArrayList<>());
            }
            graph.get(p).add(i);
        }

        HashMap<Integer, Long> map = new HashMap<>();
        countPalindromePaths(0, 0, s, graph, map);
        long count = 0;
        for (Map.Entry<Integer, Long> entry : map.entrySet()) {
            count += entry.getValue() * (entry.getValue() - 1);
            for (int i = 0; i < 26; i++) {
                count += entry.getValue() * map.getOrDefault(entry.getKey() ^ 1 << i, 0L);
            }
        }
        return count / 2;
    }

    private void countPalindromePaths(int v, int mask, String s, HashMap<Integer, ArrayList<Integer>> graph,
                                      HashMap<Integer, Long> map) {
        map.put(mask, map.getOrDefault(mask, 0L) + 1);
        for (int i : graph.getOrDefault(v, new ArrayList<>())) {
            countPalindromePaths(i, mask ^ 1 << s.charAt(i) - 'a', s, graph, map);
        }
    }
}

这周题目真的很难，尤其是第三道，脑筋转不过来。。。