序列面试题

一到面试题

题目

产生一个序列，

1，

1，2，

1，2，3

……..

1，2，3，….8，9，1，0，

1，2，3，….8，9，1，0，1，1

解答

自己简单的解法，穷举。当作字符串求解更容易一些，也更容易理解，缺点：效率低。

<?php

function get_num($index){
    $index--;
    $seq = 1;
    $count = 0;
    while(true){
        $str = join('',range(1,$seq));
        $count+=strlen($str);
        $k = $index - $count;
        if( $k <= strlen($str) - 1){
            return $str[$k];
        }
        $seq++;
    }
}

// 测试
foreach(range(1,100) as $k =>$v){
    echo $v,"    ",get_num($v).PHP_EOL;
}

优化

在上面的结果基础上，发现先生成序列，再求字符串的长度，这个过程有点繁琐。索性，当判断成立后，再生成该序列，之前求字符串长度有$len来记录。

我发现，确实，程序有的时候不应该过早的优化。在上面的代码出来之后，然后，基本思路打开了，在上面的基础上，再优化，确实是不错的。如果一开始，就想到下面的答案，确实不容易想得到。

另外，下面的代码，肯定还有提升的空间。但是呢，这个跟优化、易理解又冲突。下面，比如，计算count，可能也有规则，能确定出大概的seq范围，然后呢，求解某一行的位置时，也能优化。

function get_num($index){
    $index--;
    $seq = 1;
    $count = 0;
    $len = 0;
    while(true){
        $len+=strlen(''.$seq); //每组的长度，都在上次的结果上，增加新增的数
        $count+=$len;
        $k = $index - $count;
        if( $k <= $len - 1){
            $str = join('',range(1,$seq)); //优化，只有确定了这一列，再求该数组
            return $str[$k];
        }
        $seq++;
    }
}