題目地址
思路
第一種方法肯定是遍歷，暴力洗掉，但是資料量一大就容易超時，
第二種方法，我們想到利用等引數列來進行模擬，
我們定義首項
a0,公差為d，項數為size，
其中公差每次都是翻倍，項數每次都是減半（向下取整），
我們只需要更新首項，最后將其return就可以，
要怎么去更新首項呢？
首先我們知道：有從左到右洗掉和從右到左洗掉，兩種方式，
所以我們先要判斷是哪種方式，
如果是從左到右，就將a0+d；
如果是從右到左，判斷此時的項數：如果項數是偶數，就保持a0不變，反則則a0+d，
基本思路如上，具體細節實作請看下面的代碼，代碼中也有部分注釋，相信寫的比較清楚，
代碼實作（C++）
class Solution {
public:
int lastRemaining(int n)
{
int size=n;
int a0=1;
int d=1;
int loop_time=0; //定義洗掉輪數，初始為0輪，表示還未洗掉
while(size!=1)
{
if(loop_time%2==0) //從左向右洗掉
{
a0=a0+d;
}
else if(loop_time%2==1) //從右向左洗掉
{
if(size%2==0)
{
a0=a0;
}
else if(size%2==1)
{
a0=a0+d;
}
}
size/=2; //長度減半
d*=2; //公差加倍
loop_time++; //次數加1
}
return a0;
}
};
總結
這道題是數學和編程模擬的結合，挺有趣的，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/401478.html
標籤：其他