[Leetcode Weekly Contest]355

链接：LeetCode

[Leetcode]6921. 按分隔符拆分字符串

给你一个字符串数组 words 和一个字符 separator ，请你按 separator 拆分 words 中的每个字符串。
返回一个由拆分后的新字符串组成的字符串数组，不包括空字符串 。
注意

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

遍历split即可，注意在Java中split默认是regex类型，需要加转义"\\".

class Solution {
    public List<String> splitWordsBySeparator(List<String> words, char separator) {
        List<String> res = new ArrayList<>();
        for(String word: words) {
            for(String subWord: word.split("\\"+separator)) {
                if(!subWord.isEmpty())res.add(subWord);
            }
        }
        return res;
    }
}

[Leetcode]2789. 合并后数组中的最大元素

给你一个下标从 0 开始、由正整数组成的数组 nums 。
你可以在数组上执行下述操作 任意 次：

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

返回你可以从最终数组中获得的 最大 元素的值。
从后往前遍历数组，设置一个迭代变量last，如果last>=nums[i],则迭代变量last+=nums[i]，否则last=nums[i]，在遍历过程中更新res

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

[Leetcode]6955. 长度递增组的最大数目

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

• 每个组必须由 不同 的数字组成，也就是说，单个组内不能存在重复的数字。
• 每个组（除了第一个）的长度必须 严格大于 前一个组。
  在满足所有条件的情况下，以整数形式返回可以创建的最大组数。

二分+贪心。对于一个给定的usageLimits，我们只在乎usageLimits中数字的大小，并不在乎它实际所对应的值是多少，假设我们要满足groups=3，则最小目标序列为[3,2,1]，满足要求的usageLimits可以为[4,5,6],[3,2,1,5]... 问题可以重新描述为，对于一个给定的usageLimits和groups，能否从usageLimits中找到对应的最小目标序列target，然后对groups进行二分即可。

class Solution {
    private boolean check(List<Integer> usageLimits, int n) {
        int needed = 0;
        int cur = n;
        for(int usageLimit: usageLimits) {
            if(usageLimit < cur) needed += cur - usageLimit;
            else needed -= Math.min(needed, usageLimit-cur);
            if(cur > 0) cur -- ;
        }
        return needed == 0;
    }


    public int maxIncreasingGroups(List<Integer> usageLimits) {
        Collections.sort(usageLimits, (a,b) -> b-a);
        int lo = 1, hi = usageLimits.size();
        while(lo <= hi) {
            int mid = lo+((hi-lo) >> 1);
            if(check(usageLimits, mid)) lo = mid+1;
            else hi = mid - 1;
        }
        return hi;
    }
}

[Leetcode]2791. 树中可以形成回文的路径数

给你一棵 树（即，一个连通、无向且无环的图），根 节点为 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) ，并返回节点对的数目。
如果一个字符串正着读和反着读都相同，那么这个字符串就是一个 回文 。

位运算处理, 回文串等价于至多一个字母出现奇数次，其余字母出现偶数次。

class Solution:
    def countPalindromePaths(self, parent: List[int], s: str) -> int:
        n = len(s)
        g = [[] for _ in range(n)]
        for i in range(1, n):
            g[parent[i]].append(i)

        ans = 0
        cnt = Counter([0])  # 一条「空路径」
        def dfs(v: int, xor: int) -> None:
            nonlocal ans
            for w in g[v]:
                bit = 1 << (ord(s[w]) - ord('a'))
                x = xor ^ bit
                ans += cnt[x] + sum(cnt[x ^ (1 << i)] for i in range(26))
                cnt[x] += 1
                dfs(w, x)
        dfs(0, 0)
        return ans

参考：LeetCode