当前位置: 代码迷 >> 综合 >> leetcode 390. Elimination Game
  详细解决方案

leetcode 390. Elimination Game

热度:72   发布时间:2024-01-16 18:04:59.0

leetcode 390. Elimination Game

题意:给你一个数N,代表一个[1,n]的数组,第一次操作从左往右删除1,3,5,...下标的数,第二次操作从右往左删除第一次操作剩下的x,x-2,x-4,...下标的数(x是第一次操作后的元素总数),重复一二操作,直到只有一个数。

n的大小没告诉我们,先暴力一发,不好意思超时了!

对不起,我不会写!看了下别人的思路。。。

lastRemaining(n)表示从左往右删除

比如lastRemaining(8)

1 2 3 4 5 6 7 8

2 4 6 8

2 6

6

eliminateFromRight(n)表示从右往左删除

比如eliminateFromRight(8)

1 2 3 4 5 6 7 8

1 3 5 7

3 7

3

可以看到                             lastRemaining(8)+eliminateFromRight(8)=9;

做了别的测试,得到            lastRemaining(n)+eliminateFromRight(n)=n+1;                            (1)

那么:                                lastRemaining(n/2)+eliminateFromRight(n/2)=n/2+1;                   (2)

第二个式子移项可以得到:  eliminateFromRight(n/2)=n/2+1- lastRemaining(n/2)                    (3)


好了,再来看看lastRemaining(n)和eliminateFromRight(n/2)的关系

最初的序列为 1,2,3,…,n,也就是                                                    lastRemaining(n) (第一步)

第二次为 2,4,6...,n-1或者n,这个也就是2*(1,2,3,...,n/2),也就是    2*eliminateFromRight(n/2)        (4)

将(3)带入(4),得到                                                                        2*(n/2+1- lastRemaining(n/2))(第二步)

进去下去就是递归。。。

最后一步n=1时,就是1。

class Solution {
public:int lastRemaining(int n) {return n == 1 ? 1 : 2 * (1 + n / 2 - lastRemaining(n / 2));}
};
这钟题目不是打表找规律,就是递归找规律!