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 放到最后
}总结
还是和数学技巧有关系
