本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 加入知识星球提问。
T1. 判断一个数是否迷人(Easy)
T2. 找到最长的半重复子字符串(Medium)
T3. 移动机器人(Medium)
T4. 找到矩阵中的好子集(Hard)
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${2n}${3n}".asSequence().sorted().joinToString("")
}
}
复杂度分析:
题目范围中只有 4 个迷人数。
class Solution {
fun isFascinating(n: Int): Boolean {
return n in arrayOf(192, 219, 273, 327)
}
}
复杂度分析:
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
}
}
复杂度分析:
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()
}
}
复杂度分析:
相似题目:
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()
}
}
复杂度分析:
手机扫一扫
移动阅读更方便
你可能感兴趣的文章