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

题目大意

列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。请你对 arr 应用下述算法：

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

给你整数 n ，返回 arr 最后剩下的数字。

解题思路

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

代码

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
}

Uh oh!

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier! Saves Data!