mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-06 17:44:10 +08:00
74 lines
2.0 KiB
Markdown
74 lines
2.0 KiB
Markdown
# [390. Elimination Game](https://leetcode.com/problems/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`
|
||
|
||
## 题目大意
|
||
|
||
列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。请你对 arr 应用下述算法：
|
||
|
||
- 从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。
|
||
- 重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。
|
||
- 不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
|
||
|
||
给你整数 n ，返回 arr 最后剩下的数字。
|
||
|
||
## 解题思路
|
||
|
||
- 模拟题。按照题意，第一轮从左往右删除数字，第二轮从右往左删除数字。题目要求最后剩下的数字，模拟过程中不需要真的删除元素。只需要标记起始元素，该轮步长和方向即可。最后总元素只剩下一个即为所求。
|
||
|
||
## 代码
|
||
|
||
```go
|
||
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
|
||
}
|
||
``` |