劍指offer【30~39】

題目鏈接：

劍指offer 30-39

30. 包含 min 函數(shù)的棧
 31. 棧的壓入软族、彈出序列
 32.1 從上往下打印二叉樹
 32.2 把二叉樹打印成多行
 32.3 按之字形順序打印二叉樹
 33. 二叉搜索樹的后序遍歷序列
 34. 二叉樹中和為某一值的路徑
 35. 復(fù)雜鏈表的復(fù)制
 36. 二叉搜索樹與雙向鏈表
 37. 序列化二叉樹
 38. 字符串的排列
 39. 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字

Python 實現(xiàn)：

30. 包含 min 函數(shù)的棧

除了存儲數(shù)據(jù)的棧 stack，再定義一個最小棧 minstack。minstack 的長度和 stack 保持同步，只不過其是一個遞減棧尺棋。如 stack = [6,7,4,5,3,8]术陶，則 minstack = [6,6,4,4,3,3]燎字。這樣，在 pop 的時候勾笆，同時 pop 兩個棧敌蚜，不會因為刪除最小值而在 minstack 中找不到。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
        self.minstack = []
    
    def push(self, node):
        # write code here
        self.stack.append(node)
        if not self.minstack or node < self.minstack[-1]:
            self.minstack.append(node)
        else:
            self.minstack.append(self.minstack[-1])
            
    def pop(self):
        # write code here
        self.stack.pop()
        self.minstack.pop()
        
    def top(self):
        # write code here
        return self.stack[-1]
        
    def min(self):
        # write code here
        return self.minstack[-1]

31. 棧的壓入匠襟、彈出序列

使用一個棧 stack 模擬壓入操作钝侠；先遍歷壓入序列，將沒有在彈出序列中遇到的數(shù)字存入 stack 中酸舍；然后再遍歷彈出序列帅韧，判斷是否和 stack 中序列相同。時間復(fù)雜度和空間復(fù)雜度均為 O(n)啃勉。

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        stack = []
        j = 0
        for i in range(len(pushV)):
            if pushV[i] != popV[j]:
                stack.append(pushV[i])
            else:
                j += 1
        while stack:
            if stack[-1] != popV[j]:
                return False
            stack.pop()
            j += 1
        return True

32.1 從上往下打印二叉樹

二叉樹的層次遍歷忽舟，使用隊列即可。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections
class Solution:
    # 返回從上到下每個節(jié)點值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        if not root:
            return []
        q = collections.deque()
        ans = []
        q.append(root)
        while q:
            addr = q.popleft()
            ans.append(addr.val)
            if addr.left:
                q.append(addr.left)
            if addr.right:
                q.append(addr.right)
        return ans

32.2 把二叉樹打印成多行

同 32.1叮阅，使用隊列刁品。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections
class Solution:
    # 返回二維列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        ans = []
        if not pRoot:
            return []
        q = collections.deque()
        ans = []
        q.append(pRoot)
        while q:
            lens = len(q)  # 每一層有 lens 個數(shù)
            if lens > 0:   # 該層有數(shù)
                ans.append([])
            while lens > 0:
                addr = q.popleft()
                lens -= 1
                ans[-1].append(addr.val)
                if addr.left:
                    q.append(addr.left)
                if addr.right:
                    q.append(addr.right)
        return ans

32.3 按之字形順序打印二叉樹

同 32.2，使用一個標(biāo)記 flag浩姥，初始為 1挑随，每過一層翻轉(zhuǎn) flag 的值。如果 flag = 0勒叠，說明某層要從右到左打印兜挨，則將該層的打印結(jié)果翻轉(zhuǎn)存入結(jié)果中。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections
class Solution:
    def Print(self, pRoot):
        # write code here
        ans = []
        if not pRoot:
            return []
        q = collections.deque()
        ans = []
        q.append(pRoot)
        flag = 1
        while q:
            lens = len(q)  # 每一層有 lens 個數(shù)
            if lens > 0:   # 該層有數(shù)
                ans.append([])
            while lens > 0:
                addr = q.popleft()
                lens -= 1
                ans[-1].append(addr.val)
                if addr.left:
                    q.append(addr.left)
                if addr.right:
                    q.append(addr.right)
            if flag == 0:  # flag = 0 時翻轉(zhuǎn)該層
                ans[-1].reverse()
            flag = not flag
        return ans

33. 二叉搜索樹的后序遍歷序列

一個二叉搜索樹BST滿足： max(左子樹) < 根節(jié)點 < min(右子樹)眯分；
對于空數(shù)組拌汇，應(yīng)該返回 False。
題目給出的是一個后序遍歷弊决，那么序列的最后一個元素就應(yīng)該是根節(jié)點噪舀；
從BST的定義出發(fā)，遍歷整個序列飘诗，找到第一個大于根節(jié)點的元素k与倡，k以前的元素屬于左子樹，從k開始到根節(jié)點之前的元素屬于右子樹疚察；
判斷右子樹是否都比根節(jié)點要大蒸走，如果不是，直接返回 False貌嫡。
如果遍歷整個序列之后得到的左右子樹都滿足BST的定義比驻，則遞歸判斷左子樹和右子樹是否滿足BST定義。

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        lens = len(sequence)
        # 空數(shù)組返回 False
        if lens == 0:
            return False
        root = sequence[-1]
        # 找到大于 root 的第一個元素
        ind = 0
        while ind < lens - 1:
            if sequence[ind] > root:
                break
            ind += 1
        # 先判斷一下右子樹是不是都比根大（左子樹在上一個循環(huán)已經(jīng)判斷過了）
        i = ind + 1
        while i < lens - 1:
            if sequence[i] < root:
                return False
            i += 1
        # 遞歸判斷左右子樹是否都滿足 BST
        left = right = True  # 這里的初始值都要設(shè)置為 True岛抄，不然永遠(yuǎn)不可能為 True
        if ind > 0:  # 防止為空數(shù)組
            left = self.VerifySquenceOfBST(sequence[:ind])
        if ind < lens - 1:  # 防止為空數(shù)組
            right = self.VerifySquenceOfBST(sequence[ind:-1])
        return left and right

34.二叉樹中和為某一值的路徑

樹的深搜别惦，使用 dfs 回溯法，當(dāng)到達(dá)根且目標(biāo)值為 0 時找到一條路徑夫椭。
在遞歸左右子樹的過程中掸掸，如果發(fā)現(xiàn)提前到達(dá)根節(jié)點或者目標(biāo)值為負(fù)，要進(jìn)行剪枝蹭秋。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二維列表扰付，內(nèi)部每個列表表示找到的路徑
    def FindPath(self, root, expectNumber):
        # write code here
        def dfs(root, expectNumber, path):
            if not root and expectNumber == 0:  # 找到一條路徑
                ans.add(tuple(path))
                return
            if not root or expectNumber < 0:  # 減枝
                return
            dfs(root.left, expectNumber - root.val, path + [root.val]) 
            dfs(root.right, expectNumber - root.val, path + [root.val]) 
        
        ans = set()  # 使用 set 不是 list 防止同一路徑輸出兩次
        if not root:  # 防止 root 為空且 expectNumber 為 0 時輸出 [[]] 而不是 []
            return list(ans)
        dfs(root, expectNumber, [])
        return list(ans)

35. 復(fù)雜鏈表的復(fù)制

分三步：
（1）遍歷鏈表，復(fù)制 next 域仁讨；
（2）遍歷鏈表羽莺，復(fù)制 random 域（注意一個節(jié)點的 random 域可能為 None，因此在復(fù)制的過程中要判斷是否為空）洞豁；
（3）拆分兩個鏈表（不能只拆分復(fù)制后的鏈表盐固，會報錯荒给，兩個都要拆出來）。

# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if not pHead:
            return None
        cur = pHead  # 1 復(fù)制 next
        while cur:
            co = RandomListNode(cur.label)
            co.next = cur.next
            cur.next = co
            cur = cur.next.next
        cur = pHead  # 2 復(fù)制 random
        while cur:
            if cur.random:  # 一個節(jié)點的 random 域可能為空
                cur.next.random = cur.random.next
            cur = cur.next.next
        cur, pCloneHead = pHead, pHead.next # 3 拆分兩鏈表
        while cur.next:
            nex_ = cur.next
            cur.next = nex_.next
            cur = nex_
        return pCloneHead

36. 二叉搜索樹與雙向鏈表

設(shè)置一個 pre 指向鏈表的前一個結(jié)點刁卜，初始值為 None志电。使用中序遍歷，每次讓當(dāng)前結(jié)點左指針連接上一個結(jié)點 pre蛔趴，pre 的右指針連接當(dāng)前結(jié)點挑辆。具體做法：

（1）遍歷左子樹，找到第一個結(jié)點孝情，并設(shè)置為鏈表頭部之拨；
（2）當(dāng)前結(jié)點的左指針連接上一個結(jié)點，pre 的右指針連接當(dāng)前結(jié)點咧叭，并修改 pre 指向當(dāng)前結(jié)點；
（3）遍歷右子樹烁竭。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        def inorder(root):
            if not root:
                return
            inorder(root.left) # 中序遍歷：遍歷左子樹
            if not self.head:  # 鏈表頭部
                self.head = root
            root.left = self.pre  # 連接左指針
            if self.pre:  # 連接右指針
                self.pre.right = root
            self.pre = root  # 修改上一個指針
            inorder(root.right)  # 中序遍歷：遍歷右子樹
        
        self.pre = self.head = None  # 變量要加 self菲茬，如果是 list 則可以不用
        inorder(pRootOfTree)
        return self.head

37. 序列化二叉樹

這里使用前序遍歷對樹序列化，然后對應(yīng)的反序列化也要采取前序遍歷才能恢復(fù)派撕。在反序列化時婉弹，每次從列表中刪除一個結(jié)點，遇到 "#" 要返回终吼。之后按照前序遍歷構(gòu)造即可镀赌。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Serialize(self, root):
        # write code here
        if not root:
            return "#"
        return str(root.val) + "!" + self.Serialize(root.left) + "!" + self.Serialize(root.right)
        
    def Deserialize(self, s):
        # write code here
        def preorder():
            if not li:
                return None
            val = li.pop(0)  # 每次都從 list 中刪除一個結(jié)點
            if val == "#":
                return None
            root = ListNode(int(val))
            root.left = preorder()
            root.right = preorder()
            return root
            
        li = s.split("!")
        return preorder()

38. 字符串的排列

回溯法，很坑际跪，答案竟然要求返回的 list 的順序要和參考答案的順序一致商佛，醉了...（本來一個 set 就搞定了，還需要增加點時間復(fù)雜度）

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        def dfs(k, path):
            if k == lens and path not in ans:
                ans.append(path)
                return
            for i in range(lens):
                if flag[i] == 0:
                    flag[i] = 1
                    dfs(k + 1, path + ss[i])
                    flag[i] = 0
        
        lens = len(ss)
        if lens == 0:
            return []
        flag = [0] * lens
        ans = []
        dfs(0, "")
        return ans

39. 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字

這道題可以使用 LeetCode精講：摩爾投票算法姆打，使得時間復(fù)雜度為 O(n)良姆，空間復(fù)雜度為 O(1)。

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if not numbers:
            return 0
        pre, cnt = numbers[0], 1   # pre 記錄出現(xiàn)次數(shù)多的那個數(shù)字
        for i in range(1, len(numbers)):
            if cnt == 0:
                pre = numbers[i]
                cnt += 1
            elif pre == numbers[i]:
                cnt += 1
            elif pre != numbers[i]:
                cnt -= 1
        # pre 是否超過了一半
        return pre if numbers.count(pre) > len(numbers) // 2 else 0

劍指 offer 終于過了一遍幔戏，大多數(shù)題目還是很簡單的玛追，但是題目具有代表性，涉及鏈表闲延、數(shù)組痊剖、深搜回溯、字符串垒玲、數(shù)組陆馁、數(shù)學(xué)、位運算侍匙、動態(tài)規(guī)劃等氮惯。這里做一個總結(jié)：

劍指offer【03~09】
劍指offer【10~19】
劍指offer【20~29】
劍指offer【30~39】
劍指offer【40~49】
劍指offer【50~59】
劍指offer【60~68】

劍指offer【30~39】

題目鏈接：

目錄：

Python 實現(xiàn)：