18.python面试之数据结构

发表于 更新于 分类于 ， Changyan： 本文字数： 808 阅读时长 ≈ 3 分钟

数据结构也就是存储数据的结构，我们对数据组织的方式就叫做数据结构。

数据结构解决的就是一组数据如何保存，保存形式是怎么样的。

python最新面试宝典系列文章

斐波那契数列

数列定义:

f 0 = f 1 = 1

f n = f (n-1) + f (n-2)

根据定义

速度很慢，另外(暴栈注意！⚠ ） O(fibonacci n)

1
2
3
4
5
def fibonacci(n):
    if n == 0 or n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(1))
1

状态/循环

1
2
3
4
5
6
def fibonacci(n):
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a
print(fibonacci(10))
89

递归

1
2
3
4
5
6
7
8
def fibonacci(n):
    def fib(n_, s):
        if n_ == 0:
            return s[0]
        a, b = s
        return fib(n_ - 1, (b, a + b))
    return fib(n, (1, 1))
print(fibonacci(10))
89

青蛙跳台阶问题

一只青蛙要跳上n层高的台阶，一次能跳一级，也可以跳两级，请问这只青蛙有多少种跳上这个n层台阶的方法？

分析发现这个还是一个斐波那契数列

递归

设青蛙跳上n级台阶有f(n)种方法，把这n种方法分为两大类，第一种最后一次跳了一级台阶，这类共有f(n-1)种，第二种最后一次跳了两级台阶，这种方法共有f(n-2)种，则得出递推公式f(n)=f(n-1) + f(n-2),显然f(1)=1,f(2)=2，这种方法虽然代码简单，但效率低，会超出时间上限

1
2
3
4
5
6
7
8
9
10
class Solution:
    def climbStairs(self,n):
        if n ==1:
            return 1
        elif n==2:
            return 2
        else:
            return self.climbStairs(n-1) + self.climbStairs(n-2)
s = Solution()
print(s.climbStairs(10))
89

用循环来代替递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def climbStairs(self,n):
        if n==1 or n==2:
            return n
        a,b,c = 1,2,3
        for i in range(3,n+1):
            c = a+b
            a = b
            b = c
        return c
s = Solution()
print(s.climbStairs(10))



89

python最新面试宝典系列文章