第一題

2582. 遞枕頭

已解答

簡單

相關標簽

相關企業

提示

n?個人站成一排，按從?1?到?n?編號。

最初，排在隊首的第一個人拿著一個枕頭。每秒鐘，拿著枕頭的人會將枕頭傳遞給隊伍中的下一個人。一旦枕頭到達隊首或隊尾，傳遞方向就會改變，隊伍會繼續沿相反方向傳遞枕頭。

• 例如，當枕頭到達第?n?個人時，TA 會將枕頭傳遞給第?n - 1?個人，然后傳遞給第?n - 2?個人，依此類推。

給你兩個正整數?n?和?time?，返回?time?秒后拿著枕頭的人的編號。

示例 1：

輸入：n = 4, time = 5
輸出：2
解釋：隊伍中枕頭的傳遞情況為：1 -> 2 -> 3 -> 4 -> 3 -> 2 。
5 秒后，枕頭傳遞到第 2 個人手中。

示例 2：

輸入：n = 3, time = 2
輸出：3
解釋：隊伍中枕頭的傳遞情況為：1 -> 2 -> 3 。
2 秒后，枕頭傳遞到第 3 個人手中。

分析思路：

題目有兩個參數time 與n

先分析time參數，有兩種可能為0和不為0

time為0，沒有時間，不計算后面的數。

time不為0，有時間，需要計算后面的數。

再分析n參數，從題目已知有兩種可能n>1和n<1

n>1，數據會隨time的變化而變化

n<=1,數據不會隨time的變化而變化

最后分析time與n的關系

time與n有三種關系

time>n,會發生往復計數的情況。

time=n，會發生往復計數的情況，但結果一定是n-1啦。

time<n,不會發生往復計數的情況。

至此可以得到第一種解決方案

第一種解決方案數數法

按照先從1開始向右計數，到達n時調轉方向向左計數的方法，這種方法不需要考慮time為0的情況，需要屏蔽n為0的情況，需要屏蔽n<=1的情況。

設置一個以time為參數的while循環，當time為0時退出循環，設置flag表明方向，1為向右，2為向左。設置i作為計數參數，程序開始時i為1向右計數，當i等于n時，flag變為-1,i向左計數。

需要注意的是，把n<2剔除。

class Solution {
public:int passThePillow(int n, int time){int i=1;int flag=1;if(n<2){i=n;}else{while(time){if(flag==1){++i;if(i==n){flag=-1;}}else if(flag==-1){--i;if(i==1){flag=1;}}--time;}}return i;}
};

但是第一種思路很挫，非常挫，特別挫，作為代碼狗，怎么能看得上這種思路呢，這種屎山代碼呢，而且還沒用到分析三，相當于剛才的分析白分析啦，不能忍啊，凸(艸皿艸 )。

第二種思路 除余法（廚余垃圾），這種方法也很垃圾

除余法的思路來自于在有限的線段下，除法的結果代表需要往復的次數，余的結果代表他還要走幾次，舉個栗子。

n=4,time=5

注意一下這里，time=5的意思是從5開始，走到0為止，體現在i上，是i要在1之后走出5步。上面的圖表現出time=5時走出了一個往復，用除法體現5/3=1（這里必須是除3也就是n-1,因為向右前進時i只走了三步），剩下的兩部5%3=2,所以n=4,time=5時,i走了一個往復，先向右走到4，然后調頭走到2，這里的5/3=1的1表示的i走完一個全程（全程指的是1到4，或者4到1，不管方向，總之1代表走完一個全程，就是這樣凸(艸皿艸 )這特么的這么難寫，凸(艸皿艸 )啊）；

上面寫了一段，總結一下就是5/3=1表示i走完一段全程，5%3=2表示走完全程之后再走兩步。

確定上面的以后，需要判斷方向，以5/3為例，走完一個全程，需要調頭，這時候的方向是向左的。所以不能被2整除的此時是向左。

接下來以7/3為例

7/3等于2，此時已經走完兩個全程，方向向右。

接下來的余就簡單啦，當(time/(n-1))%2==0時，向右走，此時只需要1+time%(n-1)，相反(time/(n-1))%2!=0時向左走，用n-time%(n-1)就好了。

上面是time>n 的情況，接下來看看time=n的情況。

time=n表示走完一個全程多走一步，實際上也是一個全程以上的問題，可以歸類到上面。

time<n這是一個沒有走完全程的情況，不走完全程時，方向是向右的，那么完全可以帶入多個全程的情況，(time/(n-1))%2==0。

接下來看看n,n分為<=1和>1兩種情況，n<=1這種情況需要剔除，因為題目給的數從2開始，這個就不寫了，也就一個if的事。

再接下來，就是time為0的情況，emmmmmm。。。。。time為0時，完全不影響i=1+time%(n-1);i=n-time%(n-1);計算的結果，所以這個題目的代碼是

class Solution {
public:int passThePillow(int n, int time) {int i=0;if((time/(n-1))%2!=0){i=n-time%(n-1);}else if((time/(n-1))%2==0){i=1+time%(n-1);}return i;}
};

不用循環，但是懶得想，廚余垃圾啊?

最后看一下官方題解，目前么想明白

我們注意到每經過 2×(n?1)2 \times (n - 1)2×(n?1) 的時間，枕頭會被傳遞回起點，所以我們可以直接用 time\textit{time}time 對 2×(n?1)2 \times (n - 1)2×(n?1) 取模求余數。

如果 time<n\textit{time} < ntime<n，枕頭沒有傳遞到隊尾，傳遞到 time+1\textit{time} + 1time+1。
如果 time≥n\textit{time} \ge ntime≥n，枕頭已經傳遞過隊尾，傳遞到 n?(time?(n?1))=n×2?time?1n - (\textit{time} - (n - 1)) = n \times 2 - \textit{time} - 1n?(time?(n?1))=n×2?time?1。