leetcode390.Elimination Game

Godtoy 发布于2019-08-19 11:33 / 917人阅读

摘要：题目要求假设有一共个数字，从左往右开始每隔一位删除一个数字，到达最右侧后，再从右往左每隔一位删除一个数字，如此反复，直到剩下最后一个数字。由此可见，假如我们定义一个递归函数我们可以有来获取结果。

题目要求

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

假设有1-n一共n个数字，从左往右开始每隔一位删除一个数字，到达最右侧后，再从右往左每隔一位删除一个数字，如此反复，直到剩下最后一个数字。问最后剩下的数字是多少。

思路一：递归

先从一个例子入手，当n等于7时，数字序列为1,2,3,4,5,6,7, 删除序列如下：

1 2 3 4 5 6 7
  2   4   6
      4

可以看到，第一轮删除后剩下的2，4，6就相当于是1，2，3的两倍，我们可以等价于从右往左删除1，2，3后剩余的结果乘2。由此可见，假如我们定义一个递归函数f(n, left),我们可以有f(n/2, right)来获取结果。

    public int lastRemaining(int n) {
        return lastRemaining(n, true);
    }
    
    public int lastRemaining(int n, boolean left) {
        if(n == 1) {
            return 1;
        }
        if(n % 2 == 1) {
            return lastRemaining(n / 2, !left) * 2;
        }else{
            if( left ) {
                return lastRemaining(n/2, !left) * 2;
            }else {
                return lastRemaining(n/2, !left) * 2 -1;
            }
        }
    }

思路二

这里其实存在一个镜像删除的问题，也就是说，对于任何一个1~n的序列来说，从左往右开始删除和从右往左开始删除剩余的结果的和一定为(n+1)，也就是所谓的镜像删除问题。
举个例子：

从左往右开始删除
1 2 3 4 5 6
  2   4   6
      4
      
从右往左开始删除
1 2 3 4 5 6
1   3   5
    3

可以看到二者剩余的值加起来一定为n+1即7。
根据这个原理，我们可以优化上面的递归，无需再利用left值来标记是从左往右删除还是从右往左删除，直接执行镜像删除即可。

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

云服务器 GPU云服务器 Leetcod LeetCode LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/77452.html

[Leetcode] Nim Game 尼姆游戏

摘要：脑筋急转弯复杂度时间空间思路这题往小说可以追溯到小学奥数或者脑筋急转弯的书中，往大说可以深究到博弈论。代码如果一开始就是的倍数，你就输了，因为对方可以用同样的策略 Nim Game You are playing the following Nim Game with your friend: There is a heap of stones on the table, each ...

cartoon 2019-08-14 12:45 评论0 收藏0
LeetCode[45] Jump Game II

摘要：复杂度思路每次设置一个窗口，观察在这一步下能到达的最远距离，不断的移动这个窗口。计数，需要移动几次，才能覆盖到末尾的值。 LeetCode[45] Jump Game II Given an array of non-negative integers, you are initially positioned at the first index of the array. Eac...

keelii 2019-08-14 15:02 评论0 收藏0
Leetcode PHP题解--D37 682. Baseball Game

摘要：题目链接题目分析给定一个字符串数组，每一个字符串有以下形式数字。直接计算得分。。代表上一轮分数无效。思路这题没什么好说的了。用区分各种情况，进行相应处理即可。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 682. Baseball Game 题目链接 682. Baseball Game 题目分析给定一个字符串数组，每一个字符串有以下形式：数字。直接计算得分。 +。代表本轮...

wzyplus 2019-07-01 12:42 评论0 收藏0
Leetcode PHP题解--D64 292. Nim Game

摘要：拿到最后一颗石头的一方为剩方。现给定一个石头数量，判断你最终是否能取得胜利。对方全拿，对方赢。因此，必输无疑。当剩下的石头为的整数倍双方都采取最优策略时，先下手的一方为输家。因此这个题目就很简单了，只要判断给定的数字是否是的整数倍即可。 D64 292. Nim Game 题目链接 292. Nim Game 题目分析假设你和朋友玩一个捡石头的游戏，你和朋友轮流拿1~3颗石头。拿到最...

XGBCCC 2019-07-01 12:48 评论0 收藏0
[Leetcode] Jump Game 跳跃游戏

摘要：代码记录下当前区域的上界，以便待会更新下一个区域的上界更新下一个区域的上界更新下一个区域的下界后续如果要求返回最短跳跃路径，如何实现可以使用，并根据一个全局最短步数维护一个全局最短路径，当搜索完所有可能后返回这个全局最短路径。 Jump Game I 最新解法请见：https://yanjia.me/zh/2019/01/... Given an array of non-negat...

venmos 2019-08-14 12:24 评论0 收藏0