长春电商网站建设公司电话,wordpress微博样式评论,wordpress创意点赞,钟祥建设局网站【每日一题】LeetCode 2306.公司命名#xff08;位运算、数组、哈希表、字符串、枚举#xff09;
题目描述
给定一个字符串数组 ideas#xff0c;表示在公司命名过程中使用的名字列表。我们需要从 ideas 中选择两个不同的名字#xff0c;称为 ideaA 和 ideaB。然后交换 i…【每日一题】LeetCode 2306.公司命名位运算、数组、哈希表、字符串、枚举
题目描述
给定一个字符串数组 ideas表示在公司命名过程中使用的名字列表。我们需要从 ideas 中选择两个不同的名字称为 ideaA 和 ideaB。然后交换 ideaA 和 ideaB 的首字母。如果交换后得到的两个新名字都不在 ideas 中那么这两个名字串联起来中间用一个空格分隔就是一个有效的公司名字。我们需要返回不同且有效的公司名字的总数。 输入示例
示例 1
输入ideas [coffee,donuts,time,toffee]
输出6
解释下面列出一些有效的选择方案
- (coffee, donuts)对应的公司名字是 doffee conuts 。
- (donuts, coffee)对应的公司名字是 conuts doffee 。
- (donuts, time)对应的公司名字是 tonuts dime 。
- (donuts, toffee)对应的公司名字是 tonuts doffee 。
- (time, donuts)对应的公司名字是 dime tonuts 。
- (toffee, donuts)对应的公司名字是 doffee tonuts 。
因此总共有 6 个不同的公司名字。下面列出一些无效的选择方案
- (coffee, time)在原数组中存在交换后形成的名字 toffee 。
- (time, toffee)在原数组中存在交换后形成的两个名字。
- (coffee, toffee)在原数组中存在交换后形成的两个名字。示例 2
输入ideas [lack,back]
输出0
解释不存在有效的选择方案。因此返回 0 。提示
2 ideas.length 5 * 10^41 ideas[i].length 10ideas[i] 由小写英文字母组成ideas 中的所有字符串互不相同
思路分析
遇到困难题我们先可以尝试暴力枚举然后再逐步优化首先我们将 ideas 数组中的所有字符串添加到一个 HashSet 中以便快速检查某个字符串是否在 ideas 中。然后我们使用两层循环遍历 ideas 数组外层循环选择 ideaA内层循环选择 ideaB。对于每一对 ideaA 和 ideaB我们交换它们的首字母得到两个新的名字 newIdea1 和 newIdea2。我们检查这两个新名字是否都不在 ideas 中。如果不在那么这是一个有效的公司名字计数器 count 增加。由于每一对 ideaA 和 ideaB 可以交换两次ideaA 与 ideaB 和 ideaB 与 ideaA所以我们需要将最终的计数器 count 乘以 2。
代码实现暴力枚举
class Solution {public long distinctNames(String[] ideas) {// 将所有名字存入HashSet中方便快速查找HashSetString set new HashSet();for (String idea : ideas) {set.add(idea);}// 初始化计数器long count 0;int n ideas.length;// 外层循环遍历选择ideaAfor (int i 0; i n; i) {char firstChar1 ideas[i].charAt(0); // 获取ideaA的首字母// 内层循环遍历选择ideaB从i1开始避免重复for (int j i 1; j n; j) {char firstChar2 ideas[j].charAt(0); // 获取ideaB的首字母// 交换首字母后的新名字String newIdea1 firstChar2 ideas[i].substring(1);String newIdea2 firstChar1 ideas[j].substring(1);// 如果两个新名字都不在ideas中那么这是一个有效的公司名字if (!set.contains(newIdea1) !set.contains(newIdea2)) {count;}}}// 由于每一对可以交换两次所以最终结果需要乘以2return count * 2;}
}##思路优化
我们可以使用一个数组 groups 来存储按首字母分组的后缀。遍历 ideas 数组将每个字符串的后缀去掉首字母的部分添加到对应的 HashSet 中。使用两层循环遍历 groups 数组外层循环选择首字母 i内层循环选择首字母 j从 i1 开始避免重复计算。对于每一对首字母 i 和 j我们统计它们共有的后缀数量 m。计算可以形成的不同名称的数量即 (groups[i].size() - m) * (groups[j].size() - m)。由于每一对 ideaA 和 ideaB 可以交换两次ideaA 与 ideaB 和 ideaB 与 ideaA所以我们需要将最终的计数器 count 乘以 2。
##代码实现思路优化
class Solution {public long distinctNames(String[] ideas) {// 开一个set数组存储后缀HashSetString[] groups new HashSet[26];for (int i 0; i 26; i) {groups[i] new HashSet(); }// 将每个字符串的后缀按照首字母分组for (String str : ideas) {groups[str.charAt(0) - a].add(str.substring(1)); // 将后缀加入到对应的 HashSet 中}long count 0;// 两层循环遍历所有可能的首字母组合for (int i 0; i 26; i) {for (int j i 1; j 26; j) {int m 0; // 计数相同后缀的数量// 统计 i 组和 j 组中相同的后缀数量for (String s : groups[i]) {if (groups[j].contains(s)) {m;}}// 计算 i 组和 j 组可以形成的不同名称的数量count (long)((groups[i].size() - m) * (groups[j].size() - m));}}return count * 2; // 每对组合可以有两种排列因此乘以 2}
}效公司名字的总数。
