requirements

Given a list of integers sorted from 1 to n. First, from left to right, starting with the first number, delete every other number until you reach the end of the list. The second step, in the remaining numbers, from right to left, starting with the last digit, delete every other digit until you reach the beginning of the list. We repeat these two steps, alternating from left to right and right to left, until there is only one number left. Returns the last remaining number in a list of length n.

Example:

Input: n = 9, 1 2 3 4 5 6 7 8 9 2 4 6 8 2 6 6 output: 6Copy the code

The core code

class Solution:
    def lastRemaining(self, n: int) - >int:
        base = 1
        res = 1
        while base * 2 <= n:
            res += base
            base *= 2
            if base * 2 > n:
                break
            if int(n / base) % 2= =1:
                res += base
            base *= 2
        return res
Copy the code

Each time the numbers are deleted, the distance between them is twice as large as before.

  • When you delete from left to right, you delete the first number every time;
  • When you delete from right to left, it is possible to delete the first or second digit;
  • If the remaining number is even, the second number is deleted;
  • If the remaining number is odd, the first number is deleted;

So we just need to compute and record the first number in the current array, and once we have the first number, we can compute the rest.

Understanding of the code above: is our from left to right again, remove the Numbers 1, then the distance between our digital becomes 2 times, in removing back again, distance into four times, but when I come back we will determine whether need to delete the first location data, made a judgment. Lack of understanding, this topic is to see.