领扣-390 消除游戏 Elimination Game MD

Markdown版本笔记 我的GitHub首页 我的博客 我的微信 我的邮箱
MyAndroidBlogs baiqiantao baiqiantao bqt20094 baiqiantao@sina.com

领扣-390 消除游戏 Elimination Game MD


目录

目录
消除游戏 Elimination Game MD
题目
暴力循环删除法
递归法
分析过程
代码一
代码二
迭代法
分析过程
代码

消除游戏 Elimination Game MD

数学

题目

给定一个从1 到 n 排序的整数列表。
首先,从左到右,从第一个数字开始,每隔一个数字进行删除,直到列表的末尾。
第二步,在剩下的数字中,从右到左,从倒数第一个数字开始,每隔一个数字进行删除,直到列表开头。
我们不断重复这两步,从左到右和从右到左交替进行,直到只剩下一个数字。
返回长度为 n 的列表中,最后剩下的数字。

示例:

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

输出:
6

暴力循环删除法

类似的还可以使用链表、数组等数据结构。

class Solution {

    public int lastRemaining(int n) {
        List<Integer> list = new ArrayList<Integer>();
        int i = 1;
        while (i <= n) {
            list.add(i);
            i++;
        }

        List<Integer> temp;
        while (list.size() > 1) {
            temp = new ArrayList<Integer>(list);
            for (int j = 0; j < temp.size(); j += 2) {
                list.remove(temp.get(j));//不能使用 int ,因为这样的话 remove 的就不是对象,而是序号
            }
            if (list.size() == 1) break;

            temp = new ArrayList<Integer>(list);
            for (int j = list.size() - 1; j >= 0; j -= 2) {
                list.remove(temp.get(j));
            }
        }
        return list.get(0);
    }
}

会提示超时

递归法

分析过程

基本的规律是这样子的

  • 1、因为不管整个从左往右删或从右往左删的过程中,删除的是哪些元素,最终的结果是相同的
  • 2、所以如果我们忽略最开始的从左往右删的过程,改为直接在某一数列上从右往左删,这种情况下和之前的结果是相同的
  • 3、同样道理,我们如果继续忽略此从右往左删的过程,改为直接在另一数列上从左往右删,这种情况下和之前的结果也是相同的

很明显,这符合递归的条件!

为什么要这么思考?为了将数列变短呀,我们忽略掉某些值之后数列就变短了,数列越变越短也就将复杂问题逐级消解了,也才会触发递归结束的条件。

但问题的关键是,我们每次从左往右删或从右往左删时,怎么将原始的数列转化为等价的、更短的新数列

先看从左往右删的规律:
例子1:
1 2 3 4 5 6 【2 4 6】
1 2 3 4 5 6 7 【2 4 6】

例子2:
1 2 3 4 5 6 7 8 【2 4 6 8】
1 2 3 4 5 6 7 8 9 【2 4 6 8】

可以发现:

  • 123456 和 1234567 从左往右删的结果,应该和 246 从右到左的删结果一样;而 246 从右到左的删结果肯定和 123 从右到左的删结果的 2 倍一样。
  • 12345678 和 123456789 从左往右删的结果,应该和 2468 从右到左的删结果一样;而 2468 从右到左的删结果肯定和 1234 从右到左的删结果的 2 倍一样。

结论:从左往右遍历的结果等价于 2 倍的对 n/2从右往左删的结果(奇数偶数都一样)。

再看从右往左删的规律
因为上面我们已经把从左往右遍历的结果进行了等价处理,所以这里需要在此处理结果的基础上分析。

例如 123456 和 1234567 已经等价处理为了 123,12345678 和 123456789 已经等价处理为了 1234。

我们也很明显可以发现,处理后的结果仍是一个从 1 到 m (其中 m = n/2)的等差数列。

例子3:
1 2 3 4 5 6 【1 3 5】
1 2 3 4 5 6 7 【2 4 6】

例子4:
1 2 3 4 5 6 7 8 【1 3 5 7】
1 2 3 4 5 6 7 8 9 【2 4 6 8】

可以发现:

  • 如果 m 为奇数,等价于2倍的对m/2从左往右删的结果
  • 如果 m 为偶数,等价于2倍的对m/2从左往右删的结果再减去1

代码一

class Solution {

    public int lastRemaining(int n) {
        return help(n, true);
    }

    private int help(int n, boolean left2right) {
        if (n == 1) return 1; //递归结束条件
        if (left2right) {
            return 2 * help(n / 2, false); //不区分奇偶
        } else {
            return 2 * help(n / 2, true) - 1 + n % 2; //需区分奇偶
        }
    }
}

代码二

以上实现可以进一步优化为如下逆天的两行代码:

class Solution {

    public int lastRemaining(int n) {
        if (n == 1) return 1; //递归结束条件
        else return 2 * (1 + n / 2 - lastRemaining(n / 2));
    }
}

迭代法

分析过程

我们先来看两个简单的例子:

n = 8
1 2 3 4 5 6 7 8
  2   4   6   8    (删除了位置排在第一的数字1,以及和他相隔1个的数字3579)
  2       6        (删除了位置排在第二的数字4,以及和他相隔1个的数字8)
          6
n = 7
1 2 3 4 5 6 7
  2   4   6    (删除了位置排在第一的数字1,以及和他相隔1个的数字357)
      4        (删除了位置排在第一的数字2,以及和他相隔1个的数字6)

如果我们仔细观察,我们可以发现, 每删一次,数字之间的距离会变为之前的两倍,并且:

  • 从左往右删的时候,每次都是删掉第一个数字
  • 从右往左删的时候,则有可能删掉第一个或者第二个数字
    • 如果剩下的数字个数是偶数,删掉的是第二个数字;
    • 如果剩下的数字个数是奇数,删掉的是第一个数字;

所以我们只需要计算出并记录当前数组的第一个数字,只要第一个数字有了,后面的数字都可以计算出来了。

代码

class Solution {

    public 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;
    }
}

2018-12-8