[Jianzhi offer] 62 The last remaining number in the circle

The finger of the sword Offer 62. The last number in the circle

subject

0,1,···,n-1 this n Number in a circle , From numbers 0 Start , Delete the... From this circle every time m A digital （ Delete and count from the next number ）. Find the last number left in the circle .

for example ,0、1、2、3、4 this 5 Numbers make a circle , From numbers 0 Start deleting the 3 A digital , Before deleting 4 The numbers in turn are 2、0、4、1, So the last remaining number is 3.

Ideas

• Create a list Simulate circular linked list
• Add all elements to list in
• Every time m Step . Remove elements , Pay attention to the residual operation

Code

class Solution {
    
    public int lastRemaining(int n, int m) {
    
        //  Create a circular linked list to simulate a circle 
        ArrayList<Integer> list = new ArrayList<>(n);
        for(int i = 0; i < n; i++)
        {
    
            list.add(i);
        }
        int idx = 0;
        while(n > 1)
        {
    
            idx = (idx + m - 1) % n;//  Every time I go M Step   Remainder   Because it's a ring 
            list.remove(idx);
            n--;
        }
        return list.get(0);
    }
}