江苏扬州建设工程信息网站,男生为女生做网站,php 数据库 wordpress,驻马店住房和城乡建设局网站2306. 公司命名
给你一个字符串数组 ideas 表示在公司命名过程中使用的名字列表。公司命名流程如下#xff1a;
从 ideas 中选择 2 个 不同 名字#xff0c;称为 ideaA 和 ideaB 。 交换 ideaA 和 ideaB 的首字母。 如果得到的两个新名字 都 不在ideas 中#xff0c;那么 …2306. 公司命名
给你一个字符串数组 ideas 表示在公司命名过程中使用的名字列表。公司命名流程如下
从 ideas 中选择 2 个 不同 名字称为 ideaA 和 ideaB 。 交换 ideaA 和 ideaB 的首字母。 如果得到的两个新名字 都 不在ideas 中那么 ideaA ideaB串联 ideaA 和 ideaB 中间用一个空格分隔是一个有效的公司名字。 否则不是一个有效的名字。 返回 不同 且有效的公司名字的数目。
数据范围
2 ideas.length 5 * 1041 ideas[i].length 10ideas[i] 由小写英文字母组成ideas 中的所有字符串 互不相同
分析
将字母按开头分类放入 v e c t o r vector vector中预处理每个开头对应的集合中的单词在和后面的字母交换首字母后仍然合法的单词的数量放在 c n t [ i ] [ j ] cnt[i][j] cnt[i][j]中( c n t [ i ] [ j ] cnt[i][j] cnt[i][j]表示以 i i i开头的单词集中若和字符j交换首字母后仍然合法的单词数目)外层循环遍历所有的单词内存循环遍历字母序比当前单词首字母小的字母若能交换则 r e s res res加上 c n t cnt cnt对应的值。
代码
typedef long long LL;
class Solution {
public:const static int N 35, M 5e4 5;// unordered_mapstring, bool vis;unordered_setstring st;int cnt[N][N];vectorstring idea[N];long long distinctNames(vectorstring ideas) {for(auto v : ideas) {// vis[v] true;st.insert(v);idea[v[0] - a].push_back(v);}for(int i a - a; i z - a; i ) {for(int j a; j z; j ) {for(auto k : idea[i]) {string ts k;ts[0] j;// if(!vis[ts]) cnt[i][j - a] ;if(!st.count(ts)) cnt[i][j - a] ;}}}LL res 0;for(int i a - a; i z - a; i ) {for(auto s : idea[i]) {for(int j 0; j i; j ) {string ts s;ts[0] char(j a);if(st.count(ts)) continue;res cnt[j][i];}}}return res * 2;}
};740. 删除并获得点数
给你一个整数数组 nums 你可以对它进行一些操作。
每次操作中选择任意一个 nums[i] 删除它并获得 nums[i] 的点数。之后你必须删除 所有 等于 nums[i] - 1 和 nums[i] 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
数据范围
1 nums.length 2 * 1041 nums[i] 104
分析
将每个数字出现的个数用cnt数组记录令dp[i][0]表示不删除值为i的数获得点数最大值dp[i][1]表示删除值为i的数获得点数最大值状态转移如下 d p [ i ] [ 0 ] m a x ( d p [ i − 1 ] [ 1 ] , d p [ i − 1 ] [ 0 ] ) dp[i][0]max(dp[i-1][1],dp[i-1][0]) dp[i][0]max(dp[i−1][1],dp[i−1][0]) d p [ i ] [ 1 ] d p [ i − 1 ] [ 0 ] c n t [ i ] ∗ i dp[i][1]dp[i-1][0]cnt[i]*i dp[i][1]dp[i−1][0]cnt[i]∗i
代码
class Solution {
public:const static int N 1e4 5;int cnt[N];int dp[N][2];int n;int deleteAndEarn(vectorint nums) {n nums.size();for(int i 0; i n; i ) cnt[nums[i]] ;for(int i 1; i N - 5; i ) {dp[i][0] max(dp[i - 1][0], dp[i - 1][1]);dp[i][1] dp[i - 1][0] cnt[i] * i;}int res 0;for(int i 0; i N - 5; i ) {res max(res, dp[i][0]);res max(res, dp[i][1]);}return res;}
};120. 三角形最小路径和
给定一个三角形 triangle 找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 1 的两个结点。也就是说如果正位于当前行的下标 i 那么下一步可以移动到下一行的下标 i 或 i 1 。
数据范围
1 triangle.length 200triangle[0].length 1triangle[i].length triangle[i - 1].length 1-104 triangle[i][j] 104
分析
简单DP注意在边界的情况
代码
class Solution {
public:const static int N 205;int dp[N][N];int minimumTotal(vectorvectorint triangle) {int n triangle.size();for(int i 0; i n; i ) {for(int j 0; j i; j ) {if(j 0) dp[i 1][j 1] dp[i][j 1] triangle[i][j]; else if(j i) dp[i 1][j 1] dp[i][j] triangle[i][j]; else dp[i 1][j 1] min(dp[i][j 1], dp[i][j]) triangle[i][j];}}int res 0x3f3f3f3f;for(int i 0; i n; i ) res min(res, dp[n][i 1]);return res;}
};
