摘要:也就是同构异形体。特点是有相同数量的组成。素数可以素数表。这里使用而不是可以避免最后从导出结果的时间。修改了和得到的方法,其他都一样。但是会有解不了的地方。还有个特殊情况就是不是一组。如果数字编码出来都是如果用编码,出现的就是。
49 Group Anagrams
Given an array of strings, group anagrams together. For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], Return: [ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ]
Anagrams也就是同构异形体。特点是string有相同数量的char组成。 有两种方法,一直是把每个单词sort, 相同的anagrams肯定拥有同样的key. 时间复杂度O(klogk). 另一种方法,利用素数相乘,26个字母对应最小的26个素数,一个anagrams有唯一的key. 时间复杂度O(k).
1 素数相乘得到key。 (素数可以google素数表。)
public class Solution { public List> groupAnagrams(String[] strs) { int[] primes = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101}; List
> res = new ArrayList
>(); HashMap
map = new HashMap<>(); // key, position in array // 这里使用HashMap 而不是 HashMap > 可以避免最后从Map导出结果的时间。 for(String str:strs){ int key = 1; for(char c: str.toCharArray()){ key *= primes[c-"a"]; } List t; if(map.containsKey(key)){ t = res.get(map.get(key)); } else { t = new ArrayList (); map.put(key, res.size()); res.add(t); } t.add(str); } return res; } }
2 sort
public class Solution { public List> groupAnagrams(String[] strs) { List
> res = new ArrayList
>(); HashMap
map = new HashMap<>(); // key, position in array for(String str:strs){ // 修改了hashmap和得到Key的方法, 其他都一样。 char[] c = str.toCharArray(); Arrays.sort(c); String key = String.valueOf(c); List t; if(map.containsKey(key)){ t = res.get(map.get(key)); } else { t = new ArrayList (); map.put(key, res.size()); res.add(t); } t.add(str); } return res; } }
249 Group Shifted Strings
For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"], A solution is: [ ["abc","bcd","xyz"], ["az","ba"], ["acef"], ["a","z"] ]
拿"abc","bcd","xyz"这组举例子。 "abc": "b"-"a" = 1, "c"-"a" = 2, 012 "bcd": "c"-"b" = 1, "d"-"c" = 2, 012 "xyz": "y"-"x" = 1, "z"-"x" = 2, 012 如果用数字做Key,上面都是12。但是会有解不了的地方。 还有个特殊情况就是"a", "aa", "aaa"不是一组。如果数字编码出来都是0. 如果用string编码,出现的就是0, 00, 000。就可以区分了。
public class Solution { public List> groupStrings(String[] strings) { HashMap
> map = new HashMap<>(); for(String s: strings){ String key = getKey(s); List value = map.get(key); if(value == null){ value = new ArrayList<>(); map.put(key, value); } value.add(s); } List > res = new ArrayList<>(); for(List
list: map.values()){ Collections.sort(list); // dont forget to sort. res.add(list); } return res; } private String getKey(String s){ int[] arr = new int[s.length()]; for(int i = 1; i < s.length(); i++){ arr[i] = s.charAt(i)-s.charAt(0) < 0? (s.charAt(i)-s.charAt(0) + 26): (s.charAt(i)-s.charAt(0)); } return Arrays.toString(arr); } }
288 Unique Word Abbreviation
a) it --> it (no abbreviation) 1 b) d|o|g --> d1g 1 1 1 1---5----0----5--8 c) i|nternationalizatio|n --> i18n 1 1---5----0 d) l|ocalizatio|n --> l10n
public class ValidWordAbbr { HashMapmap; public ValidWordAbbr(String[] dictionary) { map = new HashMap<>(); for(String word : dictionary){ String key = getKey(word); if(map.containsKey(key)){ if(!map.get(key).equals(word)){ map.put(key, ""); } } else { map.put(key, word); } } } public boolean isUnique(String word) { String key = getKey(word); return !map.containsKey(key) || map.get(key).equals(word); } public String getKey(String word){ if(word.length() <= 2) return word; return word.charAt(0) + Integer.toString(word.length()-2) + word.charAt(word.length()-1); } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/66925.html
摘要:题目解答在为负数的时候,当经过的时候,数值大小会很大得反转 题目:Given a string, we can shift each of its letter to its successive letter, for example: abc -> bcd. We can keep shifting which forms the sequence: abc -> bcd -> ....
摘要:题目解答遇到这种要求一个的集合,首先想到的就是。那么被的作为把有同样的以的形式放到里,然后输出。 题目:Given an array of strings, group anagrams together. For example, given: [eat, tea, tan, ate, nat, bat], Return: [ [ate, eat,tea], [nat,tan],...
摘要:不需要关注输出的顺序,所有的输入都是小写。的就是经过排序后的字符数组所对应的字符串。因为不需要考虑输出的顺序,所以遍历完直接输出中的所有值即可。解法边界情况判断如果存在相同组成的元素 题目详情 Given an array of strings, group anagrams together.题目要求输入一个字符串数组,我们要将由同样字母组成的字符串整理到一起,然后以如下例子中的格式...
摘要:同时使用方法将数组转化为并利用的直接比较两个字符串是否相等。通过这种方法效率值提高了不少。 题目要求 Given an array of strings, group anagrams together. For example, given: [eat, tea, tan, ate, nat, bat], Return: [ [ate, eat,tea], [nat,t...
摘要:我们将每个词排序后,根据这个键值,找到哈希表中相应的列表,并添加进去。 Group Anagrams 最新更新请见:https://yanjia.me/zh/2019/01/... Given an array of strings, group anagrams together. For example, given: [eat, tea, tan, ate, nat, bat...
阅读 1708·2021-11-18 13:20
阅读 1109·2021-10-11 10:59
阅读 2938·2021-08-24 10:01
阅读 3483·2019-08-29 14:21
阅读 3321·2019-08-29 14:15
阅读 3497·2019-08-26 12:23
阅读 3320·2019-08-26 11:46
阅读 3324·2019-08-26 11:35