剑指offer【03~09】
2019-12-16 本文已影响0人
牛奶芝麻
题目链接：
剑指offer 03-09
目录：
3. 数组中重复的数字
4. 二维数组中的查找
5. 替换空格
6. 从尾到头打印链表
7. 重建二叉树
8. 二叉树的下一个结点
9. 用两个栈实现队列
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 终于过了一遍，大多数题目还是很简单的，但是题目具有代表性，涉及链表、数组、深搜回溯、字符串、数组、数学、位运算、动态规划等。这里做一个总结：
剑指offer【03~09】
剑指offer【10~19】
剑指offer【20~29】
剑指offer【30~39】
剑指offer【40~49】
剑指offer【50~59】
剑指offer【60~68】
