孩子们的游戏(圆圈中最后剩下的数),Java代码实现思路分享

KLQ 2020-04-15 11:42:30 java常见问答 8890

下面给大家分享的是一个Java代码实例,下面一起来了解一下吧。

抽象建模能力

题目:

让小朋友们围成一个大圈,之后,随机指定一个数m,让编号为0的小朋友开始报数。

每一次,喊到了m-1的那个小朋友要出列唱一首歌,然后可以在礼品箱中随意的挑选礼物,并且不用再回到圈中,从他的下一个小朋友开始,继续0...m-1报数,一直到剩下最后一个小朋友,就可以不用表演,并且拿到名侦探柯南典藏版(名额有限)。

问:哪个小朋友会得到名侦探柯南典藏版?

注:小朋友的编号是从0到n-1

假如没有小朋友,请返回-1

思路1:

用数组来模拟环,思路还是比较简单,但是各种下标要理清

代码实现:

public static int findLastNumber(int n, int m)
{
    if (n < 1 || m < 1) return -1;
    int[] array = new int[n];
    int i = -1, step = 0, count = n;
    while (count > 0)
    { //跳出循环时将最后一个元素也设置为了-1
        i++; //指向上一个被删除对象的下一个元素。
        if (i >= n) i = 0; //模拟环。
        if (array[i] == -1) continue; //跳过被删除的对象。
        step++; //记录已走过的。
        if (step == m)
        { //找到待删除的对象。
            array[i] = -1;
            step = 0;
            count--;
        }
    }
    return i; //返回跳出循环时的i,即最后一个被设置为-1的元素
}

思路2

代码实现:

public class Solution
{
    public int LastRemaining_Solution(int n, int m)
    {
        if (m <= 0 || n <= 0)
        {
            return -1;
        }
        //先构造循环链表
        ListNode head = new ListNode(0); //头结点, 值为0
        ListNode pre = head;
        ListNode temp = null;
        for (int i = 1; i < n; i++)
        {
            temp = new ListNode(i);
            pre.next = temp;
            pre = temp;
        }
        temp.next = head; //将第n-1个结点(也就是尾结点)指向头结点
        ListNode temp2 = null;
        while (n != 1)
        {
            temp2 = head;
            //先找到第m个结点的前驱
            for (int i = 1; i < m - 1; i++)
            {
                temp2 = temp2.next;
            }
            //删除第m个结点:将第m个结点的前驱指向第m个结点后面那个结点,temp2表示第m个结点的前驱
            temp2.next = temp2.next.next;
            head = temp2.next; //更新头结点
            n--;
        }
        return head.value;
    }
}
/**
 * 结点
 */
class ListNode
{
    int value;
    ListNode next = null;
    public ListNode(int val)
    {
        this.value = val;
    }
}

思路3

代码实现:

import java.util.ArrayList;
public class Solution
{
    public int LastRemaining_Solution(int n, int m)
    {
        if (n == 0)
            return -1;
        ArrayList < Integer > array = new ArrayList < > ();
        for (int i = 0; i < n; i++)
        {
            array.add(i);
        }
        int tempIndex = (m - 1) % array.size(); //用于记录最初需清除的数字索引
        while (array.size() != 1)
        {
            //System.out.println(array.get(tempIndex));
            array.remove(tempIndex);
            tempIndex = (tempIndex + (m - 1)) % array.size(); //记录当前索引
        }
        return array.get(0);
    }
}

更多的抽象建模能力Java实例,可以继续关注本站了解哦,有更多相关内容,可以分享给大家。