2020阿里实习校招算法笔试题（1）

Anna ·

更新时间:2024-09-21

· 751 次阅读

队伍选择

使用Python2.7.3
题目描述：现有n个人，要从这n个人中选任意数量的人组成一只队伍，再在这些人中选出一名队长，求不同的方案对109+710^9+7109+7取模的结果。如果两个方案选取的人的集合不同或选出的队长不同，则认为这两个方案是不同。
输入描述：

一行一个数字n。
1<=n<=1091<=n<=10^91<=n<=109

输出描述：

一行一个数字表示答案

示例1
输入

输出

说明

4种方案为(1^)(\hat1)(1^)，(2^)(\hat2)(2^)，(1^,2)(\hat1,2)(1^,2)，(1,2^)(1,\hat2)(1,2^)，其中x^\hat xx^表示选取xxx为队长。

思路：
n=1，f(1) = 1
n=2，f(2) = C21C^1_2C21*f(1) + 2
n=3，f(3) = C31C^1_3C31*f(1) + C32C^2_3C32*f(2) + 3
……
其中CnxC^x_nCnx = n!(n−x)!x!\frac{n!}{(n-x)!x!}(n−x)!x!n!

在计算f(n)时，可以明显看到是需要利用到1-n的结果，因此很自然的想到利用递归的方法计算。如果空间复杂度要求不高，还可以将前面的结果都保存下来，这样可以减少计算量。这里的代码是最简单的直接递归版本。

代码

# -*- coding:utf-8 -*-
class Solution:
    def NumOfSquad(self, n):
        if n  10**9:
            return 0
        if n == 1:
            return 1
        sum = n
        for i in range(1,n):
            sum += self.NumOfChoose(n,i) * self.NumOfSquad(i)
        return sum%(10**9+7)
    def NumOfChoose(self, n, x):
        if x == 1:
            return n
        return int(self.factorial(n)/self.factorial(n-x)/self.factorial(x))
    def factorial(self, n):
        if n == 1:
            return 1
        res = 1
        for i in range(1,n+1):
            res *= i
        return res
if __name__ == "__main__":
    num = 5
    solution = Solution()
    print(solution.NumOfSquad(num))

以空间换时间和题目2待更新……

作者：杨6

校招阿里算法

1024 个赞