LeetCode 周赛 351(2023/06/25)T2 有点意思

leetcode,t2,有点,意思 · 浏览次数 : 14

小编点评

**时间复杂度:O(lgx)** **空间复杂度:O(1)** **算法思路:** 1. 使用双向搜索 (BFS) 或栈模拟机器人遍历数组。 2. 每次扩展时,检查机器人是否已在所有可行的路径中,如果已在,则返回 -1,否则继续拓展。 3. 如果机器人能从数组中完全消除所有数字,则返回 0。 4. 如果机器人已经无法从数组中完全消除所有数字,则从数组中找出最近的 1,并将它从机器人中删除。 5. 如果所有机器人都已无法从数组中完全消除所有数字,则返回 -1。 6. 否则,返回已找到的路径数量。

正文

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

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
    }
}

复杂度分析:

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

题解二(计数 + 数学)

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

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
    }
}

复杂度分析:

  • 时间复杂度:$O(C·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 = 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++
        }
    }
}

复杂度分析:

  • 时间复杂度:$O(lgx)$
  • 空间复杂度:$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 = 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()
    }
}

复杂度分析:

  • 时间复杂度:$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]) {
                    // 栈顶健康度 -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
    }
}

复杂度分析:

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

往期回顾

与LeetCode 周赛 351(2023/06/25)T2 有点意思相似的内容:

LeetCode 周赛 351(2023/06/25)T2 有点意思

> **本文已收录到 [AndroidFamily](https://github.com/pengxurui/AndroidFamily),技术和职场问题,请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。** - 往期回顾:[LeetCode 单周赛第 348 场 · 数

LeetCode 周赛(2023/07/08)渐入佳境

> **本文已收录到 [AndroidFamily](https://github.com/pengxurui/AndroidFamily),技术和职场问题,请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。** - 往期回顾:[LeetCode 单周赛第 351 场 · 一

LeetCode 周赛 332,在套路里摸爬滚打~

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,今天是 3T 选手小彭。 上周是 LeetCode 第 332 场周赛,你参加了吗?算法解题思维需要长时间锻炼,加入我们一起刷题吧~ 小彭的 Android 交流群 02 群已经建立啦,公众号回复 “

LeetCode 周赛 333,你管这叫 Medium 难度?

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 上周是 LeetCode 第 333 场周赛,你参加了吗?这场周赛质量很高,但难度标得不对,我真的会谢。算法解题思维需要长时间锻炼,加入我们一起刷题吧~ 小彭的 Android 交流群 0

LeetCode 周赛 334,在算法的世界里反复横跳

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 今天是 LeetCode 第 334 场周赛,你参加了吗?这场周赛考察范围比较基础,整体难度比较平均,第一题难度偏高,第四题需要我们在算法里实现 “反复横跳”,非常有意思。 小彭的 And

LeetCode 周赛 335,纯纯手速场!

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 昨晚是 LeetCode 第 335 场周赛,你参加了吗?这场周赛整体难度不高,有两道模板题,第三题和第四题应该调换一下位置。 小彭的 Android 交流群 02 群来了,公众号回复 “

LeetCode 周赛 336,多少人直接 CV?

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 今天早上是 LeetCode 第 336 场周赛,你参加了吗?这场周赛整体质量比较高,但是最后一题是老题,CV 能过。但是输入数据范围被降低了,这操作也是没谁了。 2587. 统计范围内的

LeetCode 周赛 338,贪心 / 埃氏筛 / 欧氏线性筛 / 前缀和 / 二分查找 / 拓扑排序

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 上周末是 LeetCode 第 338 场周赛,你参加了吗?这场周赛覆盖的知识点很多,第四题称得上是近期几场周赛的天花板。 小彭的技术交流群 02 群来了,公众号回复 “加群” 加入我们~

LeetCode 周赛 340,质数 / 前缀和 / 极大化最小值 / 最短路 / 平衡二叉树

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 上周跟大家讲到小彭文章风格的问题,和一些朋友聊过以后,至少在算法题解方面确定了小彭的风格。虽然竞赛算法题的文章受众非常小,但却有很多像我一样的初学者,他们有兴趣参加但容易被题目难度和大神选

LeetCode 周赛 341 场,模拟 / 树上差分 / Tarjan 离线 LCA / DFS

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 上周末有单双周赛,双周赛我们讲过了,单周赛那天早上有事没参加,后面做了虚拟竞赛,然后整个人就不好了。前 3 题非常简单,但第 4 题有点东西啊,差点就放弃了。最后,被折磨了一个下午和一个大