# 剑指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

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

# -*- 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]
# write code here
ans = []
while listNode:
ans.append(listNode.val)
listNode = listNode.next
return ans[::-1]  # 反转，相当于栈的操作
##### 7. 重建二叉树

# -*- 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. 二叉树的下一个结点

# -*- coding:utf-8 -*-
#     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. 用两个栈实现队列

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

0 条评论

• ### 剑指offer【40~49】

时间复杂度为：插入为 O(logn)，计算中位数为 O(1)；空间复杂度：O(n)。

• ### 剑指offer【20~29】

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

• ### 剑指offer【30~39】

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

• ### pythonpcap原生python读取

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

• ### 利用Python自制扫雷游戏

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

• ### python 匿名代理访问浏览器

import mechanize import cookielib import random