如何在大网站做外链,企业网站建设58同城,建筑工程网络计划,重庆网页制作设计给你一个字符串数组#xff0c;请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs [eat, tea, tan, ate, nat, …给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs [eat, tea, tan, ate, nat, bat]
输出: [[bat],[nat,tan],[ate,eat,tea]]示例 2:
输入: strs []
输出: [[]]示例 3:
输入: strs [a]
输出: [[a]]提示
1 strs.length 1040 strs[i].length 100strs[i] 仅包含小写字母
我的解题思路 自定义一个hash方法将每个字符串进行hash计算将相同hash值的字符串存放在一个list当中。 我定义的hash方法每个字符的转为int值然后相乘乘积对他们的和1取余数。
出现错误 原因:上述hash方法存在碰撞没有有效处理碰撞的情况。 试了好几次自定义的hash方法一直都是存在碰撞的情况。 不死磕直接看官方题解 官方题解1 方法一排序 由于互为字母异位词的两个字符串包含的字母相同因此对两个字符串分别进行排序之后得到的字符串一定是相同的故可以将排序之后的字符串作为哈希表的键。
class Solution {public ListListString groupAnagrams(String[] strs) {MapString, ListString map new HashMapString, ListString();for (String str : strs) {char[] array str.toCharArray();Arrays.sort(array);String key new String(array);ListString list map.getOrDefault(key, new ArrayListString());list.add(str);map.put(key, list);}return new ArrayListListString(map.values());}
}作者力扣官方题解
链接https://leetcode.cn/problems/group-anagrams/solutions/520469/zi-mu-yi-wei-ci-fen-zu-by-leetcode-solut-gyoc/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。方法2 方法二计数 由于互为字母异位词的两个字符串包含的字母相同因此两个字符串中的相同字母出现的次数一定是相同的故可以将每个字母出现的次数使用字符串表示作为哈希表的键。
由于字符串只包含小写字母因此对于每个字符串可以使用长度为 26的数组记录每个字母出现的次数。需要注意的是在使用数组作为哈希表的键时不同语言的支持程度不同因此不同语言的实现方式也不同。
class Solution {public ListListString groupAnagrams(String[] strs) {MapString, ListString map new HashMapString, ListString();for (String str : strs) {int[] counts new int[26];int length str.length();for (int i 0; i length; i) {counts[str.charAt(i) - a];}// 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串作为哈希表的键StringBuffer sb new StringBuffer();for (int i 0; i 26; i) {if (counts[i] ! 0) {sb.append((char) (a i));sb.append(counts[i]);}}String key sb.toString();ListString list map.getOrDefault(key, new ArrayListString());list.add(str);map.put(key, list);}return new ArrayListListString(map.values());}
}作者力扣官方题解
链接https://leetcode.cn/problems/group-anagrams/solutions/520469/zi-mu-yi-wei-ci-fen-zu-by-leetcode-solut-gyoc/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。自我总结: 对于hash类题目还是尽量不要自己创建hash方法去计算hash值你以为的独一无二的hash方法总能被测试用力暴捶。尽量从题目描述中去找到一些独特之处作为hashmap的键。例如这一次使用排序后的字符串或者每个字符出现的次数都可以作为键。
如何在函数方法上新建对象 直接和新建对象一样的方法new
HashMap的contain方法有哪些。 containsKey(),containsValue()
如何收集HashMap的所有value值作为一个集合返回。
new ArrayListT(map.values()) // T与map的value类型要统一HashMap根据键取值的方法.
map.get(key)List list new List();错误的定义集合方法因为List是一个接口不能有实现类。
List集合修改某个位置的值
list.set(index,newValue);字符串转为字符数组的方法
char[] charArray str.toCharArray();
