给定一个从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题目，暴力法容易超时，分析找到规律即可
,
