【每日算法Day 85】图解算法:一行代码解决约瑟夫环的变体

简介: 【每日算法Day 85】图解算法:一行代码解决约瑟夫环的变体

题目链接

LeetCode 390. 消除游戏[1]

题目描述

给定一个从  到  排序的整数列表。首先,从左到右,从第一个数字开始,每隔一个数字进行删除,直到列表的末尾。第二步,在剩下的数字中,从右到左,从倒数第一个数字开始,每隔一个数字进行删除,直到列表开头。我们不断重复这两步,从左到右和从右到左交替进行,直到只剩下一个数字。返回长度为  的列表中,最后剩下的数字。

示例1

输入:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6
输出:
6

题解

还记得几天前讲过的约瑟夫环问题吗?不记得了就回顾一下吧:

韦阳的博客:【每日算法Day 74】经典面试题:约瑟夫环,我敢打赌你一定不会最后一种方法![2]

知乎专栏:【每日算法Day 74】经典面试题:约瑟夫环,我敢打赌你一定不会最后一种方法![3]

当时我们的方法是通过编号映射来递归寻找下一轮存活的人的,那么这题也可以尝试用同样的方法。

我们分奇偶两种情况来考虑。

如果  ,那么如上图所示,第一轮消除完了之后,剩下的数字就是绿色的偶数部分。

接着就要从右往左递归地消除了,那我们从右往左给绿色数字重新编号为  到  ,问题就转化为了  个数字的情况下,最后剩余的数字是几了。

假设我们用  表示初始时  个数字最后剩下的编号,那么绿色部分重新编号后最后剩下的数字就是  。但是怎么将  重新映射回绿色的数字编号呢?

通过观察我们可以发现,绿色数字整除  ,再加上蓝色的映射后的编号,结果一定等于  。所以我们就得到了映射回去的公式:

比如说你求出来  ,也就是蓝色部分最后剩下的数字是  ,那么映射成绿色的编号就是  ,这就是最初的编号了。

如果  ,那么如上图所示,只需要在后面加个橙色的  就行了。

但是第一轮的时候它就被消除了,所以绿色的剩下的编号和之前偶数情况没有任何区别。所以最终的答案也是:

最后发现奇偶情况下,公式其实可以统一起来,用  来替换  就得到了:

代码

c++

class Solution {
public:
    int lastRemaining(int n) {
        return n==1 ? 1 : 2*(n/2+1-lastRemaining(n/2));
    }
};

python

class Solution:
    def lastRemaining(self, n: int) -> int:
        return 1 if n==1 else 2*(n//2+1-self.lastRemaining(n//2))
相关文章
|
10天前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
|
21天前
|
算法 测试技术 开发者
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗;代码审查通过检查源代码发现潜在问题,提高代码质量和团队协作效率。本文介绍了一些实用的技巧和工具,帮助开发者提升开发效率。
23 3
|
20天前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
1月前
|
存储 缓存 算法
如何通过优化算法和代码结构来提升易语言程序的执行效率?
如何通过优化算法和代码结构来提升易语言程序的执行效率?
|
1月前
|
搜索推荐
插入排序算法的讲解和代码
【10月更文挑战第12天】插入排序是一种基础的排序算法,理解和掌握它对于学习其他排序算法以及数据结构都具有重要意义。你可以通过实际操作和分析,进一步深入了解插入排序的特点和应用场景,以便在实际编程中更好地运用它。
|
3月前
|
机器学习/深度学习 人工智能 自然语言处理
【自然语言处理】TF-IDF算法在人工智能方面的应用,附带代码
TF-IDF算法在人工智能领域,特别是自然语言处理(NLP)和信息检索中,被广泛用于特征提取和文本表示。以下是一个使用Python的scikit-learn库实现TF-IDF算法的简单示例,并展示如何将其应用于文本数据。
262 65
|
26天前
|
缓存 分布式计算 监控
优化算法和代码需要注意什么
【10月更文挑战第20天】优化算法和代码需要注意什么
18 0
|
1月前
|
算法 Java
数据结构与算法学习六:单向环形链表应用实例的约瑟夫环问题
这篇文章通过单向环形链表的应用实例,详细讲解了约瑟夫环问题的解决方案,并提供了Java代码实现。
21 0
|
1月前
|
算法 Java 测试技术
数据结构 —— Java自定义代码实现顺序表,包含测试用例以及ArrayList的使用以及相关算法题
文章详细介绍了如何用Java自定义实现一个顺序表类,包括插入、删除、获取数据元素、求数据个数等功能,并对顺序表进行了测试,最后还提及了Java中自带的顺序表实现类ArrayList。
21 0
|
2月前
|
机器学习/深度学习 存储 算法
经典算法代码
这段代码展示了多个经典算法,包括:穷举法解决“百钱买百鸡”问题;递推法计算“猴子吃桃”问题;迭代法求解斐波那契数列及折纸高度超越珠峰的问题。同时,还提供了希尔排序算法实现及披萨票务订购系统和汉诺塔问题的链表存储解决方案。每部分通过具体案例解释了算法的应用场景与实现方法。
31 3