斐波那契数列——jzoffer

通常排序和查找是面试时考查算法的重点。重点掌握二分查找，归并排序和快速排序，做到随时正确、完整地写出它们的代码。

# 二分查找(seq需要排好序的，假设是升序排列)
def solution(seq, target):
    if len(seq) == 0:
        raise Exception("empty seq")
    found = False
    left = 0
    right = len(seq) - 1
    while left <= right:
        mid = (right - left) // 2
        if seq[mid] == target:
            found = True
            break
        elif seq[mid] > targrt:
            right = mid
        else:
            left = mid
    return found

# 归并排序
def solution(seq):
    if len(seq) <= 1:
        return seq
    left_index = 0
    right_index = len(seq) - 1
    mid = (right_index - left_index) // 2
    left = solution(seq[0: mid])
    right = solution(seq[mid:])
    ret = merge_func(left, right)
    return ret

def merge_func(seq_a, seq_b):
    a = 0
    b = 0
    ret = []
    while a < len(seq_a) and b < len(seq_b):
        if seq_a[a] >= seq_b[b]:
            ret.append(seq_b[b])
            b += 1
        else:
            ret.append(seq_a[a])
            a += 1
    while a < len(seq_a):
        ret.append(seq_a[a])
        a += 1
    while b < len(seq_b):
        ret.append(seq_b[b])
        b += 1
    return ret

# 快速排序
def solution(seq):
    # 递归方法-pythonic，额外的存储空间成本
    if len(seq) <= 1:
        return seq
    pivot = seq[0]
    left = [i for i in seq[1:] if i < pivot]
    right = [i for i in seq[1:] if i >= pivot]
    return solution(left) + [pivot] + solution(right)
# 快速排序，没有额外的存储空间
def solution(seq, left, right):
    if left < right:
        pivot_index = get_pivot_index(seq, left, right)
        solution(seq, left, pivot_index)
        solution(seq, pivot_index+1, right)

def get_pivot_index(seq, left, right):
    pivot_index = left
    pivot = seq[left]
    small = left + 1
    large = right - 1
    while small <= large:
        while pivot > seq[small] and small <= large:
            small += 1
        while pivot <= seq[large] and small <= large:
            large -= 1
        seq[small], seq[large] = seq[large], seq[small]
    seq[pivot_index], seq[large] = seq[large], seq[pivot_index]
    return large

面试题如果要求在二维数组上搜索路径，我们可以尝试回溯法，通常回溯法很适合用递归的代码实现，如果限定不可以使用递归，考虑用栈来模拟递归的过程。

面试题要求某个问题的最优解，并且该问题可以分为多个子问题，我们可以用动态规划。自上而下的递归思路会产生重复的计算，我们用自下而上的循环代码实现，把子问题的最优解先算出来并用数组（一般是一维或者二维数组）保存下来，接下来基于子问题的解计算大问题的解

分解子问题的时候存在某个特殊的选择，如果采用这个特殊的选择将一定能得到最优解，该面试题可能适用于贪婪算法

位运算是一种特殊的算法，它是把数字表示成二进制之后对0和1的操作。

题目一：求斐波那契数列的第n项

写一个函数，输入n，求斐波那契数列的第n项

效率低的写法：

def solution(n):
    if n < 0:
        return 0
    if n in (0, 1):
        return n
    else:
        return solution(n-1) + solution(n-2)

上述方法的时间复杂度是以n的指数的方式递增的，原因是重复计算过多，自上而下的递归，解决方案：

• 将计算结果存储到哈希表中，下次计算前先查找，查找到就不用重复计算

• 自下而上的循环计算

  def solution(n):
      if n < 0:
          return 0
      if n in (0, 1):
          return n
      ret = 0
      first = 0
      second = 1
      for _ in range(2, n+1):
          ret = first + second
          first = second
          second = ret
      return ret
  

  ​