剑指offer【30~39】

题目链接:

剑指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 终于过了一遍,大多数题目还是很简单的,但是题目具有代表性,涉及链表、数组、深搜回溯、字符串、数组、数学、位运算、动态规划等。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指offer【60~68】

    动态规划。令 dp[n][6*n],其中 dp[i][j] 表示前 i 个骰子产生点数 j 的次数。则 dp[-1][1...6*n] 就是每一种点数的次数。点...

    echobingo
  • 剑指offer【50~59】

    排序数组,很明显二分查找,找到第一个 >= k 的元素索引以及第一个 > k 的元素索引,两者相减即为答案,即 lowerBound - upperBound。...

    echobingo
  • 剑指offer【20~29】

    方法1:使用正则表达式,格式为 import re,re.match(r"^...$", s) ,其中 ^ 表示匹配 s 的开始,$ 表示匹配 s 的结尾,.....

    echobingo
  • 编码篇-iOS开发中的奇巧小伎

    最近搜集了自己以前的笔记中的一些小知识点,归为这篇文章,都是亲测有效的奇巧小伎,当你使用到时,你会大呼过瘾的。

    進无尽
  • [Leetcode][python]Balanced Binary Tree/平衡二叉树

    判断一颗二叉树是否是“高度”平衡的。 平衡二叉树的定义是二叉树的任意节点的两颗子树之间的高度差小于等于1。 这实际上是AVL树(维基百科)的定义。

    后端技术漫谈
  • iOS开发-搜索栏UISearchBar和UISearchController

    最近项目中用到了搜索栏,所以在网上搜了一些相关的资料学习了一下,现在记录一下,iOS中的搜索栏实现起来相对简单一点,网上也有很多参考资料,不过靠谱的不是很多...

    roc
  • supervisor源码解析

    上篇文章介绍了supervisor的使用, 今天介绍一下supervisor的源码。 supervisor是python写的。如果你不懂python,我也介绍一...

    若与
  • 一文看尽15种语义分割损失函数(含代码解析)

    https://github.com/shruti-jadon/Semantic-Segmentation-Loss-Functions

    Amusi
  • 236. Lowest Common Ancestor of a Binary Tree

    用户1733462
  • 微信小程序-云开发 数据库http接口封装

    最近学习一下微信小程序的云开发,作为serverless架构,着实省去很多麻烦,省的搞https证书了,也不用写api,但是总是要建后台系统的,云开发的数据库是...

    纷扰D梦

扫码关注云+社区

领取腾讯云代金券