資料結構
網路
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 次瀏覽
廣告