第一道題：求有刪除情況的最長回文子串

題目：

?解題思路：

這個(gè)題嚴(yán)格意義上來說，刪除了字符就談不上回文串了，既然有刪除，那估計(jì)考察的不是回文串，而是其他的，但是這個(gè)東西又有回文串的特點(diǎn)，細(xì)想一下——那就是不連續(xù)的回文串，想到不連續(xù)，就容易使人想到最長公共子序列，把源字符串逆序之后對比兩個(gè)字符串發(fā)現(xiàn)：我靠，這不就是求兩個(gè)序列的最長公共子序列（好像跟回文串沒多大關(guān)系）。

考察：回文串，動(dòng)態(tài)規(guī)劃，知識(shí)遷移

1 #define M 100 2 int dpLCS[M][M]; //設(shè)置成全局變量，自動(dòng)初始化為0 3 4 //動(dòng)態(tài)規(guī)劃法:最長回文子串，有刪除，其實(shí)就是求最長公共子序列 5 int LongestCommonSequence(string str) 6 { 7 size_t n = str.size(); 8 if (n == 0 || n == 1) 9 return 1; 10 11 string s = str; 12 reverse(s.begin(), s.end()); 13 14 for (size_t i = 1; i <= n; ++ i) { 15 for (size_t j = 1; j <= n; ++ j) { 16 if (str[i-1] == s[j-1]) 17 dpLCS[i][j] = dpLCS[i-1][j-1] + 1; 18 else 19 dpLCS[i][j] = max(dpLCS[i-1][j], dpLCS[i][j-1]); 20 } 21 } 22 return dpLCS[n][n]; 23 }

第二個(gè)題：蛇形矩陣，又叫螺旋矩陣

題目：

?解題思路：

解螺旋矩陣的切入點(diǎn)需要知道矩陣的個(gè)數(shù)，看下面一幅圖：

如果是n = odd，則中間只有一個(gè)數(shù)，不算做一個(gè)矩陣，如果n = even，則中間是一個(gè)矩陣，總的矩陣個(gè)數(shù)為n/2，知道這一點(diǎn)，后面的工作就是分別從外向里遍歷每一個(gè)矩陣即可。

1 void HelixMatrix(int n) 2 { 3 int **a = new int *[n]; 4 for (int i = 0; i < n; i ++) 5 a[i] = new int[n]; 6 7 int m = 0; 8 for (int k = 0; k < n/2; ++ k) { //n/2矩陣個(gè)數(shù) 9 for (int i = 0; i <= n-1-k; ++ i) 10 a[k][i] = m++; //第一區(qū)塊 11 for (int i = k + 1; i < n-1-k; ++ i) 12 a[i][n-1-k] = m++; //第二區(qū)塊 13 for (int i = n-1-k; i > k; -- i) 14 a[n-1-k][i] = m++; //第三區(qū)塊 15 for (int i = n-1-k; i > k; -- i) 16 a[i][k] = m ++; //第四區(qū)塊 17 if (n%2 == 1) 18 a[n/2][n/2] = m; //n=odd，填充中間一個(gè)數(shù) 19 } 20 for (int i = 0; i < n; i ++) { 21 for (int j = 0; j < n; j ++) 22 cout << a[i][j] << " "; 23 cout << endl; 24 } 25 //釋放a 26 for(int i = 0; i < n; i ++) { 27 delete [] a[i]; 28 } 29 delete []a; 30 }

附：選擇題部分整理

1、HTTP協(xié)議的請求類型，端口號(hào)，返回碼等

2、在同一臺(tái)機(jī)器上，內(nèi)存訪問，SATA硬盤隨機(jī)訪問時(shí)間分別是：（幾十納秒，幾十毫秒）

3、E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)}的深度優(yōu)先遍歷序列

4、關(guān)于操作系統(tǒng)的說法正確的是：

　　a、同一個(gè)線程內(nèi)可以運(yùn)行多個(gè)消息隊(duì)列

　　b、Windows中使用臨界區(qū)，不需要切換到內(nèi)核態(tài)

　　c、互斥量可以用于多進(jìn)程間對資源的安全共享

　　d、信號(hào)量允許多個(gè)線程同時(shí)使用共享資源

5、頁面采用click事件會(huì)存在300ms延時(shí)的原因

6、用0-9,a-z表示36進(jìn)制的873085

7、冒泡排序，堆排序，歸并排序，快速排序的時(shí)間復(fù)雜度

8、http的返回碼101,404,502,200的含義

9、面向?qū)ο蟪绦蛟O(shè)計(jì)SOLID五大原則，各字母的含義

10、有關(guān)網(wǎng)絡(luò)協(xié)議說法正確的是:
　　A.UDP是無連接不可靠的，TCP是連接可靠的

　　B.HTTP請求的類型有g(shù)et, post, put, delete,head

　　C.HTTP默認(rèn)端口號(hào)為80，HTTPS默認(rèn)端口號(hào)為443，FTP默認(rèn)端口號(hào)為21

　　D.根據(jù)HTTP規(guī)范，GET請求用于信息獲取，并且應(yīng)該是安全的和冪等的

11、兩服務(wù)器相距1500km，一次ping請求耗時(shí)多長（4,8,16,32）

12、文件系統(tǒng)管理的最小磁盤空間單位（扇區(qū)，簇）

13、在移動(dòng)端瀏覽器，頁面采用click事件，會(huì)存在300ms的延遲，為什么？（要預(yù)先處理一些操作，還有判斷是否是雙擊操作）

14、A和B玩紐扣游戲，一共16個(gè)紐扣，兩人輪流來取，每人每次可以選取1個(gè)或3個(gè)或6個(gè)（不允許不取），規(guī)定誰取完最后的紐扣誰贏。如果讓A先取，則A的必勝策略下第一步應(yīng)該取？

總結(jié)

以上是生活随笔為你收集整理的腾讯2016春招之算法编程解析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。