T1. 美丽下标对的数目（Easy）
- 标签：计数 + 数学
T2. 得到整数零需要执行的最少操作数（Medium）
- 标签：数学
T3. 得到整数零需要执行的最少操作数（Medium）
- 标签：乘法原理
T4. 机器人碰撞（Hard）
- 标签：栈
T1. 美丽下标对的数目（Easy）
https://leetcode.cn/problems/number-of-beautiful-pairs/
题解一（暴力）
两层扫描，同时检查前驱中匹配的配对数。
class Solution {
fun countBeautifulPairs(nums: IntArray): Int {
var ret = 0
for (i in nums.indices) {
var x = nums[i]
while (x >= 10) x /= 10
for (j in i + 1 until nums.size) {
if (gcb(nums[j] % 10, x) == 1) ret++
}
}
return ret
}
private fun gcb(x: Int, y: Int) : Int {
var a = x
var b = y
while (b != 0) {
val temp = a % b
a = b
b = temp
}
return a
}
}
复杂度分析：
- 时间复杂度：
- 空间复杂度：
题解二（计数 + 数学）
线性扫描数组，同时检查前驱中匹配的配对数。由于题目只考虑前驱数字的最高位和当前位置的最低位，我们可以维护前驱数字的最高位出现次数。
class Solution {
fun countBeautifulPairs(nums: IntArray): Int {
var ret = 0
val cnt = IntArray(10)
for (i in nums.indices) {
for (j in 1 .. 9) {
if (cnt[j] > 0 && gcb(nums[i] % 10, j) == 1) ret += cnt[j]
}
var x = nums[i]
while (x >= 10) x /= 10
cnt[x]++
}
return ret
}
private fun gcb(x: Int, y: Int) : Int {
var a = x
var b = y
while (b != 0) {
val temp = a % b
a = b
b = temp
}
return a
}
}
复杂度分析：
- 时间复杂度：
其中 C = 10；
- 空间复杂度：
T2. 得到整数零需要执行的最少操作数（Medium）
https://leetcode.cn/problems/minimum-operations-to-make-the-integer-zero/
这道题的思维难度比较高。
同时考虑 2^i 和 nums2 不好处理，我们可以尝试分别处理：观察示例 1（最小操作次数为 3），如果我们先对 num1 减去 3 次 nums2，则得到二进制 1101，正好可以通过减去 3 次 2^i 清零（-1、-4 和 -8）。
// 0011 + 2
// => 0101 + 2
// => 0111 + 2
// => 1101 (-1 - 4 - 8)
因此，我们假设操作 k 次后可以消除 num1，那么需要有 nums1 - knum2 的二进制位正好存在 k 个 1，此时就可以用 k 次 2^i 消除。那么我们的问题就转换为是否存在 k，使得 nums1 - knums2 的二进制位中 1 的个数为 k。
if (k == (nums1 - k * nums2).bitCount()) return true
然而，这个思路是有陷阱的，比如说操作 4 次后的二进制位中 1 的个数只有 3 个，按照上面的思路是非法的，但事实上我们依然可以通过操作 4 次来清零（-1、-4、-8 ⇒ 将 -8 拆分为 2 次 -4，总的操作次数就是 -1、-4、-4、-4）；
- 最少操作次数：每次将二进制位中的 1 消除；
- 最多操作次数：每次减 1。
综上所述，令 x 为 num1 - k * num2，y 为 x 二进制位中 1 的个数，从 1 开始枚举 k，那么当满足 y ≤ k 且 x ≥ k 时，必然可以通过 k 次操作清零。
// 0001 + 2
// => 0011 + 2
// => 0101 + 2
// => 0111 + 2
// => 1101
最后一个问题，复杂度怎么算，显然取决于 k 的上界：
- 当 num2 == 0 时，操作次数直接等于 num1 二进制位中 1 的个数，最大操作次数是 log(num1)；
- 当 num2 > 0 或 num2 < 0 时，算法在 k ≥ bitCount(x) 时终止，最大操作次数是 log(x)。
class Solution {
fun makeTheIntegerZero(num1: Int, num2: Int): Int {
var k = 1
while (true) {
val x = num1 - 1L * k * num2
if (k > x) return -1
if (k >= java.lang.Long.bitCount(x)) return k
k++
}
}
}
class Solution {
fun makeTheIntegerZero(num1: Int, num2: Int): Int {
var k = 1
var x = 1L * num1
while (true) {
x -= num2
if (k > x) return -1
if (k >= java.lang.Long.bitCount(x)) return k
k++
}
}
}
复杂度分析：
- 时间复杂度：
- 空间复杂度：
T3. 得到整数零需要执行的最少操作数（Medium）
https://leetcode.cn/problems/ways-to-split-array-into-good-subarrays/
题解（分组 + 乘法原理）
以数字 1 为分割线，将每段连续的 0 分为一组，再用乘法原理计算总方案数。
class Solution {
fun numberOfGoodSubarraySplits(nums: IntArray): Int {
// 分组 + 乘法原理
val MOD = 1000000007
var ret = 1L
var pre1 = -1
for ((i, num) in nums.withIndex()) {
if (num == 0) continue
if (pre1 != -1) ret = ret * (i - pre1) % MOD
pre1 = i
}
return if (pre1 == -1) 0 else ret.toInt()
}
}
复杂度分析：
- 时间复杂度：
- 空间复杂度：
T4. 机器人碰撞（Hard）
https://leetcode.cn/problems/robot-collisions/
题解（栈）
这道题与经典题 735. 行星碰撞 几乎是一样的。
我们使用栈模拟保留的机器人，枚举机器人，当机器人与栈顶方向冲突时按规则消除，最后输出栈内剩余的机器人。
class Solution {
fun survivedRobotsHealths(positions: IntArray, healths: IntArray, directions: String): List<Int> {
// 排序
val indexs = Array(positions.size) { it }
Arrays.sort(indexs) { i1, i2 ->
positions[i1] - positions[i2]
}
// 模拟 <index>
val stack = ArrayDeque<Int>()
outer@ for (id in indexs) {
// 当前机器人向右，不会发生碰撞
if (directions[id] == 'R') {
stack.push(id)
continue
}
while (!stack.isEmpty() && directions[stack.peek()] == 'R') {
var topId = stack.peek()
if (healths[topId] > healths[id]) {
// 栈顶健康度 -1
if (--healths[topId] == 0) stack.poll()
continue@outer
} else if(healths[topId] < healths[id]) {
// 弹出栈顶
healths[id] -= 1
stack.poll()
} else {
// 弹出栈顶
stack.poll()
continue@outer
}
}
if (healths[id] > 0) stack.push(id)
// println(stack.joinToString())
}
// 输出
val ret = stack.toMutableList()
ret.sort() // 题目要求按照原位置顺序输出
for (i in ret.indices) {
ret[i] = healths[ret[i]]
}
return ret
}
}
复杂度分析：
- 时间复杂度：
瓶颈在排序上；
- 空间复杂度：
栈空间。
网友评论