題目

給定一個從1 到 n 排序的整數列表。

我們不斷重複這兩步，從左到右和從右到左交替進行，直到只剩下一個數字。

返回長度為 n 的列表中，最後剩下的數字。

示例：輸入:

n = 9,

1 2 3 4 5 6 7 8 9

2 4 6 8

2 6

6

輸出:6

1、遞迴；時間複雜度O(log(n))，空間複雜度O(log(n))

func lastRemaining(n int) int {	if n == 1 {		return 1	}	// f(2k)/f(2k+1) = 2(k+1-f(k))，最後奇數2k+1不影響結果	return 2 * (n/2 + 1 - lastRemaining(n/2))}

2、遞迴；時間複雜度O(log(n))，空間複雜度O(log(n))

func lastRemaining(n int) int {	return dfs(n, 1)}func dfs(n int, isLeftToRight int) int {	if n == 1 {		return 1	}	if n%2 == 1 { // 奇數		return 2 * dfs(n/2, 1-isLeftToRight)	}	if isLeftToRight == 1 { // 偶數從左往右		return 2 * dfs(n/2, 1-isLeftToRight)	}	// 偶數從右往左，如1，2，3，4，5，6，7，8 => 1，3，5，7	return 2*dfs(n/2, 1-isLeftToRight) - 1}

Medium題目，暴力法容易超時，分析找到規律即可