首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >剑指offer【03~09】

剑指offer【03~09】

作者头像
echobingo
发布2019-12-20 11:56:57
3670
发布2019-12-20 11:56:57
举报
题目链接:
剑指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 终于过了一遍,大多数题目还是很简单的,但是题目具有代表性,涉及链表、数组、深搜回溯、字符串、数组、数学、位运算、动态规划等。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目链接:
  • 剑指offer 03-09
  • Python 实现:
    • 3. 数组中重复的数字
      • 4. 二维数组中的查找
        • 5. 替换空格
          • 6. 从尾到头打印链表
            • 7. 重建二叉树
              • 8. 二叉树的下一个结点
                • 9. 用两个栈实现队列
                领券
                问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档