目錄

第51題：

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

解題思路：

解這題需要把題意仔細研究清楚，反正我試了好多次才明白的。
首先，考慮特殊情況：1>兩個字符串都為空，返回true2>當第一個字符串不空，而第二個字符串空了，返回false（因為這樣，就無法匹配成功了,而如果第一個字符串空了，第二個字符串非空，還是可能匹配成功的，比如第二個字符串是“a*a*a*a*”,由于‘*’之前的元素可以出現0次，所以有可能匹配成功）
之后就開始匹配第一個字符，這里有兩種可能：匹配成功或匹配失敗。但考慮到pattern
下一個字符可能是‘*’， 這里我們分兩種情況討論：pattern下一個字符為‘*’或
不為‘*’：1>pattern下一個字符不為‘*’：這種情況比較簡單，直接匹配當前字符。如果匹配成功，繼續匹配下一個；如果匹配失敗，直接返回false。注意這里的“匹配成功”，除了兩個字符相同的情況外，還有一種情況，就是pattern的當前字符為‘.’,同時str的當前字符不為‘\0’。2>pattern下一個字符為‘*’時，稍微復雜一些，因為‘*’可以代表0個或多個。這里把這些情況都考慮到：a>當‘*’匹配0個字符時，str當前字符不變，pattern當前字符后移兩位，跳過這個‘*’符號；b>當‘*’匹配1個或多個時，str當前字符移向下一個，pattern當前字符不變。（這里匹配1個或多個可以看成一種情況，因為：當匹配一個時，由于str移到了下一個字符，而pattern字符不變，就回到了上邊的情況a；當匹配多于一個字符時，相當于從str的下一個字符繼續開始匹配）
之后再寫代碼就很簡單了。

代碼實現：

c++

class Solution {
public:bool match(char* str, char* pattern){if (*str == '\0' && *pattern == '\0')return true;if (*str != '\0' && *pattern == '\0')return false;//if the next character in pattern is not '*'if (*(pattern+1) != '*'){if (*str == *pattern || (*str != '\0' && *pattern == '.'))return match(str+1, pattern+1);elsereturn false;}//if the next character is '*'else{if (*str == *pattern || (*str != '\0' && *pattern == '.'))return match(str, pattern+2) || match(str+1, pattern);elsereturn match(str, pattern+2);}}
};

運行時間：5ms

占用內存：480k

python

# -*- coding:utf-8 -*-

第52題：

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

解題思路：

• 暫時想到的方式是遍歷字符串，然后寫一些規則判斷是否符合數值表達式的寫法，建議判斷反例比較好。

代碼實現：

c++

python

# -*- coding:utf-8 -*-
class Solution:# s字符串def isNumeric(self, s):# write code hereif len(s) < 1:return Falsehas_sign = Falsehas_dot = Falsehas_e  = Falsefor i in range(len(s)):if s[i]=="e" or s[i]=="E":if has_e:return Falseelse:has_e = Trueif i == len(s) - 1:return Falseelif s[i]=="+" or s[i] == "-":if has_sign :if s[i-1] != "e" and s[i-1] != "E":return Falseelse:has_sign = Trueif i > 0 and s[i-1] != "e" and s[i-1]!= "E":return Falseelif s[i]==".":if has_dot or has_e:return Falseelse:has_dot = Trueif i>0 and (s[i-1]=="e" or s[i-1]=="E"):return Falseelse:if s[i]<"0" or s[i]>"9":return Falsereturn True

運行時間：28ms

占用內存：5728k

第53題：

請實現一個函數用來找出字符流中第一個只出現一次的字符。例如，當從字符流中只讀出前兩個字符"go"時，第一個只出現一次的字符是"g"。當從該字符流中讀出前六個字符“google"時，第一個只出現一次的字符是"l"。

解題思路：

• 使用一個保存到目前為止只出現一次的字符，如果隨著字符流的輸入，出現的相同的字符，則將相同的字符從棧中彈出，如果最后棧空了，則說明沒有出現一次的字符，否則第一個只出現一次的字符則為棧底的元素。
• 使用hashmap來記錄字符出現的次數，利用hashMap的有序性，第一個出現次數為1的則為我們想要的結果

代碼實現：

c++

class Solution
{
private:string s;map<char , int> tempMap;
public://Insert one char from stringstreamvoid Insert(char ch){s += ch;tempMap[ch] ++;}//return the first appearence once char in current stringstreamchar FirstAppearingOnce(){for(int i=0; i < s.size() ; i++){if(tempMap[s[i]] == 1) return s[i];}return '#';}};

運行時間：3ms

占用內存：360k

python

# -*- coding:utf-8 -*-

第54題：

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

解題思路：

• 使用快慢指針，一個指針一次走1步，一個指針一次走2步，如果最后慢指針走完了，沒有出現快慢指針相等的情況下，則是不存在環，否則慢指針會追上快指針;在確定鏈表有環后，我們需要確定環中節點的個數，方法是讓其中一個指針不動，另一個指針每次移動一步，看看最后兩個指針相遇走了多少步；最后在讓兩個指針回到頭結點，快指針先走環中節點的個數步，然后再讓2個指針相同的速度走，則兩個指針相遇的時候，慢指針所指向的節點為環的入口節點。
• 參考：
  時間復雜度為O（n），兩個指針，一個在前面，另一個緊鄰著這個指針，在后面。
  兩個指針同時向前移動，每移動一次，前面的指針的next指向NULL。
  也就是說：訪問過的節點都斷開，最后到達的那個節點一定是尾節點的下一個，
  也就是循環的第一個。
  這時候已經是第二次訪問循環的第一節點了，第一次訪問的時候我們已經讓它指向了NULL，
  所以到這結束。

代碼實現：

c++

方法1：

public class Solution {public ListNode EntryNodeOfLoop(ListNode pHead){ListNode fast = pHead;ListNode slow = pHead;while(fast != null && fast.next !=null){fast = fast.next.next;slow = slow.next;if(fast == slow)break;}if(fast == null || fast.next == null)return null;fast = pHead;while(fast != slow){fast = fast.next;slow = slow.next;}return fast;}
}

方法2

class Solution {
public:ListNode* EntryNodeOfLoop(ListNode* pHead){if (!pHead->next)return NULL;ListNode* previous = pHead; ListNode* front = pHead ->next;while (front){previous->next = NULL;previous = front;front = front->next;}return previous;}
};

運行時間：3ms

占用內存：484k

python

# -*- coding:utf-8 -*-

第55題：

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

解題思路：

• 使用2個指針，一個指針在前，一個指針在后，同時移動兩個指針，當兩個指針相同時，同時刪除兩個指針，然后從新開始遍歷，直至后指針遍歷完整個鏈表。需要注意的是如果是鏈表的尾部元素相同，則需要將前面的鏈表的尾部置NULL。

代碼實現：

c++

class Solution {
public:ListNode* deleteDuplication(ListNode* pHead){if (pHead==NULL)return NULL;if (pHead!=NULL && pHead->next==NULL)return pHead;ListNode* current;if ( pHead->next->val==pHead->val){current=pHead->next->next;while (current != NULL && current->val==pHead->val)current=current->next;return deleteDuplication(current);                     }else {current=pHead->next;pHead->next=deleteDuplication(current);return pHead;}}
};

運行時間：4ms

占用內存：456k

python

# -*- coding:utf-8 -*-

第56題：

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

解題思路：

• 分3種情況進行討論，如果該節點存在右子樹，則下一個節點就是它的右子樹；如果沒有右子樹，且該節點是其父節點的左孩子節點，則下一個就是其父節點；如果該節點沒有右孩子且不是其父節點的左孩子，則下一個節點為其父節點所在的子樹的父節點。

代碼實現：

c++

class Solution {
public:TreeLinkNode* GetNext(TreeLinkNode* pNode){if(pNode == NULL){return NULL;}TreeLinkNode *pNext = NULL;//  如果當前結點有右子樹, 那么其中序遍歷的下一個結點就是其右子樹的最左結點if(pNode->right != NULL){//  找到右子樹的最左孩子pNext = pNode->right;while(pNext->left != NULL){pNext = pNext->left;}}else if(pNode->right == NULL && pNode->next != NULL){TreeLinkNode *pCurrent = pNode;TreeLinkNode *pParent = pNode->next;//  如果當前結點是其父結點的左子結點那么其中序遍歷的下一個結點就是他的父親結點////  如果當前結點是其父結點的右子結點，//  這種情況下其下一個結點應該是當前結點所在的左子樹的根//  因此我們可以順著其父節點一直向上遍歷,//  直到找到一個是它父結點的左子結點的結點while(pParent != NULL && pCurrent == pParent->right){pCurrent = pParent;pParent = pParent->next;}pNext = pParent;}return pNext;}
};

運行時間：5ms

占用內存：376k

python

# -*- coding:utf-8 -*-

第57題：

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

解題思路：

• 從題目的意思可以看出來，當樹的左右子樹相同的時候，則該樹是對稱的。所以可以通過判斷樹的左右子樹是否相同來判斷該樹書否對稱。

代碼實現：

c++

class Solution {
public://判斷2棵子樹是否鏡像相等bool isSymmetrical(TreeNode* pRoot){if(pRoot == NULL){return true;   }return isSymmetricalRecursion(pRoot->left, pRoot->right);}bool isSymmetricalRecursion(TreeNode *pLeft, TreeNode *pRight){if(pLeft == NULL && pRight == NULL){return true;}if(pLeft == NULL || pRight == NULL){return false;}if(pLeft->val != pRight->val){return false;}//  左子樹的左與右子樹的右對稱//  左子樹的右與右子樹的左對稱return isSymmetricalRecursion(pLeft->left, pRight->right) && isSymmetricalRecursion(pLeft->right, pRight->left);}};

運行時間：4ms

占用內存：376k

python

# -*- coding:utf-8 -*-

第58題：

請實現一個函數按照之字形打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推。

解題思路：

• 使用一個二維的數組保存層次遍歷二叉樹每一層的結果，每一層保存為一行，然后在輸出的時候奇數行對數組中的元素反著打出即可。

代碼實現：

c++

class Solution {
public:vector< vector<int> > ans;//只用層次遍歷，將每一層的節點保存在一個二維數組中void LevelOrder(TreeNode *pRoot,int p ){if(pRoot == NULL){return;}if(ans.size( ) == p){ans.push_back(vector<int>( ));}ans[p].push_back(pRoot->val);LevelOrder(pRoot->left, p + 1);  //將左子樹的節點存入數組中LevelOrder(pRoot->right, p + 1);//將右子樹的節點存入數組中}vector< vector<int> > Print(TreeNode* pRoot){LevelOrder(pRoot,0);for(int i = 0; i <ans.size( ); i++){if(i & 1){reverse(ans[i].begin( ), ans[i].end( ));}}return ans;}};

運行時間：5ms

占用內存：504k

python

# -*- coding:utf-8 -*-

第59題：

從上到下按層打印二叉樹，同一層結點從左至右輸出。每一層輸出一行。

解題思路：

• 這個題目和上面的是類似的，只是這次不反著打印，而是在輸出每一層后，輸出一個回車即可。

代碼實現：

c++

class Solution {
public:vector< vector<int> > ans;//只用層次遍歷，將每一層的節點保存在一個二維數組中void LevelOrder(TreeNode *pRoot,int p ){if(pRoot == NULL){return;}//第一次遍歷某一層時，需要創建一組內存if(ans.size( ) == p){ans.push_back(vector<int>( ));}ans[p].push_back(pRoot->val);LevelOrder(pRoot->left, p + 1);  //將左子樹的節點存入數組中LevelOrder(pRoot->right, p + 1);//將右子樹的節點存入數組中}vector< vector<int> > Print(TreeNode* pRoot){LevelOrder(pRoot,0);return ans;}};

運行時間：3ms

占用內存：500k

python

# -*- coding:utf-8 -*-

第60題：

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

解題思路：

1. 對于序列化：使用前序遍歷，遞歸的將二叉樹的值轉化為字符，并且在每次二叉樹的結點
   不為空時，在轉化val所得的字符之后添加一個’ ， '作為分割。對于空節點則以 ‘#’ 代替。
2. 對于反序列化：按照前序順序，遞歸的使用字符串中的字符創建一個二叉樹(特別注意：
   在遞歸時，遞歸函數的參數一定要是char ** ，這樣才能保證每次遞歸后指向字符串的指針會
   隨著遞歸的進行而移動！！！)

代碼實現：

c++

python

# -*- coding:utf-8 -*-
class Solution:def __init__(self):self.flag = -1def Serialize(self, root):# write code hereif not root:return '#,'return str(root.val)+','+self.Serialize(root.left)+self.Serialize(root.right)def Deserialize(self, s):# write code hereself.flag += 1l = s.split(',')if self.flag >= len(s):return Noneroot = Noneif l[self.flag] != '#':root = TreeNode(int(l[self.flag]))root.left = self.Deserialize(s)root.right = self.Deserialize(s)return root

運行時間：24ms

占用內存：5856k