思路:這類資料很多的處理,一定要先去尋找前後互相之間的關系,并确定邊界情況,這樣就會好處理很多。
比如本題,可推導出公式:f(n) = (m+f(n-1))% m;當n變為1即長度為1時結束,f(n)代表n時最終删除的那個數值
題目:
面試題62. 圓圈中最後剩下的數字
0,1,n-1這n個數字排成一個圓圈,從數字0開始,每次從這個圓圈裡删除第m個數字。求出這個圓圈裡剩下的最後一個數字。
例如,0、1、2、3、4這5個數字組成一個圓圈,從數字0開始每次删除第3個數字,則删除的前4個數字依次是2、0、4、1,是以最後剩下的數字是3。
示例 1:
輸入: n = 5, m = 3
輸出: 3
示例 2:
輸入: n = 10, m = 17
輸出: 2
限制:
1 <= n <= 10^5
1 <= m <= 10^6
思路:
// 疊代 72ms 34.6mb
/**
* @param {number} n
* @param {number} m
* @return {number}
*/
var lastRemaining = function(n, m) {
let r = 0;
for(let i = 2; i <= n; i++) {
r = (m + r) % i;
}
return r
};
// 遞歸 可寫成遞歸,但是爆棧,不能通過
var lastRemaining = function (n, m) {
return recur(n, m)
};
function recur (n, m) {
if (n === 1) return 0
let r = recur(n - 1, m)
return (m + r) % n
}