腾讯2016校招编程题PHP实现

栏目: PHP · 发布时间: 6年前

内容简介:腾讯2016校招编程题PHP实现

文/michael

作为一个还没找到工作的大三狗来说,校招无疑是最好的,也是最后的机会,对于BAT,大家肯定也是削尖了脑袋往里钻的。这必须付出必别人更多的努力才行的。

2016腾讯春招的编程题

话不多说,直接上题

  • 给定一个字符串s,你可以从中删除一些字符,使得剩下的串是一个回文串。如何删除才能使得回文串最长呢?输出需要删除的字符个数  。

这道题是以回文为载体,考察两个字符间的最大子串,最大子串算法在表示字符串的关联度上用途很广泛。

而遮到题就是字符串的长度减去其和翻转字符串的长度的最大子串即可。最长子串的算法我一开始也是蒙的。这完全没没思路呀。。

后来看到一篇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)吧,要是不对,欢迎大家指正。

总结

以前的我天真的认为只要在大学期间做足够的项目经验,就可以找到份不错的工作,我承认我并不是像一些真正的大牛,对program抱有极大的兴趣。这点很重要,我们学生时代的项目再多,大多数是写业务逻辑。并不能接触到算法和架构等高端的应用场景,而大公司可以!

最后祝大家,也祝我,在校招之即找到份合适的工作!!!fighting!


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

精通Spring

精通Spring

罗时飞 / 第1版 (2005年4月1日) / 2005-4 / 39.0

本书深入剖析了当前流行的轻量级开发框架Spring技术。本书总共分成3部分。第一部分,重点阐述Spring的架构。这部分内容循序渐进带领开发者进入Spring中。主要在于阐述Spring IoC和Spring AOP。第二部分,重点阐述Spring的使用。这部分内容从简化Java/J2EE的角度出发,从J2EE平台各个技术层面分析、并给出大量的研究实例,对Spring提供的API进行阐述。主要在于......一起来看看 《精通Spring》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

在线进制转换器
在线进制转换器

各进制数互转换器

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具