文/michael
作為一個(gè)還沒找到工作的大三狗來說愚墓，校招無疑是最好的，也是最后的機(jī)會(huì)湾蔓，對(duì)于BAT土涝，大家肯定也是削尖了腦袋往里鉆的。這必須付出必別人更多的努力才行的濒憋。
2016騰訊春招的編程題
話不多說何暇，直接上題
- 給定一個(gè)字符串s，你可以從中刪除一些字符凛驮，使得剩下的串是一個(gè)回文串裆站。如何刪除才能使得回文串最長(zhǎng)呢？輸出需要?jiǎng)h除的字符個(gè)數(shù) 黔夭。
這道題是以回文為載體宏胯，考察兩個(gè)字符間的最大子串，最大子串算法在表示字符串的關(guān)聯(lián)度上用途很廣泛本姥。
而遮到題就是字符串的長(zhǎng)度減去其和翻轉(zhuǎn)字符串的長(zhǎng)度的最大子串即可肩袍。最長(zhǎng)子串的算法我一開始也是蒙的。這完全沒沒思路呀婚惫。氛赐。
后來看到一篇blog魂爪，才明白最長(zhǎng)子串，好的艰管，最后我們形成代碼
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');
- 把一個(gè)字符串的大寫字母放到字符串的后面滓侍，各個(gè)字符的相對(duì)位置不變，且不能申請(qǐng)額外的空間牲芋。
這道題感覺上必上題好理解一點(diǎn)粗井，起碼自己腦袋里面有個(gè)大概的概念，請(qǐng)注意是不能再申請(qǐng)空間（即使是數(shù)組+1）,所以要求我們?cè)谡麄€(gè)array中進(jìn)行遍歷街图〗匠模基本思路是先找出大寫字母的后一個(gè)字母，若是小寫就交換餐济，大寫就記錄下位子耘擂，指針再后移，直到是小寫字母為止絮姆，然后遍歷交換元素位子醉冤，指針是永遠(yuǎn)指向第一個(gè)大寫字母的。
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");
- 蛇形矩陣作為一種常用的數(shù)學(xué)數(shù)列篙悯，是由1開始的自然數(shù)一次排列成的一個(gè)N*N的正方形矩陣蚁阳，數(shù)字一次由外而內(nèi)的遞增,輸入蛇形矩陣寬度N，輸出整個(gè)蛇形矩陣結(jié)果鸽照，注意輸出格式要求按照矩陣從上至下的依次按行輸出螺捐，每行中間無需換行輸出。eg:樣本輸入： 3樣本輸出： 1 2 3 8 9 4 7 6 5
直接按照上矮燎、右定血、下、左的順序進(jìn)行遍歷诞外，計(jì)算好遍歷層數(shù)就OK了.我們可以拓展到n行澜沟，m列的蛇形矩陣，其中有個(gè)規(guī)律就是遍歷的層數(shù)峡谊，為（行數(shù)+1）/2的向下取整茫虽。記住這個(gè)，然后細(xì)心再細(xì)心就好既们。
function snake($row = 3, $col = 3){
$res = array();
// 初始值
$start = 1;
// 當(dāng)前遍歷層數(shù)
$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();
時(shí)間復(fù)雜度
首先列出時(shí)間復(fù)雜度濒析。第一個(gè)是O(n^2)這沒啥說的。
第二個(gè)是說白了就是個(gè)冒泡的贤壁，但最里層嵌套是和大寫字母的個(gè)數(shù)m有關(guān)系悼枢，所以為(n*m)。
第三個(gè)我看了半天脾拆，應(yīng)該是O(n)吧馒索，要是不對(duì)，歡迎大家指正名船。
總結(jié)
以前的我天真的認(rèn)為只要在大學(xué)期間做足夠的項(xiàng)目經(jīng)驗(yàn)绰上，就可以找到份不錯(cuò)的工作，我承認(rèn)我并不是像一些真正的大牛渠驼，對(duì)program抱有極大的興趣蜈块。這點(diǎn)很重要，我們學(xué)生時(shí)代的項(xiàng)目再多迷扇，大多數(shù)是寫業(yè)務(wù)邏輯百揭。并不能接觸到算法和架構(gòu)等高端的應(yīng)用場(chǎng)景，而大公司可以蜓席！
最后祝大家器一，也祝我，在校招之即找到份合適的工作３凇Ｆ盹酢！fighting雏胃！
