力扣（leetcode）每日一题 2306 公司命名
2306. 公司命名
给你一个字符串数组 ideas 表示在公司命名过程中使用的名字列表。公司命名流程如下：
- 从
ideas中选择 2 个 不同 名字，称为ideaA和ideaB。 - 交换
ideaA和ideaB的首字母。 - 如果得到的两个新名字 都 不在
ideas中，那么ideaA ideaB（串联ideaA和ideaB，中间用一个空格分隔）是一个有效的公司名字。 - 否则，不是一个有效的名字。
返回 不同 且有效的公司名字的数目。
示例 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 。
题解
因为是hard题目，所以想着如何优化到一次遍历，显然是行不通的。然后就寄了。
实践上不能通过的写法
public static long distinctNames(String[] ideas) {
HashSet<String> set = new HashSet<String>();
for (int i = 0; i < ideas.length; i++) {
set.add(ideas[i]);
}
long sum = 0;
for (int i = 0; i < ideas.length; i++) {
for (int j = i + 1; j < ideas.length; j++) {
String idea1 = ideas[i];
String idea2 = ideas[j];
String newIdea1 = idea1.substring(0, 1) + idea2.substring(1);
String newIdea2 = idea2.substring(0, 1) + idea1.substring(1);
if (!set.contains(newIdea1) && !set.contains(newIdea2)) {
sum++;
}
}
}
return sum * 2;
}
把首字母抽取出来，减少循环的数量
public static long distinctNames(String[] ideas) {
HashMap<Character, Set<String>> map = new HashMap<>();
for (int i = 0; i < ideas.length; i++) {
Set<String> set = map.getOrDefault(ideas[i].charAt(0), new HashSet<>());
set.add(ideas[i].substring(1));
map.put(ideas[i].charAt(0), set);
}
long sum = 0;
for (Map.Entry<Character, Set<String>> entry : map.entrySet()) {
Character key = entry.getKey();
Set<String> value = entry.getValue();
for (Map.Entry<Character, Set<String>> entry2 : map.entrySet()) {
Character key2 = entry2.getKey();
Set<String> value2 = entry2.getValue();
if (key == key2) {
continue;
}
HashSet<String> strings = new HashSet<>(value);
// 3 + 5 - 6 那么就是 2 strings.addAll(value2);
int count = value.size() + value2.size() - strings.size();
sum += (long) (value2.size() - count) * (long) (value.size() - count);
}
}
return sum;
}
这里可以想到用数组代替hash，但是没有什么时间上的提升
public static long distinctNames(String[] ideas) {
Set<String>[] sets = new Set[26];
HashMap<Character, Set<String>> map = new HashMap<>();
for (int i = 0; i < ideas.length; i++) {
char c = ideas[i].charAt(0);
if (sets[c - 'a'] == null) {
HashSet<String> set = new HashSet<>();
set.add(ideas[i].substring(1));
sets[c - 'a'] = set;
} else {
sets[c - 'a'].add(ideas[i].substring(1));
}
}
long sum = 0;
for (int i = 0; i < 26; i++) {
if (sets[i] != null) {
for (int j = i; j < 26; j++) {
if (sets[j] != null) {
Set<String> set1 = sets[i];
Set<String> set2 = sets[j];
Set<String> set3 = new HashSet<>(set1);
set3.addAll(set2);
int count = set1.size() + set2.size() - set3.size();
sum += (long) (set1.size() - count) * (long) (set2.size() - count);
}
}
}
}
return sum * 2;
}
看了大佬的提交，将取交替的计算，进行缓存。时间上大幅提升
public static long distinctNames(String[] ideas) {
int[] size = new int[26]; // 集合大小
int[][] dp = new int[26][26]; // 交集大小
Map<String, Integer> groups = new HashMap<>(); // 后缀 -> 首字母
for (String s : ideas) {
int key1 = s.charAt(0) - 'a';
size[key1]++; // 增加集合大小
String value1 = s.substring(1);
// key1 对应的value value还有对应的key2,key3 这里的交际都要加上1
// 而这里的key只有可能是0到25，因此可以用位来存储。 比如 ....1110001 这里字母a,e,f,g 有交际
int mask = groups.getOrDefault(value1, 0);
groups.put(value1, mask | 1 << key1); // 把 key1 加到 mask 中
for (int key2 = 0; key2 < 26; key2++) { // key2 是和 s 有着相同后缀的字符串的首字母
if ((mask >> key2 & 1) > 0) { // key2 在 mask 中
if (key1 < key2) {
dp[key1][key2]++; // 增加交集大小
} else {
dp[key2][key1]++; // 增加交集大小
}
}
}
}
long ans = 0;
for (int i = 0; i < 26; i++) { // 枚举所有组对
for (int j = i + 1; j < 26; j++) {
int m = dp[i][j];
ans += (long) (size[i] - m) * (size[j] - m);
}
}
return ans * 2; // 乘 2 放到最后
}
总结
还是和数学技巧有关系