前言

隨著行業(yè)的發(fā)展，編程能力逐漸成為軟件測試從業(yè)人員的一項(xiàng)基本能力。因此在筆試和面試中常常會(huì)有一定量的編碼題，主要考察以下幾點(diǎn)。

• 基本編碼能力及思維邏輯
• 基本數(shù)據(jù)結(jié)構(gòu)（順序表、鏈表、隊(duì)列、棧、二叉樹）
• 基本算法（排序、查找、遞歸）及時(shí)間復(fù)雜度

除基本算法之外，筆試面試中經(jīng)常會(huì)考察以下三種思想：

• 哈希
• 遞歸
• 分治

哈希

哈希即Python中的映射類型，字典和集合，鍵值唯一，查找效率高，序列（列表、元祖、字符串）的元素查找時(shí)間復(fù)雜度是O(n)，而字典和集合的查找只需要O(1)。
因此哈希在列表問題中主要有兩種作用：

1. 去重
2. 優(yōu)化查找效率

列表去重

列表去重在不考慮順序的情況下可以直接使用set()轉(zhuǎn)換（轉(zhuǎn)換后會(huì)自動(dòng)排序），需要保持順序可以使用字典構(gòu)建的fromkeys()方法，利用字典鍵值的唯一性去重。
不考慮順序：

l = [2,1,2,3,4,5,6,6,5,4,3,2,1]
result = list(set(l))
print(result)

運(yùn)行結(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)

運(yùn)行結(jié)果：

[2, 1, 3, 4, 5, 6]

列表分組

一串字母數(shù)字組合的字符串，找出相同的字母或數(shù)字，并按照個(gè)數(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)

這里使用哈希的鍵值不重復(fù)性。當(dāng)然也可以使用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

對(duì)于小數(shù)據(jù)量可以使用排序+切片，而對(duì)于海量數(shù)據(jù)，需要考慮服務(wù)器硬件條件。即要考慮時(shí)間效率，也要考慮內(nèi)存占用，同時(shí)還要考慮數(shù)據(jù)特征。如果大量的重復(fù)數(shù)據(jù)，可以先用哈希進(jìn)行去重來降低數(shù)據(jù)量。
這里我們使用生成器生成1000萬個(gè)隨機(jī)整數(shù)，求最大的1000個(gè)數(shù)，生成隨機(jī)數(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個(gè)數(shù)據(jù)會(huì)全部讀入內(nèi)存，set后列表自動(dòng)為遞增順序，使用切片取-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個(gè)數(shù)。

• 較小內(nèi)存可以分治策略，使用多線程對(duì)數(shù)據(jù)進(jìn)行分組處理（略）

兩數(shù)之和

l=[1,2,3,4,5,6,7,8] 數(shù)據(jù)不重復(fù)，target=6，快速找出數(shù)組中兩個(gè)元素之和等于target 的數(shù)組下標(biāo)。
注意，不要使用雙重循環(huán)，暴力加和來和target對(duì)比，正確的做法是單層循環(huán)，然后查找target與當(dāng)前值的差，是否存在于列表中。
但是由于列表的in查詢時(shí)間復(fù)雜度是O(n)，即隱含了一層循環(huán)，這樣效率其實(shí)和雙重循環(huán)是一樣的，都是O(n^2)。
這里就可以使用哈希來優(yōu)化查詢差值是否在列表中操作，將O(n)降為O(1)，因此總體的效率就會(huì)變成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:   # 在集合中查找,為避免重復(fù)，判斷a為較小的那個(gè)值
        result.append((list1.index(a), list1.index(b)))   # 列表index取下標(biāo)的操作為O(1) 
print(result)

遞歸問題

遞歸是一種循環(huán)調(diào)用自身的函數(shù)。可以用于解決以下高頻問題：

• 階乘
• 斐波那切數(shù)列
• 跳臺(tái)階、變態(tài)跳臺(tái)階
• 快速排序
• 二分查找
• 二叉樹深度遍歷（前序、中序、后序）
• 求二叉樹深度
• 平衡二叉樹判斷
• 判斷兩顆樹是否相同

遞歸是一種分層推導(dǎo)解決問題的方法，是一種非常重要的解決問題的思想。遞歸可快速將問題層級(jí)化，簡單化，只需要考慮出口和每層的推導(dǎo)即可。
如階乘，要想求n!，只需要知道前一個(gè)數(shù)的階乘(n-1)!，然后乘以n即可，因此問題可以轉(zhuǎn)為求上一個(gè)數(shù)的階乘，依次向前，直到第一個(gè)數(shù)。
舉個(gè)通俗的例子：
A欠你10萬，但是他沒那么多錢，B欠A 8萬，C欠B 7萬 C現(xiàn)在有錢。因此你要逐層找到C，一層一層還錢，最后你才能拿到屬于你的10萬。

編寫遞歸函數(shù)有兩個(gè)要點(diǎn)：

1. 出口條件，可以不止一個(gè)
2. 推導(dǎo)方法（已知上一個(gè)結(jié)果怎么推導(dǎo)當(dāng)前結(jié)果）

階乘

求n的階乘

• 出口：n = 1 時(shí)，返回1
• 推導(dǎo)：(n-1)層的結(jié)果 * n

代碼如下：

def factorial(n):
    if n == 1:  # 出口
        return 1
    return factorial(n-1) * n   # 自我調(diào)用求上一個(gè)結(jié)果，然后推導(dǎo)本層結(jié)果

也可以簡寫為 factorial = lambda n: 1 if n==1 else factorial(n-1) * n

斐波那切數(shù)列

斐波那切數(shù)列是 1 1 2 3 5 8 ...這樣的序列。前兩個(gè)數(shù)為1，后面的數(shù)為前兩個(gè)數(shù)之和。

• 出口：n <= 2，返回1
• 推導(dǎo)：(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)時(shí)實(shí)際上反復(fù)求解了兩次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)階、變態(tài)跳臺(tái)階

• 跳臺(tái)階：一只青蛙，一次可以跳上1階，也可以跳上2階，問跳上n階有多少種跳法。
• 變態(tài)跳臺(tái)階：一只青蛙，一次可以跳上1階，可以一次跳上n階，為跳上n階有多少種跳法。

這個(gè)問題關(guān)鍵是邏輯分析每層的推導(dǎo)過程。
跳臺(tái)階實(shí)際上就是一個(gè)從第二位開始的斐波那切數(shù)列：1 2 3 5 8 13 ...

• 出口：n <= 2，返回n（即1時(shí)返回1，2時(shí)返回2）
• 推導(dǎo)：(n-1)層的結(jié)果 + (n-2)層的結(jié)果

代碼如下：

jump1 = lambda n: n if n<=2 else jump1(n-2) + jump1(n-1)

變態(tài)跳臺(tái)階只是推導(dǎo)方式不同，每一層的結(jié)果是上一層跳法的2倍。

• 出口：n <= 2，返回n
• 推導(dǎo)：(n-1)層的結(jié)果 * 2

代碼如下：

jump2 = lambda n: n if n<=2 else jump2(n-1)  * 2

快速排序

快速排序的是想是選一個(gè)基準(zhǔn)數(shù)（如第一個(gè)數(shù)），將大于該數(shù)和小于該數(shù)的分成兩塊，然后在每一塊中重復(fù)執(zhí)行此操作，直到該塊中只有一個(gè)數(shù)，即為有序。

• 出口：列表長度為1（<2）時(shí)，返回列表
• 選擇一個(gè)數(shù)，（將小于該數(shù)的序列）排序結(jié)果 + 基準(zhǔn)數(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ù)和目標(biāo)值對(duì)比，如果目標(biāo)值小，則從前半部分（小于中間數(shù)）重復(fù)此查找，否則從后半部分重復(fù)此查找。

• 出口1：中間數(shù)和目標(biāo)數(shù)相同，返回中間數(shù)下標(biāo)
• 出口2：列表為空，返回未找到
• 推導(dǎo)：

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:])

二叉樹遍歷

二叉樹是非常?？嫉囊环N數(shù)據(jù)結(jié)構(gòu)。其基本結(jié)構(gòu)就是一個(gè)包含數(shù)據(jù)和左右節(jié)點(diǎn)的一種結(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)先）兩種，其中深度遍歷又分為前序、中序、后序三種。

分層遍歷由于每次處理多個(gè)節(jié)點(diǎn)，使用循環(huán)解決更加方便一點(diǎ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é)點(diǎn)為None
• 推導(dǎo)：
  • 前序：打印當(dāng)前節(jié)點(diǎn)-》遍歷左子樹 -》遍歷右子樹
  • 中序：遍歷左子樹 -》打印當(dāng)前節(jié)點(diǎn)-》遍歷右子樹
  • 后序：遍歷左子樹 -》遍歷右子樹-》打印當(dāng)前節(jié)點(diǎn)

以前序?yàn)槔?/p>

def deep(root):
    if root is none:
        return
    [print(root.data), deep(root.left), deep(root.right)]

二叉樹最大深度

二叉樹最大深度即其左子樹深度和右子樹深度中最大的一個(gè)加上1（當(dāng)前節(jié)點(diǎn)）。由于二叉樹的每一個(gè)左右節(jié)點(diǎn)都是一個(gè)二叉樹，這種層層嵌套的結(jié)構(gòu)非常適合使用遞歸求解。

• 出口：節(jié)點(diǎn)為空，深度返回0
• 推導(dǎo)：左子樹深度和右子樹深度中最大的一個(gè) + 1

def max_depth(root):
    if not root:
        return 0
    return max([max_depth(root.left), max_depth(root.right)]) + 1

相等二叉樹判斷

相等二叉樹是只，一個(gè)二叉樹，節(jié)點(diǎn)數(shù)據(jù)相同，左右子樹也完全相同。由于左右子樹也是一個(gè)二叉樹，因此也可以使用遞歸求解。

• 出口：最后的節(jié)點(diǎn)都為None時(shí)，兩個(gè)相等，返回True
• 推導(dǎo)：判斷兩個(gè)節(jié)點(diǎn)數(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)

平衡二叉樹判斷

平衡二叉樹是指，一個(gè)二叉樹的左右子樹的高度差不超過1。平衡二叉樹的左右子樹也應(yīng)該是平衡二叉樹，因此這也是一個(gè)遞歸問題。

• 出口：兩個(gè)節(jié)點(diǎn)都為None時(shí)，返回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)計(jì)

str1 = 'abcdaacddceea'
set1 = set(str1)
result = [(char, str1.count(char)) for char in set1]
print(result)

統(tǒng)計(jì)重復(fù)最多的n個(gè)字符

from collections import Counter
c = Counter('abcdaacddceea')
print(c.items())
print(c.most_common(3))

字符串反轉(zhuǎn)

• 簡單字符串反轉(zhuǎn)
  Python中字符串反轉(zhuǎn)方式非常多，而且比較高效，可以使用反向切片或者reverse實(shí)現(xiàn)。

'abcefg'[::-1]

或

''.join(reversed('abcdefg'))

• 包含數(shù)字字母的字符串，僅反轉(zhuǎn)字母
  可以通過遍歷判斷，如果是字母則取其對(duì)應(yīng)反轉(zhuǎn)索引位置的字母，如果是數(shù)字則取當(dāng)前數(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))

判斷括號(hào)是否閉合

這是棧使用的一個(gè)經(jīng)典示例，思路為，遇到正括號(hào)則入棧，遇到反括號(hào)則和棧頂判斷，如果匹配則匹配的正括號(hào)出棧（完成一對(duì)匹配），否則打印不匹配，break退出。

text = "({[({{abc}})][{1}]})2([]){({[]})}[]"

def is_closed(text)
    stack = []  # 使用list模擬棧, stack.append()入棧, stack.pop()出棧并獲取棧頂元素
    brackets = {')':'(',']':'[','}':'{'}  # 使用字典存儲(chǔ)括號(hào)的對(duì)應(yīng)關(guān)系, 使用反括號(hào)作key方便查詢對(duì)應(yīng)的括號(hào)
    for char in text:
        if char in brackets.values():   # 如果是正括號(hào),入棧
            stack.append(char)
        elif char in brackets.keys():  # 如果是反括號(hào)
            if brackets[char] != stack.pop():  # 如果不匹配彈出的棧頂元素
                return False
    return True

print(is_closed(text))

合并兩個(gè)有序列表，并保持有序

常見的解法有兩種：

• 連接 + 排序，時(shí)間復(fù)雜度度為O((m+n)log2(m+n))
• 兩個(gè)隊(duì)列根據(jù)大小依次彈出，時(shí)間復(fù)雜度度約為O(m+n)

依次出隊(duì)列的邏輯為：

• 隊(duì)列1為空，隊(duì)列2不為空，從隊(duì)列2彈出一個(gè)數(shù)據(jù)
• 隊(duì)列2為空，隊(duì)列1不為空，從隊(duì)列1彈出一個(gè)數(shù)據(jù)
• 兩個(gè)都不為空，判斷兩個(gè)對(duì)隊(duì)列頂端哪個(gè)小，從哪個(gè)列表彈出一個(gè)數(shù)據(jù)

以下為使用Python列表模擬兩個(gè)隊(duì)列依次彈出的示例。
由于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)