数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究用 C++ 玩淘汰游戏
假设我们有一个从 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
while rem > 1
if 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
更新于: 2020 年 5 月 2 日
756 次浏览
广告