这里是我算法练习的一些例子，当作思维训练，题目来主要来自自剑指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) # 只能判断正数
网友评论