class Solution {
public:
int lastRemaining(int n, int m) {
}
};
剑指 Offer 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^51 <= m <= 10^6原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 1.8 MB, 提交时间: 2023-09-26 09:37:02
func iceBreakingGame(n int, m int) int {
f := 0
for i := 2; i <= n; i++ {
f = (m + f) % i
}
return f
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 6.2 MB, 提交时间: 2023-09-26 09:34:59
class Solution {
public:
int iceBreakingGame(int num, int target) {
int f = 0;
for (int i = 2; i != num + 1; ++i) {
f = (target + f) % i;
}
return f;
}
};
java 解法, 执行用时: 4 ms, 内存消耗: 38 MB, 提交时间: 2023-09-26 09:34:39
class Solution {
public int iceBreakingGame(int num, int target) {
int f = 0;
for (int i = 2; i != num + 1; ++i) {
f = (target + f) % i;
}
return f;
}
}
python3 解法, 执行用时: 2896 ms, 内存消耗: 20.6 MB, 提交时间: 2023-09-26 09:33:52
class Solution:
'''
约瑟夫环问题, 用双端队列模拟
'''
def iceBreakingGame(self, n: int, m: int) -> int:
ans = collections.deque(list(range(n)))
while len(ans)!=1:
ans.rotate(-(m % len(ans)) + 1) #队列左移
ans.popleft() #移动完之后，弹出
return ans[0]
python3 解法, 执行用时: 68 ms, 内存消耗: 14.8 MB, 提交时间: 2021-05-18 13:06:47
class Solution:
def lastRemaining(self, n: int, m: int) -> int:
f = 0
for i in range(2, n+1):
f = (m + f) % i
return f