链接 (opens new window)

TIP

// 1 to 6
// 根据规律找数列
// 1,
// 22,
// 122,212,221
// 333, (3=3 or 3=1+2)
// 1333,3133,3313,3331 (4=1+3) 
// 4444,
// 14444,22333,23233,23323,23332
// 32233,32323,32332,33232,33322
// 41444 44144 44414 44441(5=1+4,2+3)
// 55555 (5=,)
// (6=1+5,2+4,1+2+3)
// 666666 (6=)
//  6 + 10 + 35 + 63
// (7=1+6,2+5,3+4,1+2+4)
// 不难发现是通过把他们拆出来的方式 比如 7=1+6 意味着6个6和1个1组合而成的数字(平衡数)
// 在观察我们发现可以利用字典序明确的回溯dfs,参考题目下一个排列,全排列
// 从而对大于目标的数进行逼近,难点在减枝
copy success

class Solution {

    public $result = [];
    public $cnt = [0];

    /**
     * @param Integer $n
     * @return Integer
     */
    function nextBeautifulNumber($n) {
        $this->cnt = array_fill(0, 10, 0);
        for ($i = 1; $i < 7; $i++) {
            $this->dfs($i, 0, 0);
        }
        //return implode(' ', $this->result);
        $this->result[] = 1224444;
        foreach ($this->result as $v) {
            if ($v > $n) {
                return $v;
            }
        }
    }

    function dfs($len, $sum, $level) {
        if($level == $len) {
            if($this->checkIsBeatutifulNumber()) {
                $this->result[] = $sum;
            }
            return;
        }

        for ($i = 1; $i <= $len; $i++) { // 剪枝一: 当前总位数多少，最多可使用的数值就是多少
            if ($this->cnt[$i] >= $i) { // // 剪枝二: 数值出现的次数不能超过当前数
                continue;
            }
            $this->cnt[$i]++;
            $this->dfs($len, $sum * 10 + $i, $level + 1);
            $this->cnt[$i]--;
        }

    }

    function checkIsBeatutifulNumber() {
        foreach ($this->cnt as $index => $val) {
            if ($val > 0 && $index != $val) {
                return false;
            }
        }
        return true;
    }
}

copy success