BaiRuic
Go back

从“爬楼梯”开始

目录

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

这是本人2022年4月份面试华为云时（实习面试）的第一道题目，也是Leetcode上一道原题（70. 爬楼梯）。从题目本身出发，当然很容易写出O(n)O(n)的解法，那还能再优化吗？你能写出时间复杂度为O(log⁡n)O(\log n)的写法吗？O(1)O(1)的写法呢？

爬楼梯的几种写法

动态规划

思路

简单的动态规划思路。

定义 dp[n]dp[n] 为爬到第 nn 级台阶的方案数，考虑最后一步可能是跨了一级台阶，也可能跨了两级台阶，所以有如下状态转移方程：

dp[n]=dp[n−1]+dp[n−2]dp[n] = dp[n-1] + dp[n-2]

这意味着爬到第 nn 级台阶的方案数是爬到 n−1n−1 级台阶的方案数和爬到第 n−2n−2 级台阶的方案数的和。因为每次只能爬 11 级或 22 级，所以 dp[n]dp[n] 只能从 dp[n−1]dp[n-1] 和 dp[n−2]dp[n-2] 转移过来，而这里要统计方案总数，就需要对这两项的贡献求和。

实现

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0 for _ in range(n+1)]
        dp[0] = 1
        dp[1] = 1

        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]

        return dp[n]

以上的实现的代码空间复杂度、时间复杂度均为O(n)O(n)。进一步的，因为在状态转移的过程中，每个状态只用到了过去最近两个状态，因此可以仅使用三个变量来保存状态值（有人称这种优化方式为滚动数组），实现 O(1)O(1) 的空间复杂度。

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        i1, i2 = 1, 2
        for i in range(3, n+1):
            temp = i1 + i2
            i1 = i2
            i2 = temp
      
        return i2

矩阵快速幂

思路

通过矩阵乘法来表示状态之间的转移，进而可以转化为矩阵的n次幂问题，然后再用矩阵的快速幂实现矩阵的n次幂，因此时间复杂度为 O(log⁡n)O(\log n)。

首先通过 dp[n]=dp[n−1]+dp[n−2]dp[n] = dp[n-1] + dp[n-2], 容易得:

dp[2]=dp[1]+dp[0]dp[3]=dp[2]+dp[1]dp[2] = dp[1] + dp[0]\\dp[3] = dp[2] + dp[1]

即：

[dp[3]dp[2]]=[1110]@[dp[2]dp[1]]\begin{bmatrix} dp[3]\\dp[2]\\ \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} @ \begin{bmatrix} dp[2] \\ dp[1] \end{bmatrix}

进一步推广有：

[dp[n]dp[n−1]]=[1110]n−2@[dp[2]dp[1]]\begin{bmatrix} & dp[n] \\ & dp[n-1]\\\end{bmatrix} = \begin{bmatrix}1 & 1 \\1 & 0\end{bmatrix}^{n-2} @ \begin{bmatrix} dp[2] \\ dp[1] \end{bmatrix}

因此 dp[n]=([1110]n−2@[dp[2]dp[1]])T@[10]dp[n] = \left(\begin{bmatrix}1 & 1 \\1 & 0\end{bmatrix}^{n-2} @ \begin{bmatrix} dp[2] \\ dp[1] \end{bmatrix} \right )^T @ \begin{bmatrix} 1 \\ 0 \end{bmatrix}

时间复杂度 O(log⁡n)O(\log n)，空间复杂度 O(1)O(1)

实现

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        mat = [[1,1], [1, 0]]
        mat_n2 = self.pow(mat, n-2)
   
        res = mat_n2[0][0] * 2 + mat_n2[0][1]

        return res

    def pow(self, mat, n):
        if n == 1:
            return mat
        if n % 2 == 0:
            temp_mat = self.pow(mat, n // 2)
            return self.matmul(temp_mat, temp_mat)
        else:
            temp_mat = self.pow(mat, n-1)
            return self.matmul(mat, temp_mat)
    
    def matmul(self, mat1, mat2):
        res = [[0] * len(mat1[0]) for _ in range(len(mat2[0]))]

        for i in range(0, len(mat1)):
            for j in range(0, len(mat2[0])):
                for k in range(len(mat2)):
                    res[i][j] += mat1[i][k] * mat2[k][j]

        return res

数学通解

数学通解有两种解法，一种是在上述矩阵快速幂的基础上使用矩阵的特征值和特征向量来求解矩阵快速幂的结果，另外一种是使用微积分来推导通项公式。

矩阵思路

上述解法二中由 将爬楼梯问题转为了矩阵的快速幂问题，接下来使用矩阵的特征值和特征向量来求解矩阵幂，其背后理论如下：如果一个n∗nn*n矩阵AA有nn个线性无关的特征向量，那么这个矩阵AA可以对角化为特征值矩阵Λ\Lambda，其中Λi\Lambda_i表示第ii个特征值。那么，这个矩阵的幂AnA^n 就可以写成An=VΛnV−1A^n=V \Lambda^n V^{-1}的形式，其中VV是由特征向量组成的矩阵。

因此，首先计算矩阵[1110]\begin{bmatrix}1 & 1 \\1 & 0\end{bmatrix} 的特征值和特征向量，有特征方程：

∣1−λ 11 −λ∣ =0\begin{vmatrix}1-\lambda  & 1\\1  & -\lambda\end{vmatrix}  = 0

进而求得特征值：

λ1=1+52,λ2=1−52\lambda_1 = \frac{1 + \sqrt 5 }{ 2}, \\\lambda_2 = \frac{1 - \sqrt 5 }{ 2}

和特征向量：

x1=[1+52,1]Tx2=[1−52,1]Tx_1 = \left[\frac{1+\sqrt 5}{2}, 1\right] ^T\\ x_2 = \left[\frac{1-\sqrt 5}{2}, 1\right] ^T\\

由于 An=VΛnV−1A^n=V \Lambda^n V^{-1} 可以有：

[1110]n=[x1,x2]@[λ1n00λ2n]n@[x1,x2]−1=[1+521−5211]@[1+52n001−52n]@15[15−12−11+52]=15[an+1−bn+1ab(bn−an)an−bnab(bn−1−an−1)],a=1+52,b=1−52\begin{aligned} \begin{bmatrix}1 & 1 \\1 & 0\end{bmatrix}^n & & = & \begin{bmatrix}x_1, x_2 \end{bmatrix} @ \begin{bmatrix}{\lambda_1}^n & 0 \\0 & {\lambda_2}^n\end{bmatrix}^n @\begin{bmatrix}x_1, x_2 \end{bmatrix}^{-1} \\ & & = & \begin{bmatrix}\frac{1+\sqrt 5}{2} & \frac{1-\sqrt 5}{2} \\1 & 1 \end{bmatrix} @ \begin{bmatrix}{\frac{1+\sqrt 5}{2}}^n & 0 \\0 & {\frac{1-\sqrt 5}{2}}^n\end{bmatrix} @ \frac{1}{\sqrt 5} \begin{bmatrix}1 & \frac{\sqrt 5 - 1}{2} \\ -1 & \frac{1+\sqrt 5}{2}\end{bmatrix} \\ & & = & \frac{1}{\sqrt 5} \begin{bmatrix}a^{n+1}-b^{n+1} & ab(b^n -a^n) \\ a^n - b^n & ab(b^{n-1} - a^{n-1})\end{bmatrix}, a = \frac{1+\sqrt 5}{2}, b = \frac{1-\sqrt 5}{2} \end{aligned}

因此有：

dp[n]=([1110]n−2@[dp[2]dp[1]])T@[10]=15[[an−1−bn−1ab(bn−2−an−2)an−2−bn−2ab(bn−3−an−3)]@[21]]T@[10]=15(2an−1−2bn−1+ab(bn−2−an−2))=2an−1−2bn−1+an−1−bn−15=2+55∗an−2−2−55∗bn−2\begin{aligned} dp[n] & = \left(\begin{bmatrix}1 & 1 \\1 & 0\end{bmatrix}^{n-2} @ \begin{bmatrix} dp[2] \\ dp[1] \end{bmatrix} \right )^T @ \begin{bmatrix} 1 \\ 0 \end{bmatrix} \\ & = \frac{1}{\sqrt 5} \left[ \begin{bmatrix}a^{n-1}-b^{n-1} & ab(b^{n-2} -a^{n-2}) \\ a^{n-2} - b^{n-2} & ab(b^{n-3} - a^{n-3})\end{bmatrix} @ \begin{bmatrix} 2 \\ 1 \end{bmatrix} \right]^T @\begin{bmatrix} 1 \\ 0 \end{bmatrix}\\ & = \frac{1}{\sqrt 5}(2a^{n-1} - 2b ^{n-1} + ab(b^{n-2}-a^{n-2}))\\ & = \frac{2a^{n-1} - 2b ^{n-1} + a^{n-1}-b^{n-1}}{\sqrt{5} } \\ & = \frac{2 + \sqrt{5}}{\sqrt{5} } * a ^{n-2} - \frac{2 - \sqrt{5}}{\sqrt{5} } * b ^{n-2} \end{aligned}

将 a=1+52,b=1−52a = \frac{1+\sqrt 5}{2}, b = \frac{1-\sqrt 5}{2} 带入有：

dp[n]=2+55∗1+52n−2−2−55∗1−52n−2dp[n] = \frac{2 + \sqrt{5}}{\sqrt{5} } * {\frac{1+\sqrt 5}{2}} ^{n-2} - \frac{2 - \sqrt{5}}{\sqrt{5} } * {\frac{1-\sqrt 5}{2}} ^{n-2}

微积分思路

根据上述已经得到了的递推公式 dp[n]=dp[n−1]+dp[n−2]dp[n] = dp[n-1] + dp[n-2] ，可以利用级数方法来求解该数列的通项公式。

首先假设该数列的通项公式为 F(n)=a∗xnF(n) = a * x^n，其中aa和xx均为待求解的常数值。

将该通项公式代入递推公式后，可得：a∗xn=a∗x(n−1)+a∗x(n−2)a * x^n = a * x^{(n-1)} + a * x^{(n-2)}。

移项后，得到：xn−x(n−1)−x(n−2)=0x^n - x^{(n-1)} - x^{(n-2)} = 0。

由于xx不等于00，可以将x(n−2)x^{(n-2)}约掉，进而得到：x2−x−1=0x^2 - x - 1 = 0。

求解上式可得：

x1=(1+5)/2x2=(1−5)/2x_1 = (1 + \sqrt 5) / 2\\x_2 = (1 - \sqrt 5) / 2

因为F(1)=1，F(2)=2F(1)=1，F(2)=2，因此可以得到：F(n)=a∗x1n+b∗x2nF(n) = a * x_1^n + b * x_2^n，将F(1)=1，F(2)=2F(1)=1，F(2)=2代入上式，可以得到如下方程

ax1+bx2=1ax12+bx22=2\begin{aligned}& ax_1 + bx_2 = 1\\& a{x_1}^2 + b{x_2}^2 = 2\end{aligned}

解得：

a=1+525b=1−525a = \frac{1 + \sqrt 5}{2\sqrt 5}\\b = \frac{1 - \sqrt 5}{2\sqrt 5}

因此，可以得到所求数列的通项公式：

F[n]=1+525∗1+52n−1−525∗1−52n=2+55∗1+52n−2−2−55∗1−52n−2\begin{aligned}F[n] &= \frac{1 + \sqrt 5}{2\sqrt 5} * {\frac{1+\sqrt 5}{2}} ^{n} - \frac{1 - \sqrt 5}{2\sqrt 5} * {\frac{1-\sqrt 5}{2}} ^{n}\\& =\frac{2 + \sqrt{5}}{\sqrt{5} } * {\frac{1+\sqrt 5}{2}} ^{n-2} - \frac{2 - \sqrt{5}}{\sqrt{5} } * {\frac{1-\sqrt 5}{2}} ^{n-2}\end{aligned}

代码实现：

class Solution:
    def climbStairs(self, n: int) -> int:
        temp = math.sqrt(5)
        a = (1+temp) / 2
        b = (1-temp) / 2
        return round(((2+temp) / temp) * a ** (n-2) - 
										 ((2-temp) / temp) * b ** (n-2))

我想象中的技术面试

IT类技术面试考算法题目已经不是什么新鲜事了，毕竟算法题可以快速的考察候选人的代码能力，而且成本也最小。我虽然身在学校，尚无面试官经验，但我恰想以我现在的视角来简单探讨一下对技术面试的一点看法。

我认为一场好的技术面试应该同时考察候选人技术深度与广度，深度如何考察呢？至少应该按照候选人简历上的项目或者过往的经历展开，尤其是校招，围绕候选人过往的技术经历，不断的深挖，来达到试探候选人技术边界的目的，也就是探探底，至于如何深挖就需要看面试官的水平了，通过深挖不仅可以很好的了解候选人对某技术的掌握程度，还可以看到候选人对技术本身的态度。至于技术的广度，应该大范围的蜻蜓点水式的考察候选人用过的一些技术、掌握的一些技能，来判断候选人平时有没有关注相关行业、对相关行业是否真的感兴趣。从这两方面我觉得足以考察一个候选人的技术水平了。

至于算法题目，个人觉得有必要考，毕竟数据结构与算法作为计算机四大件之一，其重要性不言而喻，但是并不能为了考算法题而考算法题。在候选人写题目的时候，其思考方式（拆解问题的思维方式）、沟通技能（遇到难题时是否寻求帮助、如何寻求帮助）、代码分格（是否考虑边界、变量命名是否规范等）都应该是需要关注的点，而不能仅仅以 accept 论英雄。

此外，一道好的算法题也至关重要，太难的题目直接把候选人难倒了，只能大眼瞪小眼，毫无意义；而太过容易的题目又达不到考察候选人思维方式、沟通技能和代码风格的目的。在Leetcode上写了1000多题之后，我认为一道好的题目至少应该具有以下两个特点：

  • 代码简短。通常一场面试只有40分钟，代码太长了显然有点本末倒置，毕竟算法题的目的不仅仅在于写出代码本身。
  • 基础解容易写出来且有思考空间。只有这样，当候选人写出简单的暴力解法之后，才能向候选人提出更高要求的解法，然后在这个过程中可以考察候选人的思考方式以及沟通技能。

爬楼梯就是一道我认为很好的面试题目，其动态规划的解法短短几行就可以实现，在写出时间复杂度、空间复杂度均为O(n)O(n)的解法之后，还可以继续追问候选人能否优化空间复杂度，进一步的能否写出时间复杂度为O(log⁡n)O(\log n) 的解法，然后对矩阵相乘有无优化思路。在这个过程中，需要候选人不断的思考、不断的拆解问题，需要候选人与面试官不断的沟通，从而也达到了面试的目的。

令我比较遗憾的是，彼时我面试华为时，当我写完这道题目之后，面试官并没有继续要求我优化（和我设想的完全不一样 😢），直接开始了下一道题目，甚至在写算法题目的时候，当我想与面试官沟通一下题目时，被面试管直接回绝了，让我直接写就好了。所幸最后面试通过了，在我实习入职之后，有幸见到了这位面试官，彼时是一位18级技术大佬，同事称他为朱博（华为员工对博士这么称呼）。在某次中午吃饭的时候，我抱着好奇的心态问朱博，面试写算法题时对候选人的要求是什么呢？朱博答能写代码就行了。

Previous Post
写在Leetcode1000题之后
Next Post
我又毕业了