- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
⭐️ 本文已收录到 AndroidFamily ,技术和职场问题,请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问.
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭将基于 Java / Kotlin 语言,为你分享常见的数据结构与算法问题,及其解题框架思路.
本文是数据结构与算法系列的第 18 篇文章,完整文章目录请移步到文章末尾~ 。
这道题是 LeetCode 上的 1040. 移动石子直到连续 II ,难度是 Meduium,难度分是 2455。虽然是 Medium 题,但是打 Hard 标签一点也不为过。长期作为中等题的难度 Top1,直到去年被 2289. 使数组按非递减顺序排列 题挤下来.
标签:模拟、贪心、排序、同向双指针 。
三枚石子放置在数轴上,位置分别为 a,b,c.
每一回合,你可以从两端之一拿起一枚石子(位置最大或最小),并将其放入两端之间的任一空闲位置。形式上,假设这三枚石子当前分别位于位置 x, y, z 且 x < y < z。那么就可以从位置 x 或者是位置 z 拿起一枚石子,并将该石子移动到某一整数位置 k 处,其中 x < k < z 且 k != y.
当你无法进行任何移动时,即,这些石子的位置连续时,游戏结束.
要使游戏结束,你可以执行的最小和最大移动次数分别是多少? 以长度为 2 的数组形式返回答案:answer = [minimum_moves, maximum_moves] 。
示例 1:
输入:a = 1, b = 2, c = 5
输出:[1, 2]
解释:将石子从 5 移动到 4 再移动到 3,或者我们可以直接将石子移动到 3。
示例 2:
输入:a = 4, b = 3, c = 2
输出:[0, 0]
解释:我们无法进行任何移动。
提示:
1 <= a <= 100
1 <= b <= 100
1 <= c <= 100
a != b, b != c, c != a
概括问题目标:
求移动石头直到连续的最小和最大操作次数,每次操作只能选择端点石头,且只能移动到非端点位置.
分析问题要件:
提高抽象程度:
分析放置策略:
最大移动次数分析:
最小移动次数分析:
示意图 。
如何维护长度为 n 的滑动窗口:
同向双指针:
for(i in nums 索引) {
while (j < n - 1 && 移动后窗口不大于 n) j++
}
class Solution {
fun numMovesStonesII(stones: IntArray): IntArray {
val n = stones.size
// 排序
stones.sort()
// 最大移动次数
val max1 = stones[n - 1] - stones[1] + 1 - (n - 1)
val max2 = stones[n - 2] - stones[0] + 1 - (n - 1)
val maxOp = Math.max(max1, max2)
// 最小移动次数
var minOp = n
var j = 0
// 枚举左端点
for (i in 0 until n) {
while (j < n - 1 && stones[j + 1] - stones[i] + 1 <= n) j++
if (n - (j - i + 1) == 1 /* 窗口空位数 == 1 */ && stones[j] - stones[i] + 1 == n - 1 /* 窗口石头数 == n - 1 */) {
minOp = Math.min(minOp, 2)
} else {
minOp = Math.min(minOp, n - (j - i + 1) /* 窗口空位数 */)
}
}
return intArrayOf(minOp, maxOp)
}
}
复杂度分析:
推荐阅读
数据结构与算法系列完整目录如下(2023/07/11 更新):
- #1 链表问题总结
- #2 链表相交 & 成环问题总结
- #3 计算器与逆波兰表达式总结
- #4 高楼丢鸡蛋问题总结
- #5 为什么你学不会递归?谈谈我的经验
- #6 回溯算法解题框架总结
- #7 下次面试遇到二分查找,别再写错了
- #8 什么是二叉树?
- #9 什么是二叉堆 & Top K 问题
- #10 使用前缀和数组解决 “区间和查询” 问题
- #11 面试遇到线段树,已经这么卷了吗?
- #12 使用单调队列解决 “滑动窗口最大值” 问题
- #13 使用单调栈解决 “下一个更大元素” 问题
- #14 使用并查集解决 “朋友圈” 问题
- #15 如何实现一个优秀的 HashTable 散列表
- #16 简答一波 HashMap 常见面试题
- #17 二叉树高频题型汇总
- #18 下跳棋,极富想象力的同向双指针模拟
- #19 ChatGPT 通过谷歌算法面试,年薪 18.3 万美金
Java & Android 集合框架系列文章: 跳转阅读 。
最后此篇关于数据结构与算法#18下跳棋,极富想象力的同向双指针模拟的文章就讲到这里了,如果你想了解更多关于数据结构与算法#18下跳棋,极富想象力的同向双指针模拟的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我正在开发一个跳棋游戏,我想将字符“x”和“o”打印到二维数组中。但我的代码不起作用,它打印出不同的字符。我需要帮助。 这是我的代码: #include void message() { char
我是一名 Android 新手,试图利用我的 VB 经验(8 年前)设计一个 UI。我正在尝试创建一个棋盘,在 VB 中,它是一种形式,我可以根据需要在多行中连续添加多个可调整大小的面板小部件。由于这
我是一个相对缺乏经验的程序员,最近我对为学校项目制作西洋跳棋游戏应用产生了兴趣。我不确定我可以从哪里开始(或者我是否应该尝试)创建它。我想到的项目可能只涉及简单的 AI 和多人游戏模式。 谁能给我一些
我是一名优秀的程序员,十分优秀!