乐趣区

关于android:LeetCode-周赛-34220230423容斥原理计数排序滑动窗口子数组-GCB

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

大家好,我是小彭。

前天刚举办 2023 年力扣杯集体 SOLO 赛,昨天周赛就出了一场 Easy – Easy – Medium – Medium 的水场,不得不说 LeetCode 是懂礼数的 😁。

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

往期回顾:LeetCode 单周赛 341 · 难度上来了,图论的问题好多啊!

LeetCode 周赛 342 概览

Q1. 计算列车到站工夫(Easy)

简略模拟题,不多解说。

Q2. 倍数求和(Easy)

题解 1:暴力解法 $O(n)$ 工夫复杂度

题解 2:剖析数据特色后发现数据存在等差数列性质,咱们利用容斥原理和等差数列求和公式,能够把优化到 $O(1)$ 工夫复杂度

Q3. 滑动子数组的漂亮值(Medium)

题解 1:在滑动窗口的根底上,联合疾速抉择查找滑动窗口中第 x 小的元素,工夫复杂度是 $O(n·k)$

题解 2:剖析数据特色后发现题目的值域十分小,咱们能够用计数排序代替疾速抉择,工夫复杂度为 $O(n·U)$

Q4. 使数组所有元素变成 1 的起码操作次数(Medium)

在问题剖析后咱们将原问题形象为“寻找 GCB 为 1 的最短子数组”,关联类似的“和为 k 的最短子数组”问题,咱们有从暴力 → 有序汇合 → 枯燥性优化的解法:

题解 1:暴力 $O(n·(n + logU))$ 工夫复杂度

题解 2:有序汇合 $O(n·lgU·lg(lgU))$ 工夫复杂度

题解 3:枯燥性优化 $O(n·lgU)$ 工夫复杂度


Q1. 计算列车到站工夫(Easy)

题目地址

https://leetcode.cn/problems/calculate-delayed-arrival-time/

题目形容

给你一个正整数 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)$

Q2. 倍数求和(Easy)

题目地址

https://leetcode.cn/problems/sum-multiples/

题目形容

给你一个正整数 n,请你计算在 [1,n] 范畴内能被 357 整除的所有整数之和。

返回一个整数,用于示意给定范畴内所有满足约束条件的数字之和。

示例 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 ∩ C
$$

其中:

  • 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)$ 其中 n 为 nums 数组的长度,每个元素最多拜访 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)$

Q3. 滑动子数组的漂亮值(Medium)

题目地址

https://leetcode.cn/problems/sliding-subarray-beauty/descript…

题目形容

给你一个长度为 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)$ 其中 n 是 nums 数组的长度,单次窗口疾速抉择的工夫复杂度是 $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)$ 其中 n 是 nums 数组的长度,U 是值域大小 101。每次滑动窗口求第 x 小的元素工夫是 $O(U)$;
  • 空间复杂度:$O(U)$ 计数数组空间。

Q4. 使数组所有元素变成 1 的起码操作次数(Medium)

题目地址

https://leetcode.cn/problems/minimum-number-of-operations-to-…

题目形容

给你一个下标从 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))$ 其中 n 是 nums 数组的长度,U 是数组元素的最大值。单次 GCD 计算的工夫复杂度是 $O(logU)$,乍看起来算法整体的工夫复杂度是 $O(n^2·logU)$,其实不对。因为在每层循环中,每次 GCD 计算并不是独立的,而是贯通整个内层循环的,所以 GCD 的总工夫取决于数据的最大值 U,在辗转相除中取余的次数也取决于 U。
  • 空间复杂度:$O(1)$ 不思考后果数组,仅应用常量级别空间。

题解一的复杂度是平方级别的,如果放大题目数据量到 10^5 要怎么做?

问题形象

在剖析暴力解法的反复计算之前,我先向你抛出一个“题外话”:

请你答复:“给定一个整数数组 nums 和指标和 k,如何求和为 k 的最短子数组?”

  • 解法 1:暴力枚举所有子数组,记录出所有子数组和为 k 的最短子数组长度(这与题解一暴力枚举子数组求操作出原始“1”的起码操作次数相似);
  • 解法 2:咱们从左向右线性遍历,并保护以 num[j] 为右端点的前缀和映射表 <preSum to index>。在此基础上,咱们将以后地位 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(n·lgU),但减少了空间复杂度为 O(lgU)。

示意图

题解二(有序汇合)

至此,在题解一的根底上批改“枚举子数组计算操作出原始“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(lgU·lg(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(lgU)$

类似题目:

  • 560. 和为 K 的子数组
  • 898. 子数组按位或操作
  • 1521. 找到最靠近目标值的函数值

退出移动版