算法1

这里是我算法练习的一些例子，当作思维训练，题目来主要来自自剑指offer，我用python作为实现语言，个别可能没有测试完整的，欢迎通过简书交流

二维数组查找

描述：在二维数组中，每一行按照从左到右递增，每一列按照从上到下递增，输入一个这样的二维数组(1)，和一个整数7,找到这个整数返回 True, 否则 False

1 2 8 9

2 4 9 12

4 7 10 13

思路1: 最原始的想法当然是遍历所有的元素，复杂度是 O(n^2)

思路2: 选取右上角的数字(其实左下角也可以)，然后比较与数字7的大小，如果等于，查找过程结束；如果大于，就删除整个列；如果小于，就删除整个行, 复杂度O(n)$。

简洁易懂，下面是我的python实现：

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)

从尾到头打印链表

链表实现：使用tuple表示一个Node

思路1: 遍历链表，存到栈里面，然后输出栈， 但其实我们不用手动实现栈，直接用递归函数就可以了

貌似过于简单了:)

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:上面的算法可以进行优化，递归函数在数据量大的时候会导致栈溢出， 可以用循环代替，或者尾递归优化（就是保证函数的最后一步是调用自身），但是python不支持尾递归优化，而且永远不会支持，java也是不支持的，尾递归优化貌似只在函数式语言中支持的比较好，但神奇的是es6在开启严格模式下是支持的。

重建二叉树

描述：根据二叉树的前序遍历，中序遍历 重建整个二叉树

思路：还是递归，前序的第一个元素就是root, 根据root我们可以找到中序左子树， 中序右子树；然后找到前序左子树，前序右子树；递归找下去… 还是看代码吧

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)   # 递归构建左子树
    right = rebuild(preorder_right, inorder_right)  # 递归构建右子树
    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)

用两个栈实现队列

描述：用两个栈实现一个队列

思路：维护两个栈，栈1负责插入操作，栈2负责删除操作，当栈2为空时，将栈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()

旋转数组的最小数

描述：旋转数组([1,2,3,4,5,6,7] => [4,5,6,7, 1,2,3]) 把一个有序数组的部分最小值放到后面，我们的要做的就是根据这个旋转数组找出最小值 1

思路1：从头遍历，复杂度为$O(n)$

思路2: 类似二分查找，根据题意旋转数组的特性(最大值和最小值靠在一起的，就像这种走势 /\ )，定义两个索引，让这索引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

斐波那契数

描述：略
思路1:就是递归了喽，简单清晰，不过效率很低 $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) # 下午吃饭回来还没完，放弃了。。。

思路2: 用循环代替， $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

二进制中的1的个数

描述: 计算一个整数的二进制中的1的个数

思路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: 上面的算法不能判断负数的，因为负数右移，左边补的是1，所以陷入死循环

我们可以不右移n,而是向左移动1（flag）

def count_one_2(n):
    count = 0

    flag = 1

    for i in xrange(64):  因为python的整数没有位数限制，我们自定义自己机器的位数
        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: 主要是找到一个这样的规律 n & (n-1) = 这个数的最右一位1变成变成0， 举个例子:

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)  # 只能判断正数