当前位置：首页 > news >正文

网站建设开发计划模板/友情下载网站

news 2025/7/1 14:29:14

网站建设开发计划模板,友情下载网站,重庆做网站的公司,哪些网站做的比较炫本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。往期回顾：LeetCode 单周赛第 348 场数位 DP 模版学会了吗？ T1. 美丽下标对的数目（Easy） 标签&am…

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

往期回顾：LeetCode 单周赛第 348 场 · 数位 DP 模版学会了吗？

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 = 0for (i in nums.indices) {var x = nums[i]while (x >= 10) x /= 10for (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 = xvar b = ywhile (b != 0) {val temp = a % ba = bb = temp}return a}
}

复杂度分析：

时间复杂度： $O(n^2)$
空间复杂度： $O (1)$

题解二（计数 + 数学）

线性扫描数组，同时检查前驱中匹配的配对数。由于题目只考虑前驱数字的最高位和当前位置的最低位，我们可以维护前驱数字的最高位出现次数。

class Solution {fun countBeautifulPairs(nums: IntArray): Int {var ret = 0val 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 /= 10cnt[x]++}return ret}private fun gcb(x: Int, y: Int) : Int {var a = xvar b = ywhile (b != 0) {val temp = a % ba = bb = temp}return a}
}

复杂度分析：

时间复杂度： $O (C \cdot n)$ 其中 C = 10；
空间复杂度： $O (C)$

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 = 1while (true) {val x = num1 - 1L * k * num2if (k > x) return -1if (k >= java.lang.Long.bitCount(x)) return kk++}}
}

class Solution {fun makeTheIntegerZero(num1: Int, num2: Int): Int {var k = 1var x = 1L * num1while (true) {x -= num2if (k > x) return -1if (k >= java.lang.Long.bitCount(x)) return kk++}}
}

复杂度分析：

时间复杂度： $O (l gx)$
空间复杂度： $O (1)$

T3. 得到整数零需要执行的最少操作数（Medium）

https://leetcode.cn/problems/ways-to-split-array-into-good-subarrays/

题解（分组 + 乘法原理）

以数字 1 为分割线，将每段连续的 0 分为一组，再用乘法原理计算总方案数。

class Solution {fun numberOfGoodSubarraySplits(nums: IntArray): Int {// 分组 + 乘法原理val MOD = 1000000007var ret = 1Lvar pre1 = -1for ((i, num) in nums.withIndex()) {if (num == 0) continueif (pre1 != -1) ret = ret * (i - pre1) % MODpre1 = i}return if (pre1 == -1) 0 else ret.toInt()}
}

复杂度分析：

时间复杂度： $O (n)$
空间复杂度： $O (1)$

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]) {// 栈顶健康度 -1if (--healths[topId] == 0) stack.poll()continue@outer} else if(healths[topId] < healths[id]) {// 弹出栈顶healths[id] -= 1stack.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}
}