剑指 Offer 62. 圆圈中最后剩下的数字(约瑟夫环问题)
程序员文章站
2024-03-07 21:03:03
...
题目:
题解:约瑟夫环问题
1. 题解一:模拟链表,O(n²)
2. 题解二:数学解法,O(n)
代码:
1. 代码一:模拟链表,O(n²)
import java.util.*;
public class 面试题62 {
// 方法1:模拟链表
public static int lastRemaining(int n, int m) {
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0; i < n; i++)
{
list.add(i);
}
int index = 0;
while(n > 1)
{
index = (index + m - 1) % n;
list.remove(index);
n--;
}
return list.get(0);
}
public static void main(String[] args) {
int n1 = 5, m1 = 3;
int res1 = lastRemaining(n1, m1);
System.out.println(res1); // 3
int n2 = 10, m2 = 17;
int res2 = lastRemaining(n2, m2);
System.out.println(res2); // 2
}
}
2. 代码二:数学解法,O(n)
import java.util.*;
public class 面试题62 {
// 方法2:数学解法
public static int lastRemaining(int n, int m) {
int ans = 0;
// 最后一轮剩下2个人,所以从2开始反推
for(int i = 2; i <= n; i++)
{
ans = (ans + m) % i;
}
return ans;
}
public static void main(String[] args) {
int n1 = 5, m1 = 3;
int res1 = lastRemaining(n1, m1);
System.out.println(res1); // 3
int n2 = 10, m2 = 17;
int res2 = lastRemaining(n2, m2);
System.out.println(res2); // 2
}
}
参考:
上一篇: Java 编程之IO流资料详细整理
下一篇: Android如何实现接收和发送短信