390. 消除游戲
串列 arr 由在范圍 [1, n] 中的所有整陣列成，并按嚴格遞增排序，請你對 arr 應用下述演算法：
- 從左到右，洗掉第一個數字，然后每隔一個數字洗掉一個，直到到達串列末尾，
- 重復上面的步驟，但這次是從右到左，也就是，洗掉最右側的數字，然后剩下的數字每隔一個洗掉一個，
- 不斷重復這兩步，從左到右和從右到左交替進行，直到只剩下一個數字，
給你整數 n ，回傳 arr 最后剩下的數字，
示例 1：
輸入：n = 9
輸出：6
解釋：
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr = [2, 4, 6, 8]
arr = [2, 6]
arr = [6]
示例 2：
輸入：n = 1
輸出：1
提示：
- 1 <= n <= 109
解題思路：
從題目中可以分析，我們可以使用一個變數來維護陣列最左邊的值，每次回圈洗掉時都會將陣列減半，當陣列長度為1時，回傳此變數及為此題答案，那什么時候維護此時變數呢？
查看演算法可得出更新變數應該存在四種情況：
- 當陣列長度為奇數時，且從左向右洗掉數字，此時最左邊的數字需要洗掉，此時我們需要將左邊變數往右進行偏移，
- 當陣列長度為偶數時，且從左向右洗掉數字，此時最左邊的數字需要洗掉，此時我們需要將左邊變數往右進行偏移，
- 當陣列長度為奇數時，且從右向左洗掉數字，此時最左邊的數字需要洗掉，此時我們需要將左邊變數往右進行偏移，
- 當陣列長度為偶數時，且從右向左洗掉數字，此時最左邊的數字不需要洗掉，此時我們不需要將左邊變數往右進行偏移，
舉例：
輸入：n = 9
輸出：6
解釋：
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr = [2, 4, 6, 8]
arr = [2, 6]
arr = [6]
- 當此時陣列為1, 2, 3, 4, 5, 6, 7, 8, 9時，我們可設定初始變數num = 1，count = n， time = 0， step = 1，
- 這是第一次從左往右洗掉數字，此時陣列長度為奇數，需要將最左邊的數往右偏移step，此時需要將 num = num + step，此時num = 2，需要將step *= 2，此時左移一位，step = step << 1,step = 2,將陣列長度count右移一位，count = count >> 1,count = 4，可得最終陣列2，4，6，8，
- 第二次需要從右向左洗掉數字，此時陣列長度為偶數，不需要將最左邊的數往右偏移step，此時需要將 num = num，此時num = 2，需要將step *= 2，此時左移一位，step = step << 1,step = 4，將陣列長度count右移一位，count = count >> 1,count = 2，可得最終陣列2，6，
- 第三次需要從左向右洗掉數字，此時陣列長度為偶數，需要將最左邊的數往右偏移step，此時需要將 num = num + step，此時num = 6，需要將step *= 2，此時左移一位，step = step << 1,step = 8，將陣列長度count右移一位，count = count >> 1,count = 1，跳出回圈，可得最終陣列6，
代碼：
int lastRemaining(int n){
if(n == 1)
return 1;
int count = n;
int time = 0;
int num = 1;
int step = 1;
while(count > 1)
{
if(time % 2 == 0)
{
num = num + step;
}
else
{
num = (count % 2 == 0) ? num : num + step;
}
time++;
step = step << 1;
count = count >> 1;
}
return num;
}
時間復雜度： O(logn)
空間復雜度： O(1)
新年第二天，大家一起加油，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/401482.html
標籤：其他
上一篇：LeetCode390. 消除游戲題解（Medium）
下一篇：10段代碼教你玩轉C++