【每日算法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天前
|
算法 Java
JavaSE——算法(2/2):查找算法-二分查找(前言、详细图解、代码部分)
JavaSE——算法(2/2):查找算法-二分查找(前言、详细图解、代码部分)
11 2
|
10天前
|
算法 搜索推荐 Java
JavaSE——算法(1/2):认识、冒泡排序、选择排序及优化(介绍、详细图解、代码)
JavaSE——算法(1/2):认识、冒泡排序、选择排序及优化(介绍、详细图解、代码)
9 0
|
11天前
|
算法 C语言
数据结构和算法——桶排序和基数排序(图示、伪代码、多关键字排序,基数排序代码)
数据结构和算法——桶排序和基数排序(图示、伪代码、多关键字排序,基数排序代码)
9 0
|
11天前
|
算法 C语言
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
10 0
|
11天前
|
存储 算法 C语言
数据结构和算法——堆排序(选择排序、思路图解、代码、时间复杂度、堆排序及代码)
数据结构和算法——堆排序(选择排序、思路图解、代码、时间复杂度、堆排序及代码)
8 0
|
11天前
|
算法 Shell C语言
数据结构与算法——希尔排序(引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列)
数据结构与算法——希尔排序(引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列)
11 0
|
11天前
|
人工智能 算法 C语言
数据结构与算法——简单排序-冒泡排序、插入排序,时间复杂度下界(图示、代码、时间复杂度、定理)
数据结构与算法——简单排序-冒泡排序、插入排序,时间复杂度下界(图示、代码、时间复杂度、定理)
8 0
|
11天前
|
算法 C语言
数据结构与算法——拓扑排序(引例、拓扑排序、伪代码、代码、关键路径问题)
数据结构与算法——拓扑排序(引例、拓扑排序、伪代码、代码、关键路径问题)
11 0
|
12天前
|
存储 算法 Java
必会的10个经典算法题(附解析答案代码Java/C/Python看这一篇就够)(二)
必会的10个经典算法题(附解析答案代码Java/C/Python看这一篇就够)(二)
20 1
|
12天前
|
存储 算法 Java
必会的10个经典算法题(附解析答案代码Java/C/Python看这一篇就够)(一)
必会的10个经典算法题(附解析答案代码Java/C/Python看这一篇就够)(一)
21 0

热门文章

最新文章