I*******g
发帖数: 7600 | 1 【 以下文字转载自 Military 讨论区 】
发信人: IFloating (Floating Freely), 信区: Military
标 题: 将军们， 再来做道题
发信站: BBS 未名空间站 (Sat May 20 14:02:51 2017, 美东)
监狱长把一群犯人排成圆圈，假设有1000人，id分别为 1，2，..., 1000.
监狱长决定从1号开始，每隔两个人就杀掉一个人，杀完了尸体拖走， 由于是首位相连
，这样一直杀下去
，直到最后一个人留下来不杀。
所以杀的顺序是3号， 6号， 9号。。。。。。
请问最后谁活下来啊？ | c****e
发帖数: 60 | 2 604 号。 今天刚好在学Python，就拿它来练手：
myList = list(range(1,1001))
def reBuild(list):
"""This function rebuilds a new list after removing the elements that
meet
the condition"""
newList=[]
if len(list) % 3 == 2:
newList.append(list[len(list) -2])
newList.append(list[len(list)-1])
elif len(list) % 3 == 1:
newList.append(list[len(list) -1])
for i in range(1, len(list) - len(list) % 3 + 1 ):
if i%3 != 0:
newList.append(list[i-1])
list = newList
if len(list) > 2:
reBuild(list)
else:
print ("last left ", list[1])
reBuild(myList) | o*******r
发帖数: 73 | 3 OK.
f[1] = 0;
f[i] = (f[i - 1] + m) % i (i > 1)
所以：
public class Solution {
public int lastStand(int n, int m) {
int ret = 0;
for (int i = 2; i <= n; i++) {
ret = (ret + m) % i;
}
return (ret + 1);
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.lastStand(1000, 3));
}
}
复杂度O(n). | u***n
发帖数: 21026 | |
|
