经典面试题：玩家进游戏场地分配号码、判断括号是否闭合、提取回文串字符的分析和 php 程序实现 - 经典数据结构面试

经典面试题一、判断括号是否闭合的代码实现

1. 题目内容：

给定一长串字母和符号，里面有三种括号包括([{}])这些，需要判断这三种括号必须是配对的。即这三类括号要么不出现，要出现必须是先出现左边的括号，然后出现右边的，中间括号可以嵌套。

2. 解答思路：

定义一个字符对应关系数组，初始化一个数组栈。所以进入的左边符号入栈，如果进入的是右边的符号，则与栈中最后进入的元素进行配对判断，如果配对则消除这对符号。如果不配对，则说明不配对。

3. PHP编程实现：

#([{)]}类括号符号是否闭合的判断
#04.cn
$args = getopt('c:');
extract($args);
echo "\n接收字符串:".$c."\n闭合判断结果：";

function checkClose($str){
    #定义一个关系
    $relate = array('('=>')', '['=>']', '{'=>'}' );  

    #遍历字符串将对应符号插入栈
    $quene = array();
    for($i=0; $i< strlen($str); $i++){
        #如果是出现了([{类字符，则直接存入栈等待配对
        if(isset($relate[$str{$i}])){
            array_push($quene, $str{$i}); 
        }elseif( in_array($str{$i}, $relate)){
            #如果出现了右边的)]}类字符，则必须与栈中最后一个元素相匹配，否则即为不是闭合的
            if($str{$i} != $relate[end($quene)]){
                return false;
            }else{
                #匹配的话则消除这对符号
                array_pop($quene);
            }   
        }else{
            #非上述6个符号的内容不用考虑
            continue;
        }   
    }   

    #结尾只需要返回对$quene的判断
    return (bool)!$quene;
}
var_dump(checkClose($c));

4. 运行结果：

在服务器命令行模式中运行结果如下：

[root@047 php]# php close.php -c='req(9[09]pp{rew}'
接收字符串:req(9[09]pp{rew}
闭合判断结果：bool(false)

[root@047 php]# php close.php -c='req(9[09]pp{rew})'
接收字符串:req(9[09]pp{rew})
闭合判断结果：bool(true)

经典面试题二、一个玩家进游戏场地分配号码的php代码实现

1. 题目内容：

一个简单的容易在面试中碰到的动手编码题，一个游戏场地最多只能容纳200个玩家，每个玩家都有一个号码，号码的范围从0~199，全程不断地有玩家进进出出，但是每个在场玩家的号码各不相同。 请设计一个类TicketsPool，负责给进去的玩家分配号码（给出玩家申请号码的实现，并给出你觉得应该有的成员方法，代码可以适当加注释）以及用户退出的方法实现。

2. 解答思路：

实现起来也简单，可以设想有一套玩家用户系统，经过玩家基本账号验证之后进入玩家游戏场地，我这里就用的玩家的名称作为进入的唯一标记吧，当然可以使用用户uid，只要保障每次进来的时候能正确分配号码，不会冲突，如果出现房间满员能返回满员的信息。

3. PHP编程实现：

<?php
#玩家入场退出类
class TicketsPool{
    
    static $numArr = array();

    #成员初始化进入
    public function getNum($username){
            
        //同一用户重入
        $key = array_search($username, self::$numArr);
        if($key!==false){
            return $key;
        }   
            
        #查找空号码
        #for($i=0; $i<200; $i++){
        for($i=0; $i<5; $i++){
            if(!isset(self::$numArr[$i])){
                self::$numArr[$i] = $username;
                return $i; 
            }   
        }   
            
        #满员
        return false;
    }   
        
    #成员退出
    public function logout($username){
        $key = array_search($username, self::$numArr);
        if($key!==false){
            unset(self::$numArr[$key]);
            return true;
        }else{
            #非法调用
            return false;
        }   
            
    }   
        
}

$TicketsPool = new TicketsPool();
$gamerArr = array( 'tomorrow', '哈哈', '国庆了', '大飞机', '歼20', '快递来了', '再来一个');
foreach($gamerArr as $username){
    $room_id = $TicketsPool->getNum($username);
    if($room_id !== false){
        echo $username."-分配号码：".$room_id,"\n";
    }else{
        echo $username."--分配失败:房间满员了\n";    
        echo "国庆了 退出房间：退出".($TicketsPool->logout('国庆了')?'成功':'失败')."\n";
    }   
}

4. 运行结果：

在linux上执行结果如下：

[root@007 php]# php game.php
tomorrow-分配号码：0
哈哈-分配号码：1
国庆了-分配号码：2
大飞机-分配号码：3
歼20-分配号码：4
快递来了--分配失败:房间满员了
国庆了 退出房间：退出成功
再来一个-分配号码：2

经典面试题三、php从给定字符串中提取出所有回文串字符的代码实现

1. 题目内容：

php从字符串中提出回文串数据，什么是回文串？回文串是一个正读和反读都一样的字符串，比如abcba或者abba等等就是回文串。今天看到了一道回文串相关的题目：给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？输出需要删除的字符个数。

这是网上有人记录的遇到的面试题，我到还没有碰到过，于是就当自己去面试吧，拿到题后就自己开始考虑接着就开始干了，事情都是越想越清楚，在慢慢地尝试和试错中解决，晚上也在未借助任何外力进行实现了，不知道网上有没有同样的实现方法。虽然我自己能单独完成，但我不得不承认，如果是在一个面试环境，同时时间又有限的情况下，我也无法保证自己能做出来。更不要说考虑性能了。

2. 解答思路：

思路也很简单，回文串肯定至少有2个字符，可以是奇数个也可以是偶数个，所以拿到一个字符串，直接从第2个字符开始我将字符切成左右两边，然后同时从中间出发去两边寻找同样的字符以达到回文，如果找到了就表示这个字符可以在回文串中，并进行记录。同时把两段字符分别从中间删除掉查找过的字符或者部分字符（因为这部分不会再有可能出现在回文串中），一直到左边或者右边的字符串为空，最终查出了整个字符串中所有可能的回文串，再从这些回文串数据列表里查找最长的回文串就不是问题了。

3. PHP编程实现：

具体完整实现的php代码如下：

<?php
#入参检查
$args = getopt('c:');
extract($args);
if(empty($c)) exit('need param:c');

echo "入参c:{$c}\n";
#调用实例
$BackChar = new BackChar();
print_r($BackChar->getBackChar($c));

#回文串实现类
class BackChar{

    #定义一个数组存储字符
    private $char;
    public $backArr = array();

    #每个位置开始尝试寻找回文串
    protected function calcute($i, $odd=true){

        #从中间开始向两边尝试找回串,将查找寄数个和偶数个字符的方式合并
        $left = substr($this->char, 0, $i);
        $right = substr($this->char, $odd?($i+1):$i);
        $c = $odd?$this->char{$i}:'';
        $ok = ''; 
        $index_l = strlen($left);
        while($left && $right){
            $val = substr($left, $index_l - 1, 1); 
            $left= substr($left,0,-1);

            #如果找到了，则说明可以关闭一组字符
            $index_r = strpos($right, $val);
            if($index_r !== false){
                $ok.=$val;
                $right = substr($right, $index_r +1);
            }   
    
            $index_l --; 
        }   

        #只有在找到了匹对的字符才认为是有回串
        if($ok){
            $key = strrev($ok).$c.$ok; 
            $this->backArr[$key] = strlen($key);
        }   
    }   
    
    #供外部调用的方法
    public function getBackChar($char){

        $this->char = $char;

        #循环尝试回文串的位置
        for($i=1; $i<strlen($char)-1; $i++){
            #尝试找出所有奇数个回文串字符
            $this->calcute($i);
            #尝试找出偶数个回文串字符
            $this->calcute($i, false);
        }

        #返回所有的回文串字符串
        return $this->backArr;
    }
}

4. 运行结果：

在linux服务器上执行结果如下：

[root@007 php]# php back.php -c=helloworld
入参c:helloworld
Array
(
    [lll] => 3
    [ll] => 2
    [lol] => 3
    [lowol] => 5
    [lool] => 4
    [lrl] => 3
)
[root@007 php]# php back.php -c=abcdehkkkabzhtt99ba
入参c:abcdehkkkabzhtt99ba
Array
(
    [aba] => 3
    [aa] => 2
    [abcba] => 5
    [abba] => 4
    [abdba] => 5
    [abeba] => 5
    [abhba] => 5
    [abhkhba] => 7
    [abhhba] => 6
    [abhkkkhba] => 9
    [abhkkhba] => 8
    [abhahba] => 7
    [abzba] => 5
    [abtba] => 5
    [abttba] => 6
    [ab9ba] => 5
    [ab99ba] => 6
)

后在网上看到说这个问题可从两个字符间的最大子串角度来思考，我到没去想这块，只是把目标一步一步实现了吧，当然这个方法肯定还有改进的余地，等下回有时间有闲再看看吧。