Elimination Game
这道题目出于leetcode,题目虽然很简单但是很有趣，因为有趣才能称得上游戏吧！
0x00 题目介绍
简单介绍一下题目意思
给定一个数字N（N>0），一个列表存着1～N的数字。每次从左到右从第一个数字开始，然后隔开一个数字删除数字，一直删除到最后再从右向左删除，一直删除到只剩下一个数字。
Example:
Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6
Output:
6
0x01 解法
解法一 按部就班
- 思想：直接按照题目意思，模拟删除步骤
- 代码：
int lastRemaining(int n) {
int start = 1, step = 1;
while (n > 1) {
//模拟删除元素一直到最后元素
start += step + (n-2)/2 * 2*step;
//每删除一轮剩余元素为该轮元素的一半
n /= 2;
//每次到达最后一个元素反向并且步数扩大两倍
//因为每次都隔开删除一个元素，
//所以下一轮的步数都是上一次的两倍
step *= -2;
}
return start;
}
算法时间复杂度:O(logN),空间复杂度O(1);
代码思想简单，易懂，一般最开始想到的也是这种算法
解法二 来去递归(一)
-
思想
模拟去回删除元素,去即为从左到右,回即为从右往左,用一个变量代表状态,
每轮删除后剩余这轮元素的一半.递归退出条件为当剩余元素为我们设
F(N)为从{1~N}删除的剩余元素.1). 从左往右删除
那么每次删除掉的元素为奇数项元素,剩下的元素里全部都是偶数元素,并且最终结果也在这些元素里面.
那么此时我们将所有元素同时除以2,此时元素又变为{1N/2},此时问题就变为找出{1N/2}剩余元素*2
即:F(N)=2*F(N/2);(方向----> N为偶数8) 1 2 3 4 5 6 7 8
剩余的元素在2{1,2,3,4}里面 即2F(8/2);(方向----> N为奇数9)
1 2 3 4 5 6 7 8 9
剩余元素为2{1,2,3,4}即 2F(9/2)2). 从右往左删除
如果最后一个元素是偶数,如果我们从右往左删除,剩余元素全部为奇数,为了使得剩余元素全部为偶数
(方便下一步运算,因为我们需要把N的问题分解为N/2的问题)那么我们将所有元素 加1,这样删除后
剩余元素就全部变为偶数了,为了弥补加1,我们需要在获得的结果后减1;
所以当从左往右的时候F(N) = F(N/2)-(1-N%2)=F(N/2)-1+N%2比如:当N=8 list = {1,2,3,4,5,6,7,8}
(方向<---- N为偶数8)
1 2 3 4 5 6 7 8
答案在剩余元素{1,3,5,7}里面,如果我们写作2{1,2,3,4}答案明显不对,需要修正变为2{1,2,3,4}-1即2*F(8/2)-1;(方向<---- N为奇数9)
1 2 3 4 5 6 7 8 9
剩余元素为2{1,2,3,4}即 2F(9/2)如果我们使用2*F(4/2) 答案明显不对了,所以我们需要在此基础上需要加上一个offset 1 或者在开始的基础上加一
递归版本代码
int getNext(int n,bool direction){
if(n==1) return 1;
//判断方向 从左往右
if(direction) return 2*getNext(n/2,!direction);
// 从右往左 偶数需要减一
else return 2*(getNext(n/2,!direction))-1+n%2;
}
int lastRemaining1(int n) {
return getNext(n,true);
}
时间复杂度O(logN) 空间复杂度O(logN)
- 迭代版本代码
/*
direction:删除方向 true:从左往右 false:从右往左
ratio: 记录当前删除深度
offset: 偏移值(分析如上)
*/
int lastRemaining(int n) {
bool direction = true;
int ratio = 1;
int offset = 0;
while(n!=1){
if(!direction && n%2==0)
offset+=ratio;
ratio<<=1;
n/=2;
direction=!direction;
}
return ratio-offset;
}
时间复杂度O(logN) 空间复杂度O(1)
解法三 来去递归(二)
-
算法思想
也是来往依次删除,把每次删除操作统一为一个方向.这样不需要每次判定方向如何,
也不需要判定是否为偶数再去减掉偏移值.如何将删除方向统一为一个方向呢?
注意:我们每次都是先从左往右删除
例如:当N=8时
方向(---->) 1 2 3 4 5 6 7 8
剩余元素在:2*{1,2,3,4}里面, 接着删除,此时我们删除方向反向为右往左.
如果我们将{1,2,3,4}反转,并用4+1-反转后的结果
即:4+1 - {1,2,3,4} = {4,3,2,1} 此时我们从右往左删除{4,3,2,1}就转化为从左往右删除{1,2,3,4}
方向就统一了起来.当然N为奇数的时候也是一样,读者可以手动模拟一下 代码
int lastRemaining(int n) {
if(n <= 1) { return 1; }
//每次需要删除元素减半
n >>= 1;
//将方向反转 且结果需要乘以2
return (1 + n - lastRemaining2(n)) << 1;
};
时间复杂度O(logN) 空间复杂度O(1)
短短三行代码就解决了问题,短小精悍!
0x02结论
有趣的题目千篇一律,精致的解法百里挑一!