今天突然想起来很多年前去一家游戏公司现场面试遇到的一个逻辑题，题目是有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版
import java.util.ArrayList;
public class ChildrenGame {
public static void main(String[] args){
String[]children_arr = {"zhangsan","lisi","wangwu","zhaoliu","xiaoming","xiaohua","laowu"};
String last_child;
last_child =ChildrenGame2(children_arr);
System.out.println(last_child);
}
public static String ChildrenGame2(String[] children_arr) {
ArrayListchildren_list =new ArrayList();
String last_child ="错误";
try {
for (String val: children_arr ) {
children_list.add(val);
}
int j =1;
while (true){
if (j ==3){
children_list.remove(0);
j =1;
}else {
children_list.add(children_list.get(0));
children_list.remove(0);
j++;
}
if (children_list.size() ==1){
break;
}
}
last_ child =children_list.get(0);
}catch (Exception e){
System.out.println("所传输组为空");
}
return last_child;
}
}
