牛客120497586号

题解

/ 注册

全部文章 / 题解（共6篇）

题解 | #Head of a Gang#

实战 - Head of gang - 并查集输入一串序列：Name1 Name2 Time表示A和B的通话时间，假定存在通话的人所在圈子大于2个人，认为是一个黑帮，在这个黑帮中，打电话时间最长的是老大思路：使用并查集的思想构建节点的边关系，同时需要保存每个节点的通话时间注意：①因为在初始化...

Python3

2022-04-12

1 478

题解 | #最小邮票数#

01背包实战 - 最小邮票数题目要求：给定不同面额的邮票，要求我们用最少的邮票数，达到指定的面值求解思路：该题属于典型的01背包问题，因为给定邮票张数时，相同面额也认为是单独的一张，即只有0（不拿）和1（拿）两种状态指定面值为我们的背包容量m，给定的邮票张数为我们的物品数量n，每张邮票的价值...

Python3

2022-04-07

0 315

题解 | #采药#

采药问题属于01背包问题采用动态规划进行求解：保存结果：dp[i][j]表示前i件物品放入容量为j的背包，所能带来的最大价值递推公式：①如果第i件物品不放入背包，那么就代表我们要放的是前i - 1件物品 => dp[i][j] = dp[i - 1][j]；②如果第i件物品放入背包，那...

Python3

2022-04-07

0 339

题解 | #点菜问题#

点菜问题属于背包问题中的01背包物品是一个整体，两个状态，放或不放，因此得名01背包有n个物品，背包容量为m，每个物品有重量w和价值v，要求放入背包中的物品价值最大保存结果：dp[i][j]表示前i个物品放入容量为j的背包的最大价值递推起点：dp[0][j] = dp[i][...

Python3

2022-04-06

0 504

题解 | #Coincidence#

最长公共子序列题目要求：对字符串S1（长度为n）和S2（长度为m）求公共子串S3，并且S3的长度最大，求该长度动态规划分析：保存结果：dp[i][j]表示以S1[i]结尾和S2[j]结尾的最长公共子序列的长度递推起点： dp[i][0] = 0; dp[0][j] = 0;（同时也是边界值处...

Python3

2022-04-06

0 370

题解 | #合唱队形#

合唱队形题目要求：现有N名同学，求至少需要让多少名同学出列，使得现有的同学不需要调整就可以形成合唱队形，即中间高两边低思路：求一个最长递增子序列和一个最长递减子序列，然后两者交集代码： def chorusFormation(): # 求最长递增子序列 def maxAscSu...

Python3

2022-04-06

0 356