剑指offer【30~39】

echobingo

发布于 2019-12-20 11:58:16

3640

发布于 2019-12-20 11:58:16

文章被收录于专栏：Bingo的深度学习杂货店Bingo的深度学习杂货店

题目链接：

剑指offer 30-39

Python 实现：

30. 包含 min 函数的栈

除了存储数据的栈 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 模拟压入操作；先遍历压入序列，将没有在弹出序列中遇到的数字存入 stack 中；然后再遍历弹出序列，判断是否和 stack 中序列相同。时间复杂度和空间复杂度均为 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:
    # 返回从上到下每个节点值列表，例：[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 个数
            if lens > 0:   # 该层有数
                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，使用一个标记 flag，初始为 1，每过一层翻转 flag 的值。如果 flag = 0，说明某层要从右到左打印，则将该层的打印结果翻转存入结果中。

# -*- 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 个数
            if lens > 0:   # 该层有数
                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 时翻转该层
                ans[-1].reverse()
            flag = not flag
        return ans

33. 二叉搜索树的后序遍历序列

一个二叉搜索树BST满足： max(左子树) < 根节点 < min(右子树)；
对于空数组，应该返回 False。
题目给出的是一个后序遍历，那么序列的最后一个元素就应该是根节点；
从BST的定义出发，遍历整个序列，找到第一个大于根节点的元素k，k以前的元素属于左子树，从k开始到根节点之前的元素属于右子树；
判断右子树是否都比根节点要大，如果不是，直接返回 False。
如果遍历整个序列之后得到的左右子树都满足BST的定义，则递归判断左子树和右子树是否满足BST定义。

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        lens = len(sequence)
        # 空数组返回 False
        if lens == 0:
            return False
        root = sequence[-1]
        # 找到大于 root 的第一个元素
        ind = 0
        while ind < lens - 1:
            if sequence[ind] > root:
                break
            ind += 1
        # 先判断一下右子树是不是都比根大（左子树在上一个循环已经判断过了）
        i = ind + 1
        while i < lens - 1:
            if sequence[i] < root:
                return False
            i += 1
        # 递归判断左右子树是否都满足 BST
        left = right = True  # 这里的初始值都要设置为 True，不然永远不可能为 True
        if ind > 0:  # 防止为空数组
            left = self.VerifySquenceOfBST(sequence[:ind])
        if ind < lens - 1:  # 防止为空数组
            right = self.VerifySquenceOfBST(sequence[ind:-1])
        return left and right

34.二叉树中和为某一值的路径

树的深搜，使用 dfs 回溯法，当到达根且目标值为 0 时找到一条路径。
在递归左右子树的过程中，如果发现提前到达根节点或者目标值为负，要进行剪枝。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    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. 复杂链表的复制

分三步：（1）遍历链表，复制 next 域；（2）遍历链表，复制 random 域（注意一个节点的 random 域可能为 None，因此在复制的过程中要判断是否为空）；（3）拆分两个链表（不能只拆分复制后的链表，会报错，两个都要拆出来）。

# -*- 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 复制 next
        while cur:
            co = RandomListNode(cur.label)
            co.next = cur.next
            cur.next = co
            cur = cur.next.next
        cur = pHead  # 2 复制 random
        while cur:
            if cur.random:  # 一个节点的 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. 二叉搜索树与双向链表

设置一个 pre 指向链表的前一个结点，初始值为 None。使用中序遍历，每次让当前结点左指针连接上一个结点 pre，pre 的右指针连接当前结点。具体做法：

（1）遍历左子树，找到第一个结点，并设置为链表头部；（2）当前结点的左指针连接上一个结点，pre 的右指针连接当前结点，并修改 pre 指向当前结点； （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. 序列化二叉树

这里使用前序遍历对树序列化，然后对应的反序列化也要采取前序遍历才能恢复。在反序列化时，每次从列表中删除一个结点，遇到 "#" 要返回。之后按照前序遍历构造即可。

# -*- 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 中删除一个结点
            if val == "#":
                return None
            root = ListNode(int(val))
            root.left = preorder()
            root.right = preorder()
            return root
            
        li = s.split("!")
        return preorder()

38. 字符串的排列

回溯法，很坑，答案竟然要求返回的 list 的顺序要和参考答案的顺序一致，醉了...（本来一个 set 就搞定了，还需要增加点时间复杂度）

# -*- 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. 数组中出现次数超过一半的数字

这道题可以使用 LeetCode精讲：摩尔投票算法，使得时间复杂度为 O(n)，空间复杂度为 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 记录出现次数多的那个数字
        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 终于过了一遍，大多数题目还是很简单的，但是题目具有代表性，涉及链表、数组、深搜回溯、字符串、数组、数学、位运算、动态规划等。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

文件存储

二叉树

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

文件存储

二叉树

编程算法

登录后参与评论

0 条评论

热度