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

简介: 一行代码解决约瑟夫环的变体

题目链接


LeetCode 390. 消除游戏[1]

题目描述



image.png

示例1

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

题解


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

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

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

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

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

image.png


image.png

image.png


image.png

image.png


c++

classSolution {
public: 
intlastRemaining(intn) { 
returnn==1?1 : 2*(n/2+1-lastRemaining(n/2)); 
    }
};

python

classSolution: 
deflastRemaining(self, n: int) ->int:    
return1ifn==1else2*(n//2+1-self.lastRemaining(n//2))

参考资料


[1]

LeetCode 390. 消除游戏: https://leetcode-cn.com/problems/elimination-game/

[2]

韦阳的博客:【每日算法Day 74】经典面试题:约瑟夫环,我敢打赌你一定不会最后一种方法!: https://godweiyang.com/2020/03/19/leetcode-interview-62/

[3]

知乎专栏:【每日算法Day 74】经典面试题:约瑟夫环,我敢打赌你一定不会最后一种方法!: https://zhuanlan.zhihu.com/p/114391147

image.png

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习喜欢与人分享技术与知识,期待与你的进一步交流~


相关文章
|
2天前
|
搜索推荐 算法
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
|
2天前
|
搜索推荐
排序算法----快速排序----详解&&代码
排序算法----快速排序----详解&&代码
|
2天前
|
搜索推荐
排序算法---冒泡排序----详解&&代码
排序算法---冒泡排序----详解&&代码
|
2天前
|
搜索推荐
排序算法---希尔排序---详解&&代码
排序算法---希尔排序---详解&&代码
|
2天前
|
搜索推荐
排序算法---插入排序-----详解&&代码
排序算法---插入排序-----详解&&代码
|
2天前
|
搜索推荐
排序算法---选择排序-----详解&&代码
排序算法---选择排序-----详解&&代码
|
12天前
|
算法 Java
JavaSE——算法(2/2):查找算法-二分查找(前言、详细图解、代码部分)
JavaSE——算法(2/2):查找算法-二分查找(前言、详细图解、代码部分)
11 2
|
12天前
|
算法 搜索推荐 Java
JavaSE——算法(1/2):认识、冒泡排序、选择排序及优化(介绍、详细图解、代码)
JavaSE——算法(1/2):认识、冒泡排序、选择排序及优化(介绍、详细图解、代码)
9 0
|
13天前
|
算法 C语言
数据结构和算法——桶排序和基数排序(图示、伪代码、多关键字排序,基数排序代码)
数据结构和算法——桶排序和基数排序(图示、伪代码、多关键字排序,基数排序代码)
9 0
|
13天前
|
算法 C语言
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
10 0

热门文章

最新文章