算法:消除游戏

2024-01-03 12:35:32

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

目录

一、问题描述

二、基础解法

总结


提示:以下是本篇文章正文内容,下面案例可供参考

一、问题描述

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

输入:
n = 9,
1 2 3 4 5 6 7 8 9 (1,3,5,7,9被删除)
2 4 6 8 (8,4被删除)
2 6 (2被删除)
6 (剩余6)

输出:
6

二、基础解法

解题思路:

这个题目的关键,就在于以下几个地方:

1、删除的顺序,相邻两次是相反的

2、正序删除时,第一个元素是必删;倒序删除时,第一个元素删不删,是分场景的,如果剩余的数字数量是奇数,则删,偶数,则不删。如果是偶数,首位元素不动,如果是奇数,则首位元素移动。举个例子,第一轮删完之后,剩余是2468,则下次删除时会删掉4和8,首位元素2不动;第一轮删完之后,剩余是246,则下次删除时会删掉2和6,首位元素向后移动,指向4

3、每次删除一半元素,剩余的元素数量为上次遗留总数的一半,如果上次遗留数量是奇数,则删除的数字为一半+1,可以用右移操作,也可以用对2取整,后者更方便理解。

4、步长的变化,可以通过几组简单的数据去总结一下规律,举个例子:

1 2 3 4 5 6 7 8 9 10 11 12 13 ? 初始步长1, 步长为相邻两个元素间的差值
2 4 6 8 10 12 ? ?删掉1 3 5 7 9 11 13, 剩下的元素间, 步长变为2
2 6 10 ? ?删掉12 8 4, 剩下2 6 10, 剩下的元素间, 步长变为4
6 ? ?删掉2 10, 剩下一个元素, 步长不再计算


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ? 初始步长1, 步长为相邻两个元素间的差值
2 4 6 8 10 12 14 16 ?删掉1 3 5 7 9 11 13 15, 剩下的元素间, 步长变为2
2 6 10 14 ? 删掉16 12 8 4, 剩下2 6 10 14, 剩下的元素间, 步长变为4
6 14 ? 删掉2 10, 剩下6 14, 剩下的元素间, 步长变为8

代码示例:

public void test() {
    int n = 9;
    // 初始方向为从左至右
    boolean left = true;
    // 剩余数字数量, 初始值为最大的n
    int remaining = n;
    // 初始步长是1, 由于未删除任何一个元素, 所以每个元素间差值是1
    int step = 1;
    // 初始位置指向左边第一个元素
    int head = 1;
    // 当剩余数字大于等于2个时, 继续删除
    while (remaining > 1) {
        if (left) {
            // 从左到右删除时, 第一个元素必删, 所以head必定向后移动
            head = head + step;
        } else if (remaining % 2 == 1) {
            // 从右到左时, 剩余是偶数, head不动  剩余是奇数, head移动, 移动位置为向后移动step
            head = head + step;
        }
        // 剩下的数字数量是奇数, 则删除remaining/2 + 1个数字, 如果是偶数, 则删除remaining/2个数字
        remaining = remaining >> 1; // remaining = remaining / 2
        // 每次删除一半的数字, 剩下的数字间, 步长变大
        step = step << 1;
        // 顺序调转
        left = !left;
    }
    System.out.println(head);
}

总结

详细注释已添加,快快练习吧,简单到有手就行!

文章来源:https://blog.csdn.net/ql_gome/article/details/135358522
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。