題目鏈接：
劍指offer 03-09
目錄：
3. 數(shù)組中重復的數(shù)字
4. 二維數(shù)組中的查找
5. 替換空格
6. 從尾到頭打印鏈表
7. 重建二叉樹
8. 二叉樹的下一個結點
9. 用兩個棧實現(xiàn)隊列
Python 實現(xiàn)：
3. 數(shù)組中重復的數(shù)字
利用下標和值的關系，不斷交換。
# -*- coding:utf-8 -*-
class Solution:
# 這里要特別注意~找到任意重復的一個值并賦值到duplication[0]
# 函數(shù)返回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]]: # 找到重復的數(shù)字
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
注意：這道題如果數(shù)據(jù)范圍變?yōu)?[1, n]，那么可以將其轉(zhuǎn)化為使用快慢指針判斷有環(huán)問題，和 Leetcode 【Two Pointers】287. Find the Duplicate Number 一模一樣了。
4. 二維數(shù)組中的查找
從每一行的最后查，從上到下，從右到左。
# -*- 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")
這個才是這道題需要考察的，使用雙指針，但是注意修改字符串中的字符，需要先把字符串轉(zhuǎn)化為列表 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] # 反轉(zhuǎn)，相當于棧的操作
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根節(jié)點
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: # 向上找第一個左鏈接指向的樹包含該節(jié)點的祖先節(jié)點
parent = pNode.next
if parent.left == pNode:
return parent
pNode = pNode.next # 將 pNode 也向上傳
return None # 沒有找到
9. 用兩個棧實現(xiàn)隊列
一個棧 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 中所有的數(shù)存儲到 stack2 中
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop() # stack2 負責出隊列
劍指 offer 終于過了一遍，大多數(shù)題目還是很簡單的，但是題目具有代表性，涉及鏈表、數(shù)組、深搜回溯、字符串、數(shù)組、數(shù)學、位運算、動態(tài)規(guī)劃等。這里做一個總結：
劍指offer【03~09】
劍指offer【10~19】
劍指offer【20~29】
劍指offer【30~39】
劍指offer【40~49】
劍指offer【50~59】
劍指offer【60~68】
