Sword finger offer 62 The last remaining number in the circle

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

lastRemaining(n - 1, m) yes n - 1 Number , namely 0, 1, …, n - 2, From numbers 0 Start , Delete the... From this circle every time m A digital （ Delete and count from the next number ）. And the real sequence m, m + 1, …, n - 2, 0, …, m - 2 Make an innuendo .x -> (m + x) % n.

Method 1 ： recursive

class Solution:
    # Python  The default recursion depth is not enough , Manual setting required 
    sys.setrecursionlimit(100000)

    def lastRemaining(self, n: int, m: int) -> int:        
        if n == 0: return 0
        x = self.lastRemaining(n - 1, m)
        return (m + x) % n

class Solution {
    
    public int lastRemaining(int n, int m) {
    
        if(n == 1) return 0;
        int index = lastRemaining(n - 1, m); // x  Is in accordance with the  0, 1, 2 ... n - 2  The result of the calculation 
        return (index + m) % n; //  Make an innuendo with the actual 
    }
}

Method 2 ： iteration

law ： Delete the... In each round m The number is the first m - 1 The number is moved to the end of the array for circulation , Every time i It's equivalent to moving left m A place .
trace to its source ： From the last time index by 0 Start tracing back , Let in turn index Situated i Move right m A place , That is to add m.
Every time in reverse order index + m You can find the one in the last round i Where index, At the same time, it is necessary to take the remainder of the round array to prevent cross-border size

class Solution {
    
    public int lastRemaining(int n, int m) {
    
        int index = 0; //  Extrapolate from the last remaining number , Finally get  0, 1, ... , n - 1  Index in .
        for (int i = 2; i <= n; ++i) {
    
            index = (m + index) % i;
        }
        return index;
    }
}

Method 3 ： Simulation , use ArrayList simulation ： Time complexity O(n^2)

class Solution {
    
    public int lastRemaining(int n, int m) {
    
        List<Integer> list = new ArrayList<>(); // LinkedList  Overtime 
        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);
    }
}

1823. Find the winner of the game

Method 1 ： recursive

class Solution {
    
    public int findTheWinner(int n, int k) {
    
        if(n == 1) return 1;
        int x = findTheWinner(n - 1, k); // x  Convert to index 
        return (k + x - 1) % n + 1;
    }
}

Method 2 ： iteration

class Solution {
    
    public int findTheWinner(int n, int k) {
    
        int winner = 1;
        for (int i = 2; i <= n; i++) {
    
            winner = (k + winner - 1) % i + 1;
        }
        return winner;
    }
}

Method 3 ： Queue simulation

class Solution {
    
    public int findTheWinner(int n, int k) {
    
        Deque<Integer> q = new ArrayDeque<>();
        for(int i = 1; i <= n; i++) q.add(i);
        while(q.size() > 1){
    
            for(int i = 0; i < k - 1; i++){
    
                q.offer(q.pop());
            }
            q.pop();
        }
        return q.peek();
    }
}