2016腾讯春招的编程题 – Ivan's Blog

Ivan's Blog

2016腾讯春招的编程题

2月
24

这道题是以回文为载体,考察两个字符间的最大子串,最大子串算法在表示字符串的关联度上用途很广泛。
而遮到题就是字符串的长度减去其和翻转字符串的长度的最大子串即可。最长子串的算法我一开始也是蒙的。这完全没没思路呀。。
后来看到一篇blog,才明白最长子串,好的,最后我们形成代码

function solution ($str){
        $res=strrev($str);
        $len=strlen($str);
        $data=array();
        for ($i = 0; $i < $len; $i++) 
            for($j=0 ; $j< $len;$j++){
                    $data[$i][$j]= 0; 
                }
                //开始查找
        for($i=1;$i<$len+1;$i++){
            for($j=1;$j<$len+1;$j++){
                if($str[$i-1] == $res[$j-1]){
                    $data[$i][$j]=$data[$i-1][$j-1] +1;
                }
                else if($data[$i-1][$j] >= $data[$i][$j-1]){
                    $data[$i][$j] = $data[$i-1][$j];
                } 
                else{
                    $data[$i][$j] = $data[$i][$j-1]; 
                }
            }
        }
        print_r($data);
        //其中$data[$len][$len]j即为最大子串
        return $len - $data[$len][$len];
}
//echo  solution('google');
  • 把一个字符串的大写字母放到字符串的后面,各个字符的相对位置不变,且不能申请额外的空间。

这道题感觉上必上题好理解一点,起码自己脑袋里面有个大概的概念,请注意是不能再申请空间(即使是数组+1),所以要求我们在整个array中进行遍历。基本思路是先找出大写字母的后一个字母,若是小写就交换,大写就记录下位子,指针再后移,直到是小写字母为止,然后遍历交换元素位子,指针是永远指向第一个大写字母的。

function solution2($str){
        function  checkcase($s){
                if(preg_match('/^[a-z]+$/', $s)){
                        return 1;
                    }else if(preg_match('/^[A-Z]+$/', $s)){
                                return 2;
                    }
            }
            for($i=0;$i<strlen($str);$i++){
                if(checkcase($str[$i]) ==2){
                    for($j=$i+1;$j<strlen($str);$j++){
                        $t=$j;
                        if(checkcase($str[$j]) ==1){
                            for($l=$t;$l>=$i+1;$l--){
                                $tem=$str[$l];
                                $str[$l]=$str[$l-1];
                                $str[$l-1]=$tem;
                            }
                            break;
                        }
                        else{
                                //echo $j.','.$t;
                        }
                    }
                }
                
            }
            return $str;
    }
    echo solution2("AkleBiCeilD");
  • 蛇形矩阵作为一种常用的数学数列,是由1开始的自然数一次排列成的一个N*N的正方形矩阵,数字一次由外而内的递增,输入蛇形矩阵宽度N,输出整个蛇形矩阵结果,注意输出格式要求按照矩阵从上至下的依次按行输出,每行中间无需换行输出。eg:样本输入: 3样本输出: 1 2 3 8 9 4 7 6 5

直接按照上、右、下、左的顺序进行遍历,计算好遍历层数就OK了.我们可以拓展到n行,m列的蛇形矩阵,其中有个规律就是遍历的层数,为(行数+1)/2的向下取整。记住这个,然后细心再细心就好。

function snake($row = 3, $col = 3){
    $res = array();
    // 初始值
    $start = 1;
    // 当前遍历层数
    $flag = intval(($row + 1) / 2);

    for ($i = 1; $i <= $flag; $i++) { 
        $startx = $i - 1;
        $starty = $i - 1;
        $width = $col - $i + 1;
        $height = $row - $i + 1;
        // 上
        for ($u = $starty; $u < $width; $u++) { 
            $res[$startx][$u] = $start;
            $start += 1;
        }
        // 右
        for ($r = $startx + 1; $r < $height; $r++) { 
            $res[$r][$u-1] = $start;
            $start += 1;
        }
        // 下
        for ($d = $u - 1 - 1; $d >= $starty; $d--) { 
            $res[$r-1][$d] = $start;
            $start += 1;
        }
        // 左
        for ($l = $r - 1 - 1; $l >= $startx + 1; $l--) { 
            $res[$l][$d+1] = $start;
            $start += 1;
        }

    }

    // 输出
    for ($i = 0; $i < $row; $i++) { 
        for ($j = 0; $j < $col; $j++) { 
            echo $res[$i][$j] . " ";
        }
    }

}

snake();
时间复杂度

首先列出时间复杂度。第一个是O(n^2)这没啥说的。
第二个是说白了就是个冒泡的,但最里层嵌套是和大写字母的个数m有关系,所以为(n*m)。
第三个我看了半天,应该是O(n)吧,要是不对,欢迎大家指正。

总结

最近加了几个校招群,动不动北大复旦,还有研究生,感到跟大佬差距甚远,加油吧骚年。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注