前言
隨著行業(yè)的發(fā)展，編程能力逐漸成為軟件測試從業(yè)人員的一項基本能力烟零。因此在筆試和面試中常常會有一定量的編碼題宁炫，主要考察以下幾點。
- 基本編碼能力及思維邏輯
- 基本數(shù)據(jù)結(jié)構(gòu)（順序表龙亲、鏈表、隊列、棧鳄炉、二叉樹）
- 基本算法（排序杜耙、查找、遞歸）及時間復雜度
除基本算法之外迎膜，筆試面試中經(jīng)常會考察以下三種思想：
- 哈希
- 遞歸
- 分治
哈希
哈希即Python中的映射類型泥技，字典和集合，鍵值唯一磕仅，查找效率高珊豹，序列（列表、元祖榕订、字符串）的元素查找時間復雜度是O(n)店茶，而字典和集合的查找只需要O(1)。
因此哈希在列表問題中主要有兩種作用：
- 去重
- 優(yōu)化查找效率
列表去重
列表去重在不考慮順序的情況下可以直接使用set()轉(zhuǎn)換（轉(zhuǎn)換后會自動排序）劫恒，需要保持順序可以使用字典構(gòu)建的fromkeys()方法贩幻，利用字典鍵值的唯一性去重。
不考慮順序：
l = [2,1,2,3,4,5,6,6,5,4,3,2,1]
result = list(set(l))
print(result)
運行結(jié)果：
[1, 2, 3, 4, 5, 6]
考慮順序：
l = [2,1,2,3,4,5,6,6,5,4,3,2,1]
result = list({}.fromkeys(l).keys())
print(result)
運行結(jié)果：
[2, 1, 3, 4, 5, 6]
列表分組
一串字母數(shù)字組合的字符串两嘴，找出相同的字母或數(shù)字丛楚，并按照個數(shù)排序。
l = [1,2,3,'a','b','c',1,2,'a','b',3,'c','d','a','b',1]
set1 = set(l)
result = [(item, l.count(item)) for item in set1]
result.sort(key=lambda x:x[1], reverse=True)
print(result)
這里使用哈希的鍵值不重復性憔辫。當然也可以使用python自帶的groupby函數(shù)趣些，代碼如下：
from itertools import groupby
l = [1,2,3,'a','b','c',1,2,'a','b',3,'c','d','a','b',1]
l.sort(key=lambda x: str(x)) # 分組前需要先排序
result = []
for item, group in groupby(l, key=lambda x: str(x)):
result.append((item, len(list(group))))
result.sort(key=lambda x:x[1], reverse=True)
print(result)
海量數(shù)據(jù)top K
對于小數(shù)據(jù)量可以使用排序+切片，而對于海量數(shù)據(jù)贰您，需要考慮服務(wù)器硬件條件坏平。即要考慮時間效率，也要考慮內(nèi)存占用锦亦，同時還要考慮數(shù)據(jù)特征舶替。如果大量的重復數(shù)據(jù)，可以先用哈希進行去重來降低數(shù)據(jù)量杠园。
這里我們使用生成器生成1000萬個隨機整數(shù)顾瞪，求最大的1000個數(shù)，生成隨機數(shù)的代碼如下：
import random
import time
n = 10000 * 1000
k = 1000
print(n)
def gen_num(n):
for i in range(n):
yield random.randint(0, n)
l = gen_num(n)
- 不限內(nèi)存可以直接使用set()去重+排序
start = time.time()
l = list(set(l))
result = l[-k:]
result.reverse()
print(time.time()-start)
1000w個數(shù)據(jù)會全部讀入內(nèi)存抛蚁，set后列表自動為遞增順序玲昧，使用切片取-1000到最后的即為top 1000的數(shù)
- 使用堆排可以節(jié)省一些內(nèi)存
start = time.time()
result = heapq.nlargest(k, l)
print(time.time()-start)
這里是用來Python自帶的堆排庫heapq。使用nlargest(k,l)可以取到l序列篮绿，最大的k個數(shù)。
- 較小內(nèi)存可以分治策略吕漂，使用多線程對數(shù)據(jù)進行分組處理（略）
兩數(shù)之和
l=[1,2,3,4,5,6,7,8] 數(shù)據(jù)不重復亲配，target=6，快速找出數(shù)組中兩個元素之和等于target 的數(shù)組下標。
注意吼虎，不要使用雙重循環(huán)犬钢，暴力加和來和target對比，正確的做法是單層循環(huán)思灰，然后查找target與當前值的差玷犹，是否存在于列表中。
但是由于列表的in查詢時間復雜度是O(n)洒疚，即隱含了一層循環(huán)歹颓，這樣效率其實和雙重循環(huán)是一樣的，都是O(n^2)油湖。
這里就可以使用哈希來優(yōu)化查詢差值是否在列表中操作巍扛，將O(n)降為O(1)，因此總體的效率就會變成O(n^2)->O(n)乏德。
l = [1,2,3,4,5,6,7,8]
set1 = set(list1) # 使用集合已方便查找
target = 6
result = []
for a in list1:
b = target - a
if a < b < target and b in set1: # 在集合中查找,為避免重復撤奸，判斷a為較小的那個值
result.append((list1.index(a), list1.index(b))) # 列表index取下標的操作為O(1)
print(result)
遞歸問題
遞歸是一種循環(huán)調(diào)用自身的函數(shù)『袄ǎ可以用于解決以下高頻問題：
- 階乘
- 斐波那切數(shù)列
- 跳臺階胧瓜、變態(tài)跳臺階
- 快速排序
- 二分查找
- 二叉樹深度遍歷（前序、中序郑什、后序）
- 求二叉樹深度
- 平衡二叉樹判斷
- 判斷兩顆樹是否相同
遞歸是一種分層推導解決問題的方法府喳，是一種非常重要的解決問題的思想。遞歸可快速將問題層級化蹦误，簡單化劫拢，只需要考慮出口和每層的推導即可。
如階乘强胰，要想求n!舱沧，只需要知道前一個數(shù)的階乘(n-1)!，然后乘以n即可偶洋，因此問題可以轉(zhuǎn)為求上一個數(shù)的階乘熟吏，依次向前，直到第一個數(shù)玄窝。
舉個通俗的例子：
A欠你10萬牵寺，但是他沒那么多錢，B欠A 8萬恩脂，C欠B 7萬 C現(xiàn)在有錢帽氓。因此你要逐層找到C，一層一層還錢俩块，最后你才能拿到屬于你的10萬黎休。
編寫遞歸函數(shù)有兩個要點：
- 出口條件浓领，可以不止一個
- 推導方法（已知上一個結(jié)果怎么推導當前結(jié)果）
階乘
求n的階乘
- 出口：n = 1 時，返回1
- 推導：(n-1)層的結(jié)果 * n
代碼如下：
def factorial(n):
if n == 1: # 出口
return 1
return factorial(n-1) * n # 自我調(diào)用求上一個結(jié)果势腮，然后推導本層結(jié)果
也可以簡寫為
factorial = lambda n: 1 if n==1 else factorial(n-1) * n
斐波那切數(shù)列
斐波那切數(shù)列是 1 1 2 3 5 8 ...這樣的序列联贩。前兩個數(shù)為1，后面的數(shù)為前兩個數(shù)之和捎拯。
- 出口：n <= 2泪幌，返回1
- 推導：(n-1)層的結(jié)果 + (n-2)層的結(jié)果
代碼如下：
def fib(n):
if n<=2:
return 1
return fib(n-2) + fib(n-1)
遞歸是一種分層簡化問題的解法，但不一定是效率最高的解法署照，比如斐波那切數(shù)列中祸泪，在求fib(n-2) 和 fib(n-1)時實際上反復求解了兩次fib(n-2)。
可以通過緩存來優(yōu)化效率藤树，代碼如下浴滴。
from functools import lru_cache
@lru_cache()
def fib(n):
if n<=2:
return 1
return fib(n-2) + fib(n-1)
跳臺階、變態(tài)跳臺階
- 跳臺階：一只青蛙岁钓，一次可以跳上1階升略，也可以跳上2階，問跳上n階有多少種跳法屡限。
- 變態(tài)跳臺階：一只青蛙品嚣，一次可以跳上1階，可以一次跳上n階钧大，為跳上n階有多少種跳法翰撑。
這個問題關(guān)鍵是邏輯分析每層的推導過程。
跳臺階實際上就是一個從第二位開始的斐波那切數(shù)列：1 2 3 5 8 13 ...
- 出口：n <= 2啊央，返回n（即1時返回1眶诈，2時返回2）
- 推導：(n-1)層的結(jié)果 + (n-2)層的結(jié)果
代碼如下：
jump1 = lambda n: n if n<=2 else jump1(n-2) + jump1(n-1)
變態(tài)跳臺階只是推導方式不同，每一層的結(jié)果是上一層跳法的2倍瓜饥。
- 出口：n <= 2逝撬，返回n
- 推導：(n-1)層的結(jié)果 * 2
代碼如下：
jump2 = lambda n: n if n<=2 else jump2(n-1) * 2
快速排序
快速排序的是想是選一個基準數(shù)（如第一個數(shù)），將大于該數(shù)和小于該數(shù)的分成兩塊乓土，然后在每一塊中重復執(zhí)行此操作宪潮，直到該塊中只有一個數(shù)，即為有序趣苏。
- 出口：列表長度為1（<2）時狡相，返回列表
- 選擇一個數(shù)，（將小于該數(shù)的序列）排序結(jié)果 + 基準數(shù) + （大于該數(shù)的序列）排序結(jié)果
def quick_sort(l):
length = len(l)
if len(l) <=1:
return l
mid = 0
low_part = [i for i in l[1:] if i < l[mid]]
eq_part = [i for i in l[1:] if i == l[mid]]
high_part = [i for i in l[1:] if i > l[mid]]
return quick_sort(low_part) + eq_part + quick_sort(high_part)
二分查找
二分查找需要序列首先有序食磕。思想是先用序列中間數(shù)和目標值對比尽棕，如果目標值小，則從前半部分（小于中間數(shù)）重復此查找彬伦，否則從后半部分重復此查找滔悉。
- 出口1：中間數(shù)和目標數(shù)相同蟀悦，返回中間數(shù)下標
- 出口2：列表為空，返回未找到
- 推導：
def bin_search(l, n):
if not l:
return None
mid = len(l) // 2
if l[mid] == n:
return mid
if l[mid] > n:
return bin_search(l[:mid])
return bin_search(l[mid+1:])
二叉樹遍歷
二叉樹是非常逞醺遥考的一種數(shù)據(jù)結(jié)構(gòu)。其基本結(jié)構(gòu)就是一個包含數(shù)據(jù)和左右節(jié)點的一種結(jié)構(gòu)询张，使用Python類描述如下：
class Node(object):
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
二叉樹的遍歷分為分層遍歷（廣度優(yōu)先）和深度遍歷（深度優(yōu)先）兩種孙乖，其中深度遍歷又分為前序、中序份氧、后序三種唯袄。
分層遍歷由于每次處理多個節(jié)點，使用循環(huán)解決更加方便一點（也可以是使用遞歸解決）蜗帜。
分層遍歷代碼如下：
def lookup(root):
row = [root]
while(row):
print(row)
row = [kid for item in row for kid in (item.left, item.right) if kid]
深度遍歷
- 出口：節(jié)點為None
- 推導：
- 前序：打印當前節(jié)點-》遍歷左子樹 -》遍歷右子樹
- 中序：遍歷左子樹 -》打印當前節(jié)點-》遍歷右子樹
- 后序：遍歷左子樹 -》遍歷右子樹-》打印當前節(jié)點
以前序為例：
def deep(root):
if root is none:
return
[print(root.data), deep(root.left), deep(root.right)]
二叉樹最大深度
二叉樹最大深度即其左子樹深度和右子樹深度中最大的一個加上1（當前節(jié)點）恋拷。由于二叉樹的每一個左右節(jié)點都是一個二叉樹，這種層層嵌套的結(jié)構(gòu)非常適合使用遞歸求解厅缺。
- 出口：節(jié)點為空蔬顾，深度返回0
- 推導：左子樹深度和右子樹深度中最大的一個 + 1
def max_depth(root):
if not root:
return 0
return max([max_depth(root.left), max_depth(root.right)]) + 1
相等二叉樹判斷
相等二叉樹是只，一個二叉樹湘捎，節(jié)點數(shù)據(jù)相同诀豁，左右子樹也完全相同。由于左右子樹也是一個二叉樹窥妇，因此也可以使用遞歸求解舷胜。
- 出口：最后的節(jié)點都為None時，兩個相等活翩，返回True
- 推導：判斷兩個節(jié)點數(shù)據(jù)是否相等烹骨，左子樹是否相等（遞歸），右子樹是否相等（遞歸）
def is_same_tree(p, q):
if p is None and q is None:
return True
elif p and q:
return p.data == q.data and is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)
平衡二叉樹判斷
平衡二叉樹是指材泄，一個二叉樹的左右子樹的高度差不超過1沮焕。平衡二叉樹的左右子樹也應該是平衡二叉樹，因此這也是一個遞歸問題脸爱。
- 出口：兩個節(jié)點都為None時遇汞，返回True（平衡）
- 判斷左子樹和右子樹深度的差<=1，并且左右子樹都是平衡二叉樹（遞歸）
注：這里需要使用以上求二叉樹深度的方法
def max_depth(root):
if not root:
return 0
return max([max_depth(root.left), max_depth(root.right)]) + 1
def is_balance_tree(root):
if root is None:
return True
return abs(max_depth(root.left)-max_depth(root.right))<=1 and is_balance_tree(root.left) and is_balance_tree(root.right)
其他
字符串統(tǒng)計
str1 = 'abcdaacddceea'
set1 = set(str1)
result = [(char, str1.count(char)) for char in set1]
print(result)
統(tǒng)計重復最多的n個字符
from collections import Counter
c = Counter('abcdaacddceea')
print(c.items())
print(c.most_common(3))
字符串反轉(zhuǎn)
- 簡單字符串反轉(zhuǎn)
Python中字符串反轉(zhuǎn)方式非常多簿废，而且比較高效空入，可以使用反向切片或者reverse實現(xiàn)。
'abcefg'[::-1]
或
''.join(reversed('abcdefg'))
- 包含數(shù)字字母的字符串族檬，僅反轉(zhuǎn)字母
可以通過遍歷判斷歪赢，如果是字母則取其對應反轉(zhuǎn)索引位置的字母，如果是數(shù)字則取當前數(shù)字单料。
a = 'abc123efg'
l = len(a)
r = []
for i,c in enumerate(a):
r.append(c) if c.isdigit() else r.append(a[l-i-1])
print(''.join(r))
判斷括號是否閉合
這是棧使用的一個經(jīng)典示例埋凯，思路為点楼，遇到正括號則入棧，遇到反括號則和棧頂判斷白对，如果匹配則匹配的正括號出棧（完成一對匹配）掠廓，否則打印不匹配，break退出甩恼。
text = "({[({{abc}})][{1}]})2([]){({[]})}[]"
def is_closed(text)
stack = [] # 使用list模擬棧, stack.append()入棧, stack.pop()出棧并獲取棧頂元素
brackets = {')':'(',']':'[','}':'{'} # 使用字典存儲括號的對應關(guān)系, 使用反括號作key方便查詢對應的括號
for char in text:
if char in brackets.values(): # 如果是正括號,入棧
stack.append(char)
elif char in brackets.keys(): # 如果是反括號
if brackets[char] != stack.pop(): # 如果不匹配彈出的棧頂元素
return False
return True
print(is_closed(text))
合并兩個有序列表蟀瞧，并保持有序
常見的解法有兩種：
- 連接 + 排序，時間復雜度度為O((m+n)log2(m+n))
- 兩個隊列根據(jù)大小依次彈出条摸，時間復雜度度約為O(m+n)
依次出隊列的邏輯為：
- 隊列1為空悦污，隊列2不為空，從隊列2彈出一個數(shù)據(jù)
- 隊列2為空钉蒲，隊列1不為空切端，從隊列1彈出一個數(shù)據(jù)
- 兩個都不為空，判斷兩個對隊列頂端哪個小顷啼，從哪個列表彈出一個數(shù)據(jù)
以下為使用Python列表模擬兩個隊列依次彈出的示例踏枣。
由于Python列表尾部彈出list.pop()的的操作效率O(1)，比首部彈出list.pop(0)的操作效率O(n)更高线梗，因此我們先按從大到小排序椰于，最后在執(zhí)行一次反轉(zhuǎn)。
list1 = [1,5,7,9]
list2 = [2,3,4,5, 6,8,10,12,14]
result = []
for i in range(len(list1) + len(list2)):
if list1 and not list2:
result.append(list1.pop())
elif list2 and not list1:
result.append(list2.pop())
else:
result.append(list1.pop()) if list1[-1] > list2[-1] else result.append(list2.pop()) # 彈出頂端大的數(shù)
result.reverse() # 執(zhí)行反轉(zhuǎn)
print(result)
