C++ 中的消除游戏
c++server side programmingprogramming更新于 2024/11/8 23:22:00
假设我们有一个从 1 到 n 的已排序整数列表。即从左开始到右结束，我们必须删除第一个数字以及之后的每个其他数字，直到到达列表末尾。我们将再次重复上一步，但这次是从右到左，从剩余数字中删除最右边的数字和每个其他数字。我们将再次重复这些步骤，交替从左到右和从右到左，直到剩下一个数字。我们必须从长度为 n 的列表开始找到剩下的最后一个数字。
因此，如果输入为 n = 9，则步骤如下 −
1,2,3,4,5,6,7,8,9
2,4,6,8
2,6
6
因此答案将是 6。
要解决这个问题，我们将遵循以下步骤 −
left := 1, head := 1, step := 1，rem := n
当 rem > 1
如果 left 非零或 rem 为奇数，则 head := head + step
step := step * 2
left := left 的逆
rem := rem / 2
return head
示例 (C++)
让我们看下面的实现，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lastRemaining(int n) {
int head = 1;
int step = 1;
int rem = n;
int left = 1;
while(rem > 1){
if(left || rem % 2 == 1){
head += step;
}
step *= 2;
left = !left;
rem /= 2;
}
return head;
}
};
main(){
Solution ob;
cout << (ob.lastRemaining(9));
}
输入
9
输出
6
