📖本篇內容：leetcode每日一題390.消除游戲 暴力的數學之美一邊就懂 由淺入深
📆 最近更新：2022年1月1日 leetcode每日一題2022. 將一維陣列轉變成二維陣列 2022年從2022題開始 由1到2我相信咱們會更好
🙊個人簡介：一只二本院校在讀的大三程式猿，本著注重基礎，打卡演算法，分享技術作為個人的經驗總結性的博文博主，雖然可能有時會犯懶，但是還是會堅持下去的，如果你很喜歡博文的話，建議看下面一行~（瘋狂暗示QwQ）
🌇 點贊 👍 收藏 ?留言 📝 一鍵三連 關愛程式猿，從你我做起
本文目錄
- 寫在前面
- 題目
- 示例
- 思路
- 代碼實作
- 執行結果
- 寫在最后
寫在前面
小付在元旦節吃好喝好玩好，不知各位是如何度過這新年的第一天呢？到了第二天了，不要忘記打卡哦~，今天玩得是消除游戲，話不多說，打卡！
題目
- 消除游戲
串列 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
思路
小付剛看到這題的時候還是午覺睡醒的時候，整個腦子木的很，直接暴力遍歷來模擬
但是我忘記了這種中等題一般還要考慮超時這個問題了，所以就出現了.
class Solution {
public int lastRemaining(int n) {
boolean left = true;
List<Integer> list = new ArrayList<>();
//初始化
for (int i = 1; i<=n; i++){
list.add(i);
}
while(true){
if (left){
//當從左往右開始消除的時候
for (int i = 0;i<list.size();i++){
if (list.size() == 1)return list.get(0);
list.remove(i);
}
}else{
//當從右往左開始消除的時候
for (int i = list.size()-1;i>=0;i-=2){
if(list.size() == 1)return list.get(0);
list.remove(i);
}
}
//更換方向
left = !left;
}
}
}
不出意外 你會得到一個
超時的錯誤 ,但是 暴力真的無法解決么？ 我們再來找找規律!
例題：咱們來手動模擬
如n = 20 時 如何解決呢？
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
經過第一次消除！
還是用 left 來進行判讀是為從左往右還是從右往左
第一次消除之后得到：（從左往右）
2 4 6 8 10 12 14 16 18 20
第二次消除之后得到：（從右往左）
2 6 10 14 18
第三次消除之后得到：（從左往右）
6 14
第四次消除之后得到：（從右往左）
6
所以回傳 6
那么我們將回傳的值作為 結果值 將其定為 變數res
這個變數從一開始在 1 的位置 經過每次（從左往右）都在變化，但是從右往左并未變化（這道例題中沒有變化，但實際的是如果此時從右向左遍歷與2取模為1則需要向后移動）我們得到的 n 也在每次 減半 每次移動的值都是前一次移動的倍數，所以代碼實作如下：
代碼實作
class Solution {
public int lastRemaining(int n) {
//需要回傳結果值的位置
int res = 1;
//初始的移動長度
int step = 1;
//判斷從左往右還是從右往左
boolean left = true;
while (n > 1){
//只有當從左邊或者右邊余數為1時才進行步長移動
if (left || n % 2 == 1){
res += step;
}
// n 數量減半
n = n >> 1;
// 步長加倍
step = step << 1;
// 方向轉換
left = !left;
}
return res;
}
}
執行結果
寫在最后
打卡2022 - 01 -02 ！
加油！堅持每天打卡~
最后
每天進步點 每天識訓點
愿諸君 事業有成 學有所獲
如果覺得不錯 別忘啦一鍵三連哦~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/401567.html
標籤：其他
上一篇：CAS了解一下