《劍指Offer》各面試題總結

目錄

• 前言
• 面試題4 二維陣列的查找
  • 一維二分法
  • 二維查找法
• 面試題5：替換空格
  • 偽新建陣列法
  • 從后往前法
• 面試題6：從尾到頭列印鏈表
• 面試題7：重建二叉樹
  • 題解
• 面試題8：二叉樹的下一個節點
  • 題解
• 面試題9：用兩個堆疊實作佇列
  • 題解
• 面試題10：斐波那契數列
  • 矩陣快速冪
• 面試題11：旋轉陣列的最小數字
  • 二分查找
• 面試題12：矩陣中的路徑
  • 思路
• 面試題13：機器人的運動范圍
  • 思路
• 面試題14：剪繩子
  • 貪心
  • 動態規劃
• 面試題15：二進制中1的個數
  • 思路
• 面試題16：數值的整數次方
  • 思路
• 面試題17：列印從1到最大的n位數
  • 思路
• 面試題18：洗掉鏈表的節點
  • 題目一
    • 思路
  • 題目二
    • 思路
• 面試題19：正則運算式匹配
  • 思路
• 面試題20：表示數值的字串
  • 思路
• 面試題21：調整陣列順序使奇數位于偶數前面
  • 思路
• 面試題22：鏈表中倒數第k個節點
  • 常規解法
  • 遞回法
• 面試題23：鏈表中環的入口節點
  • 書上題解有關快指標追上慢指標的證明
  • set標記
• 面試題24：反轉鏈表
  • 思路
• 面試題25：合并兩個排序的鏈表
  • 思路
• 面試題26：樹的子結構
  • 思路
• 面試題27：二叉樹的鏡像
  • 思路
• 面試題28：對稱的二叉樹
  • 思路
• 面試題29：順時針列印矩陣
  • 思路
• 面試題30：包含min函式的堆疊
  • 思路
• 面試題31：堆疊的壓入、彈出序列
  • 思路
• 面試題32：從上到下列印二叉樹
  • 思路
• 面試題33：二叉搜索樹的后序遍歷序列
  • 思路
• 面試題34：二叉樹中和為某一值的路徑
  • 思路
• 面試題35：復雜鏈表的復制
  • 思路
• 面試題36：二叉搜索樹與雙向鏈表
  • 遞回
• 面試題37：序列化二叉樹
  • 思路
• 面試題38：字串的排列
  • 思路
• 面試題39：陣列中出現次數超過一半的數字
  • 思路
• 面試題40：最小的k個數
  • 基于快排的Partition函式
  • 基于優先佇列（堆）
• 面試題41：資料流中的中位數
  • 兩個優先佇列（堆）
• 面試題42：連續子陣列的最大和
  • 貪心
• <--------To be continued

前言

找作業必刷書，每次學習其他內容前先刷一兩題熱熱身，相對于ACM來說簡單了很多，就當復習下學過的知識，順便劃劃水，疫情期間還是太閑的，
題目在牛客網上都有，不過牛客網似乎沒有非法輸入樣例，例如空指標作為測驗資料啥的，為節省時間，所以一切從簡，無視非法輸入資料，給出的代碼均在牛客網上AC就算了，
牛客網地址：https://www.nowcoder.com/ta/coding-interviews?page=1

面試題4 二維陣列的查找

題目：在一個二維陣列中（每個一維陣列的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序，請完成一個函式，輸入這樣的一個二維陣列和一個整數，判斷陣列中是否含有該整數，

一維二分法

顯然，每行或每列都是順序排序，所以可以遍歷每行，然后對每列進行二分查找，反之亦可，
時間復雜度O(nlogn)，空間復雜度O(1)

二維查找法

這是書上的方法，只要將右上角的數字作為重點即可，
顯然，對于右上角的數字X來說，其左邊的必然小于X，其下面的必然大于X，
那么，當所需查找的數字小于X時，顯然可以排除掉X所在的列，因為該列的數字大小均 >=X，反之則排出行即可，
時間復雜度O(n)，空間復雜度O(1)

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int max_row = array.size();
        int row = 0;
        int column = array[0].size()-1;

        while(row < max_row && column >= 0){
            if (target == array[row][column]) return true;
            else if (target < array[row][column]) column--;
            else row++;
        }

        return false;
    }
};

面試題5：替換空格

題目：請實作一個函式，將一個字串中的每個空格替換成“%20”，例如，當字串為We Are Happy.則經過替換之后的字串為We%20Are%20Happy，要求只能在原來的陣列中替換，保證輸入后的字串有足夠多的空余記憶體，

偽新建陣列法

雖然題目要求了不能在原來陣列替換，但是原來陣列記憶體足夠多啊，完全可以把原來陣列的后面當作一個新陣列即可，替換完后再將原來陣列的起始地址再+原來陣列的長度+1，這方法有點取巧，雖然符合題目要求，這里就懶得敲代碼了，

從后往前法

先找出所有空格數，顯然替換后的陣列長度 = 舊陣列長度 + 空個數*2，然后從后往前依次替換即可，

class Solution {
public:
	void replaceSpace(char *str,int length) {
		int num = 0;//空格數
		for(int i = 0;str[i];i++)
			num += (str[i] == ' ');
		int index_old = length;
		int index_new = length+num*2;

		while(index_old >= 0){
			if(str[index_old] != ' ') str[index_new--] = str[index_old--];
			else{
				str[index_new--] = '0';
				str[index_new--] = '2';
				str[index_new--] = '%';
				index_old--;
			}
		}

		return ;
	}
};

面試題6：從尾到頭列印鏈表

簡單遞回即可，略，

面試題7：重建二叉樹

題目：輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹，假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字，例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并回傳，

題解

較為簡單，僅給出代碼

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution
{
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.empty()) return nullptr;
        TreeNode *root = new TreeNode(pre[0]);
        auto it = find(vin.begin(),vin.end(),pre[0]);
        root->left = reConstructBinaryTree(
            vector<int>(pre.begin()+1,pre.begin()+1+(it-vin.begin())),vector<int>(vin.begin(),it));
        root->right = reConstructBinaryTree(
            vector<int>(pre.begin()+1+(it-vin.begin()),pre.end()),vector<int>(it+1,vin.end()));
        return root;
    }
};

面試題8：二叉樹的下一個節點

題目：給定一個二叉樹和其中的一個結點，請找出中序遍歷順序的下一個結點并且回傳，注意，樹中的結點不僅包含左右子結點，同時包含指向父結點的指標，

題解

較為簡單，兩種情況：
1、若有右節點，則找出右節點的最左節點
2、若無右節點，則回圈找出父節點，當一個父節點的左節點等于子節點時，回傳父節點

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode){
        if (pNode->right != nullptr){
            pNode = pNode->right;
            while(pNode->left != nullptr)
                pNode = pNode->left;
            return pNode;
        }
        while(true){
            TreeLinkNode *father = pNode->next;
            if(father == nullptr||father->left == pNode) return father;
            pNode = father;
        }
    }
};

面試題9：用兩個堆疊實作佇列

題目：用兩個堆疊來實作一個佇列，完成佇列的Push和Pop操作， 佇列中的元素為int型別，

題解

較為簡單，堆疊是先進后出，佇列是先進先出，堆疊和佇列正好相反，兩個堆疊之間可以實作元素的反序，
舉個例子，第一個堆疊依次放入{1,2,3,4}，將第一個堆疊依次排除放入第二個堆疊中，第二個堆疊則變成了{4,3,2,1}，此時pop出第二個堆疊便是佇列的順序，
注意：當第二個堆疊為空時才能進行此操作，

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {//懶得考慮佇列為空的情況
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int ans = stack2.top();
        stack2.pop();
        return ans;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

面試題10：斐波那契數列

題目：大家都知道斐波那契數列，現在要求輸入一個整數n，請你輸出斐波那契數列的第n項（從0開始，第0項為0）

矩陣快速冪

遞回效率太低，時間復雜度應該是\(O(2^n)\)，如果使用記憶化搜索或回圈的話，可以降到\(O(n)\)，不過這兩個都是常規操作，使用矩陣快速冪的話可以達到\(O(logn)\)，
詳見博文：https://www.cnblogs.com/MMMMMMMW/p/12300262.html

面試題11：旋轉陣列的最小數字

題目：把一個陣列最開始的若干個元素搬到陣列的末尾，我們稱之為陣列的旋轉，
輸入一個非遞減排序的陣列的一個旋轉，輸出旋轉陣列的最小元素，
例如陣列{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該陣列的最小值為1，
NOTE：給出的所有元素都大于0，若陣列大小為0，請回傳0，

二分查找

書上寫的是遞增，牛客的是非遞減，所以需要注意的是可能會有相同元素，
對于牛客的非遞減而言，就會出現{1,2,1,1,1,1,1}和{1,1,1,1,1,2,1}的情況，顯然難以二分，這里就有坑了，只能一格一格移動，所以即使用二分，最壞情況下還是\(O(n)\)，而書上的遞增陣列則可以\(O(logn)\)，直接跳過這題了，

面試題12：矩陣中的路徑

請設計一個函式，用來判斷在一個矩陣中是否存在一條包含某字串所有字符的路徑，路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子，如果一條路徑經過了矩陣中的某一個格子，則該路徑不能再進入該格子， 例如\(\begin{bmatrix} a & b & c &e \\ s & f & c & s \\ a & d & e& e\end{bmatrix}\)矩陣中包含一條字串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因為字串的第一個字符b占據了矩陣中的第一行第二個格子之后，路徑不能再次進入該格子，

思路

dfs和bfs都行吧，水題跳過，

面試題13：機器人的運動范圍

地上有一個m行和n列的方格，一個機器人從坐標0,0的格子開始移動，每一次只能向左，右，上，下四個方向移動一格，但是不能進入行坐標和列坐標的數位之和大于k的格子， 例如，當k為18時，機器人能夠進入方格（35,37），因為3+5+3+7 = 18，但是，它不能進入方格（35,38），因為3+5+3+8 = 19，請問該機器人能夠達到多少個格子？

思路

dfs或bfs，水題跳過

面試題14：剪繩子

給你一根長度為n的繩子，請把繩子剪成整數長的m段（m、n都是整數，n>1并且m>1），每段繩子的長度記為k[0],k[1],...,k[m]，請問k[0]xk[1]x...xk[m]可能的最大乘積是多少？例如，當繩子的長度是8時，我們把它剪成長度分別為2、3、3的三段，此時得到的最大乘積是18，

貪心

書上題解很詳細，略，只貼出代碼

class Solution {
public:
    int cutRope(int number) {
        return number <= 3?number-1:((int)pow(3,number/3-(number%3==1))*(number%3?(number%3==1?4:2):1));
    }
};

動態規劃

如式：\(f(n)=max[f(i)*f(n-i),f(n)]\)，然而本題dp效果不如貪心，故略，

面試題15：二進制中1的個數

輸入一個整數，輸出該數二進制表示中1的個數，其中負數用補碼表示，

思路

基礎做法自然是先轉化成二進制，再求解，但鑒于負數的存在（負數用二進制表示時，最高位表示負數，其他位表示正數，其值為和），可以考慮下其他解決方法，將一個數n最后一個1置0的方法為\(n &= n-1\)，很好理解，一個數減1后，最后一個1變為0，后面的數變為1，再&原來的數，這部分就全變成0了，

int  NumberOf1(int n) {
    int count = 0;
    while(n) count++, n&=n-1;
    return count;
}

面試題16：數值的整數次方

給定一個double型別的浮點數base和int型別的整數exponent，求base的exponent次方，
保證base和exponent不同時為0

思路

考慮各種特殊情況即可，可使用快速冪，略，

面試題17：列印從1到最大的n位數

這題牛客居然沒有，沒題目復制，看書吧，

思路

顯然需要用到大數，java就舒服了，自帶大數，C/C++就需要自己用字串模擬，但并不算難，ACM準大一新生賽必出題，話說int達到1e9，long long則1e18，正常范圍內都幾乎不可能列印完的，代碼略，

面試題18：洗掉鏈表的節點

題目一

給定單向鏈表的頭指標和一個節點指標，O(1)內洗掉該節點，

思路

這題目簡直在逗我，交換資料后洗掉下一個節點，雖說達到了功能，但準確來講還是洗掉了下一個節點而不是該節點，不過正常操作下單向鏈表O(1)洗掉指定節點是不存在的，因為找不到前面的節點，

題目二

在一個排序的鏈表中，存在重復的結點，請洗掉該鏈表中重復的結點，重復的結點不保留，回傳鏈表頭指標， 例如，鏈表1->2->3->3->4->4->5 處理后為 1->2->5

思路

思路不難，就是鏈表和指標有點惡心，還需要考慮各種特殊情況，比較麻煩，

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead){
        ListNode *NewHead = new ListNode(0);//頭部可能重復，因此頭指標可能會洗掉，需自定義一個偽頭指標
        ListNode *Now = pHead;
        ListNode *Pre = NewHead;
        while(Now != nullptr){
            bool need_delete = false;
            while(Now->next != nullptr && Now->val == Now->next->val){
                need_delete = true;
                Now = Now->next;
            }
            ListNode *pNext = Now->next;
            if(!need_delete){
                Pre->next = Now;
                Pre = Now;
                Pre->next = nullptr;
            }
            Now = pNext;
        }
        return NewHead->next;
    }
};

面試題19：正則運算式匹配

請實作一個函式用來匹配包括'.'和'*'的正則運算式，模式中的字符'.'表示任意一個字符，而'*'表示它前面的字符可以出現任意次（包含0次）， 在本題中，匹配是指字串的所有字符匹配整個模式，例如，字串"aaa"與模式"a.a"和"ab*ac*a"匹配，但是與"aa.a"和"ab*a"均不匹配

思路

簡單模擬，模擬題思路都比較簡單，就是考慮各種亂七八糟的情況，所以比較麻煩，需要考慮全，漏一個都不行，所以寫起來比較惡心，

class Solution {
public:
    bool match(char* str, char* pattern){
        if (str == nullptr || pattern == nullptr)
            return false;
        if (*str == '\0' && *pattern == '\0')
            return true;
        if (*pattern == '\0' )
            return false;
        if (*(pattern+1) == '*' )
            return match(str,pattern+2) || ((((*pattern == '.' && *str != '\0') || *str == *pattern) &&(match(str+1,pattern))));
        if ((*pattern == '.' && *str != '\0') || *str == *pattern )
            return match(str+1,pattern+1);
        return false;
    }
};

面試題20：表示數值的字串

請實作一個函式用來判斷字串是否表示數值（包括整數和小數），例如，字串"+100","5e2","-123","3.1416"和"-1E-16"都表示數值， 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是，

思路

模擬水題，需考慮各種情況，寫起來惡心但思路很水，跳過

面試題21：調整陣列順序使奇數位于偶數前面

輸入一個整數陣列，實作一個函式來調整該陣列中數字的順序，使得所有的奇數位于陣列的前半部分，所有的偶數位于陣列的后半部分，并保證奇數和奇數，偶數和偶數之間的相對位置不變，

思路

兩個指標，當前面指標指向偶數，后面指標指向奇數時，交換兩個值即可，水題略，可通過函式指標實作其他功能，

面試題22：鏈表中倒數第k個節點

輸入一個鏈表，輸出該鏈表中倒數第k個結點，

常規解法

題解思路挺水的，需要遍歷兩遍，當然也可以用兩個指標遍歷，指標相距k-1后同時遍歷，然而事實上這種解法遍歷次數和前者一樣，都是需要一個指標遍歷到終點，一個指標遍歷到答案點，本質上并無區別，水題略，

遞回法

跳過兩題了，還是得敲敲代碼，然而遍歷兩遍的解法太常規了，這時候我覺得，如果要求鏈表的每個節點只能經過一次呢？也就是真正意義上遍歷一遍，此時便可以使用遞回法，遍歷到終點時回傳終點指標和計數1，此后遞回回傳時計數+1，這時候相當于從終點開始遍歷了，

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    pair<ListNode*,int> FindKthToTail_pair(ListNode* pListHead,unsigned int k){
        if (pListHead->next == nullptr) return make_pair(pListHead,1);
        pair<ListNode*,int> pre = FindKthToTail_pair(pListHead->next,k);
        if(pre.second == k) return pre;
        return make_pair(pListHead,pre.second+1);
    }
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(pListHead == nullptr || k == 0)
            return nullptr;
        pair<ListNode*,int> ans = FindKthToTail_pair(pListHead,k);
        return ans.second == k?ans.first: nullptr; //不等于說明整個鏈表長度不足
    }
};

面試題23：鏈表中環的入口節點

給一個鏈表，若其中包含環，請找出該鏈表的環的入口結點，否則，輸出null，

書上題解有關快指標追上慢指標的證明

隨便寫寫，并不規范
證明追上時必定在環上
顯然，當快指標追上慢指標時，快指標顯然已經回圈過了，那么快指標必然在環上，
證明快指標必然會與慢指標在同一位置
快指標行走2t，慢指標行走t，慢指標進入環內后，開始時兩者相距m，環的大小為n，相遇時快指標回圈了x圈，慢指標回圈了y圈，則必有\(2a + m = x*n\)和\(a = y*n\)，相減并整理得\(x - y = (a+m)/n\)，其中m，n均固定，a每次加1，所以\((a+m)/n\)必然會出現整數的情況，即上式必然有解，

不過其實不用這么麻煩，考慮各種情況即可，

• 慢指標在快指標前一格
  • 慢先走一格，快再走兩格，相遇
  • 快先走兩各，慢再走一個，相遇
• 慢指標在快指標前兩格
  • 慢先走一格，快再走兩格，就變成上面的情況【慢指標在快指標前一格】
  • 快先走兩個，直接相遇

所以，快指標一定能和慢指標相遇，

set標記

一個寫起來輕松但并非高效的做法，使用set記錄下經過的節點，只需要遍歷一遍即可，不過使用set的時間復雜度為\(O(logn)\)，故總時間復雜度為\(O(logn*n)\)，再加上set所需的空間復雜度，效果肯定沒題解好，但敲起來輕松點，書上的題解就懶得敲了，

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead){
        set<ListNode*> set_node;
        while(pHead != nullptr){
            if(set_node.count(pHead)) return pHead;
            set_node.insert(pHead);
            pHead = pHead->next;
        }
        return nullptr;
    }
};

面試題24：反轉鏈表

輸入一個鏈表，反轉鏈表后，輸出新鏈表的表頭，

思路

略，僅提供代碼

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* pPre = nullptr;

        while(pHead != nullptr){
            ListNode* temp = pHead->next;
            pHead->next = pPre;
            pPre = pHead;
            pHead = temp;
        }

        return pPre;
    }
};

面試題25：合并兩個排序的鏈表

輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則，

思路

略

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2){
        if(pHead1 == nullptr || pHead2 == nullptr) return pHead1 == nullptr?pHead2:pHead1;
        ListNode* pNewHead = (pHead1->val < pHead2->val)?pHead1:pHead2;
        pNewHead->next = (pHead1->val < pHead2->val)? Merge(pHead1->next,pHead2):Merge(pHead1,pHead2->next);
        return pNewHead;
    }
};

面試題26：樹的子結構

輸入兩棵二叉樹A，B，判斷B是不是A的子結構，（ps：我們約定空樹不是任意一個樹的子結構），

思路

遞回水題，僅給出代碼

class Solution {
public:
    bool IsSubtree(TreeNode* pRoot1, TreeNode* pRoot2){
        if (pRoot2 == nullptr) return true;
        if (pRoot1 == nullptr) return false;
        return  abs(pRoot1->val - pRoot2->val)< 1e-6
                &&IsSubtree(pRoot1->left,pRoot2->left)
                &&IsSubtree(pRoot1->right,pRoot2->right);
    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2){
        return (pRoot1 == nullptr || pRoot2 == nullptr)?false
                :(IsSubtree(pRoot1,pRoot2) || HasSubtree(pRoot1->left,pRoot2) || HasSubtree(pRoot1->right,pRoot2));
    }
};

面試題27：二叉樹的鏡像

操作給定的二叉樹，將其變換為源二叉樹的鏡像，

思路

遞回，每次交換左右節點，水題略

面試題28：對稱的二叉樹

請實作一個函式，用來判斷一顆二叉樹是不是對稱的，注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的，

思路

中左右和中右左同時遍歷，

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pNode1,TreeNode* pNode2){
        return  (pNode1 == nullptr && pNode2 == nullptr)?true:
                (pNode1 != nullptr && pNode2 != nullptr
                &&pNode1->val == pNode2->val
                &&isSymmetrical(pNode1->left,pNode2->right)
                &&isSymmetrical(pNode2->right,pNode1->left));
    }
    bool isSymmetrical(TreeNode* pRoot){
        return isSymmetrical(pRoot,pRoot);
    }
};

面試題29：順時針列印矩陣

輸入一個矩陣，按照從外向里以順時針的順序依次列印出每一個數字，例如，如果輸入如下4 X 4矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依次列印出數字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

思路

找規律，例如題目給出的例子，其位置變化為y+3 x+3 y-3 x-2 y+2 x+1 y-1 ，規律很明顯，代碼能省就省，但面試千萬別這么寫

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> ans;
        if (matrix.empty() || matrix[0].empty()) return ans;
        int matrix_num_x = matrix.size(),matrix_num_y = matrix[0].size();
        int sum = matrix_num_x*matrix_num_y,check = 1,x = 0,y = matrix_num_y-1;
        for(int i = 0;i < matrix_num_y;ans.push_back(matrix[0][i++])); 
        while(ans.size() < sum ){
            for(int i = --matrix_num_x;i;i--,ans.push_back(matrix[x+= check][y]));
            check *= -1;
            for(int i = --matrix_num_y;i;i--,ans.push_back(matrix[x][y+= check]));
        }
        return ans;
    }
};

面試題30：包含min函式的堆疊

定義堆疊的資料結構，請在該型別中實作一個能夠得到堆疊中所含最小元素的min函式（時間復雜度應為O（1）），
注意：保證測驗中不會當堆疊為空的時候，對堆疊呼叫pop()或者min()或者top()方法，

思路

再定義一個輔助堆疊，其堆疊頂為最小值，每次壓入新值時與輔助堆疊的堆疊頂比較，若大于等于，則在輔助堆疊繼續壓入堆疊頂的值，若小于，則在輔助堆疊壓入新值，代碼略，

面試題31：堆疊的壓入、彈出序列

輸入兩個整數序列，第一個序串列示堆疊的壓入順序，請判斷第二個序列是否可能為該堆疊的彈出順序，假設壓入堆疊的所有數字均不相等，例如序列1,2,3,4,5是某堆疊的壓入順序，序列4,5,3,2,1是該壓堆疊序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓堆疊序列的彈出序列，（注意：這兩個序列的長度是相等的）

思路

按順序壓入堆疊，當堆疊頂等于彈出序列首個元素時，彈出堆疊頂并洗掉彈出序列的首個元素，當壓入結束后堆疊中仍有元素時，則回傳false，

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> st;
        int point_push = 0,point_pop = 0;
        while(point_push < pushV.size()){
            st.push(pushV[point_push++]);
            while(!st.empty()&&popV[point_pop] == st.top()){
                point_pop++;
                st.pop();
            }
        }
        return st.empty();
    }
};

面試題32：從上到下列印二叉樹

從上往下列印出二叉樹的每個節點，同層節點從左至右列印，

思路

佇列先進先出，題目二可以使用pair<TreeNode,int>存盤該節點第幾層，題目三則是按層數奇偶判斷即可，二三代碼略，

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        vector<int> ans;
        queue<TreeNode*> que_print;
        if (root != nullptr) que_print.push(root);
        while(!que_print.empty()){
            TreeNode* front_que = que_print.front();
            que_print.pop();
            ans.push_back(front_que->val);
            if(front_que->left != nullptr) que_print.push(front_que->left);
            if(front_que->right != nullptr) que_print.push(front_que->right);
        }
        return ans;
    }
};

面試題33：二叉搜索樹的后序遍歷序列

輸入一個整數陣列，判斷該陣列是不是某二叉搜索樹的后序遍歷的結果，如果是則輸出Yes,否則輸出No，假設輸入的陣列的任意兩個數字都互不相同，

思路

二叉搜索樹，值的大小左<中<右，后續遍歷順序左右中，顯然最后一個為根，前面連續小于根的元素均為左子樹部分，其他的為右子樹，當右子樹部分有小于根的情況，則不是二叉搜索樹，回傳false，否則對左右子樹繼續遞回判斷，

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        int len = sequence.size(),i = 0,j = 0;
        if (len == 0 || len == 1) return len;//陣列只剩一個節點時，可生成二叉搜索樹
        while(sequence[i] < sequence[len-1]) j=++i;
        while(j < len-1) if (sequence[j++] <sequence[len-1]) return false;
        return (!i?true:VerifySquenceOfBST(vector<int>(sequence.begin(),sequence.begin()+i)))
        &&(!(len-i-1)?true:VerifySquenceOfBST(vector<int>(sequence.begin()+i,sequence.end()-1)));
    }
};

面試題34：二叉樹中和為某一值的路徑

輸入一顆二叉樹的根節點和一個整數，列印出二叉樹中結點值的和為輸入整數的所有路徑，路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑，(注意: 在回傳值的list中，陣列長度大的陣列靠前)，

思路

bfs或遞回均可，遞回為fuc(左右子樹，k=值-當前節點值)，當到葉節點時判斷當前值與k是否相等即可，代碼略，
需要注意的是，題目要求陣列長度大的陣列靠前，而bfs是從短到長，因此每次加入新陣列時可以從頭加，而遞回則無序，需要重新排序，

面試題35：復雜鏈表的復制

輸入一個復雜鏈表（每個節點中有節點值，以及兩個指標，一個指向下一個節點，另一個特殊指標指向任意一個節點），回傳結果為復制后復雜鏈表的head，（注意，輸出結果中請不要回傳引數中的節點參考，否則判題程式會直接回傳空）

思路

難點在于另個一特殊指標，它指向的是原來鏈表的位置，但復制的話就需要指向新鏈表的位置，方法很多，例如兩重回圈\(O(n^2)\)，用map將特殊節點對應\(O(logn*n)/O(n)\)，map也可用unorded_map，即哈希來使得時間復雜度\(O(n)\)，但這些的空間復雜度都較高，于是最好的肯定就是時間\(O(n)\)，空間\(O(1)\)的做法了，做法看書即可，還算明了，就是寫代碼的時候有些大坑，例如特殊指標可能為空，可能從空指標取值而導致崩潰，此外還有牛客上提交的代碼千萬不能改變原來的鏈表結構，因此拆分時需要還原舊鏈表，不然會顯示輸出結果為空，我之前拆分的時候就只管拆出新鏈表，而不管舊鏈表，坑了好久百度后才發現必須將舊鏈表還原，

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead){
        RandomListNode* pNewHead = nullptr;//無需判斷頭指標為空情況，因為運行程序中已經判斷了
        for(RandomListNode *pNewTemp,*pOldTemp = pHead;pOldTemp!= nullptr;pOldTemp = pNewTemp->next){
            pNewTemp = new RandomListNode(pOldTemp->label);
            if (pNewHead == nullptr) pNewHead = pNewTemp;
            pNewTemp->next = pOldTemp->next;
            pOldTemp->next = pNewTemp;
        }
        for(RandomListNode* pTemp = pHead;pTemp != nullptr;pTemp = pTemp->next->next)
            pTemp->next->random = (pTemp->random== nullptr? nullptr:pTemp->random->next);//注意：特殊節點可能為空
        for(RandomListNode* pTemp = pHead;pTemp != nullptr;pTemp = pTemp->next) {
            RandomListNode* pNext = pTemp->next->next;
            if (pNext != nullptr) pTemp->next->next = pNext->next;//空指標取值會崩潰
            pTemp->next = pNext;
        }
        return pNewHead;
    }
};

面試題36：二叉搜索樹與雙向鏈表

輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表，要求不能創建任何新的結點，只能調整樹中結點指標的指向，

遞回

對于一個節點來說，其左邊連接左子樹的最右（大）節點，其右邊連接右子樹的最左（小）節點，如此便是排序的雙向鏈表，

TreeNode* Convert_(TreeNode* pRootOfTree,bool is_left){
    if (pRootOfTree == nullptr) return nullptr;
    if (pRootOfTree->left != nullptr) {
        pRootOfTree->left = Convert_(pRootOfTree->left,true);
        pRootOfTree->left->right = pRootOfTree;
    }
    if (pRootOfTree->right != nullptr) {
        pRootOfTree->right = Convert_(pRootOfTree->right,false);
        pRootOfTree->right->left = pRootOfTree;
    }
    if (is_left) return pRootOfTree->right == nullptr?pRootOfTree:pRootOfTree->right;
    else return pRootOfTree->left == nullptr?pRootOfTree:pRootOfTree->left;
}
TreeNode* Convert(TreeNode* pRootOfTree){
    TreeNode* ans = Convert_(pRootOfTree,true);
    while(ans != nullptr && ans->left != nullptr)
        ans = ans->left;
    return ans;
}

面試題37：序列化二叉樹

請實作兩個函式，分別用來序列化和反序列化二叉樹，

思路

前中后序均可，將空指標用特殊字符替代，代碼略，

面試題38：字串的排列

輸入一個字串,按字典序列印出該字串中字符的所有排列，例如輸入字串abc,則列印出由字符a,b,c所能排列出來的所有字串abc,acb,bac,bca,cab和cba，(可能有字符重復)

思路

我記得當時準大一，在暑假的ACM新生賽時遇到過這題，花了挺長時間找規律解決的，沒用遞回（初學C語言），當時的方法也忘了，不過印象挺深的，
遞回，需要注意的是，可能有字符重復，所以需要去重，例如"aaa"，就只能輸出一個結果，不過，其實C/C++自帶實作排列的函式，但是面試的時候肯定不能用的，不過機試的時候只要AC就行，如果不查代碼的話倒是可以用用，

//正常面試寫法
class Solution {
public:
    void Permutation(vector<string> &ans,string &str,int begin){
        if (!str[begin]) ans.push_back(str);
        for(int i = begin;str[i];i++){
            swap(str[begin],str[i]);
            Permutation(ans,str,begin+1);
            swap(str[begin],str[i]);
        }
    }
    vector<string> Permutation(string &str) {
        vector<string> ans;
        if (str.empty()) return ans;
        Permutation(ans,str,0);
        sort(ans.begin(),ans.end());
        ans.erase(unique(ans.begin(),ans.end()),ans.end());
        return ans;
    }
};
//機試寫法
class Solution {
public:
    vector<string> Permutation(string &str) {
        vector<string> ans;
        if (str.empty()) return ans;
        sort(str.begin(),str.end());
        do{
            ans.push_back(str);
        }while(next_permutation(str.begin(),str.end()));
        return ans;
    }
};

面試題39：陣列中出現次數超過一半的數字

陣列中有一個數字出現的次數超過陣列長度的一半，請找出這個數字，例如輸入一個長度為9的陣列{1,2,3,2,2,2,5,4,2}，由于數字2在陣列中出現了5次，超過陣列長度的一半，因此輸出2，如果不存在則輸出0，

思路

劍指題解二，僅提供代碼

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if (numbers.empty()) return 0;
        int cent = 1,pre = numbers[0],times = 0;
        for(int i = 1;i < numbers.size();i++)
            if (numbers[i] != numbers[i-1]){
                if (cent == 1) pre = numbers[i];
                else cent--;
            }
            else cent++;
        for(int i = 0;i < numbers.size();i++)
            if (pre == numbers[i]) times++;
        return times*2 > numbers.size()?pre:0;
    }
};

面試題40：最小的k個數

輸入n個整數，找出其中最小的K個數，例如輸入4,5,1,6,2,7,3,8這8個數字，則最小的4個數字是1,2,3,4，

基于快排的Partition函式

準確來說，該時間復雜度不應該是題解所說的\(O(n)\)，

• 最佳情況下是選擇中位數作為基準數，這時候就能將陣列一分為二，直接舍棄一半，遍歷次數為\(S = n+n/2+n/4...\)，時間復雜度倒是可以算作\(O(n)\)，
• 最差情況下是每次都選擇了值最小或最大的元素作為基準值，那每次就只能舍棄一個值，遍歷次數為\(S = n+(n-1)+(n-2)...\)，所以時間復雜度為\(O(n^2)\)，
• 綜合來說，時間復雜度介于\(O(n)\)到\(O(n^2)\)之間

class Solution {
public:
    int partition(vector<int> &input,int left,int right){
        int key = rand()%(right-left+1)+left;
        swap(input[key],input[left]);
        key = left;
        while(left < right){
            //如果兩個where交換位置呢？
            //最后可能出現input[left] > input[key]&&left > key的情況
            //即最后交換后左側會有一個值大于基準值
            while(left < right && input[right] >= input[key]) right--;
            while(left < right && input[left] <= input[key]) left++;
            if (left < right) swap(input[left],input[right]);
        }
        swap(input[left],input[key]);
        return left;
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
            if (input.empty() ||  k > input.size() || --k < 0) return vector<int>(input.begin(),input.begin());
            int left = 0,right = input.size();//范圍[left,right)
            while(left < right){
                    int mid = partition(input,left,right-1);
                    if (mid == k) return vector<int>(input.begin(),input.begin()+k+1);
                    else if (mid < k ) left = mid +1;
                    else right = mid;
            }
    }
};

基于優先佇列（堆）

當資料量大，且不允許改變資料范圍時，使用堆，時間復雜度\(O(nlogk)\)

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
    		vector<int> ans;
    		priority_queue<int> que;
            if (input.empty() ||  k > input.size() || k <= 0) return ans;
            for(auto it = input.begin();it != input.end();it++)
                if (que.size() < k) que.push(*it);
                else if (que.top() > *it){
                    que.pop();
                    que.push(*it);
                }
           while(!que.empty()){
            	ans.push_back(que.top());
            	que.pop();
            }
            return ans;
    }
};

面試題41：資料流中的中位數

如何得到一個資料流中的中位數？如果從資料流中讀出奇數個數值，那么中位數就是所有數值排序之后位于中間的數值，如果從資料流中讀出偶數個數值，那么中位數就是所有數值排序之后中間兩個數的平均值，我們使用Insert()方法讀取資料流，使用GetMedian()方法獲取當前讀取資料的中位數，

兩個優先佇列（堆）

左側用最大堆，右側用最小堆，顯然中位數就是兩個堆頂之一或兩個堆頂的平均值

class Solution {
public:
    priority_queue<int> max_que;
    priority_queue<int,vector<int>,greater<int> > min_que;
    void Insert(int num){
        int sum = max_que.size()+min_que.size();
        if (sum&1) min_que.push(num);
        else max_que.push(num);
        if (!min_que.empty()&&min_que.top() < max_que.top()){//當右側最小值小于左側最大值時交換
            min_que.push(max_que.top());
            max_que.push(min_que.top());
            min_que.pop();
            max_que.pop();
        }
    }
    double GetMedian(){ 
        return ((max_que.size()+min_que.size())&1)?max_que.top():(max_que.top()+min_que.top())/2.0;
    }
};

面試題42：連續子陣列的最大和

HZ偶爾會拿些專業問題來忽悠那些非計算機專業的同學，今天測驗組開完會后,他又發話了:在古老的一維模式識別中,常常需要計算連續子向量的最大和,當向量全為正數的時候,問題很好解決，但是,如果向量中包含負數,是否應該包含某個負數,并期望旁邊的正數會彌補它呢？例如:{6,-3,-2,7,-15,1,2,2},連續子向量的最大和為8(從第0個開始,到第3個為止)，給一個陣列，回傳它的最大連續子序列的和，你會不會被他忽悠住？(子向量的長度至少是1)

貪心

思路略，僅提供代碼

int FindGreatestSumOfSubArray(vector<int> array) {
	if (array.empty()) return 0;
	int ans = array[0];
	int Max = array[0];
	int pre = 0;
	for(auto each:array){
		pre += each;
		Max = max(each,Max);
		ans = max(pre,ans);
		pre = max(pre,0);
	}
	return Max < 0?Max:ans;
}

<--------To be continued

標籤：其他

上一篇：Nginx學習總結(一)

下一篇：前端面試積累（整理中）