0390. Elimination Game

# 390. Elimination Game#

## 题目 #

You have a list `arr` of all integers in the range `[1, n]` sorted in a strictly increasing order. Apply the following algorithm on `arr`:

• Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
• Repeat the previous step again, but this time from right to left, remove the rightmost number and every other number from the remaining numbers.
• Keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Given the integer `n`, return the last number that remains in `arr`.

Example 1:

``````Input: n = 9
Output: 6
Explanation:
arr = [1, 2,3, 4,5, 6,7, 8,9]
arr = [2,4, 6,8]
arr = [2, 6]
arr = [6]

``````

Example 2:

``````Input: n = 1
Output: 1

``````

Constraints:

• `1 <= n <= 109`

## 题目大意 #

• 从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。
• 重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。
• 不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。

## 解题思路 #

• 模拟题。按照题意，第一轮从左往右删除数字，第二轮从右往左删除数字。题目要求最后剩下的数字，模拟过程中不需要真的删除元素。只需要标记起始元素，该轮步长和方向即可。最后总元素只剩下一个即为所求。

## 代码 #

``````package leetcode

func lastRemaining(n int) int {
start, dir, step := 1, true, 1
for n > 1 {
if dir { // 正向
start += step
} else { // 反向
if n%2 == 1 {
start += step
}
}
dir = !dir
n >>= 1
step <<= 1
}
return start
}
``````

Apr 8, 2023