測(cè)試開(kāi)發(fā)的技能之一就是需要掌握一些開(kāi)發(fā)的語(yǔ)言，而針對(duì)于考察開(kāi)發(fā)語(yǔ)言，業(yè)界內(nèi)比較容易采用的方式就是考察各種算法。在此做一個(gè)簡(jiǎn)單的總結(jié)（最近比較喜歡玩Python，所以都是以Python為例子，其它的語(yǔ)言類推。）

• 冒泡排序
• 遞歸
• 二叉樹(shù)遍歷算法
• 字符串的倒序輸出

冒泡排序

冒泡排序算法的運(yùn)作如下：（從后往前）
比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

實(shí)例：對(duì)列表 [2, 8, 4, 7, 5, 9, 0]進(jìn)行冒泡排序

def bubble(bubbleList):
    listLength = len(bubbleList)
    while listLength > 0:
        for i in range(listLength - 1):
            if bubbleList[i] > bubbleList[i + 1]:
                bubbleList[i] = bubbleList[i] + bubbleList[i + 1]
                bubbleList[i + 1] = bubbleList[i] - bubbleList[i + 1]
                bubbleList[i] = bubbleList[i] - bubbleList[i + 1]
        listLength -= 1
    print(bubbleList)


if __name__ == '__main__':
    bubbleList = [2, 8, 4, 7, 5, 9, 0]
    bubble(bubbleList)

遞歸

遞歸過(guò)程一般通過(guò)函數(shù)或子過(guò)程來(lái)實(shí)現(xiàn)。遞歸方法：在函數(shù)或子過(guò)程的內(nèi)部，直接或者間接地調(diào)用自己的算法。

遞歸算法流程

實(shí)例：要計(jì)算1-10的10位數(shù)字的乘積，直觀的算法是123456789，利用遞歸則思路是循環(huán)執(zhí)行n*n-1,直到n=1時(shí)

def recursion(n):
    if n == 1:
        return 1        
    else:
        return n * recursion(n-1)

print(recursion(10))

二叉樹(shù)遍歷算法
從二叉樹(shù)的遞歸定義可知，一棵非空的二叉樹(shù)由根結(jié)點(diǎn)及左、右子樹(shù)這三個(gè)基本部分組成。因此，在任一給定結(jié)點(diǎn)上，可以按某種次序執(zhí)行三個(gè)操作：
⑴訪問(wèn)結(jié)點(diǎn)本身（N），
⑵遍歷該結(jié)點(diǎn)的左子樹(shù)（L），
⑶遍歷該結(jié)點(diǎn)的右子樹(shù)（R）。
以上三種操作有六種執(zhí)行次序：
NLR、LNR、LRN、NRL、RNL、RLN。

二叉樹(shù).png

二叉樹(shù)的節(jié)點(diǎn)表示可以使用

class Node:  
    def __init__(self,value=None,left=None,right=None):  
        self.value=value  
        self.left=left  
        self.right=right  

前序遍歷：根節(jié)點(diǎn)->左子樹(shù)->右子樹(shù)
中序遍歷：左子樹(shù)->根節(jié)點(diǎn)->右子樹(shù)
后序遍歷：左子樹(shù)->右子樹(shù)->根節(jié)點(diǎn)

def preTraverse(root):  
    if root==None:  
        return  
    print(root.value)  
    preTraverse(root.left)  
    preTraverse(root.right)  
  
def midTraverse(root):  
    if root==None:  
        return  
    midTraverse(root.left)  
    print(root.value)  
    midTraverse(root.right)  
  
def afterTraverse(root):  
    if root==None:  
        return  
    afterTraverse(root.left)  
    afterTraverse(root.right)  
    print(root.value) 

實(shí)例：求二叉樹(shù)深度和寬度
求深度用遞歸；求寬度用隊(duì)列，然后把每層的寬度求出來(lái)，找出最大的就是二叉樹(shù)的寬度

import queue  
  
class Node:  
    def __init__(self,value=None,left=None,right=None):  
        self.value=value  
        self.left=left  
        self.right=right  
  
def treeDepth(tree):  
    if tree==None:  
        return 0  
    leftDepth=treeDepth(tree.left)  
    rightDepth=treeDepth(tree.right)  
    if leftDepth>rightDepth:  
        return leftDepth+1  
    if rightDepth>=leftDepth:  
        return rightDepth+1  
  
def treeWidth(tree):  
    curwidth=1  
    maxwidth=0  
    q=queue.Queue()  
    q.put(tree)  
    while not q.empty():  
        n=curwidth  
        for i in range(n):  
            tmp=q.get()  
            curwidth-=1  
            if tmp.left:  
                q.put(tmp.left)  
                curwidth+=1  
            if tmp.right:  
                q.put(tmp.right)  
                curwidth+=1  
        if curwidth>maxwidth:  
            maxwidth=curwidth  
    return maxwidth  
  
if __name__=='__main__':  
    root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))  
    depth=treeDepth(root)  
    width=treeWidth(root)  
    print('depth:',depth)  
    print('width:',width)  

字符串倒序輸出

思路一：索引的方法

strA = input("請(qǐng)輸入需要翻轉(zhuǎn)的字符串：")
print (strA[::-1])

思路二：借組列表進(jìn)行翻轉(zhuǎn)

strA = input("請(qǐng)輸入需要翻轉(zhuǎn)的字符串：")
order = []
for i in strA:
  order.append(i)
order.reverse()   #將列表反轉(zhuǎn)

print (''.join(order))   #將list轉(zhuǎn)換成字符串

后續(xù)還有的話會(huì)繼續(xù)添加的。