這里是我算法練習(xí)的一些例子叹括，當(dāng)作思維訓(xùn)練，題目來(lái)主要來(lái)自自劍指offer宵荒，我用python作為實(shí)現(xiàn)語(yǔ)言汁雷，個(gè)別可能沒(méi)有測(cè)試完整的，歡迎通過(guò)簡(jiǎn)書(shū)交流

二維數(shù)組查找

描述：在二維數(shù)組中报咳，每一行按照從左到右遞增摔竿，每一列按照從上到下遞增，輸入一個(gè)這樣的二維數(shù)組(1)少孝，和一個(gè)整數(shù)7,找到這個(gè)整數(shù)返回 True, 否則 False

1 2 8 9

2 4 9 12

4 7 10 13

思路1: 最原始的想法當(dāng)然是遍歷所有的元素，復(fù)雜度是 O(n^2)

思路2: 選取右上角的數(shù)字(其實(shí)左下角也可以)熬苍，然后比較與數(shù)字7的大小稍走，如果等于，查找過(guò)程結(jié)束柴底；如果大于婿脸，就刪除整個(gè)列；如果小于柄驻，就刪除整個(gè)行, 復(fù)雜度O(n)$狐树。

簡(jiǎn)潔易懂，下面是我的python實(shí)現(xiàn)：

def find_num(matrix, num):
    ct = 0
    for cols in matrix[::-1]:
        for col in cols[ct:]:
            if col == num:
                return True
            elif col > num:
                break  # 刪除一列
            else:
                ct += 1  # 刪除一行
                continue

# test
if __name__ == "__main__":
    m = [[1, 2, 3, 6],[2, 4, 7, 8],[8, 9, 10, 11],[9, 12, 13, 15]]
    n = 7
    find_num(m, n)

從尾到頭打印鏈表

鏈表實(shí)現(xiàn)：使用tuple表示一個(gè)Node

思路1: 遍歷鏈表鸿脓，存到棧里面抑钟，然后輸出棧， 但其實(shí)我們不用手動(dòng)實(shí)現(xiàn)棧野哭，直接用遞歸函數(shù)就可以了

貌似過(guò)于簡(jiǎn)單了:)

def print_rlt(lt):  # lt: linked_table
    if lt[1] is not None:
        print_rlt(lt[1])
    print lt[0]


# test
if __name__ == "__main__":
    # a node => (val, next) 
    linked_table = (1, (2, (3, (4, None))))
    print_rlt(linked_table)

思路2:上面的算法可以進(jìn)行優(yōu)化在塔，遞歸函數(shù)在數(shù)據(jù)量大的時(shí)候會(huì)導(dǎo)致棧溢出， 可以用循環(huán)代替拨黔，或者尾遞歸優(yōu)化（就是保證函數(shù)的最后一步是調(diào)用自身）蛔溃，但是python不支持尾遞歸優(yōu)化，而且永遠(yuǎn)不會(huì)支持，java也是不支持的贺待，尾遞歸優(yōu)化貌似只在函數(shù)式語(yǔ)言中支持的比較好徽曲，但神奇的是es6在開(kāi)啟嚴(yán)格模式下是支持的。

重建二叉樹(shù)

描述：根據(jù)二叉樹(shù)的前序遍歷麸塞，中序遍歷 重建整個(gè)二叉樹(shù)

思路：還是遞歸秃臣，前序的第一個(gè)元素就是root, 根據(jù)root我們可以找到中序左子樹(shù)， 中序右子樹(shù)喘垂；然后找到前序左子樹(shù)甜刻，前序右子樹(shù)；遞歸找下去… 還是看代碼吧

def rebuild(preorder, inorder):
    if not preorder:
        return None
    root_val = preorder[0]
    root_index = inorder.index(root_val)

    inorder_left = inorder[:root_index]
    inorder_right = inorder[root_index + 1:]

    preorder_left = preorder[1:len(inorder_left) + 1]
    preorder_right = preorder[len(inorder_left) + 1:]

    left = rebuild(preorder_left, inorder_left)   # 遞歸構(gòu)建左子樹(shù)
    right = rebuild(preorder_right, inorder_right)  # 遞歸構(gòu)建右子樹(shù)
    root = (left, root_val, right)
    return root


# test
if __name__ == "__main__":
    # a node => (left, val, right)
    a = [1, 2, 4, 7, 3, 5, 6, 8]
    b = [4, 7, 2, 1, 5, 3, 8, 6]
    print rebuild(a, b)

用兩個(gè)棧實(shí)現(xiàn)隊(duì)列

描述：用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列

思路：維護(hù)兩個(gè)棧正勒，棧1負(fù)責(zé)插入操作得院，棧2負(fù)責(zé)刪除操作，當(dāng)棧2為空時(shí)章贞，將棧1的元素都推到棧2里面

class Queue(object):
    stack1 = []
    stack2 = []

    def append_tail(self, val):
        self.stack1.append(val)

    def delete_head(self):
        if not self.stack2:
            while self.stack1:
                val = self.stack1.pop()
                self.stack2.append(val)
        if not self.stack2:
            raise IndexError("empty queue")
        self.stack2.pop()


# test
if __name__ == "__main__":
    # stack => []
    q = Queue()
    q.append_tail(1)
    q.append_tail(2)
    q.append_tail(3)
    q.delete_head()
    q.append_tail(4)
    q.delete_head()
    q.delete_head()
    q.delete_head()

    q.delete_head()

旋轉(zhuǎn)數(shù)組的最小數(shù)

描述：旋轉(zhuǎn)數(shù)組([1,2,3,4,5,6,7] => [4,5,6,7, 1,2,3]) 把一個(gè)有序數(shù)組的部分最小值放到后面祥绞，我們的要做的就是根據(jù)這個(gè)旋轉(zhuǎn)數(shù)組找出最小值 1

思路1：從頭遍歷，復(fù)雜度為$O(n)$

思路2: 類似二分查找鸭限，根據(jù)題意旋轉(zhuǎn)數(shù)組的特性(最大值和最小值靠在一起的蜕径，就像這種走勢(shì) /\ )，定義兩個(gè)索引败京，讓這索引1不投涤鳎靠近最大值，索引2不蜕穆螅靠近最小值

def min_num(arr):
    first = 0
    end = len(arr) - 1

    while first != end - 1:
        mid = (end + first) / 2
        if arr[mid] > arr[first]:
            first = mid
        else:
            end = mid

    return arr[end]

# test
if __name__ == "__main__":
    print min_num([4, 5, 6, 7, 1, 2, 3])
    # ==> 1

斐波那契數(shù)

描述：略
思路1:就是遞歸了嘍朴皆，簡(jiǎn)單清晰，不過(guò)效率很低 $O(2^n)$,

def fib(num):
    if num == 0:
        return 0
    elif num == 1:
        return 1
    else:
        return fib(num - 1) + fib(num - 2)


# test
if __name__ == "__main__":
    print fib(0)
    print fib(1)
    print fib(2)
    print fib(3)
    print fib(10)
    print fib(100) # 下午吃飯回來(lái)還沒(méi)完泛粹，放棄了遂铡。。晶姊。

思路2: 用循環(huán)代替扒接， $O(n)$

def fib2(n):
    if n < 2:
        return n

    fib_n = 0

    fib_one = 0
    fib_two = 1
    for i in range(n):
        fib_n = fib_one + fib_two
        fib_one = fib_two
        fib_two = fib_n

    return fib_n


# test
if __name__ == "__main__":
    import time

    b = int(time.time() * 1000000)
    fib2(32)
    print int(time.time() * 1000000) - b
    #=> 77

二進(jìn)制中的1的個(gè)數(shù)

描述: 計(jì)算一個(gè)整數(shù)的二進(jìn)制中的1的個(gè)數(shù)

思路1: 判斷最右一位是不是，記錄们衙，右移一位钾怔；...

def count_one(n):
    count = 0
    while n:
        if n & 1:
            count += 1
        n >>= 1
    return count



# test
if __name__ == "__main__":
    print count_one(1)  # => 1
    print count_one(7346273462734697342374629346234)  # => 53

思路2: 上面的算法不能判斷負(fù)數(shù)的，因?yàn)樨?fù)數(shù)右移砍艾，左邊補(bǔ)的是1蒂教，所以陷入死循環(huán)

我們可以不右移n,而是向左移動(dòng)1（flag）

def count_one_2(n):
    count = 0

    flag = 1

    for i in xrange(64):  因?yàn)閜ython的整數(shù)沒(méi)有位數(shù)限制，我們自定義自己機(jī)器的位數(shù)
        if n & flag:
            count += 1
        flag <<= 1

    return count


# test
if __name__ == "__main__":
    print count_one_2(1)  #==>
    print count_one_2(-1)  #== 64
    print count_one_2(-10)  #==> 62

思路3: 主要是找到一個(gè)這樣的規(guī)律 n & (n-1) = 這個(gè)數(shù)的最右一位1變成變成0脆荷， 舉個(gè)例子:

1100 & (1100 - 1) = 1000; 看到了嗎凝垛，1100 => 1000懊悯，基于此的算法

def count_one_3(n):
    count = 0

    while n:
        count += 1
        n &= (n - 1)

    return count


# test
if __name__ == "__main__":
    print count_one_3(1)
    print count_one_3(10) 
    # print count_one_3(-1)
    # print count_one_3(-10)  # 只能判斷正數(shù)