经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 其他 » 职业生涯 » 查看文章
LeetCode 周赛上分之旅 #35 两题坐牢,菜鸡现出原形
来源:cnblogs  作者:彭旭锐  时间:2023/7/24 8:52:36  对本文有异议

?? 本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。

本文是 LeetCode 上分之旅系列的第 35 篇文章,往期回顾请移步到文章末尾~

T1. 按分隔符拆分字符串(Easy)

  • 标签:模拟

T2. 合并后数组中的最大元素(Medium)

  • 标签:贪心

T3. 长度递增组的最大数目(Hard)

  • 标签:排序、贪心

T4. 树中可以形成回文的路径数(Hard)

  • 标签:状态压缩、前缀和、散列表


T1. 按分隔符拆分字符串(Easy)

  1. https://leetcode.cn/problems/split-strings-by-separator/

题解(模拟)

简单模拟题。

  1. class Solution:
  2. def splitWordsBySeparator(self, words: List[str], separator: str) -> List[str]:
  3. ans = []
  4. for x in words:
  5. for y in x.split(separator):
  6. if y != "":
  7. ans.append(y)
  8. return ans

复杂度分析:

  • 时间复杂度:$O(L)$ 其中 $L$ 为字符总数;
  • 空间复杂度:$O(1)$ 不考虑结果数组,仅占用常量级别空间。

T2. 合并后数组中的最大元素(Medium)

  1. https://leetcode.cn/problems/largest-element-in-an-array-after-merge-operations/

题解(贪心)

由于题目操作的前提是 nums[i] ≤ nums[i + 1],因此我们可以优先合并靠后的相邻序列,这样可以保证靠前的更多数能够被合并。如果中间出现 nums[i] 不小于 nums[i + 1] 的情况,说明遇到一个较大的数,它的权重大于后续数组的合并,我们则直接使用这个较大的数。

  1. class Solution:
  2. def maxArrayValue(self, nums: List[int]) -> int:
  3. for i in range(len(nums) - 2, -1, -1):
  4. if (nums[i] <= nums[i + 1]): nums[i] += nums[i + 1]
  5. return nums[0]
  1. class Solution {
  2. fun maxArrayValue(nums: IntArray): Long {
  3. val n = nums.size
  4. var ret = Long.MIN_VALUE
  5. for (i in n - 1 downTo 0) {
  6. if (ret >= nums[i]) {
  7. ret += nums[i]
  8. } else {
  9. ret = nums[i].toLong()
  10. }
  11. }
  12. return ret
  13. }
  14. }

复杂度分析:

  • 时间复杂度:$O(n)$ 线性遍历;
  • 空间复杂度:$O(1)$ 仅使用常量级别空间。

T3. 长度递增组的最大数目(Hard)

  1. https://leetcode.cn/problems/maximum-number-of-groups-with-increasing-length/

题解(排序)

输入数组相当于数字的出现频率,由于题目只关心构造组合的方案数而不关心数字的内容,数字本身是不重要的,因此我们可以先对频率数组排序,并从小到大枚举频率。

在构造的过程中,我们将当前遍历到的频率追加到已经拼接过的分组上(默认存在一个空分组),如果当前的频率不够或者超出,则将剩余元素放到候选容器中,严格证明见灵神的题解。

  1. # 测试用例 [2, 2, 2]
  2. 0 => 0 1 => 0 1 2
  3. 1 1 2
  4. 0
  5. # 测试用例 [1, 2, 5]
  6. 0 => 0 1 => 0 1 2
  7. 1 1 2
  8. 2
  9. # 测试用例 [2, 1, 2] => 排序 [1, 2, 2]
  10. 0 => 0 1 => 0 1 2
  11. 1 1 2
  12. # 测试用例 [1,1]
  13. 0
  14. # 测试用例 [2, 100, 2, 2, 2] => 排序 [2, 2, 2, 2, 100]
  15. 0 => 0 1 => 0 1 2 => 跳过 => 0 1 2 3 => 剩余的 4 可以拼接,但不会产生增加分组数量
  16. 1 1 2 1 2 3
  17. 0 0 4
  18. 4
  1. class Solution {
  2. fun maxIncreasingGroups(usageLimits: List<Int>): Int {
  3. Collections.sort(usageLimits)
  4. var ret = 0
  5. var left = 0L
  6. for (x in usageLimits) {
  7. left += x.toLong()
  8. // 可以构造新分组
  9. if (left >= ret + 1) {
  10. ret ++
  11. left -= ret
  12. }
  13. }
  14. return ret
  15. }
  16. }

复杂度分析:

  • 时间复杂度:$O(nlgn)$ 瓶颈在排序;
  • 空间复杂度:$O(lgn)$ 瓶颈在排序。

T4. 树中可以形成回文的路径数(Hard)

  1. 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」条件的路径,这可以用类似「两数之和」中的散列表的方法求解。

  1. class Solution {
  2. fun countPalindromePaths(parent: List<Int>, s: String): Long {
  3. var ret = 0L
  4. val cnt = HashMap<Int, Int>()
  5. val memo = HashMap<Int, Int>()
  6. // 两数之和模板
  7. for (i in 0 until parent.size) {
  8. val path = getPath(parent, s, memo, i)
  9. // 1、两条路径异或值等于 0 的情况
  10. ret += cnt.getOrDefault(path, 0)
  11. for (j in 0 until 26) {
  12. // 2、两条路径异或值中二进制位 1 只有 1 个的情况
  13. ret += cnt.getOrDefault(path xor 1.shl(j), 0)
  14. }
  15. cnt[path] = cnt.getOrDefault(path, 0) + 1
  16. }
  17. return ret
  18. }
  19. private fun getPath(parent: List<Int>, s: String, memo: MutableMap<Int, Int>, i: Int): Int {
  20. // 终止条件
  21. if (i == 0) return 0
  22. // 读备忘录
  23. if (memo.containsKey(i)) return memo[i]!!
  24. val path = getPath(parent, s, memo, parent[i]) xor (1.shl(s[i] - 'a')) // 增加一个计数等于奇偶性翻转
  25. // 存备忘录
  26. memo[i] = path
  27. return path
  28. }
  29. }

复杂度分析:

  • 时间复杂度:$O(Cn)$ getPath() DFS 的时间复杂度为 $O(n)$,枚举方案的时间复杂度为 $O(Cn)$,其中 $C$ 为字符集大小;
  • 空间复杂度:$O(n)$ 记录每个节点到根节点的路径值空间。

推荐阅读

LeetCode 上分之旅系列往期回顾:

?? 永远相信美好的事情即将发生,欢迎加入小彭的 Android 交流社群~

原文链接:https://www.cnblogs.com/pengxurui/p/17576176.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号