Interview Python

Grammar

Python 多行输入输出

输入 m, n 两个数:

str_in = input()
m, n = [int(_) for _ in str_in.split()]

多组输入,第一行 n 表示数的数量,第二行输入这 n 个数:

n, m = input(), list(map(int, input().split()))

输入有多组数据:

import sys

s = sys.stdin.readline().strip()
if not s:
    break

What is GIL

What is meta_class

Python 如何进行内存管理

Problems

用 Python 实现一个 Fibonacci 数列

斐波那契数列:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

如果设F(n)为该数列的第n项(n∈N*),那么这句话可以写成如下形式:F(n)=F(n-1)+F(n-2)

Recursive approach

使用递归法,时间复杂度 O(n^2),空间复杂度 O(n)

def fib_recur(n):
    if n < 2:
        return  n
    return fib_recur(n-1) + fib_recur(n-2)

Dynamic programmming approach reco

使用 DP, 时间复杂度和空间复杂度均为 O(n)

def fib_dyn(n):
    if n < 2:
        return n
    memo = [-1 for i in range(n+1)]
    # 使用 range(n) 会数组越界
    memo[0] = 0
    memo[1] = 1
    for i in range(2, n + 1):
        memo[i] = memo[i - 1] + memo[i - 2]
    return memo[n]

Imperative approach

使用公式,时间复杂度 O(n), 空间复杂度 O(1)

def fib_imp(n):
    if n < 2:
        return n
    a = 0
    b = 1
    for i in range(1, n):
        a, b = b, a + b
    return b
Last Updated: 3/8/2019, 2:34:43 PM