难度: Hard
Submission
运行时间: 32 ms
内存: 16.1 MB
class Solution:
def numberOfWays(self, numPeople: int) -> int:
#分析 卡特兰数
#n-k 与 1-k 分开的
n=numPeople//2
from math import factorial
return (factorial(2*n)//factorial(n)//factorial(n)//(n+1))%(10**9+7)
# 作者：树叶烦
# 链接：https://leetcode.cn/problems/handshakes-that-dont-cross/solutions/44416/zhi-jie-yong-qia-te-lan-shu-gong-shi-ke-yi-yi-xing/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
Explain
这个题解使用了卡特兰数的公式。卡特兰数是一系列自然数，广泛用于计算在各种情境中不相交结构的数量。在这个问题中，我们要找到不相交的握手方式数，这可以用卡特兰数来解决。卡特兰数的第n项可以用公式 C(n) = (2n)! / ((n + 1)! * n!) 来计算。这里，n是握手的对数，即总人数的一半。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def numberOfWays(self, numPeople: int) -> int:
# 使用卡特兰数公式计算不相交的握手方式数
n = numPeople // 2
from math import factorial
return (factorial(2 * n) // factorial(n) // factorial(n) // (n + 1)) % (10**9 + 7)
Explore
卡特兰数是用于解决多种组合计数问题的一种数列，特别是那些涉及递归结构或不交叉结构的问题。在不相交的握手问题中，有偶数个人围成一个圈，每个人必须与另一个人握手，且所有的握手线不能交叉。这个问题可以通过递归方法解决：选择一个人作为起始点，这个人可以选择圈中任何一个非相邻的人进行握手。假设选定的两个人之间有 2k 个人，外侧有 2(n-k-1) 个人。这两部分都必须独立地进行不相交的握手，而这正是卡特兰数的定义问题。因此，总的不相交握手方式可以通过卡特兰数来计算。
是的，使用阶乘的方法计算卡特兰数在数字非常大时确实会遇到性能问题。首先，阶乘数值增长非常快，很快就会超出普通整数类型的存储范围，尽管使用了Python的内置bigint来解决这个问题。其次，计算大数的阶乘需要更多的CPU时间和内存。通常在实际应用中，计算大的卡特兰数会采用更优的算法，如用逐项除或者使用组合公式直接计算需要的项，而不是完全展开阶乘。
模数`10**9 + 7`是一个常用的大质数，广泛用于算法竞赛和编程题目中，主要是为了防止结果过大导致溢出和减少计算时间。此外，使用质数作为模数还有一个好处，那就是在模这个质数时，大部分操作（如加法、乘法）都可以保持良好的性能，因为质数可以保证除了1和它本身外，没有其他数能整除它，这有助于在使用哈希表等数据结构时减少冲突。
在卡特兰数的计算公式 C(n) = (2n)! / ((n + 1)! * n!) 中，我们需要注意的是两次除法操作。首先，由于n是握手的对数，它必须是非负整数。在这种情况下，n和n+1的阶乘都是定义良好的，且不为零（即使n为0，0! = 1）。因此，除以n! 和 (n+1)! 是安全的，不会出现除以零的异常。在实际编程实现中，只要保证n是非负整数，就不会有除零错误发生。