关于android:刷爆-LeetCode-双周赛-100单方面宣布第一题最难

90次阅读

共计 7087 个字符，预计需要花费 18 分钟才能阅读完成。

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 发问。

大家好，我是小彭。

上周末是 LeetCode 第 100 场双周赛，你加入了吗？这场周赛整体没有 Hard 题，然而也没有 Easy 题。第一题国服前百名里超过一半人 wa，很少见。

小彭的技术交换群 02 群来了，公众号回复“加群”退出咱们~

周赛概览

  • 2591. 将钱分给最多的儿童（Easy）

    • 题解一：模仿 $O(1)$
    • 题解二：齐全背包 $O(children·money^2)$

  • 2592. 最大化数组的平凡值（Medium）

    • 题解一：贪婪 / 田忌赛马 $O(nlgn)$
    • 题解二：最大反复计数 $O(n)$

  • 2593. 标记所有元素后数组的分数（Medium）

    • 题解一：排序 O$(nlgn)$
    • 题解二：依照严格递加字段分组 $O(n)$

  • 2594. 修车的起码工夫（Medium)

    • 题解一：二分查找 $O(n + U·log(mc^2))$
    • 题解二：二分查找 + 计数优化 $O(n·log(mc^2))$

2591. 将钱分给最多的儿童（Easy）

题目地址

https://leetcode.cn/problems/distribute-money-to-maximum-chil…

题目形容

给你一个整数 money，示意你总共有的钱数（单位为美元）和另一个整数 children，示意你要将钱调配给多少个儿童。

你须要依照如下规定调配：

  • 所有的钱都必须被调配。
  • 每个儿童至多取得 1 美元。
  • 没有人取得 4 美元。

请你依照上述规定调配金钱，并返回 最多  有多少个儿童取得  恰好 **8 美元。如果没有任何调配计划，返回 -1。

题解一（模仿）

这道题搞数字科学？发发发 888？

简略模拟题，然而错误率很高，提交通过率仅 19%。

class Solution {fun distMoney(money: Int, children: Int): Int {
        var left = money
        // 每人至多调配 1 元
        left -= children
        // 违反规定 2
        if (left < 0) return -1
        // 1、完满：正好所有人能够调配 8 元
        if (left == children * 7) return children
        // 2、溢出：所有人能够调配 8 元有结余，须要抉择 1 集体调配结余的金额
        if (left > children * 7) return children - 1
        // 3、有余：尽可能调配 8 元
        var sum = left / 7
        // 结余金额
        left -= sum * 7
        // 如果结余 3 元，并且剩下 1 人调配了 1 元，须要毁坏一个 8 元避免出现调配 4 美元
        if (left == 3 && children - sum == 1) return sum - 1
        return sum
    }
}

复杂度剖析：

  • 工夫复杂度：$O(1)$
  • 空间复杂度：$O(1)$

题解二（齐全背包问题）

比赛中脑海闪现过背包问题的思路，但第一题暴力才是王道，赛后验证可行。

  • 包裹：最多有 children 人；
  • 物品：每个金币价值为 1 且不可分割，最多物品数为 money 个；
  • 指标：包裹价值恰好为 8 的最大个数；
  • 限度条件：不容许包裹价值为 4，每个包裹至多装 1 枚金币。

令 dp[i][j] 示意调配到 i 集体为止，且调配总金额为 j 元时的最大价值，则有：

  • 递推关系：

$$
dp[i][j]=\sum_{k=1}^{j,k!=4} dp[i-1][j-k] + I(k==8)
$$

  • 初始状态 dp[0][0] = 0
  • 终止状态 dp[children][money]
class Solution {fun distMoney(money: Int, children: Int): Int {
        var left = money
        // 每人至多调配 1 元
        left -= children
        // 违反规定 2
        if (left < 0) return -1
        val dp = Array(children + 1) {IntArray(left + 1) {-1} }
        dp[0][0] = 0
        // i：枚举包裹
        for (i in 1..children) {
            // j：枚举金额
            for (j in 0..left) {
                // k：枚举选项
                for (k in 0..j) {
                    // 不容许抉择 3
                    if (k == 3) continue
                    // 子状态违反规定
                    if (-1 == dp[i - 1][j - k]) continue
                    // 子状态 + 以后包裹状态
                    val cnt = dp[i - 1][j - k] + if (k == 7) 1 else 0
                    dp[i][j] = Math.max(dp[i][j], cnt)
                }
            }
        }
        return dp[children][left]
    }
}

滚动数组优化：

class Solution {fun distMoney(money: Int, children: Int): Int {
        var left = money
        // 每人至多调配 1 元
        left -= children
        // 违反规定 2
        if (left < 0) return -1
        val dp = IntArray(left + 1) {-1}
        dp[0] = 0
        // i：枚举包裹
        for (i in 1..children) {
            // j：枚举金额
            for (j in left downTo 0) {
                // k：枚举选项
                for (k in 0..j) {
                    // 不容许抉择 3
                    if (k == 3) continue
                    // 子状态违反规定
                    if (-1 == dp[j - k]) continue
                    // 子状态 + 以后包裹状态
                    val cnt = dp[j - k] + if (k == 7) 1 else 0
                    dp[j] = Math.max(dp[j], cnt)
                }
            }
        }
        return dp[left]
    }

复杂度剖析：

  • 工夫复杂度：$O(children·money^2)$
  • 空间复杂度：$O(money)$

近期周赛背包问题：

  • LeetCode 周赛 333 · 无平方子集计数（Medium）
  • LeetCode 周赛 335 · 取得分数的办法数（Hard）

2592. 最大化数组的平凡值（Medium）

题目地址

https://leetcode.cn/problems/maximize-greatness-of-an-array/

题目形容

给你一个下标从 0 开始的整数数组 nums。你须要将 nums 重新排列成一个新的数组 perm。

定义 nums 的 平凡值 为满足 0 <= i < nums.length 且 perm[i] > nums[i] 的下标数目。

请你返回重新排列 nums 后的 最大 平凡值。

题解一（贪婪 / 田忌赛马）

贪婪思路：田忌赛马，以下赛马策略最优：

  • 田忌的中等马对齐威王的下等马，田忌胜；
  • 田忌的上等马对齐威王的中等马，田忌胜；
  • 田忌的下等马对齐威王的下等马，齐威王胜。

回到本题，思考一组奉献平凡值的配对 $(p, q)$，其中 $p < q$。因为越小的值越匹配到更大值，为了让后果最优，应该让 p 尽可能小，即优先匹配 nums 数组的较小值。那么 $q$ 如何抉择呢？有 2 种策略：

  • 策略 1 – 优先匹配最大值：无奈失去最优解，因为会耗费了较大的 q 值，可能导致局部 p 值无奈匹配（如果田忌用上等马对齐威王的下等马，最终将是齐威王生出）；

  • 策略 2- 优先匹配最靠近的更大值：最优解，即田忌赛马策略，以 [1,1,1,2,3,3,5] 为例：

    • 初始状态 i = 0，j = 0；
    • i = 0，j = 0，无奈奉献平凡值，j 自增 1（寻找最靠近的更大值）；
    • i = 0，j = 1，无奈奉献平凡值，j 自增 1；
    • i = 0，j = 2，无奈奉献平凡值，j 自增 1；
    • i = 0，j = 3，奉献平凡值，j 自增 1，i 自增 1；
    • i = 1，j = 4，奉献平凡值，j 自增 1，i 自增 1；
    • i = 2，j = 5，奉献平凡值，j 自增 1，i 自增 1；
    • i = 3，j = 6，奉献平凡值，j 自增 1，i 自增 1；
    • 退出循环，i = 4；正好等于平凡值 4。
class Solution {fun maximizeGreatness(nums: IntArray): Int {nums.sort()
        // i：参加匹配的指针
        var i = 0
        for (num in nums) {
            // 奉献平凡值
            if (num > nums[i]) i++
        }
        return i
    }
}

复杂度剖析：

  • 工夫复杂度：$O(nlgn + n)$ 排序 + 线性遍历，其中 $n$ 是 $nums$ 数组长度；
  • 空间复杂度：$O(lgn)$ 排序递归栈空间。

题解二（最大反复计数）

比赛中从测试用例中察看到题解与最大反复数存在关系，例如：

  • 用例 [1,1,1,2,3,3,5]：最大反复数为 3，一个最优计划为 [2,3,3,5,x,x,x]，最大平凡值为 7 – 3 = 4，其中 7 是数组长度；
  • 用例 [1,2,2,2,2,3,5]：最大反复数为 4，一个最优计划为 [2,3,5,x,x,x,x]，最大平凡值为 7 – 4 = 3，其中 7 是数组长度；
  • 用例 [1,1,2,2,2,2,3,3,5]，最大反复数为 4，一个最优计划为 [2,2,3,3,5,x,x,x,x]，最大平凡值为 9 – 4 = 5，其中 9 是数组长度。

咱们发现题目的瓶颈在于数字最大反复呈现计数。最大平凡值正好等于 数组长度 – 最大反复计数。

如何证实？关键在于 i 指针和 j 指针的最大间隔：

当 i 指针指向反复元素的首个元素时（例如下标为 0、2、6 的地位），j 指针必须挪动到最靠近的较大元素（例如下标为 2，6，8 的地位）。而 i 指针和 j 指针的最大错开间隔取决于数组反复呈现次数最多的元素，只有错开这个间隔，无论数组后续局部有多长，都可能匹配上。

class Solution {fun maximizeGreatness(nums: IntArray): Int {
        var maxCnt = 0
        val cnts = HashMap<Int, Int>()
        for (num in nums) {cnts[num] = cnts.getOrDefault(num, 0) + 1
            maxCnt = Math.max(maxCnt, cnts[num]!!)
        }
        return nums.size - maxCnt
    }
}

复杂度剖析：

  • 工夫复杂度：$O(n)$ 其中 $n$ 是 $nums$ 数组的长度；
  • 空间复杂度：$O(n)$ 其中 $n$ 是 $cnts$ 散列表空间。

2593. 标记所有元素后数组的分数（Medium）

题目地址

https://leetcode.cn/problems/find-score-of-an-array-after-mar…

题目形容

给你一个数组 nums，它蕴含若干正整数。

一开始分数 score = 0，请你依照上面算法求出最初分数：

  • 从数组中抉择最小且没有被标记的整数。如果有相等元素，抉择下标最小的一个。
  • 将选中的整数加到 score 中。
  • 标记 被选中元素 ，如果有相邻元素，则同时标记  与它相邻的两个元素。
  • 反复此过程直到数组中所有元素都被标记。

请你返回执行上述算法后最初的分数。

题解一（排序）

这道题犯了大忌，没有正确理解题意。一开始认为“相邻的元素”是指未标记的最相邻元素，花了很多工夫思考如何疾速找到左右未标记的数。其实题目没有这么简单，就是标记数组上的相邻元素。

如此这道题只能算 Medium 偏 Easy 难度。

class Solution {fun findScore(nums: IntArray): Long {
        // 小顶堆（索引）val heap = PriorityQueue<Int>() { i1, i2 ->
            if (nums[i1] != nums[i2]) nums[i1] - nums[i2] else i1 - i2
        }.apply {for (index in nums.indices) {offer(index)
            }
        }
        var sum = 0L
        while (!heap.isEmpty()) {val index = heap.poll()
            if (nums[index] == 0) continue
            // 标记
            sum += nums[index]
            nums[index] = 0
            // 标记相邻元素
            if (index > 0) nums[index - 1] = 0
            if (index < nums.size - 1) nums[index + 1] = 0
        }
        return sum
    }
}

复杂度剖析：

  • 工夫复杂度：$O(nlgn)$ 堆排序工夫，其中 $n$ 是 $nums$ 数组长度；
  • 空间复杂度：$O(n)$ 堆空间。

题解二（依照严格递加字段分组）

思路参考：灵茶山艾府的题解

依照严格递加字段分组，在找到坡底后距离累加 nums[i]，nums[i – 2]，nums[i – 4]，并从 i + 2 开始持续寻找坡底。

class Solution {fun findScore(nums: IntArray): Long {
        val n = nums.size
        var sum = 0L
        var i = 0
        while (i < nums.size) {
            val i0 = i // 坡顶
            while (i + 1 < n && nums[i] > nums[i + 1]) i++ // 寻找坡底
            for (j in i downTo i0 step 2) { // 距离累加
                sum += nums[j]
            }
            i += 2 // i + 1 不能选
        }
        return sum
    }
}

复杂度剖析：

  • 工夫复杂度：$O(n)$ 其中 $n$ 是 $nums$ 数组的长度，每个元素最多拜访 2 次；
  • 空间复杂度：$O(1)$ 只应用常数空间。

2594. 修车的起码工夫（Medium)

题目地址

https://leetcode.cn/problems/minimum-time-to-repair-cars/

题目形容

给你一个整数数组 ranks，示意一些机械工的 能力值。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工能够在 r * n2 分钟内修好 n 辆车。

同时给你一个整数 cars，示意总共须要修理的汽车数目。

请你返回修理所有汽车 起码 须要多少工夫。

留神： 所有机械工能够同时修理汽车。

题解（二分查找）

咱们发现问题在工夫 t 上存在枯燥性：

  • 假如能够在 t 工夫内修完所有车，那么大于 t 的工夫都能修完；
  • 如果不能在 t 工夫内修完所有车，那么小于 t 的工夫都无奈修完。

因而，咱们能够用二分查找寻找“能够修完的最小工夫”：

  • 二分的下界：1；
  • 二分的上界：将所有的车交给能力值排序最高的工人，因为他的效率最高。
class Solution {fun repairCars(ranks: IntArray, cars: Int): Long {
        // 寻找能力值排序最高的工人
        var minRank = Integer.MAX_VALUE
        for (rank in ranks) {minRank = Math.min(minRank, rank)
        }
        var left = 1L
        var right = 1L * minRank * cars * cars
        // 二分查找
        while (left < right) {val mid = (left + right) ushr 1
            if (check(ranks, cars, mid)) {right = mid} else {left = mid + 1}
        }
        return left
    }
 
    // return 是否在 t 工夫内修完所有车
    private fun check(ranks: IntArray, cars: Int, t: Long): Boolean {
        // 计算并行修车 t 工夫能修完的车（因为 t 的上界较大，carSum 会溢出 Int）var carSum = 0L
        for (rank in ranks) {carSum += Math.sqrt(1.0 * t / rank).toLong()}
        return carSum >= cars
    }
}

复杂度剖析：

  • 工夫复杂度：$O(n·log(mc^2))$ 其中 $n$ 是 $ranks$ 数组长度，$m$ 是 $ranks$ 数组的最小值，$c$ 是车辆数量，二分的次数是 $O(log(mc^2))$，每次 $check$ 操作破费 $O(n)$ 工夫；
  • 空间复杂度：$O(1)$ 仅应用常量级别空间。

题解二（二分查找 + 计数优化）

咱们发现 $ranks$ 的取值范畴很小，所有能够用计数优化每次 $check$ 操作的工夫复杂度：

class Solution {fun repairCars(ranks: IntArray, cars: Int): Long {
        // 寻找能力值排序最高的工人
        val cnts = IntArray(101)
        var minRank = Integer.MAX_VALUE
        for (rank in ranks) {minRank = Math.min(minRank, rank)
            cnts[rank]++
        }
        var left = 1L
        var right = 1L * minRank * cars * cars
        // 二分查找
        while (left < right) {val mid = (left + right) ushr 1
            if (check(ranks, cars, cnts, minRank, mid)) {right = mid} else {left = mid + 1}
        }
        return left
    }
 
    // return 是否在 t 工夫内修完所有车
    private fun check(ranks: IntArray, cars: Int, cnts: IntArray, minRank: Int, t: Long): Boolean {
        // 计算并行修车 t 工夫能修完的车（因为 t 的上界较大，carSum 会溢出 Int）var carSum = 0L
        for (rank in minRank..100) {if (cnts[rank] == 0) continue
            carSum += cnts[rank] * Math.sqrt(1.0 * t / rank).toLong()}
        return carSum >= cars
    }
}

复杂度剖析：

  • 工夫复杂度：$O(n + U·log(mc^2))$ 其中 $n$ 是 $ranks$ 数组长度，$m$ 是 $ranks$ 数组的最小值，$U$ 是 $ranks$ 数组的取值范畴，$c$ 是车辆数量，二分的次数是 $O(log(mc^2))$，每次 $check$ 操作破费 $O(U)$ 工夫；
  • 空间复杂度：$O(U)$ $cnts$ 计数数组空间。

近期周赛二分查找题目：

  • LeetCode 332 · 统计偏心数对的数目（Medium）
  • LeetCode 334 · 在网格图中拜访一个格子的起码工夫（Hard）

这场周赛就这么多，咱们下周见。

正文完
android
发表至： android
2023-03-21
 0
关于android:用华为HMS-ML-kit人体骨骼识别技术Android快速实现人体姿势动作抓拍
关于android:2022最新Android大厂面试题详解堪称金三银四的葵花宝典
关于android:Android-多返回栈技术详解
关于android:当你真的学会DataBinding后你会发现这玩意真香