「约瑟夫环」
class Solution {
public int findTheWinner(int n, int k) {
if (n <= 1) return n;
int ans = (findTheWinner(n - 1, k) + k) % n;
if(ans == 0){
return n;
}else{
return ans;
}
// return ans == 0 ? n : ans;
}
}
https://mp.weixin.qq.com/s/xP9m1Ci6bMX9LRYe3t1X2w
f[i]定义，起始是从左开始，轮流换向间隔删除(从左向右，从右向左，从左向右… ，直到只剩下一个数)。 f[i]为从左开始，最后剩下的那个数。f’[i]为从右开始，最后剩下的那个数。
f
[
i
]
+
f
′
[
i
]
=
i
+
1
f[i] + f'[i] = i + 1
f[i]+f′[i]=i+1
f
[
i
]
=
f
′
[
i
2
]
?
2
f[i] = f'[\frac{i}{2}] * 2
f[i]=f′[2i?]?2
将
f
′
[
i
]
f'[i]
f′[i]进行消除:
f
[
i
]
=
2
?
(
i
2
+
1
?
f
[
i
2
]
)
f[i] = 2 * (\frac{i}{2}+1-f[\frac{i}{2}])
f[i]=2?(2i?+1?f[2i?])
需要实现的函数 lastRemaining 其实就是 f [ i ] f[i] f[i]
class Solution {
public int lastRemaining(int n) {
if(n <= 1){
return n;
}else{
return 2 * (n / 2 + 1 - lastRemaining(n / 2));
}
}
}
