Massive Algorithms: LeetCode 390

http://bookshadow.com/weblog/2016/08/28/leetcode-elimination-game/

There is a list of sorted integers from 1 to n. 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 right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n.

Example:

Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

Output:
6

X.

下面这种迭代的解法是我请教另一位大神的方法，个人感觉也非常叼，膜拜大神中。我们先来看两个简单的例子：

n = 8
1 2 3 4 5 6 7 8
   2    4    6   8
   2          6
               6

n = 7
1 2 3 4 5 6 7
   2 4    6
     4

如果我们仔细观察，我们可以发现从左往右删的时候，每次都是删掉第一个数字，而从右往左删的时候，则有可能删掉第一个或者第二个数字，而且每删一次，数字之间的距离会变为之前的两倍。我们要做的是每次记录当前数组的第一个数字，而且我们再通过观察可以看出，从右往左删时，如果剩下的数字个数是偶数个时，删掉的是第二个数字；如果是奇数个的时候，删掉的是第一个数字。总结出了上述规律

    int lastRemaining(int n) {
        int base = 1, res = 1;
        while (base * 2 <= n) {
            res += base;
            base *= 2;
            if (base * 2 > n) break;
            if ((n / base) % 2 == 1) res += base;
            base *= 2;
        }
        return res;
    }

X. https://blog.csdn.net/feifeiiong/article/details/73612197
我们首先分析能够得到的信息。一个很容易观察到的变化规律就是步长信息，那我们就首先得到步长的规律。观察第一列的步长为2，第二列的步长为4（相隔元素），第三列元素为8（假设存在10 11 12 第二列元素就变成 2 4 6 8 10 12 第三列就变成 2 6 10），也就是说步数在每轮循环中是上一轮的两倍。我们再来观察元素个数递减规律，发现元素个数是按1/2的速度递减的。当递减元素个数减少到1时，就得到了最终的剩余元素。最难的部分就是追踪每次的头部元素，很容易观察到的一个结论是，从左侧开始的头部元素都是上一次的头部元素加上步长。对于从右侧开始的迭代过程，则分为两种情况，一种情况是左侧头部元素不变，一种情况是左侧头部元素为上次迭代的头部元素加步长，对于后一种情况，我们容易观察到的一点是，在剩余元素是奇数个时，头部元素会发生改变，否则不变。因此，根据上面分析得到的几点结论，我们可以写出最终的解如下
遇到这种题目，不要着急去写，先把能够得到的信息列出来，然后分析题目要求，再挖掘有用的信息，一步一步分析。

https://leetcode.com/problems/elimination-game/discuss/87119/JAVA%3A-Easiest-solution-O(logN)-with-explanation

    public int lastRemaining(int n) {
        boolean left = true;
        int remaining = n;
        int step = 1;
        int head = 1;
        while (remaining > 1) {
            if (left || remaining % 2 ==1) {
                head = head + step;
            }
            remaining = remaining / 2;
            step = step * 2;
            left = !left;
        }
        return head;
    }

My idea is to update and record head in each turn. when the total number becomes 1, head is the only number left.

When will head be updated?

if we move from left
if we move from right and the total remaining number % 2 == 1
like 2 4 6 8 10, we move from 10, we will take out 10, 6 and 2, head is deleted and move to 4
like 2 4 6 8 10 12, we move from 12, we will take out 12, 8, 4, head is still remaining 2

then we find a rule to update our head.

example:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

Let us start with head = 1, left = true, step = 1 (times 2 each turn), remaining = n(24)
we first move from left, we definitely need to move head to next position. (head = head + step)
So after first loop we will have:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 - > 2 4 6 8 10 12 14 16 18 20 22 24
head = 2, left = false, step = 1 * 2 = 2, remaining = remaining / 2 = 12
second loop, we move from right, in what situation we need to move head?
only if the remaining % 2 == 1, in this case we have 12 % 2 == 0, we don't touch head.
so after this second loop we will have:
2 4 6 8 10 12 14 16 18 20 22 24 - > 2 6 10 14 18 22
head = 2, left = true, step = 2 * 2 = 4, remaining = remaining / 2 = 6
third loop, we move from left, move head to next position
after third loop we will have:
2 6 10 14 18 22 - > 6 14 22
head = 6, left = false, step = 4 * 2 = 8, remaining = remaining / 2 = 3
fourth loop, we move from right, NOTICE HERE:
we have remaining(3) % 2 == 1, so we know we need to move head to next position
after this loop, we will have
6 14 22 - > 14
head = 14, left = true, step = 8 * 2 = 16, remaining = remaining / 2 = 1
while loop end, return head

X. log(n) leftToRight
https://blog.csdn.net/fuxuemingzhu/article/details/79526571
看到这个题，我一定能肯定，这个题的不是使用暴力去求解的，否则没有意义。这个题的做法非常巧妙。消除的规律是同样的，只不过顺序不同，那么，可以封装成两个函数，互相调用达到目的。这是建立在这个思想上的：

第一次从左向右检索完，剩下，2 4 6 8，其实这跟1 2 3
4的信息几乎是一样的，只是差了倍数2，所以问题就变为从右往左对规模4的问题进行操作，找到答案乘以2就行。对于从右往左，如果是1 2 3 4
5的话，检索完还剩2 4，同样是1 2的问题，如果是 1 2 3 4，剩 1 3，我们可以认为是1
2乘以2减一，总之，我们可以找到将每次的剩余子序列转化为同类子问题的方法。

这个算是分而治之的思想，很巧妙的通过2倍关系实现了递归调用。

    public int lastRemaining(int n) {
      return leftToRight(n);
    }

    private static int leftToRight(int n) {
      if(n <= 2) return n;
      return 2 * rightToLeft(n / 2);
    }

    private static int rightToLeft(int n) {
      if(n <= 2) return 1;
      if(n % 2 == 1) return 2 * leftToRight(n / 2);
      return 2 * leftToRight(n / 2) - 1;
    }

X.
https://leetcode.com/problems/elimination-game/discuss/87116/Java-Recursion-and-Proof

f(n, left): the result starting from the left.
f(n, right): the result starting from the right.
For Elimination Game, we are asked to find f(n, left).
For the base case, f(1, left) = 1 = f(1, right)

Claim: f(n, left) + f(n, right) = n + 1 for all n >= 1.
Use this, we immediately get the recursion formula:
f(n, left) = 2*f(n/2, right) = 2*[n + 1 - f(n/2, left)]

The claim can be seen from few examples and proven by induction.
It is true for n = 1. Now, assuming the claim is true for all n <= N we need to show f(N+1, left) + f(N+1, right) = N + 2.

Case 1: N is even.
Clearly, f(N+1, left) = f(N, left) as the additional number N+1 will be eliminated in the first round and will not affect the result of f(N, left).

For f(N+1, right), from the remaining elements after the first round, we have:
f(N+1, right) = 2*f(N/2, left).
And by induction, 2*f(N/2, left) = N + 2 - 2*f(N/2, right).
Note that 2*f(N/2, right) = f(N, left).(N is even.)
Combining everything gives:
f(N+1, right) = N + 2 - f(N, left) = N + 2 - f(N+1, left) (Case 1 done).

Case 2: N is odd.
The argument is similar to Case 1 but roles of left and right are exchanged.

    public int lastRemaining(int n) {
        if(n == 1) return 1;
        return 2*(1 + n/2 - lastRemaining(n/2));
    }

https://blog.csdn.net/MebiuW/article/details/52713918
这道题首先可以推出一个规律：
1、无论是1还是2，若当前序列长度为k，那么下一轮一定只剩k/2【整除】个

然后我们来说下这个递推的式子：
1、一开始不是1,2,3,4,5,6..n 对吧？第一轮结束剩下2，4，6，8，10….2*(n/2) 等于2*(1,2,3,4…n/2),看着这个序列，是否觉得和一开始的问题很像，对吧，但是似乎有点不一样？
2、对于下一轮而言，虽然是1,2,3,4…,n/2,但是顺序是相反的消除？那既然这样，我们转变成n/2,…,4,3,2,1不就好了，所以我们还是按照1的方式求1，2，3，4…n/2但是对于结果要n/2 + 1 - lastremain掉不就好了？

https://leetcode.com/problems/elimination-game/discuss/87120/one-line-java-solution-based-on-Josephus-Problem

This problem is similar to Josephus problem when k=2, the recursive version is easy after referring to the josephus problem on wiki.
it is highly recommend to refer to Josephus problem first, because i am chinese, my english is poor, my explanation may not be good, but the wiki explanation is very good.

    public int lastRemaining(int n) {
        return ((Integer.highestOneBit(n) - 1) & (n | 0x55555555)) + 1;
    }

recursive version
for example:
1,2,3,4,...n
if you start from the left to right, the result is i
then, if you start from right to left, the result is n+1-i
for n numbers, after one pass, there are n/2 left, each number is two times of the original,
1,2,3,4,5,6,7,8,9
after one pass
2,4,6,8
assume the result of 1,2,3,4 from left to right is f(4)
then the result of 1,2,3,4 from right to left is 5-f(4)
then the result of 2,4,6,8 from right to left is 2*(5-f(4))
this is the formula
f(n)=2(1+n/2-f(n/2))* when n is 1, of course the result is 1

    public int lastRemaining(int n) {
        return n == 1 ? 1 : 2 * (1 + n / 2 - lastRemaining(n / 2));
    }

non-recursive version:

    public int lastRemaining(int n) {
        Stack<Integer> stack = new Stack<>();
        while (n > 1) {
            n /= 2;
            stack.push(n);
        }
        int result = 1;
        while (!stack.isEmpty()) {
            result = 2 * (1 + stack.pop() - result);
        }
        return result;
    }

模拟题，时间复杂度O(log n) 空间复杂度O(1)。

根据题设要求的数字移除过程，可以发现每执行完一趟数字移除操作，列表中剩余相邻数字之间的差都会加倍。

因此解决问题的关键就是找到每一趟数字消除操作之后剩余数字的起点。

def lastRemaining(self, n): """ :type n: int :rtype: int """ a = p = 1 cnt = 0 while n > 1: n /= 2 cnt += 1 p *= 2 if cnt % 2: a += p / 2 + p * (n - 1) else: a -= p / 2 + p * (n - 1) return a

http://zyy1314.com/2016/08/28/leetcode390/

解题思路是每次遍历删除元素时，更新并用head记录数组第一个元素。每次遍历之后，数组相邻元素间隔step都会变成2倍，当数组个数为1时，head就是最后剩下的元素。
那什么时候更新head呢？

当我们从左边开始遍历删除元素时
当我们从右边开始遍历元素，并且剩下的数组元素个数为奇数时

例如：

2,4,6,8,10

从10开始移动，会删除10,6,2。数组的第一个元素head会被删除，因此需要更新head

2,4,6,8,10,12

从12从右至左遍历，我们会删除12,8,4，head此时依然是2


public int lastRemaining(int n) {

boolean left = true;

int remain = n;

int step = 1;

int head = 1;

while(remain>1){

if(left||remain%2==1){

head +=step;



}

remain /=2;

left =!left;

step *=2;

}

return head;

}

https://segmentfault.com/a/1190000006739199

    public int lastRemaining(int n) {
        int rest = n, start = 1, step = 2;
        boolean left = true;
        while (rest > 1) {
            rest /= 2;
            if (left) start = start + step * rest - step / 2;
            else start = start - step * rest + step / 2;
            step *= 2;
            left = !left;
        }
        return start;
    }

X. Recursive
https://discuss.leetcode.com/topic/58042/c-1-line-solution-with-explanation
第一次从左往右删除的时候，奇数都被删掉了，剩下的都是偶数。如果我们对所有数都除以2，那么得到一个1到n/2的新数列。下一次我们从右往左删出，那么返回的结果应该是调用递归的结果lastRemaining(n / 2)在数组1到n/2之间的镜像。何为镜像，比如1, 2, 3, 4这个数字，2的镜像就是3, 1的镜像是4

After first elimination, all the rest numbers are even numbers.
Divide by 2, we get a continuous new sequence from 1 to n / 2.
For this sequence we start from right to left as the first elimination.
Then the original result should be two times the mirroring result of lastRemaining(n / 2).

int lastRemaining(int n) {
    return n == 1 ? 1 : 2 * (1 + n / 2 - lastRemaining(n / 2));
}

3 d
http://www.cnblogs.com/grandyang/p/5860706.html

发现这道题用递归来做很简单，我们用一个bool型变量left2right，为true表示从左往右，为false表示从右往左遍历。当n为1时，不论从左往右还是从右往左都返回1。如果n大于1，且是从左往右的话，我们返回2倍的对n/2的从右往左的遍历；如果是从右往左的话，稍稍麻烦一些，我们肯定还是要对n/2调用递归函数的，

    int lastRemaining(int n) {
        return help(n, true);    
    }
    int help(int n, bool left2right) {
        if (n == 1) return 1;
        if (left2right) {
            return 2 * help(n / 2, false);
        } else {
            return 1 + n - 2 * (1 + n / 2 - help(n / 2, true));
        }
    }

http://codefang.blogspot.com/2016/08/leetcode-weekly-contest390-elimination.html

LeetCode 390 - Elimination Game

Labels

Popular Posts