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

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

科技资讯 投稿 6200℃ 0 评论

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

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

上周跟大家讲到小彭文章风格的问题，和一些朋友聊过以后，至少在算法题解方面确定了小彭的风格。虽然竞赛算法题的文章受众非常小，但却有很多像我一样的初学者，他们有兴趣参加但容易被题目难度和大神选手的题解劝退。

好一波强行自证价值？ 😁

2614. 对角线上的质数（Easy）

    质数判断：$O(n·\sqrt(U$

2615. 等值距离和（Medium）

    题解 1：暴力 $O(n^2$
  • 题解 2：前缀和数组 $O(n + O(n$
  • 题解 3：前缀和 + DP $O(n + O(1$

2616. 最小化数对的最大差值（Medium）

    贪心 + 二分查找 $O(nlgn + nlgU$

2617. 网格图中最少访问的格子数（Hard）

    最短路 BFS + 平衡二叉树 + 队列 $O(nm·(lgn + lgm$

2614. 对角线上的质数（Easy）

题目地址

题目描述

给你一个下标从 0 开始的二维整数数组 nums 。

nums 至少一条 对角线 上的最大 质数 。如果任一对角线上均不存在质数，返回 0 。

    如果某个整数大于 1 ，且不存在除 1 和自身之外的正整数因子，则认为该整数是一个质数。
  • 如果存在整数 i ，使得 nums[i][i] = val 或者 nums[i][nums.length - i - 1]= val ，则认为整数 val 位于 nums 的一条对角线上。

题解（质数）

另外再检查数据量，数组的长度 n 最大为 300，而数据最大值为 4*10^6，所以用朴素的质数判断算法能满足要求。

class Solution {
    fun diagonalPrime(nums: Array<IntArray>: Int {
        var ret = 0
        val n = nums.size
        for (i in 0 until n {
            val num1 = nums[i][i]
            val num2 = nums[i][n - 1 - i]
            if (num1 > ret && isPrime(num1 ret = num1
            if (num2 > ret && isPrime(num2 ret = num2
        }
        return ret
    }

    private fun isPrime(num: Int: Boolean {
        if (num == 1 return false
        var x = 2
        while (x * x <= num {
            if (num % x == 0 {
                return false
            }
            x++
        }
        return true
    }
}

复杂度分析：

    时间复杂度：$O(n·\sqrt(U$ 其中 n 是 nums 二维数组的长度，U 是输入数据的最大值；
  • 空间复杂度：$O(1$ 仅使用常量级别空间。
    2600. 质数减法运算（Medium）

2615. 等值距离和（Medium）

题目地址

https://leetcode.cn/problems/sum-of-distances/

题目描述

0 开始的整数数组 nums 。现有一个长度等于 nums.length 的数组 arr 。对于满足 nums[j] == nums[i] 且 j != i 的所有 j ，arr[i] 等于所有 |i - j| 之和。如果不存在这样的 j ，则令 arr[i] 等于 0 。

arr 。

问题分析

题解一（暴力 · 超出时间限制）

暴力解法是计算每个位置与其他组内元素的距离差绝对值。

class Solution {
    fun distance(nums: IntArray: LongArray {
        val n = nums.size
        // 分组
        val map = HashMap<Int, ArrayList<Int>>(
        for (index in nums.indices {
            map.getOrPut(nums[index] { ArrayList<Int>( }.add(index
        }
        val ret = LongArray(n
        // 暴力
        for ((_, indexs in map {
            for (i in indexs.indices {
                for (j in indexs.indices {
                    ret[indexs[i]] += 0L + Math.abs(indexs[i] - indexs[j]
                }
            }
        }
        return ret
    }
}

复杂度分析：

    时间复杂度：$O(n^2$ 其中 n 为 nums 数组的长度
  • 空间复杂度：$O(1$ 不考虑分组的数据空间。

题解二（前缀和数组）

以组内下标为 [0, 1, 2, 3, 4, 5] 为例，下标 [2] 位置的距离和计算过程为：

    (x - 0 + (x - 1 + (x - x + (3 - x + (4 - x + (5 - x
    (x - 0 - (x - 1 正好等于 (左边元素个数 * x - 左边元素之和
  • (3 - x + (4 - x + (5 - x 正好等于 (右边元素之和 - (右边元素个数 * x

数组区间和有前缀和的套路做法，可以以空间换时间降低时间复杂度。

    细节：x * i 是 Int 运算会溢出，需要乘以 1 转换为 Long 运算 
class Solution {
    fun distance(nums: IntArray: LongArray {
        val n = nums.size
        // 分组
        val map = HashMap<Int, ArrayList<Int>>(
        for (index in nums.indices {
            map.getOrPut(nums[index] { ArrayList<Int>( }.add(index
        }
        val ret = LongArray(n
        // 分组计算
        for ((_, indexs in map {
            val m = indexs.size
            // 前缀和
            val preSums = LongArray(m + 1
            for (i in indexs.indices {
                preSums[i + 1] = preSums[i] + indexs[i]
            }
            for ((i, x in indexs.withIndex( {
                // x * i 是 Int 运算会溢出，需要乘以 1 转换为 Long 运算
                val left = 1L * x * i - preSums[i]
                val right = (preSums[m] - preSums[i + 1] - 1L * x * (m - 1 - i
                ret[x] = left + right
            }
        }
        return ret
    }
}

复杂度分析：

    时间复杂度：$O(n$ 其中 n 为 nums 数组的长度，分组、前缀和的时间是 $O(n$，每个位置的距离和计算时间为 $O(1$；
  • 空间复杂度：$O(n$ 不考虑分组空间，需要前缀和数组 $O(n$。

题解三（前缀和 + DP）

ret[x] = x * i - preSums[i] + (preSums[m] - preSums[i + 1] - x * (m - 1 - i

ret[x] = (preSums[m] - preSums[i + 1] - preSums[i] + x (2 * i - m + 1

class Solution {
    fun distance(nums: IntArray: LongArray {
        val n = nums.size
        // 分组
        val map = HashMap<Int, ArrayList<Int>>(
        for (index in nums.indices {
            map.getOrPut(nums[index] { ArrayList<Int>( }.add(index
        }
        val ret = LongArray(n
        // 前缀和 DP
        for ((_, indexs in map {
            val m = indexs.size
            var leftSum = 0L
            var rightSum = 0L
            for (element in indexs {
                rightSum += element
            }
            for ((i, x in indexs.withIndex( {
                rightSum -= x
                ret[x] = rightSum - leftSum + 1L * x * (2 * i - m + 1
                leftSum += x
            }
        }
        return ret
    }
}

复杂度分析：

    时间复杂度：$O(n$ 其中 n 为 nums 数组的长度，分组时间是 $O(n$，每个位置的距离和计算时间为 $O(1$；
  • 空间复杂度：$O(1$ 不考虑分组空间。

相似题目：

    1685. 有序数组中差绝对值之和

2616. 最小化数对的最大差值（Medium）

题目地址

题目描述

给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对，每个下标对对应数值取差值，你需要使得这 p 个差值的 最大值 最小。同时，你需要确保每个下标在这 p 个下标对中最多出现一次。

i 和 j ，这一对的差值为 |nums[i] - nums[j]| ，其中 |x| 表示 x 的 绝对值 。

p 个下标对对应数值 最大差值 的 最小值 。

问题分析

    二分的值越大，越能 / 越不能满足条件；
  • 二分的值越小，越不能 / 越能满足条件。

贪心思路：由于元素位置不影响结果，可以先排序，尽量选相邻元素。

题解（二分 + 贪心）

如何二分？

    二分的 left：0，无法构造出更小的差值；
  • 二分的 right：数组的最大值 - 数组的最小值，无法构造出更大的差值；
  • 我们可以选择一个差值 max，再检查差值 max 是否能够构造出来：
    • 如果存在差值为 max 的方案：那么小于 max 的差值都不能构造（无法构造出更小的差值）；
    • 如果不存在差值为 max 的方案：那么大于 max 的差值都能构造（任意调整数对使得差值变大即可）；

如何判断 “差值为 max 的方案”，即 “存在至少 p 个数对，它们的最大差值为 max 的方案” 存在？

举个例子，在数列 [1, 1, 2, 3, 7, 10] 中，p = 2，检查的差值 max = 5。此时我们构造数列对 {1, 1} {2, 3} 满足差值不超过 max 且方案数大于等于 p 个，那么 max 就是可构造的，且存在比 max 更优的方案。

所以，现在的问题转换为如何构造出尽可能多的数列数，使得它们的差值不超过 max？

class Solution {
    fun minimizeMax(nums: IntArray, p: Int: Int {
        if (p == 0 return 0
        // 排序
        nums.sort(
        val n = nums.size
        // 二分查找
        var left = 0
        var right = nums[n - 1] - nums[0]
        while (left < right {
            val mid = (left + right ushr 1
            if (check(nums, p, mid {
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left
    }

    // 检查
    private fun check(nums: IntArray, p: Int, max: Int: Boolean {
        var cnt = 0
        var i = 0
        while (i < nums.size - 1 {
            if (nums[i + 1] - nums[i] <= max {
                // 选
                i += 2
                cnt += 1
            } else {
                i += 1
            }
            if (cnt == p return true
        }
        return false
    }
}

复杂度分析：

    时间复杂度：$O(nlgn + nlgU$ 其中 n 是 nums 数组的长度，U 是数组的最大差值。预排序时间为 $O(nlgn$，二分次数为 $lgU$，每轮检查时间为 $O(n$；
  • 空间复杂度：$O(lgn$ 排序递归栈空间。

2617. 网格图中最少访问的格子数（Hard）

题目地址

题目描述

给你一个下标从 0 开始的 m x n 整数矩阵 grid 。你一开始的位置在 左上角 格子 (0, 0 。

(i, j 的时候，你可以移动到以下格子之一：

    满足 j < k <= grid[i][j] + j 的格子 (i, k （向右移动），或者
  • 满足 i < k <= grid[i][j] + i 的格子 (k, j （向下移动）。

右下角 格子 (m - 1, n - 1 需要经过的最少移动格子数，如果无法到达右下角格子，请你返回 -1 。

问题分析

初看之下这道题与经典题 45. 跳跃游戏 II 非常相似，简直是二维上的跳跃游戏问题。在 45. 这道题中，有时间复杂度 O(n 且空间复杂度 O(1 的动态规划解法，我也可以用图的思路去思考 45. 题（当然它的复杂度不会由于动态规划）

45. 跳跃游戏 II（最短路思路）

参考 Dijkstra 最短路算法的思路，我们将数组分为 “已确定集合” 和 “候选集合” 两组，那么对于已确定集合中最短路长度最小的节点 j，由于该点不存在更优解，所以可以用该点来确定其它店的最短路长度。

class Solution {
    fun jump(nums: IntArray: Int {
        val n = nums.size
        val INF = Integer.MAX_VALUE
        // 候选集
        val unVisitSet = HashSet<Int>(n.apply {
            // 排除 0
            for (i in 1 until n {
                this.add(i
            }
        }
        // 最短路长度
        val dst = IntArray(n { INF }
        dst[0] = 0
        // 队列
        val queue = LinkedList<Int>(
        queue.offer(0
        while (!queue.isEmpty( {
            // 由于边权为 1，队列中最先访问的节点一定是最短路长度最短的节点
            val from = queue.poll(
            // 更新可达范围
            for (to in from + 1..Math.min(from + nums[from], n - 1 {
                if (!unVisitSet.contains(to continue
                // 最短路
                queue.offer(to
                dst[to] = dst[from] + 1
                // 从候选集移除
                unVisitSet.remove(to
                // 到达终点
                if (to == n - 1 break
            }
        }
        return dst[n - 1]
    }
}

复杂度分析：

    时间复杂度：$O(n^2$ 其中 n 是 nums 数组的长度，每个节点最多入队一次，每次出队最多需要扫描 n - 1 个节点
  • 空间复杂度：$O(n$
class Solution {
    fun jump(nums: IntArray: Int {
        val n = nums.size
        val INF = Integer.MAX_VALUE
        // 候选集（平衡二叉树）
        val unVisitSet = TreeSet<Int>(.apply {
            // 排除 0
            for (i in 1 until n {
                this.add(i
            }
        }
        // 最短路长度
        val dst = IntArray(n { INF }
        dst[0] = 0
        // 队列
        val queue = LinkedList<Int>(
        queue.offer(0
        while (!queue.isEmpty( {
            // 由于边权为 1，队列中最先访问的节点一定是最短路长度最短的节点
            val from = queue.poll(
            // 更新可达范围
            val max = Math.min(from + nums[from], n - 1
            while (true {
                // 大于等于 from 的第一个元素
                val to = unVisitSet.ceiling(from ?: break
                if (to > max break
                // 最短路
                queue.offer(to
                dst[to] = dst[from] + 1
                // 从候选集移除
                unVisitSet.remove(to
                // 到达终点
                if (to == n - 1 break
            }
        }
        return dst[n - 1]
    }
}

复杂度分析：

    时间复杂度：$O(nlgn$ 其中 n 是 nums 数组的长度，每个节点最多入队一次，每次寻找左边界的时间是 O(lgn;
  • 空间复杂度：$O(n$ 平衡二叉树空间。

题解（BFS + 平衡二叉树 + 队列）

    1、由于题目每个位置有向右和向下两个选项，所以我们需要建立 m + n 个平衡二叉树；
  • 2、由于存在向右和向下两种可能性
class Solution {
    fun minimumVisitedCells(grid: Array<IntArray>: Int {
        val n = grid.size
        val m = grid[0].size
        if (n == 1 && m == 1 return 1
        // 每一列的平衡二叉树
        val rowSets = Array(n { TreeSet<Int>( }
        val columnSets = Array(m { TreeSet<Int>( }
        for (row in 0 until n {
            for (column in 0 until m {
                if (row + column == 0 continue
                rowSets[row].add(column
                columnSets[column].add(row
            }
        }
        // 队列（行、列、最短路长度）
        val queue = LinkedList<IntArray>(
        queue.offer(intArrayOf(0, 0, 1

        while (!queue.isEmpty( {
            val node = queue.poll(
            val row = node[0]
            val column = node[1]
            val dst = node[2]
            val step = grid[row][column]

            // 向右
            var max = Math.min(column + step, m - 1
            while (true {
                val to = rowSets[row].ceiling(column ?: break
                if (to > max break
                // 最短路
                queue.offer(intArrayOf(row, to, dst + 1
                // 从候选集移除（行列都需要移除）
                rowSets[row].remove(to
                columnSets[column].remove(row
                // 到达终点
                if (row == n - 1 && to == m - 1 return dst + 1
            }

            // 向下
            max = Math.min(row + step, n - 1
            while (true {
                val to = columnSets[column].ceiling(row ?: break
                if (to > max break
                // 最短路
                queue.offer(intArrayOf(to, column, dst + 1
                // 从候选集移除（行列都需要移除）
                rowSets[row].remove(row
                columnSets[column].remove(to
                // 到达终点
                if (to == n - 1 && column == m - 1 return dst + 1
            }
        }
        return -1
    }
}

复杂度分析：

    时间复杂度：$O(nm·(lgn + lgm$ 其中 n 是行数，m 是列数，每个点最多入队一次，每次出队需要 O(lgn + lgm 时间确定左边界；
  • 空间复杂度：$O(nm$ 平衡二叉树空间。

近期周赛最短路问题：

    2612. 最少翻转操作数（Hard）
  • 2608. 图中的最短环（Hard）
  • 2577. 在网格图中访问一个格子的最少时间（Hard）

为了 Guardian 加油！

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

赞同 (31) or 分享 (0)
游客 发表我的评论   换个身份
取消评论

表情
(0)个小伙伴在吐槽