长沙市网站推广哪家专业,学网站建设课程,贵阳网页设计培训,网站制作应该选什么文章目录题目描述思路 代码链表模拟法数学方法二刷题目描述
约瑟夫环#xff01;题目可太经典了说实话还是有点难度的
思路 代码
链表模拟法
第一想法是用 LinkedList#xff0c;但是会超时#xff0c;于是选择ArrayList关键在于 index (index m - 1) %…
文章目录题目描述思路 代码链表模拟法数学方法二刷题目描述
约瑟夫环题目可太经典了说实话还是有点难度的
思路 代码
链表模拟法
第一想法是用 LinkedList但是会超时于是选择ArrayList关键在于 index (index m - 1) % n这个公式的推导注意这个 -1 噢
class Solution {public int lastRemaining(int n, int m) {// 模拟链表法LinkedList 会超时用 ArrayListArrayListInteger list new ArrayList();for(int i 0; i n; i) {list.add(i);}int index 0;while(n 1){// -1: 进行删除后前移index (index m - 1) % n;list.remove(index);n--;}// 剩下最后一个return list.get(0);}
}数学方法
倒推法非常厉害需要花时间理解。甜姨的这篇题解写得很好主要思路经过 n 轮后只剩下最后一个答案此时下标一定为0。那么往前推到经过 n - 1轮后此时有两个数字如果能推出此时答案下标那么就可以迭代地推到一开始未去掉数字时的答案下标然后就得到答案了想推出上一轮下标此时有什么信息当前轮下标、当前轮数字个数、规定删除计数。根据这三个已知量有公式 ans (m ans) % i。其实就是往前补 m 个然后再取余即可。
class Solution {public int lastRemaining(int n, int m) {// 数学方法倒推// 最后剩下一个数字下标就是0int ans 0;// 最后一轮剩下两个人从后往前for(int i 2; i n; i){// 推出“当前元素下标在上一轮中的下标”ans (m ans) % i;}// 结束后元素下标 元素return ans;}
}二刷
模拟法
class Solution {public int lastRemaining(int n, int m) {ListInteger loop new ArrayList();for(int i 0; i n; i) {loop.add(i);}int index 0;while(loop.size() 1) {index (index m - 1) % loop.size();loop.remove(index);}return loop.get(0);}
}数学法倒推 先 m 恢复到上一状态再用上一状态长度 i 来进行数值修正
class Solution {public int lastRemaining(int n, int m) {int ans 0;for(int i 2; i n; i) {ans (ans m) % i;}return ans;}
}
