php单向链表解决约瑟夫环问题
一个经典的面试题:41一个人排成一个圈,从1开始数数,数到4,那个人就要离开队伍,然后下一个人从1开始再数,依次类推。这种算法叫做约瑟夫环问题。也可以叫丢手绢问题。由于php没有指针可以用,我们可以用类来模拟这个过程。好了,废话不多说,直接上代码:
<?php
// 节点类
class Node
{
public $data = null;
public $next = null;
public function __construct($data)
{
$this->data = $data;
}
}
// 创建节点
function createNode($node, $data)
{
$curr = findLastNode($node);
$newNode = new Node($data);
$curr->next = $newNode;
}
// 计算节点的数量
function countNode($node, $head)
{
$num = 1;
$curr = $node;
while(!is_null($curr->next)){
if($curr->next == $head){
break;
}
$num++;
$curr = $curr->next;
}
return $num;
}
// 获取最后一个节点
function findLastNode($node)
{
$curr = $node;
while(!is_null($curr->next)){
$curr = $curr->next;
}
return $curr;
}
// 删除节点 $no -- 指定删除的节点位置
function delNode(&$node, $no)
{
$curr = $node;
$num = 1;
while(($num + 1) < $no ){
$curr = $curr->next;
$num++;
}
$curr->next = $curr->next->next;
return $curr->next;
}
// 展示节点数据
function showNode($node, $head)
{
$curr = $node;
while(!is_null($curr->next)){
echo $curr->data . "号<br/>";
if($curr->next == $head){
break;
}
$curr = $curr->next;
}
}
// 头结点
$head = new Node(1);
// 41 个人
for($i = 2; $i < 42; $i++){
createNode($head, $i);
}
// 排成一圈
$last = findLastNode($head);
$last->next = $head;
// 每数到4 退出一个
$count = countNode($head, $head);
while($count > 3){
$head = delNode($head, 4);
$count = countNode($head, $head);
}
echo "41个人从 1-41编号,每数到4退出一个人,最后剩下的是:<br/>";
showNode($head, $head);