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

大家好，我是小彭。

前天刚举行 2023 年力扣杯个人 SOLO 赛，昨天周赛就出了一场 Easy – Easy – Medium – Medium 的水场，不得不说 LeetCode 是懂礼数的 。

接下来，请你跟着小彭的思路，一步步将问题做难，再将问题做简略。

往期回顾：LeetCode 单周赛 341 难度上来了，图论的问题很多啊！

LeetCode 周赛 342 概览

Q1. 核算列车到站时刻（Easy）

简略模仿题，不多解说。

Q2. 倍数求和（Easy）

题解 1：暴力解法 O(n)O(n) 时刻复杂度

题解 2：剖析数据特征后发现数据存在等差数列性质，咱们运用容斥原理和等差数列求和公式，能够把优化到 O(1)O(1) 时刻复杂度

Q3. 滑动子数组的美丽值（Medium）

题解 1：在滑动窗口的基础上，结合快速挑选查找滑动窗口中第 x 小的元素，时刻复杂度是 O(n⋅k)O(nk)

题解 2：剖析数据特征后发现标题的值域十分小，咱们能够用计数排序替代快速挑选，时刻复杂度为 O(n⋅U)O(nU)

Q4. 使数组一切元素变成 1 的最少操作次数（Medium）

在问题剖析后咱们将原问题笼统为 “寻觅 GCB 为 1 的最短子数组”，关联相似的 “和为 k 的最短子数组” 问题，咱们有从暴力 → 有序调集 → 单调性优化的解法：

题解 1：暴力 O(n⋅(n+logU))O(n(n + logU)) 时刻复杂度

题解 2：有序调集 O(n⋅lgU⋅lg(lgU))O(nlgUlg(lgU)) 时刻复杂度

题解 3：单调性优化 O(n⋅lgU)O(nlgU) 时刻复杂度

LeetCode 周赛 342（2023/04/23）容斥原理、计数排序、滑动窗口、子数组 GCB

LeetCode 周赛 342（2023/04/23）容斥原理、计数排序、滑动窗口、子数组 GCB

Q1. 核算列车到站时刻（Easy）

标题地址

leetcode.cn/problems/ca…

标题描绘

给你一个正整数arrivalTime表明列车正点到站的时刻（单位：小时），另给你一个正整数delayedTime表明列车延误的小时数。

回来列车实践到站的时刻。

留意，该问题中的时刻采用 24 小时制。

示例 1：

输入：arrivalTime = 15, delayedTime = 5
输出：20
解说：列车正点到站时刻是 15:00 ，延误 5 小时，所以列车实践到站的时刻是 15 + 5 = 20（20:00）。

示例 2：

输入：arrivalTime = 13, delayedTime = 11
输出：0
解说：列车正点到站时刻是 13:00 ，延误 11 小时，所以列车实践到站的时刻是 13 + 11 = 24（在 24 小时制中表明为 00:00 ，所以回来 0）。

提示：

  • 1 <= arrivaltime <24
  • 1 <= delayedTime <= 24

题解（模仿）

简略模仿题，按题意完成即可。

class Solution {
    fun findDelayedArrivalTime(arrivalTime: Int, delayedTime: Int): Int {
        return (arrivalTime + delayedTime) % 24
    }
}

复杂度剖析：

  • 时刻复杂度：O(1)O(1)
  • 空间复杂度：O(1)O(1)

Q2. 倍数求和（Easy）

标题地址

leetcode.cn/problems/su…

标题描绘

给你一个正整数n，请你核算在[1，n]规模内能被3、5、7整除的一切整数之和。

回来一个整数，用于表明给定规模内一切满意约束条件的数字之和。

示例 1：

输入：n = 7
输出：21
解说：在[1, 7] 规模内能被 3、5、7 整除的一切整数分别是 3、5、6、7 。数字之和为21 。

示例 2：

输入：n = 10
输出：40
解说：在[1, 10] 规模内能被 3、5、7 整除的一切整数分别是 3、5、6、7、9、10 。数字之和为40 。

示例 3：

输入：n = 9
输出：30
解说：在[1, 9] 规模内能被 3、5、7 整除的一切整数分别是 3、5、6、7、9 。数字之和为30 。

提示：

  • 1 <= n <= 103

准备常识 – 容斥原理

界说调集 A 表明能够被 3 整除的数，界说调集 B 表明能够被 5 整除的数，界说调集 C 表明能够被 7 整除的数。假如把这 3 个调集直接加起来，会多出来一些元素重复统计了，因而需求扣除 A ∩ B，A ∩ C 和 B ∩ C ，可是又有一小部分元素多扣了，反而再需求加上 A ∩ B ∩ C。这便是 容斥原理：

A∪B∪C=A+B+C−A∩B−A∩C−B∩C+A∩B∩CA ∪ B ∪ C = A + B + C – A ∩ B – A ∩ C – B ∩ C + A ∩ B ∩ C

LeetCode 周赛 342（2023/04/23）容斥原理、计数排序、滑动窗口、子数组 GCB

其间：

  • A ∪ B ∪ C 表明能够被 3 或 5 或 7 整除的数，也便是原问题的解；
  • A ∩ B 表明能够一起被 3 和 5 整除的数；
  • A ∩ C 表明能够一起被 3 和 7 整除的数；
  • B ∩ C 表明能够一起被 5 和 7 整除的数。

准备常识 – 等差数列求和

  • 等差数列求和公式：(首项 + 尾项) * 项数 / 2

题解一（暴力）

先考虑暴力解法：

算法：枚举每个数，查看该数字是否为 3 / 5 / 7 的倍数，是则计入成果中。

class Solution {
    fun sumOfMultiples(n: Int): Int {
        var ret = 0
        for (i in 1 .. n) {
            if(i % 3 == 0 || i % 5 == 0 || i % 7 == 0) ret += i
        }
        return ret
    }
}

复杂度剖析：

  • 时刻复杂度：O(n)O(n) 其间 n 为 nums 数组的长度，每个元素最多拜访 1 次；
  • 空间复杂度：O(1)O(1)

题解二（容斥原理 + 等差数列求和公式）

暴力解法是否有优化空间呢，先剖析重复核算：

  • 要点 1：能够观察到 [1, n] 规模中的方针数是存在关联的，以 3 的倍数为例，3、6、9、12 是以 3 为等差的等差数列，而等差数列的和能够运用公式核算。数字 m 在 [1, n] 规模内里的倍数为 n / m 个，能够运用等差数列求和公式以 O(1) 算出这部分元素之和；
  • 要点 2：结合容斥原理，能够在 O(1) 时刻复杂度求出原问题。那么能够一起被 3 和 5 整除的等差数列怎么核算呢？其实便是核算 15 的倍数。同理能够一起被 3 和 5 和 7 整除的等差数列便是 105 的倍数。

至此，结合容斥原理模仿即可：

class Solution {
    fun sumOfMultiples(n: Int): Int {
        return sum(n, 3) + sum(n, 5) + sum(n, 7) - sum(n, 15) - sum(n, 21) - sum(n, 35) + sum(n, 105)
    }
    private fun sum(n:Int, k:Int) :Int {
        // 等差数列求和公式：(首项 + 尾项) * 项数 / 2
        return (k + (n / k * k)) * (n / k) / 2
    }
}

复杂度剖析：

  • 时刻复杂度：O(1)O(1)
  • 空间复杂度：O(1)O(1)

Q3. 滑动子数组的美丽值（Medium）

标题地址

leetcode.cn/problems/sl…

标题描绘

给你一个长度为n的整数数组nums，请你求出每个长度为k的子数组的美丽值。

一个子数组的美丽值界说为：假如子数组中第x小整数是负数，那么美丽值为第x小的数，否则美丽值为0。

请你回来一个包含**n - k + 1个整数的数组，顺次表明数组中从榜首个下标开端，每个长度为k的子数组的美丽值。

  • 子数组指的是数组中一段接连非空的元素序列。

示例 1：

输入：nums = [1,-1,-3,-2,3], k = 3, x = 2
输出：[-1,-2,-2]
解说：总共有 3 个 k = 3 的子数组。
榜首个子数组是[1, -1, -3] ，第二小的数是负数 -1 。
第二个子数组是[-1, -3, -2] ，第二小的数是负数 -2 。
第三个子数组是[-3, -2, 3]，第二小的数是负数 -2 。

示例 2：

输入：nums = [-1,-2,-3,-4,-5], k = 2, x = 2
输出：[-1,-2,-3,-4]
解说：总共有 4 个 k = 2 的子数组。
[-1, -2] 中第二小的数是负数 -1 。[-2, -3] 中第二小的数是负数 -2 。[-3, -4] 中第二小的数是负数 -3 。[-4, -5] 中第二小的数是负数 -4 。

示例 3：

输入：nums = [-3,1,2,-3,0,-3], k = 2, x = 1
输出：[-3,0,-3,-3,-3]
解说：总共有 5 个 k = 2 的子数组。
[-3, 1] 中最小的数是负数 -3 。[1, 2] 中最小的数不是负数，所以美丽值为 0 。[2, -3] 中最小的数是负数 -3 。[-3, 0] 中最小的数是负数 -3 。[0, -3] 中最小的数是负数 -3 。

提示：

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= k <= n
  • 1 <= x <= k
  • 50<= nums[i] <= 50

准备常识

求出每个长度为k的子数组的美丽值，简单想到能够用滑动窗口。

伪代码为：

// 伪代码
for (i in 0 until n) {
    // 进入窗口
    list.add(i)
    // 脱离窗口
    if (i >= k) list.remove(i - k)
    if (i >= k - 1) {
        // 核算窗口答案
    }
}

题解一（滑动窗口 + 快速挑选 超出时刻约束）

在滑动窗口的基础上，运用快速挑选查找窗口中第 x 小的数：

class Solution {
    private val random = Random(0)
    fun getSubarrayBeauty(nums: IntArray, k: Int, x: Int): IntArray {
        val n = nums.size
        val ret = LinkedList<Int>()
        val list = ArrayList<Int>()
        for (i in 0 until n) {
            // 进入窗口
            list.add(i)
            // 脱离窗口
            if (i >= k) list.remove(i - k)
            if (i >= k - 1) {
                // 核算窗口答案
                quickSelect(nums, list, x)
                val num = nums[list[x - 1]]
                ret.add(if (num < 0) num else 0)
            }
        }
        return ret.toIntArray()
    }
    private fun quickSelect(nums: IntArray, list: ArrayList<Int>, x: Int) {
        val target = x - 1
        var left = 0
        var right = list.size - 1
        while (left < right) {
            val pivot = partition(nums, list, left, right)
            if (pivot == target) {
                return
            } else if (pivot < target) {
                left = pivot + 1
            } else {
                right = pivot - 1
            }
        }
    }
    private fun partition(nums: IntArray, list: ArrayList<Int>, left: Int, right: Int): Int {
        val random = random.nextInt(right - left + 1) + left
        list.swap(random, right)
        var p = left
        for (i in left until right) {
            if (nums[list[i]] < nums[list[right]]) list.swap(i, p++)
        }
        list.swap(p, right)
        return p
    }
    private fun ArrayList<Int>.swap(i: Int, j: Int) {
        val temp = this[i]
        this[i] = this[j]
        this[j] = temp
    }
}

复杂度剖析：

  • 时刻复杂度：O(n⋅k)O(nk) 其间 n 是 nums 数组的长度，单次窗口快速挑选的时刻复杂度是 O(k)O(k)；
  • 空间复杂度：O(k)O(k) 滑动窗口空间。

题解二（滑动窗口 + 计数排序）

留意到标题的值域十分小，能否运用起来：

咱们能够用计数排序替代快速挑选，用 cnts 计数数组核算窗口内每个元素的出现次数，再根据计数数组核算出第 x 小的数：

class Solution {
    private val random = Random(0)
    fun getSubarrayBeauty(nums: IntArray, k: Int, x: Int): IntArray {
        val n = nums.size
        val OFFSET = 50
        val cnts = IntArray(OFFSET * 2 + 1)
        val ret = IntArray(n - k + 1)
        outer@ for (i in 0 until n) {
            // 进入窗口
            cnts[OFFSET + nums[i]]++
            // 脱离窗口
            if (i >= k) cnts[OFFSET + nums[i - k]]--
            if (i >= k - 1) {
                // 核算窗口美丽值
                var count = x
                // for (num in -OFFSET .. -1) {
                for (num in -OFFSET .. OFFSET) {
                    count -= cnts[num + 50]
                    if (count <= 0) {
                        // 找到第 x 小的数
                        // ret[i - k + 1] = num
                        ret[i - k + 1] = if(num < 0) num else 0
                        continue@outer
                    }
                }
            }
        }
        return ret
    }
}

别的，由于标题要求美丽值是负数，所以在核算窗口美丽值时，咱们只需求枚举 [-50, -1] 的元素值。

复杂度剖析：

  • 时刻复杂度：O(n⋅U)O(nU) 其间 n 是 nums 数组的长度，U 是值域巨细 101。每次滑动窗口求第 x 小的元素时刻是 O(U)O(U)；
  • 空间复杂度：O(U)O(U) 计数数组空间。

Q4. 使数组一切元素变成 1 的最少操作次数（Medium）

标题地址

leetcode.cn/problems/mi…

标题描绘

给你一个下标从0开端的正整数数组nums。你能够对数组履行以下操作任意次：

  • 挑选一个满意0 <= i < n - 1的下标i，将nums[i]或许nums[i+1]两者之一替换成它们的最大公约数。

请你回来使数组nums中一切元素都等于1的最少操作次数。假如无法让数组全部变成1，请你回来-1。

两个正整数的最大公约数指的是能整除这两个数的最大正整数。

示例 1：

输入：nums = [2,6,3,4]
输出：4
解说：咱们能够履行以下操作：
- 挑选下标 i = 2 ，将 nums[2] 替换为 gcd(3,4) = 1 ，得到 nums = [2,6,1,4] 。
- 挑选下标 i = 1 ，将 nums[1] 替换为 gcd(6,1) = 1 ，得到 nums = [2,1,1,4] 。
- 挑选下标 i = 0 ，将 nums[0] 替换为 gcd(2,1) = 1 ，得到 nums = [1,1,1,4] 。
- 挑选下标 i = 2 ，将 nums[3] 替换为 gcd(1,4) = 1 ，得到 nums = [1,1,1,1] 。

示例 2：

输入：nums = [2,10,6,14]
输出：-1
解说：无法将一切元素都变成 1 。

提示：

  • 2 <= nums.length <= 50
  • 1 <= nums[i] <= 106

问题剖析

剖析方针成果：

使得数组中一切元素都变成 1 的最少操作次数。

剖析标题示例：

  • 由于在每次操作中最多只能将一个数字修正为最大公约数，那么将 1 个元素操作为 “1” 的最小操作次数（假如可行）不会低于 1 次，将 n 个大于 1 的元素操作为 “1” 的最小次数不会低于 n 次，例如样例 [2,6,1,4]。
  • 假如数组中至少存在 1 个 “1” 时，咱们只需求将每个 “1” 与相邻的 “非 1” 元素组合操作，就能将一切元素，例如样例 [2,6,1,4]。这说明，问题的最小操作次数正好便是数组中不是 “1” 的个数。
  • 假如数组中不存在 “1”，需求先操作出原始的 “1”：
    • 假如数组中一切元素的最大公约数大于 1，那么无论怎么也无法操作出数字 1，例如样例 [2, 10, 6, 14]；
    • 否则，咱们总能够操作 x 次取得原始 “1”，那么问题就等于 count + n – 1；

至此，程序全体结构确认。伪代码为：

if (一切元素的最大公约数 > 1) return -1
if (1 的个数 > 0) return n - (1 的个数)
操作 count 次得到原始的 “1”
return count + n - 1

接下来，咱们需求考虑怎么核算出操作出原始 “1” 的最小次数：

回归到原问题操作，咱们在每次操作中能够将一个数修正为最大公约数，那么对于接连的一段子数组（长度为 subSize），咱们总能够用 subSize – 1 次操作将其间一个数变为整个子数组的最大公约数。假如这个最大公约数是 1，那么操作次数正好是 subSize – 1，反之无法操作出 1。

至此，能够想出暴力解法：

题解一（暴力枚举子数组）

在暴力解法中，咱们枚举一切子数组，记载出一切子数组操作出原始 “1” 的最少操作次数。

class Solution {
    fun minOperations(nums: IntArray): Int {
        val n = nums.size
        // 1 的个数
        var cnt1 = 0
        var gcbAll = 0
        for (x in nums) {
            gcbAll = gcb(gcbAll, x)
            if (x == 1) cnt1++
        }
        // 一切数的最大公约数大于 1
        if (gcbAll > 1) return -1
        // 1 的个数大于 0
        if (cnt1 > 0) return n - cnt1
        // 操作出原始 “1” 的最小次数
        var minCount = n
        // 枚举子数组
        for (i in 0 until n) {
            var gcb = 0
            for (j in i until n) {
                gcb = gcb(gcb, nums[j])
                if (gcb == 1) {
                    minCount = Math.min(minCount, j - i /* 子数组长度 - 1 */)
                    break // 持续枚举 i 为起点的子数组不会得到更优解
                }
            }
        }
        return minCount + n - 1
    }
    // 求 x 和 y 的最大公约数（曲折相除法）
    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⋅(n+logU))O(n(n + logU)) 其间 n 是 nums 数组的长度，U 是数组元素的最大值。单次 GCD 核算的时刻复杂度是 O(logU)O(logU)，乍看起来算法全体的时刻复杂度是 O(n2⋅logU)O(n^2logU)，其实不对。由于在每层循环中，每次 GCD 核算并不是独立的，而是贯穿整个内层循环的，所以 GCD 的总时刻取决于数据的最大值 U，在曲折相除中取余的次数也取决于 U。
  • 空间复杂度：O(1)O(1) 不考虑成果数组，仅运用常量等级空间。

题解一的复杂度是平方等级的，假如扩大标题数据量到 10^5 要怎么做？

问题笼统

在剖析暴力解法的重复核算之前，我先向你抛出一个 “题外话”：

请你答复：“给定一个整数数组 nums 和方针和 k，怎么求和为 k 的最短子数组？”

  • 解法 1：暴力枚举一切子数组，记载出一切子数组和为 k 的最短子数组长度（这与题解一暴力枚举子数组求操作出原始 “1” 的最少操作次数相似）；
  • 解法 2：咱们从左向右线性遍历，并维护以 num[j] 为右端点的前缀和映射表 。在此基础上，咱们将当时位置 nums[i] 的前缀和与前缀和映射表中的每个元素取差值，就能够快速地取得以 num[i] 为右端点一切子数组的和。别的，由于咱们是从左向右遍历的，所以前缀和映射表记载的索引正好是能够构造最短子数组的索引，子数组长度为 i – j + 1（当然，咱们能够直接 O(1) 查询方针前缀和出现时的索引，而不需求真的用前缀和映射表的每个元素取差值）。

注：这个 “题外话” 与 LeetCode 560.和为 K 的子数组 相似，假如你不熟悉能够先做做看。

那么，这个 “题外话” 与今天这道题有什么关系：

根据 GCB 运算的性质，当咱们以 nums[i] 为左端点，不断向右扩展子数组的右端点时，咱们的方针是求 “GCB 为 1 的子数组” 对吧。与 “求和为 k 的最短子数组” 相似，咱们能够维护以 nums[j] 为左端点的 GCB 映射表 <gcb to 左端点 index>。在此基础上，咱们将当时位置 nums[i] 与 GCB 映射表中的每个元素取 GCB，就能够快速的取得以 nums[i] 为右端点的一切子数组的 GCB。

那听起来这个算法依然是 O(n^2)？不对。

原因在题解一的时刻复杂度剖析中讲到了，由于每次 GCD 核算并不是独立的，而是贯穿整个循环的，GCB 映射表的巨细取决于数据的最大值 U，而不是数据量，最多有 logU 种 GCB。因而优化后算法的时刻复杂度是 O(nlgU)，但添加了空间复杂度为 O(lgU)。

示意图

LeetCode 周赛 342（2023/04/23）容斥原理、计数排序、滑动窗口、子数组 GCB

题解二（有序调集）

至此，在题解一的基础上修正 “枚举子数组核算操作出原始 “1” 的最小次数” 不分代码即可：

class Solution {
    fun minOperations(nums: IntArray): Int {
        // 略...
        // 核算操作出原始 “1” 的最小次数
        var minCount = n
        // gcb 散列表 <gcd to 左端点 index>
        var gcbMap = TreeMap<Int, Int>()
        // 枚举子数组
        for (i in 0 until n) {
            val newGcbMap = TreeMap<Int, Int>()
            // 枚举 gcb 映射表
            for ((gcb, index) in gcbMap) {
                newGcbMap[gcb(gcb, nums[i])] = index
            }
            newGcbMap[nums[i]] = i
            // 查看最小的 gcb 是否为 1
            val minEntry = newGcbMap.firstEntry()
            if (1 == minEntry.key) {
                minCount = Math.min(minCount, i - minEntry.value /* 子数组长度 - 1 */)
            }
            gcbMap = newGcbMap
        }
        return minCount + n - 1
    }
    // 求 x 和 y 的最大公约数
    private fun gcb(x: Int, y: Int): Int {
        // 略...
    }
}

复杂度剖析：

  • 时刻复杂度：O(n⋅lgU⋅lg(lgU))O(nlgUlg(lgU)) 由于运用了有序调集，所以每一轮迭代中要算上排序时刻 O(lgU⋅lg(lgU))O(lgUlg(lgU))；
  • 空间复杂度：O(lgU)O(lgU) GCB 映射表空间。

题解三（单调性优化）

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

题解二的时刻复杂度比咱们剖析的复杂度略要一些，怎么寻觅优化空间？

持续剖析 GCB 的数据特征，能够发现：当咱们从左向右遍历时，随着子数组的长度增大，子数组的 GCB 要么不变，要么变小，存在 单调性。 所以，咱们并不需求维护有序调集，GCB 列表中最靠前的元素一定是最小的 GCB。

class Solution {
    fun minOperations(nums: IntArray): Int {
        // 略...
        // 核算操作出原始 “1” 的最小次数
        var minCount = n
        // gcb 列表 <gcd to 左端点 index>
        var gcbs = ArrayList<IntArray>()
        // 枚举子数组
        for (i in 0 until n) {
            val newGcbs = ArrayList<IntArray>()
            // 枚举 gcb 列表
            for (element in gcbs) {
                val gcb = gcb(element[0], nums[i])
                if (newGcbs.isEmpty() || newGcbs[newGcbs.size - 1][0] != gcb) {
                    // 添加 GCB
                    newGcbs.add(intArrayOf(gcb, element[1]))
                } else {
                    // 原地去重
                    newGcbs[newGcbs.size - 1][1] = element[1]
                }
            }
            newGcbs.add(intArrayOf(nums[i], i))
            // 查看最小的 gcb 是否为 1
            val minEntry = newGcbs[0]
            if (1 == minEntry[0]) {
                minCount = Math.min(minCount, i - minEntry[1] /* 子数组长度 - 1 */)
            }
            gcbs = newGcbs
        }
        return minCount + n - 1
    }
    // 求 x 和 y 的最大公约数
    private fun gcb(x: Int, y: Int): Int {
        // 略...
    }
}

复杂度剖析：

  • 时刻复杂度：O(n⋅lgU)O(nlgU)
  • 空间复杂度：O(lgU)O(lgU)

相似标题：

  • 560.和为 K 的子数组
  • 898. 子数组按位或操作
  • 1521. 找到最接近方针值的函数值