剑指offer【03~09】

题目链接:

剑指offer 03-09


Python 实现:

3. 数组中重复的数字

利用下标和值的关系,不断交换。

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        i = 0
        while i < len(numbers):
            print(numbers)
            if i != numbers[i]:
                if numbers[i] == numbers[numbers[i]]:  # 找到重复的数字
                    duplication[0] = numbers[i]
                    return True
                else:  # 不支持 n[i], n[n[i]] = n[n[i]], n[i] 这种
                    tmp = numbers[numbers[i]]
                    numbers[numbers[i]] = numbers[i]
                    numbers[i] = tmp
            else:
                i += 1
        return False

注意:这道题如果数据范围变为 [1, n],那么可以将其转化为使用快慢指针判断有环问题,和 Leetcode 【Two Pointers】287. Find the Duplicate Number 一模一样了。


4. 二维数组中的查找

从每一行的最后查,从上到下,从右到左。

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if not array or not array[0]:  # [] or [[]]
            return False
        i, j = 0, len(array) - 1
        while i < len(array) and j >= 0:
            if array[i][j] == target:
                return True
            elif array[i][j] < target:
                i += 1
            else:
                j -= 1
        return False

5. 替换空格

前两种也能通过,但是貌似并不是这道题想要考察的。

# -*- coding:utf-8 -*-
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        news = ""
        for i in range(len(s)):
            if s[i] != ' ':
                news += s[i]
            else:
                news += "%20"
        return news
# -*- coding:utf-8 -*-
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        return s.replace(" ", "%20")

这个才是这道题需要考察的,使用双指针,但是注意修改字符串中的字符,需要先把字符串转化为列表 list,最后 "".join(list)。

# -*- coding:utf-8 -*-
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        s = list(s)
        lens = len(s)
        for i in range(lens):
            if s[i] == ' ':
                s.append(' ')
                s.append(' ')
        p1, p2 = lens - 1, len(s) - 1  # 分别指向原字符串末尾和新字符串末尾
        for i in range(p1, -1, -1):
            if s[i] != ' ':
                s[p2] = s[i]
                p2 -= 1
            else:
                s[p2], s[p2-1], s[p2-2] = '0', '2', '%'
                p2 -= 3
        return "".join(s)

6. 从尾到头打印链表

栈(或者递归和头插法也能做)。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # 返回从尾部到头部的列表值序列,例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        ans = []
        while listNode:
            ans.append(listNode.val)
            listNode = listNode.next
        return ans[::-1]  # 反转,相当于栈的操作

7. 重建二叉树

查找前序的根在中序中的位置 ind,将中序划分 [:ind] 和 [ind+1:] 左右两部分递归构造。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if not pre or not tin:
            return None
        i = 0
        while pre[i] not in tin:  # 在 tin 中找到 pre[i]
            i += 1
        root = TreeNode(pre[i])
        ind = tin.index(pre[i])  # 在 tin 中找到 pre[i] 的索引
        root.left = self.reConstructBinaryTree(pre[i+1:], tin[:ind])
        root.right = self.reConstructBinaryTree(pre[i+1:], tin[ind+1:])
        return root

8. 二叉树的下一个结点

分搜索结点 node 有右子树和无右子树的情况。

# -*- coding:utf-8 -*-
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    def GetNext(self, pNode):
        # write code here
        if pNode.right: # 当前结点 node 有右子树
            node = pNode.right
            while node.left:
                node = node.left
            return node  # 右子树的最左子结点
        else:
            while pNode.next:  # 向上找第一个左链接指向的树包含该节点的祖先节点
                parent = pNode.next
                if parent.left == pNode:
                    return parent
                pNode = pNode.next # 将 pNode 也向上传
        return None  # 没有找到

9. 用两个栈实现队列

一个栈 stack1 负责入队列,一个栈 stack2 负责出队列。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    
    def push(self, node):
        # write code here
        self.stack1.append(node)  # stack1 负责入队列
        
    def pop(self):
        # return xx
        if not self.stack2:  # stack2 为空,把 stack1 中所有的数存储到 stack2 中
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()  # stack2 负责出队列

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指offer【40~49】

    时间复杂度为:插入为 O(logn),计算中位数为 O(1);空间复杂度:O(n)。

    echobingo
  • 剑指offer【20~29】

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

    echobingo
  • 剑指offer【30~39】

    除了存储数据的栈 stack,再定义一个最小栈 minstack。minstack 的长度和 stack 保持同步,只不过其是一个递减栈。如 stack = [...

    echobingo
  • 第二章、深入类和对象

    zhang_derek
  • py3_cookbook_notes_02

    jeremyxu
  • pythonpcap原生python读取

    本文代码都由python编写,无需安装第三方拓展库,代码更新:https://github.com/mengdj/python

    py3study
  • BERT代码实现及解读

    $$ \text{Attention}(\boldsymbol{Q},\boldsymbol{K},\boldsymbol{V}) = \text{soft...

    机械视角
  • BERT代码实现及解读

    $$ \text{Attention}(\boldsymbol{Q},\boldsymbol{K},\boldsymbol{V}) = \text{soft...

    机械视角
  • 利用Python自制扫雷游戏

    这次,我们来模仿做一个 XP 上的扫雷,感觉 XP 上的样式比 win7 上的好看多了。

    数据森麟
  • python 匿名代理访问浏览器

    import mechanize import cookielib import random

    用户5760343

扫码关注云+社区

领取腾讯云代金券