文章目錄

• 題目描述
• 思路 & 代碼
• • • 鏈表模擬法
    • 數(shù)學(xué)方法
    • 二刷

題目描述

• 約瑟夫環(huán)！題目可太經(jīng)典了
• 說實話還是有點(diǎn)難度的= =
  

思路 & 代碼

鏈表模擬法

• 第一想法是用 LinkedList，但是會超時，于是選擇ArrayList
• 關(guān)鍵在于 index = (index + m - 1) % n這個公式的推導(dǎo)，注意這個 -1 噢～

class Solution {public int lastRemaining(int n, int m) {// 模擬鏈表法：LinkedList 會超時，用 ArrayListArrayList<Integer> list = new ArrayList<>();for(int i = 0; i < n; i++) {list.add(i);}int index = 0;while(n > 1){// -1: 進(jìn)行刪除后前移index = (index + m - 1) % n;list.remove(index);n--;}// 剩下最后一個～return list.get(0);} }

數(shù)學(xué)方法

• 倒推法，非常厲害，需要花時間理解。
• 甜姨的這篇題解寫得很好
• 主要思路：經(jīng)過 n 輪后，只剩下最后一個答案，此時下標(biāo)一定為0。那么往前推到經(jīng)過 n - 1輪后，此時有兩個數(shù)字，如果能推出此時答案下標(biāo)，那么就可以迭代地推到一開始（未去掉數(shù)字時）的答案下標(biāo)，然后就得到答案了～
• 想推出上一輪下標(biāo)，此時有什么信息：當(dāng)前輪下標(biāo)、當(dāng)前輪數(shù)字個數(shù)、規(guī)定刪除計數(shù)。
• 根據(jù)這三個已知量，有公式 ans = (m + ans) % i。其實就是往前補(bǔ) m 個，然后再取余即可。

class Solution {public int lastRemaining(int n, int m) {// 數(shù)學(xué)方法：倒推// 最后剩下一個數(shù)字，下標(biāo)就是0int ans = 0;// 最后一輪剩下兩個人，從后往前for(int i = 2; i <= n; i++){// 推出“當(dāng)前元素下標(biāo)在上一輪中的下標(biāo)”ans = (m + ans) % i;}// 結(jié)束后，元素下標(biāo) == 元素return ans;} }

二刷

• 模擬法

class Solution {public int lastRemaining(int n, int m) {List<Integer> 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);} }

• 數(shù)學(xué)法：倒推， 先 + m 恢復(fù)到上一狀態(tài)，再用上一狀態(tài)長度 i 來進(jìn)行數(shù)值修正

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;} }

總結(jié)

以上是生活随笔為你收集整理的【LeetCode笔记】剑指 Offer 62. 圆圈中最后剩下的数字（Java、约瑟夫环、链表）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。