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 包含数字 [2] 。
- 组 2 包含数字 [1,2] 。
- 组 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);
}
}
}这周题目真的很难，尤其是第三道，脑筋转不过来。。。