共计 2633 个字符，预计需要花费 7 分钟才能阅读完成。
本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 退出常识星球发问。
- 往期回顾：LeetCode 单周赛第 348 场 · 数位 DP 模版学会了吗？
双周赛 106 概览
T1. 判断一个数是否迷人（Easy）
- 标签：计数
T2. 找到最长的半重复子字符串（Medium）
- 标签：同向双指针
T3. 移动机器人（Medium）
- 标签：脑筋急转弯、排序
T4. 找到矩阵中的好子集（Hard）
- 标签：散列表、贪婪
T1. 判断一个数是否迷人（Easy）
https://leetcode.cn/problems/check-if-the-number-is-fascinating/description/题解一（计数）
- 计算拼接后的数字，并查看数字 1 到 9 的数量是否为 1，能够用字符串比拟来模仿计数；
- 察看数字法则，非法 n 的无效范畴是 [123, 329]。
class Solution {fun isFascinating(n: Int): Boolean {if (n !in 123..329) return false
return "123456789" == "$n${2*n}${3*n}".asSequence().sorted().joinToString("")
}
}复杂度剖析：
- 工夫复杂度：O(UlgU) U 是单个数字的最大长度
- 空间复杂度：O(U)
题解二（打表）
题目范畴中只有 4 个迷人数。
class Solution {fun isFascinating(n: Int): Boolean {return n in arrayOf(192, 219, 273, 327)
}
}复杂度剖析：
- 工夫复杂度：O(1)
- 空间复杂度：O(1)
T2. 找到最长的半重复子字符串（Medium）
https://leetcode.cn/problems/find-the-longest-semi-repetitive-substring/题解（同向双指针）
保护滑动窗口，如果右指针与前一个地位雷同，阐明减少一个相邻反复对。
当相邻反复对 repeatCnt 大于 1 时，此时须要膨胀左指针，如果左指针与左边后一个地位雷同，阐明缩小一个相邻反复对（因为 repeatCnt 大于 1 时左指针不可能超过窗口，所以不须要查看左指针挪动越界）。
class Solution {fun longestSemiRepetitiveSubstring(s: String): Int {
val n = s.length
var ret = 0
var i = 0
var repeatCnt = 0
for (j in 0 until n) {
// 挪动右指针
if (j > 0 && s[j] == s[j - 1]) repeatCnt ++
while (repeatCnt > 1) {
// 挪动左指针
if (s[i] == s[i + 1]) repeatCnt --
i++
}
// 记录后果
ret = Math.max(ret, j - i + 1)
}
return ret
}
}复杂度剖析：
- 工夫复杂度：O(n)
- 空间复杂度：O(1)
T3. 移动机器人（Medium）
https://leetcode.cn/problems/movement-of-robots/题解（模仿 + 排序）
留神到当产生碰撞而扭转机器人方向时，咱们能够对调机器人身份，此时等价于没有产生碰撞且机器人依照失常方向行驶，因而咱们能够间接漠视碰撞规定，计算机器人的最终地位并计算两两间隔。
为了计算两两间隔，咱们先对所有点排序。因为两个机器人的间隔公式是 x – y，那么对于每个机器人 nums[i]，在间隔公式中它将作为 i 次 x 做加法，以及作为 (n -1 – i) 次 y 做解法，能够枚举每个机器人对间隔公式的贡献度而算出整体的两两间隔和。
class Solution {fun sumDistance(nums: IntArray, s: String, d: Int): Int {
val n = nums.size
val MOD = 1000000007
// 挪动（漠视碰撞）for (i in nums.indices) {nums[i] += if (s[i] == 'R') d else -d
}
// 排序
nums.sort()
// 计算两两间隔
var ret = 0L
for (i in nums.indices) {ret = (ret + (2L * i - n + 1) * nums[i]) % MOD
}
return ret.toInt()}
}复杂度剖析：
- 工夫复杂度：O(nlgn) 瓶颈在排序
- 空间复杂度：O(lgn)
类似题目：
- 1503. 所有蚂蚁掉下来前的最初一刻
T4. 找到矩阵中的好子集（Hard）
https://leetcode.cn/problems/find-a-good-subset-of-the-matrix/题解（散列 + 贪婪）
容易想到，咱们须要抉择出 1 绝对稠密的那些行（但不肯定是最稠密的行），而且反复抉择完全相同的行不会对后果产生价值，所以咱们先对行去重。
因为题目最多只有 5 列，所有最多只有 2^5=32 种行类型，能够证实题目在 n = 5 的状况下，无效解最多只有 2 行。
class Solution {fun goodSubsetofBinaryMatrix(grid: Array<IntArray>): List<Int> {
val n = grid.size
val m = grid[0].size
// 分组
val U = 32 // 0 - 31
val indexs = IntArray(U) {-1}
for ((i, row) in grid.withIndex()) {
var mask = 0
for ((j, e) in row.withIndex()) {mask = mask or (e shl j)
}
indexs[mask] = i
}
// 全 0
if (-1 != indexs[0]) return listOf(indexs[0])
// 贪婪
for (x in 1 until U) {for (y in 1 until U) {
// 过滤
if (-1 == indexs[x] || -1 == indexs[y]) continue
// 是否互补
if (x and y == 0) return listOf(indexs[x], indexs[y]).sorted()}
}
return Collections.emptyList()}
}复杂度剖析：
- 工夫复杂度：O(n + U^2) U = 32
- 空间复杂度：O(U)
往期回顾
- LeetCode 单周赛第 348 场 · 数位 DP 模版学会了吗？
- LeetCode 单周赛第 347 场 · 二维空间上的 LIS 最长递增子序列问题
- LeetCode 双周赛第 104 场 · 流水的动静布局，铁打的结构化思考
- LeetCode 双周赛第 103 场 · 区间求和的树状数组经典利用
正文完
