欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

剑指Offer:孩子们的游戏

程序员文章站 2022-03-15 09:49:45
题目描述有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中从他的下一个小朋友开始,继续0...m-1报数直到剩下最后一个小朋友,可以不用表演请你试着想下,哪个小朋友会得到这份礼品呢?(注:小朋友的编号是从0到n-1)如果没有小朋友,请返回-1题目分析首先我们可以模拟整个过程,从而获得最后一个的编号只需要将孩子们存入一个List中,然后每次...

题目描述

有个游戏是这样的:

  • 首先,让小朋友们围成一个大圈。
  • 然后,他随机指定一个数m,让编号为0的小朋友开始报数。
  • 每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中
  • 从他的下一个小朋友开始,继续0...m-1报数
  • 直到剩下最后一个小朋友,可以不用表演
  • 请你试着想下,哪个小朋友会得到这份礼品呢?
  • (注:小朋友的编号是从0n-1)
  • 如果没有小朋友,请返回-1

题目分析

  • 首先我们可以模拟整个过程,从而获得最后一个的编号
  • 只需要将孩子们存入一个List中,然后每次循环找到出列的编号,将其remove,到最后List中剩下的就是返回值
  • 另外一个就是通过数学的方法来分析了

数学分析

  • 第一次循环中,删除的元素是第m % n
    剑指Offer:孩子们的游戏

  • 然后就只剩下了 n-1 个元素,且下一次开始是跟着被删除的元素开始的
    剑指Offer:孩子们的游戏

  • 将其进行重排序后,即将开始的元素放在第一个位置
    剑指Offer:孩子们的游戏

  • 下一次循环,删除的是第 m % n-1 个元素

  • 同样的思想,现在要求的是last(n, m),即最终会留下的是第几个小孩

  • 最开始的时候,求last(n, m),那就要知道last(n-1, m),假设为X,即:
    剑指Offer:孩子们的游戏

  • 知道last(n-1, m)后,就可以知道删除当前元素之后,留下的是第x个元素
    剑指Offer:孩子们的游戏

  • 即表达式为f(n, m) = ( f(n-1, m) + m ) % n

解法分析

  • 根据第一种方法,可以使用ArrayList集合来存储小孩序列
  • 第二种方法,使用递归即可,但是递归的缺陷是效率较低,特别是当递归层数多的时候,容易产生*Error
  • 可以将递归改造成迭代的方式,即循环计算赋值

代码

第一种方式,强行模拟

import java.util.List;
import java.util.ArrayList;

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n==0 || m==0) return -1;
        List<Integer> kids = new ArrayList<Integer>();
        // 孩子
        // 添加孩子编号进入集合
        for(int i=0;i<n;i++){
            kids.add(i);
        }
        // 循环 知道孩子只剩下一个
        // index表示的是第几个孩子,而不是孩子的编号
        int index = -1; // 第一次循环开始的位置
        while(kids.size() > 1){
            int count = 0;
            // 出列
            while(count<m){
                // 报数
                count++;
                // 移动到下一个
                index++;
                // 重复循环孩子序列
                if(index == kids.size()) index = 0;
            }
            kids.remove(index);
            // 因为是接着被删除的元素去报数的,所以要将指针放到删除元素的前一个
            index--;
        }
        // List只剩下一个,获取第0个元素即可
        return kids.get(0);
    }
}

第二种方式:递归计算

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if (n <= 0) return -1; 
        return f(n,m);
	}

	public int f(int n, int m) {
		// 只剩下一个人的时候,将第一个人的位置返回即可
        if (n == 1) return 0;
        // 计算 n-1 序列中最终留下的人的位置
        int x = f(n-1, m);
        return (x+m) % n;
    }
}

改造成递归方式

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        int s = 0;
        if(m == 0){
            return -1;
        }
        for(int i = 2; i <= n; i++){
            s = (s + m) % i;
            
        }
        return s;
    }
}

本文地址:https://blog.csdn.net/Kobe_k/article/details/108181268

相关标签: Leetcode题目