区块链技术博客
www.b2bchain.cn

【LeetCode(Java) – 1259】不相交的握手

这篇文章主要介绍了【LeetCode(Java) – 1259】不相交的握手的讲解,通过具体代码实例进行17812 讲解,并且分析了【LeetCode(Java) – 1259】不相交的握手的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=17812

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

文章目录

  • 1、题目描述
  • 2、解题思路
  • 3、解题代码

1、题目描述

【LeetCode(Java) - 1259】不相交的握手

2、解题思路

  本题的输入值保证为:2 <= num_people <= 1000 和 num_people % 2 == 0,因此不用做非法数字判断。

  设 dp[i] 表示 i 个人的不会相交的握手方案数。

  当我们只有 2 个人时,只有一种握手方法,dp[2] == 1。

  当我们有 n 个人时,可以分为两类:

  1、第 1 个人和第 2 个人握手,那么剩下[3,n]的人又可以自成一圈,即 dp[n-2]; 当第 1 个人和第 n 个人握手,剩下的[2,n-1]的人又可以自成一圈,即 dp[n-2];

  2、第 1 个人和第 k 个人握手(k = 4、6、8、…、n-2) ,会让 [2,k-1] 和 [k+1,n] 分别自成一圈,其中,[2,k-1] 总共有 k-1-2+1 = k-2 个人,[k+1,n] 总共有 n-(k+1)+1 = n-k 个人,因此,对于每一个 k ,都有 dp[k-2] × dp[n-k] 种握手数。

  综上,dp[i] = 2 × dp[i-2] + Σ(dp[k-2] × dp[n-k]),其中(k = 4、6、8、…、n-2)

  当 n 很大时,容易造成超出 int 类型的数据上限,因此,对于每一个 dp[i] ,题目都要求是模 10^9+7 后的结果。

  因此,在我们计算中,只要使用了 dp[?] ,就得在使用后进行取模,防止数据溢出。

3、解题代码

class Solution {     public int numberOfWays(int num_people) {         if (num_people == 2) return 1;         int mod = (int) (Math.pow(10, 9) + 7);         // dp[i] 表示 i 个人的不会相交的握手方案数         long[] dp = new long[num_people + 1];         dp[0] = dp[1] = 0;  // 一个人或者没有人无法握手         dp[2] = 1;  // 两个人只有一种握手         for (int i = 3; i <= num_people; i++) {             long sum = 0;             for (int k = 4; k <= i - 2; k += 2) {                 sum += (dp[k - 2] * dp[i - k]) % mod;             }             dp[i] = (2 * dp[i - 2] % mod + sum) % mod;         }         return (int) (dp[num_people] % mod);     } } 

本文转自互联网,侵权联系删除【LeetCode(Java) – 1259】不相交的握手

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 【LeetCode(Java) – 1259】不相交的握手
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们