Add solution 390

halfrost · halfrost · commit 9e302d29247f · 2022-01-06T01:22:12.000-08:00
diff --git a/leetcode/0390.Elimination-Game/390. Elimination Game.go b/leetcode/0390.Elimination-Game/390. Elimination Game.go
@@ -0,0 +1,18 @@
+package leetcode
+
+func lastRemaining(n int) int {
+	start, dir, cnt, step := 1, true, n, 1
+	for cnt > 1 {
+		if dir { // 正向
+			start += step
+		} else { // 反向
+			if cnt%2 == 1 {
+				start += step
+			}
+		}
+		dir = !dir
+		cnt >>= 1
+		step <<= 1
+	}
+	return start
+}
diff --git a/leetcode/0390.Elimination-Game/390. Elimination Game_test.go b/leetcode/0390.Elimination-Game/390. Elimination Game_test.go
@@ -0,0 +1,47 @@
+package leetcode
+
+import (
+	"fmt"
+	"testing"
+)
+
+type question390 struct {
+	para390
+	ans390
+}
+
+// para 是参数
+// one 代表第一个参数
+type para390 struct {
+	n int
+}
+
+// ans 是答案
+// one 代表第一个答案
+type ans390 struct {
+	one int
+}
+
+func Test_Problem390(t *testing.T) {
+
+	qs := []question390{
+
+		{
+			para390{9},
+			ans390{6},
+		},
+
+		{
+			para390{1},
+			ans390{1},
+		},
+	}
+
+	fmt.Printf("------------------------Leetcode Problem 390------------------------\n")
+
+	for _, q := range qs {
+		_, p := q.ans390, q.para390
+		fmt.Printf("【input】:%v       【output】:%v\n", p, lastRemaining(p.n))
+	}
+	fmt.Printf("\n\n\n")
+}
diff --git a/leetcode/0390.Elimination-Game/README.md b/leetcode/0390.Elimination-Game/README.md
@@ -0,0 +1,74 @@
+# [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
+}
+```
