題目鏈接：
劍指offer 50-59
目錄：
50. 第一個只出現(xiàn)一次的字符位置
51. 數(shù)組中的逆序?qū)?/a>
52. 兩個鏈表的第一個公共結(jié)點
53. 數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)
54. 二叉查找樹的第 K 個結(jié)點
55.1 二叉樹的深度
55.2 平衡二叉樹
56. 數(shù)組中只出現(xiàn)一次的數(shù)字
57.1 和為 S 的兩個數(shù)字
57.2 和為 S 的連續(xù)正數(shù)序列
58.1 翻轉(zhuǎn)單詞順序列
58.2 左旋轉(zhuǎn)字符串
59. 滑動窗口的最大值
Python 實現(xiàn)：
50. 第一個只出現(xiàn)一次的字符位置
使用大小為 256 的數(shù)組記錄每個字符出現(xiàn)的次數(shù)。遍歷兩遍即可。
# -*- coding:utf-8 -*-
class Solution:
def FirstNotRepeatingChar(self, s):
# write code here
dic = [0] * 256
for i in range(len(s)):
dic[ord(s[i])] += 1
for i in range(len(s)):
if dic[ord(s[i])] == 1:
return i
return -1
51. 數(shù)組中的逆序?qū)?/a>
- 常規(guī)方法 O(n^2)，先 pass。可以使用歸并排序的思想，在歸并的過程中統(tǒng)計逆序?qū)Φ臄?shù)量。
- 比如在歸并過程中，left = [1,3,5,7,9]，right = [2,4,6,8,10]，發(fā)現(xiàn) 3 > 2，則 left[1:] 的所有數(shù)都比 right[0] 大，就累加逆序?qū)?shù)量，后面的也同理。
- 詳情可以參考博客 劍指Offer（三十五）：數(shù)組中的逆序?qū)?/a>
- 這樣時間復(fù)雜度為 O(nlogn)，空間復(fù)雜度為 O(n)。但是 Python 卡了一下時間，AC 了 75%。
# -*- coding:utf-8 -*-
class Solution:
def InversePairs(self, data):
# write code here
self.ans = 0 # 逆序?qū)?shù)量
self.mergeSort(data) # 歸并排序
return self.ans % 1000000007
def mergeSort(self, nums):
# 遞歸過程
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = self.mergeSort(nums[:mid])
right = self.mergeSort(nums[mid:])
return self.merge(left, right)
# 歸并過程 + 統(tǒng)計逆序?qū)?shù)量
def merge(self, left, right):
result = [] # 保存歸并后的結(jié)果
i = j = 0
left_len = len(left)
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else: # left[i] > right[j]
self.ans += (left_len - i) # 核心：說明 nums[i:] 都大于 nums[j]
result.append(right[j])
j += 1
result = result + left[i:] + right[j:] # 剩余的元素直接添加到末尾
return result
52. 兩個鏈表的第一個公共結(jié)點
- 設(shè) A 的長度為 a + c，B 的長度為 b + c，其中 c 為尾部公共部分長度，可知 a + c + b = b + c + a。
- 當訪問鏈表 A 的指針 L1 訪問到鏈表尾部時，令它從鏈表 B 的頭部重新開始訪問鏈表 B；同樣地，當訪問鏈表 B 的指針 L2 訪問到鏈表尾部時，令它從鏈表 A 的頭部重新開始訪問鏈表 A。這樣就能控制 L1 和 L2 能同時訪問到公共結(jié)點。即 L1 總共走了 (a + c) + b，L2 總共走了 (b + c) + a。
- 這樣，鏈表 A 和鏈表 B 都走了 a + b + c 步，時間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(1)。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
# write code here
l1, l2 = pHead1, pHead2
while l1 != l2:
l1 = l1.next if l1 != None else pHead2
l2 = l2.next if l2 != None else pHead1
return l1 # 或者 l2
53. 數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)
排序數(shù)組，很明顯二分查找，找到第一個 >= k 的元素索引以及第一個 > k 的元素索引，兩者相減即為答案，即 lowerBound - upperBound。時間復(fù)雜度為 O(logn)，空間復(fù)雜度為 O(1)。
# -*- coding:utf-8 -*-
class Solution:
def GetNumberOfK(self, data, k):
# write code here
if not data:
return 0
lo, hi = 0, len(data) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if data[mid] >= k:
hi = mid
elif data[mid] < k:
lo = mid + 1
ind1 = lo if data[lo] >= k else len(data) # >=k 的第一個元素
lo, hi = 0, len(data) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if data[mid] > k:
hi = mid
elif data[mid] <= k:
lo = mid + 1
ind2 = lo if data[lo] > k else len(data) # # >k 的第一個元素
return ind2 - ind1 # 相減即為答案
更簡潔的，可以使用 Python 的 bisect 模塊中的函數(shù)實現(xiàn)?？梢詤⒖疾┛停?a href="http://m.itdecent.cn/p/741c3d29a1ff" target="_blank">二分查找及其變形與Python的bisect模塊的關(guān)系。
# -*- coding:utf-8 -*-
import bisect
class Solution:
def GetNumberOfK(self, data, k):
# write code here
return bisect.bisect_right(data, k) - bisect.bisect_left(data, k)
54. 二叉查找樹的第 K 個結(jié)點
中序遍歷，找到第 k 個數(shù)即可。
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回對應(yīng)節(jié)點TreeNode
def __init__(self):
self.cnt = 0
def KthNode(self, pRoot, k):
# write code here
if not pRoot or self.cnt >= k: # self.cnt >= k 剪枝
return None
left = self.KthNode(pRoot.left, k)
if left:
return left
self.cnt += 1
if self.cnt == k:
return pRoot
right = self.KthNode(pRoot.right, k)
if right:
return right
return None
55.1 二叉樹的深度
遞歸左右子樹找最大高度。注意：根的高度為 1。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def TreeDepth(self, pRoot):
# write code here
if not pRoot:
return 0
return max(self.TreeDepth(pRoot.left), self.TreeDepth(pRoot.right)) + 1
55.2 平衡二叉樹
平衡二叉樹（AVL）的左右子樹的高度差不超過 1，因此引入求高度的函數(shù)。并且，判斷該樹的每個結(jié)點的左右子樹是否也滿足 AVL 的定義。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def IsBalanced_Solution(self, pRoot):
# write code here
if not pRoot:
return True
if abs(self.TreeDepth(pRoot.left) - self.TreeDepth(pRoot.right)) > 1: # 不滿足 AVL 的定義
return False
return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
def TreeDepth(self, pRoot):
if not pRoot:
return 0
return max(self.TreeDepth(pRoot.left), self.TreeDepth(pRoot.right)) + 1
改進：自頂向下在調(diào)用求樹的高度的函數(shù)時，有很多重復(fù)的操作。因此，可以使用自底向上的方法，一邊計算樹的高度，一邊判斷是否是 AVL 樹。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def IsBalanced_Solution(self, pRoot):
# write code here
self.isBalance = True
self.TreeDepth(pRoot) # 在求樹的高度過程中判斷 AVL
return self.isBalance
def TreeDepth(self, pRoot):
if not pRoot:
return 0
left = self.TreeDepth(pRoot.left)
right = self.TreeDepth(pRoot.right)
if abs(left - right) > 1: # 不滿足 AVL 定義，修改 self.isBalance 的值
self.isBalance = False
return max(left, right) + 1
56. 數(shù)組中只出現(xiàn)一次的數(shù)字
如果只出現(xiàn)一次的數(shù)字只有一個，很好做，就是全部異或即可。但是，只出現(xiàn)一次的數(shù)字有兩個怎么做呢？
- 假設(shè)只出現(xiàn)一次的數(shù)字為 x 和 y，首先，還是先全部異或得到一個結(jié)果 xor，則 x ^ y = xor（相同的數(shù)字異或后抵消為 0）
- 因為 x 和 y 肯定不同，那么它們的二進制表示中肯定有一位一個是 0， 一個是 1。比如 x = 6 (110)，y = 4 (100)，xor = 2 (10)，則我們對 xor 從后往前找到倒數(shù)第一個 1 的位置 bits（倒數(shù)第 2 位），則以這個 1 為界限，x 和 y 的倒數(shù)第 2 位肯定是不同。
- 因此，對原來的數(shù)組重新異或，將 bits 位置為 1 的全部異或，bits 為 0 的全部異或，就是最終的兩個返回的結(jié)果。
# -*- coding:utf-8 -*-
class Solution:
# 返回[a,b] 其中ab是出現(xiàn)一次的兩個數(shù)字
def FindNumsAppearOnce(self, array):
# write code here
xor = 0
ans = [0, 0]
for num in array:
xor ^= num
bits = 0 # 找到倒數(shù)第 i 位為 1
while xor & 1 << bits == 0:
bits += 1
for num in array:
if num >> bits & 1 == 1: # num 的倒數(shù)第 i 位為 1
ans[0] ^= num
else: # num 的倒數(shù)第 i 位為 0
ans[1] ^= num
return ans
57.1 和為 S 的兩個數(shù)字
雙指針指向首尾，往中間走，碰到第一對和為 S 的就是答案。
# -*- coding:utf-8 -*-
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
lo, hi = 0, len(array) - 1
while lo < hi: # 不能指向相同的數(shù)字
if array[lo] + array[hi] == tsum:
return [array[lo], array[hi]]
elif array[lo] + array[hi] < tsum:
lo += 1
else:
hi -= 1
return []
57.2 和為 S 的連續(xù)正數(shù)序列
經(jīng)典的滑動窗口例題，只不過該題的窗口大小不確定。用一個遍歷 left 記錄窗口左側(cè)的值，window_sum 將窗口中數(shù)進行累加。當發(fā)現(xiàn) window_sum >= S 時，相等時輸出結(jié)果，更新 left 和 window_sum。
# -*- coding:utf-8 -*-
class Solution:
def FindContinuousSequence(self, tsum):
# write code here
if tsum <= 1: # 特殊情況
return []
ans = []
left, window_sum = 1, 0 # left 記錄窗口左界
for i in range(1, (tsum + 1) // 2 + 1): # 窗口中至少兩個數(shù)
window_sum += i # 窗口中的累加和
while window_sum >= tsum:
if window_sum == tsum: # 輸出一組結(jié)果
ans.append([j for j in range(left, i + 1)])
window_sum -= left # 修改窗口中的累加和
left += 1 # 修改窗口的左界
return ans
58.1 翻轉(zhuǎn)單詞順序列
如果要求空間復(fù)雜度為 O(1)，即只能使用字符串本身，該怎么操作呢？
- 如 s = "I am a student."，先將各個單詞翻轉(zhuǎn)，得 s = ".tneduts a ma I"；
- 再將整個字符串翻轉(zhuǎn)，得 s = "student. a am I"
這樣就可以在字符串本身上做修改，使得空間復(fù)雜度為 O(1) 了。
注意：但是使用 Python 實現(xiàn)得話，由于不能修改字符串本身，所以還是先要將字符串轉(zhuǎn)化為列表。但是如果使用 C++ 的字符數(shù)組，就不用開辟空間了。
# -*- coding:utf-8 -*-
class Solution:
def ReverseSentence(self, s):
# write code here
def reverseWord(s, i, j):
while i < j:
s[i], s[j] = s[j], s[i]
i += 1
j -= 1
s = list(s) # python 中 s 不能修改，先轉(zhuǎn)化為 list
start = 0 # start 指向當前單詞的起始位置
lens = len(s)
for i in range(lens + 1):
if i == lens or s[i] == ' ':
reverseWord(s, start, i - 1) # 先翻轉(zhuǎn)每個單詞
start = i + 1 # 下一個單詞的起始位置
reverseWord(s, 0, lens - 1) # 再將整個句子翻轉(zhuǎn)
return "".join(s)
58.2 左旋轉(zhuǎn)字符串
如果也不能使用空間，怎么做呢？參考上面的 58.1，如 s = "abcXYZdef"，n = 3，先將 "abc" 和 "XYZdef" 分別翻轉(zhuǎn)，得到 "cbafedZYX"，然后再把整個字符串翻轉(zhuǎn)得到 "XYZdefabc"。這樣就可以空間復(fù)雜度為 O(1) 了。
# -*- coding:utf-8 -*-
class Solution:
def LeftRotateString(self, s, n):
# write code here
def reverseWord(s, i, j):
while i < j:
s[i], s[j] = s[j], s[i]
i += 1
j -= 1
if not s:
return ""
s = list(s)
lens = len(s)
n %= lens # 循環(huán)左移
reverseWord(s, 0, n - 1) # 先將前 n 個字符翻轉(zhuǎn)
reverseWord(s, n, lens - 1) # 再將后面的字符翻轉(zhuǎn)
reverseWord(s, 0, lens - 1) # 最后將整個字符串翻轉(zhuǎn)
return "".join(s) # 再轉(zhuǎn)化回字符串
59. 滑動窗口的最大值
使用雙向遞減隊列，隊列中始終維護的是窗口中的遞減值。
- 如果隊列的大小達到了 size，則應(yīng)該把隊列最前面的數(shù)字刪除掉。
- 如果從最右邊加入了一個較大的數(shù)字，需要從右開始退隊列（while 循環(huán)），使得隊列是單調(diào)遞減的。
- 由于雙向隊列中，從左邊出隊列和從右邊出隊列的操作時間復(fù)雜度均為 O(1)，因此該算法的時間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(n)。
例如，num = [2,3,4,2,6,2,5,1]，size = 3，雙向隊列的變化情況為 dq： [2] -> [3] -> [4] -> [4,2] -> [6] (6 比 2 和 4 都大) -> [6,2] -> [6,5] (5 比 2 大) -> [5,1] (6 超出窗口，從隊列首部出隊)。
# -*- coding:utf-8 -*-
import collections
class Solution:
def maxInWindows(self, num, size):
# write code here
if size > len(num) or size < 1:
return []
dq = collections.deque() # [num[i], i]
ans = []
for i in range(len(num)):
if dq and i - dq[0][1] >= size:
dq.popleft() # O(1)
while dq and num[i] > dq[-1][0]: # 從后往前刪除比 num[i] 大的數(shù)
dq.pop() # O(1)
dq.append([num[i], i])
if i >= size - 1:
ans.append(dq[0][0]) # 隊列首部始終最大
return ans
劍指 offer 終于過了一遍，大多數(shù)題目還是很簡單的，但是題目具有代表性，涉及鏈表、數(shù)組、深搜回溯、字符串、數(shù)組、數(shù)學(xué)、位運算、動態(tài)規(guī)劃等。這里做一個總結(jié)：
劍指offer【03~09】
劍指offer【10~19】
劍指offer【20~29】
劍指offer【30~39】
劍指offer【40~49】
劍指offer【50~59】
劍指offer【60~68】
