软件开发岗

上台阶的方法数

100级台阶，一次可以上1级或2级，问有多少种方法上完；

dp[i] = dp[i - 1] + dp[i - 2]

判断单向链表是否有环

快慢指针；

rand5如何生成rand7

要使用rand5()函数来实现rand7()函数，我们可以使用拒绝采样技术。以下是步骤和一个简单的方法：

使用两次rand5()调用生成一个范围在[0, 24]之间的随机数。

• 如果随机数小于21，我们可以将其重新映射到[0, 6]范围内的一个数。
• 如果随机数大于或等于21，我们将重新生成。

以下是具体的实现：

def rand5():
    # 假设这是一个已有的函数，它能返回0到4之间的一个随机数
    pass

def rand7():
    while True:
        # 使用两次rand5()生成一个0到24之间的随机数
        num = rand5() + rand5() * 5
        # 如果这个数小于21，将其映射到0到6范围内
        if num < 21:
            return num % 7

此方法保证了每个从0到6的数字都有相同的机会被返回，从而生成了一个均匀的随机分布。

randn() + n * randn()会返回[0, n^2 - 1]的随机数（即randn^2）。