小孩数数出列问题

凯老师斯密达 · · 273 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

今天突然想起来很多年前去一家游戏公司现场面试遇到的一个逻辑题,题目是有N个小朋友围在一起从1开始报数,报到3的出列,然后剩下的人重新报数,问最后剩下的小孩是谁,试写一些伪代码。当时第一反应是采用常规的递归算法实现了,当时对方赞同但并不满意,随即补充了一个条件,假定N的人数为2时,如何才能进行递归?当时真是一下子懵逼了,想好好久,在对方提示下采用了链轮方式,发现代码不但精简很多而且逻辑更清晰。后来有次做棋牌游戏的出牌坐次需求时还真的给用上了。下面分享下相关代码和逻辑步骤。

逻辑步骤:

第一步,要将要看似是队列结构的循环想象成数据链轮结构

第二步,想实现链轮循环则须将遍历过的数据塞到队尾

第三步,设置计数器,及时将符合排出条件数据从链轮中不断剔除

相关代码:

PHP版

<?php

/*

* 小朋友数数算法

*/

function childrenCount(){

    $start_time = microtime(true);

    $children_list = array("zhangsan", "lisi", "wangwu", "zhaoliu", "xiaoming", "xiaohua", "laowu");

    $i = 0;

    $j = 1;

    while (1){

        if ($j == 3){

            $j = 1;

            unset($children_list[$i]);

//            print_r($children_list);

        }else{

            $children_list []= $children_list[$i];

            unset($children_list[$i]);

            $j++;

        }

        $i++;

        if (count($children_list) == 1){

            break;

        }

}

    echo $children_list[$i], PHP_EOL;

    $end_time = microtime(true);

    $cost_time = $end_time - $start_time;

    echo PHP_EOL, $start_time, PHP_EOL, $end_time, PHP_EOL, $cost_time;

}

children_count();

?>

Golang版

package main

import "fmt"

func main()  {

        var whoChild string

        whoChild =childrenGame()

        fmt.Println(whoChild)

}

func childrenGame()string{

        var children_list = []string{"zhangsan", "lisi", "wangwu", "zhaoliu", "xiaoming", "xiaohua", "laowu"}

        var j =1

        for true {    //Golang是没有while循环的,可以用for true来代替

                if j ==3 {

                    children_list =append(children_list[:0],children_list[1:]...)

                    j =1

                }else {

                    children_list =append(children_list,children_list[0])

                    children_list =append(children_list[:0],children_list[1:]...)    //用切割切片的方式来实现对切片数据的删除

                    j++

                }

                if len(children_list) ==1 {

                        break

                }

        }

        return children_list[0];

}

Java版(今天不想写了,明天更)


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:凯老师斯密达

查看原文:小孩数数出列问题

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

273 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传