⭐️ 本文已收录到 AndroidFamily,技术和职场问题,请重视公众号 [彭旭锐] 和 [BaguTree Pro] 常识星球提问。
学习数据结构与算法的要害在于掌握问题背面的算法思维框架,你的考虑越笼统,它能掩盖的问题域就越广,了解难度也更复杂。在这个专栏里,小彭与你共享每场 LeetCode 周赛的解题陈述,一同体会上分之旅。
本文是 LeetCode 上分之旅系列的第 35 篇文章,往期回顾请移步到文章结束~
T1. 按分隔符拆分字符串(Easy)
- 标签:仿照
T2. 吞并后数组中的最大元素(Medium)
- 标签:贪心
T3. 长度递加组的最大数目(Hard)
- 标签:排序、贪心
T4. 树中可以形成回文的途径数(Hard)
- 标签:情况紧缩、前缀和、散列表
T1. 按分隔符拆分字符串(Easy)
https://leetcode.cn/problems/split-strings-by-separator/
题解(仿照)
简单仿照题。
class Solution:
def splitWordsBySeparator(self, words: List[str], separator: str) -> List[str]:
ans = []
for x in words:
for y in x.split(separator):
if y != "":
ans.append(y)
return ans
复杂度分析:
- 时间复杂度:O(L)O(L) 其间 LL 为字符总数;
- 空间复杂度:O(1)O(1) 不考虑效果数组,仅占用常量等级空间。
T2. 吞并后数组中的最大元素(Medium)
https://leetcode.cn/problems/largest-element-in-an-array-after-merge-operations/
题解(贪心)
由于标题操作的前提是 nums[i] ≤ nums[i + 1],因此我们可以优先吞并靠后的相邻序列,这样可以保证靠前的更大都可以被吞并。假设中心出现 nums[i] 不小于 nums[i + 1] 的情况,阐明遇到一个较大的数,它的权重大于后续数组的吞并,我们则直接运用这个较大的数。
class Solution:
def maxArrayValue(self, nums: List[int]) -> int:
for i in range(len(nums) - 2, -1, -1):
if (nums[i] <= nums[i + 1]): nums[i] += nums[i + 1]
return nums[0]
class Solution {
fun maxArrayValue(nums: IntArray): Long {
val n = nums.size
var ret = Long.MIN_VALUE
for (i in n - 1 downTo 0) {
if (ret >= nums[i]) {
ret += nums[i]
} else {
ret = nums[i].toLong()
}
}
return ret
}
}
复杂度分析:
- 时间复杂度:O(n)O(n) 线性遍历;
- 空间复杂度:O(1)O(1) 仅运用常量等级空间。
T3. 长度递加组的最大数目(Hard)
https://leetcode.cn/problems/maximum-number-of-groups-with-increasing-length/
题解(排序)
输入数组相当于数字的出现频率,由于标题只关心构造组合的方案数而不关心数字的内容,数字自身是不重要的,因此我们可以先对频率数组排序,并从小到大枚举频率。
在构造的过程中,我们将其时遍历到的频率追加到现已拼接过的分组上(默认存在一个空分组),假设其时的频率不行或许超出,则将剩下元素放到候选容器中,严厉证明见灵神的题解。
# 测试用例 [2, 2, 2]
0 => 0 1 => 0 1 2
1 1 2
# 测试用例 [1, 2, 5]
0 => 0 1 => 0 1 2
1 1 2
2
# 测试用例 [2, 1, 2] => 排序 [1, 2, 2]
0 => 0 1 => 0 1 2
1 1 2
# 测试用例 [1,1]
# 测试用例 [2, 100, 2, 2, 2] => 排序 [2, 2, 2, 2, 100]
0 => 0 1 => 0 1 2 => 越过 => 0 1 2 3 => 剩下的 4 可以拼接,但不会发生添加分组数量
1 1 2 1 2 3
0 0 4
4
class Solution {
fun maxIncreasingGroups(usageLimits: List<Int>): Int {
Collections.sort(usageLimits)
var ret = 0
var left = 0L
for (x in usageLimits) {
left += x.toLong()
// 可以构造新分组
if (left >= ret + 1) {
ret ++
left -= ret
}
}
return ret
}
}
复杂度分析:
- 时间复杂度:O(nlgn)O(nlgn) 瓶颈在排序;
- 空间复杂度:O(lgn)O(lgn) 瓶颈在排序。
T4. 树中可以形成回文的途径数(Hard)
https://leetcode.cn/problems/count-paths-that-can-form-a-palindrome-in-a-tree/
题解(情况紧缩 + 前缀和 + 散列表)
1、回文判别: 首要,由于标题的回文串判别允许重排,因此回文串的 check 可以转换为字母的计数:
- 出现次数为奇数的字母最多只能出现 1 个;
- 出现次数为偶数的字母可以出现任意次。
2、奇偶性: 其次,由于标题的数组仅为小写字母,我们可以运用一个整型来紧缩标明 26 个字母的出现次数情况,0 标明出现次数为偶数,1 标明出现次数为奇数。例如 0001 标明 ‘a’ 字母的出现次数为奇数,其他字母的出现次数为偶数(可能未出现)。
3、情况紧缩: 基于以上 2 点,我们的方针是在树上找到两个点的途径 [u, v] 使得途径的情况 mask 满足以下其间 1 个条件:
- mask == 0:阐明一切字母都出现偶数次;
- mask & (mask – 1) == 0:阐明二进制位中 1 的出现次数为 1 次,即只需一个字母出现奇数次。
4、前缀和: 那么,假设怎样求树上两点间的途径?这里有一个技巧,假设直接收集两个点之间的途径信息很难,我们可以先求从根节点到 u 的途径 root_u,以及从根节点到 v 的途径 root_v,再将两段途径异或就可以得到 u 到 v 的途径(假设两个节点的 LCA 不是根节点,那么重复的途径会被异或消除)。以标题示例 1 中节点 3 和节点 4 为例:path_3 = 0101,path_4 = 0110,而 path_3 xor path_4 = 0011,即 “ab”。
5、两数之和: 最终,我们的方针就变成:寻找从到根节点的途径异或值满足「分析 3」条件的途径,这可以用类似「两数之和」中的散列表的办法求解。
class Solution {
fun countPalindromePaths(parent: List<Int>, s: String): Long {
var ret = 0L
val cnt = HashMap<Int, Int>()
val memo = HashMap<Int, Int>()
// 两数之和模板
for (i in 0 until parent.size) {
val path = getPath(parent, s, memo, i)
// 1、两条途径异或值等于 0 的情况
ret += cnt.getOrDefault(path, 0)
for (j in 0 until 26) {
// 2、两条途径异或值中二进制位 1 只需 1 个的情况
ret += cnt.getOrDefault(path xor 1.shl(j), 0)
}
cnt[path] = cnt.getOrDefault(path, 0) + 1
}
return ret
}
private fun getPath(parent: List<Int>, s: String, memo: MutableMap<Int, Int>, i: Int): Int {
// 停止条件
if (i == 0) return 0
// 读备忘录
if (memo.containsKey(i)) return memo[i]!!
val path = getPath(parent, s, memo, parent[i]) xor (1.shl(s[i] - 'a')) // 添加一个计数等于奇偶性翻转
// 存备忘录
memo[i] = path
return path
}
}
复杂度分析:
- 时间复杂度:O(Cn)O(Cn) getPath() DFS 的时间复杂度为 O(n)O(n),枚举方案的时间复杂度为 O(Cn)O(Cn),其间 CC 为字符集大小;
- 空间复杂度:O(n)O(n) 记载每个节点到根节点的途径值空间。
举荐阅读
LeetCode 上分之旅系列往期回顾:
- LeetCode 单周赛第 354 场 摩尔投票派上用场
- LeetCode 单周赛第 353 场 看似没考 LIS 最长递加子序列,如同又考了
- LeetCode 双周赛第 109 场 故步自封地处理动态规划问题
- LeetCode 双周赛第 107 场 很有意思的 T2 题
⭐️ 永远信任美好的工作即将发生,欢迎参加小彭的 Android 交流社群~