騰訊2016春招之算法編程解析

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

題目：

?解題思路：

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

考察：回文串，動態規劃，知識遷移

#define M 100
int dpLCS[M][M]; //設置成全局變量，自動初始化為0

//動態規劃法:最長回文子串，有刪除，其實就是求最長公共子序列
int LongestCommonSequence(string str)
{
    size_t n = str.size();
    if (n == 0 || n == 1)
        return 1;
    
    string s = str;
    reverse(s.begin(), s.end());

    for (size_t i = 1; i <= n; ++ i) {
        for (size_t j = 1; j <= n; ++ j) {
            if (str[i-1] == s[j-1]) 
                dpLCS[i][j] = dpLCS[i-1][j-1] + 1;
            else 
                dpLCS[i][j] = max(dpLCS[i-1][j], dpLCS[i][j-1]); 
        }
    }
    return dpLCS[n][n];
}

第二個題：蛇形矩陣，又叫螺旋矩陣

題目：

?解題思路：

解螺旋矩陣的切入點需要知道矩陣的個數，看下面一幅圖：

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

void HelixMatrix(int n)
{
    int **a = new int *[n];
    for (int i = 0; i < n; i ++)
        a[i] = new int[n];

    int m = 0;
    for (int k = 0; k < n/2; ++ k) { //n/2矩陣個數
        for (int i = 0; i <= n-1-k; ++ i)
            a[k][i] = m++; //第一區塊
        for (int i = k + 1; i < n-1-k; ++ i)
            a[i][n-1-k] = m++; //第二區塊
        for (int i = n-1-k; i > k; -- i)
            a[n-1-k][i] = m++; //第三區塊
        for (int i = n-1-k; i > k; -- i)
            a[i][k] = m ++; //第四區塊
        if (n%2 == 1)
            a[n/2][n/2] = m; //n=odd，填充中間一個數
    }
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++)
            cout << a[i][j] << " ";
        cout << endl;
    }
    //釋放a
    for(int i = 0; i < n; i ++) {
        delete [] a[i];
    }
    delete []a;
}

附：選擇題部分整理

1、HTTP協議的請求類型，端口號，返回碼等

2、在同一臺機器上，內存訪問，SATA硬盤隨機訪問時間分別是：（幾十納秒，幾十毫秒）

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

4、關于操作系統的說法正確的是：

　　a、同一個線程內可以運行多個消息隊列

　　b、Windows中使用臨界區，不需要切換到內核態

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

　　d、信號量允許多個線程同時使用共享資源

5、頁面采用click事件會存在300ms延時的原因

6、用0-9,a-z表示36進制的873085

7、冒泡排序，堆排序，歸并排序，快速排序的時間復雜度

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

9、面向對象程序設計SOLID五大原則，各字母的含義

10、有關網絡協議說法正確的是:
　　A.UDP是無連接不可靠的，TCP是連接可靠的

　　B.HTTP請求的類型有get, post, put, delete,head

　　C.HTTP默認端口號為80，HTTPS默認端口號為443，FTP默認端口號為21

　　D.根據HTTP規范，GET請求用于信息獲取，并且應該是安全的和冪等的

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

12、文件系統管理的最小磁盤空間單位（扇區，簇）

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

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