php面试题：FizzBuzz最短连续序列问题

[php]代码库
<?php
 
/**
 * FizzBuzz问题：
 *
 * The aim of the test is to discover the shortest sequence of consecutive numbers, which when they are run through the fizzbuzz algorithm produce the required output.
 *
 * For example, the shortest sequence that produces fizz is 3
 *
 * When looking for the shortest sequence for
 *
 * fizz buzz
 *
 * one sequence that produces that output is
 *
 * 3, 4, 5
 *
 * However, this isn't the shortest. The shortest sequence is 9, 10
 *
 * In our case, we are only interested in the numbers between 1 and 100, so be sure you limit your calculations to that range, otherwise you are likely to exceed timeout limits.
 *
 * InverseFizzBuzz
 *
 * @author 剑锋
 * @qq 1421560459
 *
 */
class InverseFizzBuzz {
 
    private $list;
    private $max = 100; //扫描最大值
 
    public function __construct($list) {
        $this->list = $list;
    }
 
    /**
     * 查找序列
     * 思路：遍历1-max，分别遍历字符数组，找到fizz或buzz，放到散列结果中保存；补全散列结果得到连续结果序列；找到结果长度最短的
     * Enter description here ...
     */
    public function sequence() {
        $resultList = array(); //结果集
 
        //遍历1-max
        for($i = 1; $i <= $this->max; $i++){
            $resultHash = array(); //结果散列
            $result = array(); //结果序列之一
            $last = $i; //上一个扫描结果
            $isFull = true; //标记是否找到完整序列
 
            //查找fizz或buzz
            foreach($this->list as $k => $v){
                $index = $i; //索引
 
                switch($v){
                    case 'fizz':{
                        $index = $this->_scanNextFizz($last);
 
                        if ($index){ //找到fizz
                            array_push($resultHash, $index);
                            $last = $index;
                        }else{ //未找到fizz
                            $isFull = false;
                            $last++;
                        }
 
                        break;
                    }
                    case 'buzz':{
                        $index = $this->_scanNextBuzz($last);
                             
                        if ($index){ //找到buzz
                            array_push($resultHash, $index);
                            $last = $index;
                        }else{ //未找到buzz
                            $isFull = false;
                            $last++;
                        }
 
                        break;
                    }
                    default:{
                        break;
                    }
 
                }
            }
 
            //填充数字间隔，不完整序列不填充
            if ($resultHash && $isFull){
                $time = count($resultHash) - 1; //循环终止下标
                for($j = $resultHash[0]; $j <= $resultHash[$time]; $j++){
                    array_push($result, $j);
                }
                array_push($resultList, $result);
            }
 
 
        }
 
        //判断是否存在结果（例如  buzz fizz buzz）
        if (count($resultList) == 0){
            return null;
        }
 
        //查找最短结果
        $count = $this->max;
        foreach ($resultList as $v){
            $length = count($v);
            if ($length < $count){
                $count = $length;
                $result = $v;
            }
        }
 
        return $result;
    }
 
    /**
     * 查找下一个Fizz
     *
     * Enter description here ...
     * @param unknown_type $current
     */
    private function _scanNextFizz($current){
        for($i = $current + 1; $i <= $this->max; $i++){
 
            if($i % 5 == 0){ //上次结果与今次结果之间不能有buzz
                return 0;
            }
 
            if($i % 3 == 0){
                return $i;
            }
        }
        return 0;
    }
 
    /**
     * 查找下一个Buzz
     *
     * Enter description here ...
     * @param unknown_type $current
     */
    private function _scanNextBuzz($current){
        for($i = $current + 1; $i <= $this->max; $i++){
 
            if($i % 3 == 0){ //上次结果与今次结果之间不能有fizz
                return 0;
            }
 
            if($i % 5 == 0){
                return $i;
            }
        }
        return 0;
    }
 
}
 
 
//测试
$inverse = new InverseFizzBuzz(array('fizz', 'buzz', 'fizz')); //3 4 5 6
var_dump($inverse->sequence());
?>
用户注册

用户登录

发表随想

该用户最新代码

编程随想

[php]代码库

网友评论 (发表评论)

发表评论：

评论须知：

扫码下载

输入口令后可复制整站源码
