剑指offer【03~09】

# -*- 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

# -*- 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

# -*- 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")

# -*- 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)

# -*- 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]  # 反转，相当于栈的操作

# -*- 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

# -*- 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  # 没有找到

# -*- 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 负责出队列