链接: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
- Leetcode Contest Weekly 355leetcode contest weekly 355 leetcode contest weekly 361 leetcode contest weekly 365 leetcode contest weekly 367 leetcode contest weekly 368 leetcode contest weekly 350 leetcode contest weekly 351 leetcode contest weekly 339 leetcode contest weekly 364 leetcode contest weekly 359