题目链接：

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