个人中心
文章发布
退出
作者热门文章
- Java锁的逻辑（结合对象头和ObjectMonitor）
- 还在用饼状图？来瞧瞧这些炫酷的百分比可视化新图形（附代码实现）⛵
- 自动注册实体类到EntityFrameworkCore上下文，并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
36
4
本文已收录到 AndroidFamily ，技术和职场问题，请关注公众号 [彭旭锐] 提问.
大家好，我是小彭.
上周跟大家讲到小彭文章风格的问题，和一些朋友聊过以后，至少在算法题解方面确定了小彭的风格。虽然竞赛算法题的文章受众非常小，但却有很多像我一样的初学者，他们有兴趣参加但容易被题目难度和大神选手的题解劝退.
考虑到这些跟我一样的小白，我决定算法题解风格会向这些初学者倾斜，我们不会强调最优解法，而是强调从题意分析到问题抽象，再从暴力解法一步步升级到最优解法的推导过程，希望能帮到喜欢算法的朋友，向 Guardian 出发.
好一波强行自证价值？ 😁 。
今天讲 LeetCode 单周赛第 340 场，今天状态不好，掉了一波大分.
2614. 对角线上的质数（Easy） 。
这道题是最近第 2 次出现质数问题，注意 1 不是质数！ 。
2615. 等值距离和（Medium） 。
这道题是标准的前缀和数组题目，我们有从暴力到前缀和的解法，最后有消除前缀和数组的最优解法，理解从暴力解法到最优解法的推导过程非常重要.
2616. 最小化数对的最大差值（Medium） 。
这道题是 “极大化最小值” 问题，与以前我们讲过的 “高楼丢鸡蛋” 问题属于同一种类型，理解 “极大化最小值” 中的单调性与二分查找的思路非常重要.
2617. 网格图中最少访问的格子数（Hard） 。
这道题是经典题目 45. 跳跃游戏 II 的二维版本，我创新性地从图的最短路视角理解 跳跃游戏 II，再迁移到这道二维数组问题上，难度降低为 Medium.
https://leetcode.cn/problems/prime-in-diagonal 。
给你一个下标从 0 开始的二维整数数组 nums .
返回位于 nums 至少一条 对角线 上的最大 质数 。如果任一对角线上均不存在质数，返回 0 .
注意:
1 ，且不存在除 1 和自身之外的正整数因子，则认为该整数是一个质数。 i ，使得 nums[i][i] = val 或者 nums[i][nums.length - i - 1]= val ，则认为整数 val 位于 nums 的一条对角线上。 
遍历两条对角线上的元素，如果是质数则更新答案。注意 1 不是质数！ 。
另外再检查数据量，数组的长度 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
}
}
复杂度分析:
近期周赛质数问题:
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
}
}
复杂度分析:
分析计算元素 x 与组内元素距离差绝对值之和的过程:
以组内下标为 [0, 1, 2, 3, 4, 5] 为例，下标 [2] 位置的距离和计算过程为:
我们以 [2] 为分割点将数组分为两部分，则发现:
数组区间和有前缀和的套路做法，可以以空间换时间降低时间复杂度.
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
}
}
复杂度分析:
将 left + right 的计算公式合并，则有 。
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
}
}
复杂度分析:
相似题目:
https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/description/ 。
给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对，每个下标对对应数值取差值，你需要使得这 p 个差值的 最大值 最小 。同时，你需要确保每个下标在这 p 个下标对中最多出现一次.
对于一个下标对 i 和 j ，这一对的差值为 |nums[i] - nums[j]| ，其中 |x| 表示 x 的 绝对值 .
请你返回 p 个下标对对应数值 最大差值 的 最小值 .
二分思路：“极大化最小值” 和 “极小化最小值” 存在单调性，是典型的二分查找问题.
贪心思路：由于元素位置不影响结果，可以先排序，尽量选相邻元素.
如何二分?
如何判断 “差值为 max 的方案”，即 “存在至少 p 个数对，它们的最大差值为 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?
如果当前元素 x 参与配对，那么配对相邻数的差值是最小的，否则 x 与不相邻数匹配无法得到更优解.
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
}
}
复杂度分析:
https://leetcode.cn/problems/minimum-number-of-visited-cells-in-a-grid/ 。
给你一个下标从 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 .
分析 1 - 题意：这道题的题意可能有点小绕，其实就是说站在 [i][j] 位置上，且 grid[i][j] = x，则最远可以走到向右 [i][j + x] 或向下 [i + x][j] 的位置上。现在求从左上角到右下角的最少移动次数，显然，这是一个在二维空间上的最短路问题，将格子之间的可达关系视为图的边，也可以视为图上的最短路问题.
初看之下这道题与经典题 45. 跳跃游戏 II 非常相似，简直是二维上的跳跃游戏问题。在 45. 这道题中，有时间复杂度 O(n) 且空间复杂度 O(1) 的动态规划解法，我也可以用图的思路去思考 45. 题（当然它的复杂度不会由于动态规划） 。
定义 dst[i] 表示到达 i 位置的最少跳跃次数，那么对于 i 位置可以到达的区间 (i+1, i + nums[i])，它们的最少跳跃次数最多不会高于 dst[i] + 1.
参考 Dijkstra 最短路算法的思路，我们将数组分为 “已确定集合” 和 “候选集合” 两组，那么对于已确定集合中最短路长度最小的节点 j，由于该点不存在更优解，所以可以用该点来确定其它店的最短路长度.
而且由于这道题中图的边权是 1，所以只要越早进入 “已确定集合” 中的点的最短路长度越低，不需要使用小顶堆来搜索 “已确定集合中最短路长度最小的节点” 。
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]
}
}
复杂度分析:
在内层循环更新可达范围时，会重复检查已经确定最短路长度的点，我们可以使用平衡二叉树优化，这就类似于上一场周赛中第 4 题 2612. 最少翻转操作数 的思路.
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]
}
}
复杂度分析:
理解了用最短路思路解决一维数组上的跳跃游戏 II，很容易推广到二维数组上:
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
}
}
复杂度分析:
近期周赛最短路问题:
为了 Guardian 加油！ 。
最后此篇关于LeetCode周赛340，质数/前缀和/极大化最小值/最短路/平衡二叉树的文章就讲到这里了,如果你想了解更多关于LeetCode周赛340，质数/前缀和/极大化最小值/最短路/平衡二叉树的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
36
4
0
我在使用 Android 时遇到了一点问题。 我有我的 GPS 位置，明确的经纬度，以及以米为单位的搜索射线(例如 100 米)，可以吗？ 想象一下我在射线形成的圆心的位置，我会知道如何在 Andro
深夜的编程之旅 这是一个深夜，街头灯光昏暗，大部分人都已陷入梦乡。但对于我来说，这却是一个灵感迸发的时刻。窗外的星空仿佛在诉说着某种宇宙的密码，而键盘下的代码则是我解密这个宇宙的工具。 一个突如其来的
我将数据集结构定义为 struct Dataset: Hashable { var x: Double var y: Double } 然后是数组 var dataset: [Data
我在 Excel 文件中有一个摘要选项卡，需要查看应计选项卡才能找到 Max和 Min .我遇到的问题是有许多不同的位置/商品组合，我需要找到 Max和 Min基于位置/商品组合。位置和商品位于两个单
我有一个 Excel 表，其中包含两列感兴趣的年份和捐款。年份值为 2008,2009,2010 等... 我想获得 2009 年所有捐款中的最低金额。我试过了 MIN(IF(Year="2009",
到现在为止，我刚刚找到了为列表中多个数据帧中的列获取最大值的解决方案。 我已经将数据帧 df1, df2, df3, ..., dfn 存储在列表 dfList 中，我想获取列 df_ 的最大值$a
假设我有一个列名列表作为向量: vec=c("C1" , "C2" ,"C3"). 我知道这些列名来自数据框 df: df: C1 C2 C3 C4 C5 1 2 3 4 5 1 4
我需要计算大数组的最小值/最大值。我知道Math.max.apply() ，但在大型数组上，它会因堆栈溢出异常而失败。有什么简单的解决方案吗？ 最佳答案 使用 sort() 对数组进行排序方法它使用快
例如，我有一个像这样的模型: class Record(models.Model): name = CharField(...) price = IntegerField(...)
我正在编写一个用于测试听力的简单应用，并且正在使用Audiotrack生成纯音。因为它是用于测试听力的应用程序，所以我使用非常低的音量来播放这些音调。 要设置音量，我使用音轨的 setVolume(f
Example data set 对，上面是我的数据集子段图像的链接。它以 3 列为一组，第一个是浓度，第二个是限定值，最后一个是 MDL - 并持续最多 95 个 sample (因此总共 285
我想计算 df 的每 n 行的最小值/最大值，比如 10，但是使用 df.rolling(10).max() 给出第 0-9、1-10、2-11 行的值等。我想要 0-9、10-19、20-29 等
我被问到了关于 c# 的同样问题 here我发现通过使用 linq 你可以轻松地做到这一点。 但是既然 java 中的 linq 没有其他选择，我该如何简单地做到这一点呢？ 最佳答案 如果您想要类似于
我曾经使用过数组，并且知道如何对使用数值(double 和 int)的数组进行排序，但我必须使用字符串数组制作相同的应用程序。我的教授不允许我发挥“创造力”，也不允许我与其他可能有助于完成这项工作的静
我想知道通过这样的回溯获得某些事实的最大值(最年长的人)是否是个好主意: data(MaxID, MaxName, MaxAge), \+ (data(ID, Name, Age), ID \= Ma
我想计算 df 的每 n 行的最小值/最大值，比如 10，但是使用 df.rolling(10).max() 给出第 0-9、1-10、2-11 行的值等。我想要 0-9、10-19、20-29 等
我的数据如下所示: df <- tribble( ~A, ~B, 0.2, 0.1, 0.2, 0.3, 0.5, 0.1, 0.7, 0.9,
我有以下数据集 Date Category 2014-01-01 A 2014-01-02 A 2014-01-03 A 2014-01-04
我是使用 Python 进行数据分析的初学者，并且坚持以下几点: 我想使用广播/矢量化方法从各个列 (pandas.dataframe) 中找到最大值(value)。 我的数据框的快照如下: 最佳答案
C99 中是否有一个标准函数来使用给定的比较函数获取给定数组中的最小/最大元素。 类似: void* get_min(void* start,size_t size,size_t elementSiz
我是一名优秀的程序员,十分优秀！