国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

49. Group Anagrams and 249. Group Shifted Strings

cppowboy / 2229人閱讀

摘要:也就是同構異形體。特點是有相同數量的組成。素數可以素數表。這里使用而不是可以避免最后從導出結果的時間。修改了和得到的方法,其他都一樣。但是會有解不了的地方。還有個特殊情況就是不是一組。如果數字編碼出來都是如果用編碼,出現的就是。

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 {
    HashMap map;
    
    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);
    }
}

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/66925.html

相關文章

  • 249. Group Shifted String

    摘要:題目解答在為負數的時候,當經過的時候,數值大小會很大得反轉 題目: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 -> ....

    JerryZou 評論0 收藏0
  • 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],...

    wangtdgoodluck 評論0 收藏0
  • leetcode 49 Group Anagrams

    摘要:不需要關注輸出的順序,所有的輸入都是小寫。的就是經過排序后的字符數組所對應的字符串。因為不需要考慮輸出的順序,所以遍歷完直接輸出中的所有值即可。解法邊界情況判斷如果存在相同組成的元素 題目詳情 Given an array of strings, group anagrams together.題目要求輸入一個字符串數組,我們要將由同樣字母組成的字符串整理到一起,然后以如下例子中的格式...

    陳偉 評論0 收藏0
  • leetcode49 Group Anagrams

    摘要:同時使用方法將數組轉化為并利用的直接比較兩個字符串是否相等。通過這種方法效率值提高了不少。 題目要求 Given an array of strings, group anagrams together. For example, given: [eat, tea, tan, ate, nat, bat], Return: [ [ate, eat,tea], [nat,t...

    sunsmell 評論0 收藏0
  • [Leetcode] Group Anagrams 變形詞

    摘要:我們將每個詞排序后,根據這個鍵值,找到哈希表中相應的列表,并添加進去。 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...

    Lin_YT 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<