LeetCode(34) -- 804, 806, 811, 812, 819

P804. Unique Morse Code Words (Easy)

26个字母都可以用摩斯密码来表示。

我的思路

只想到暴力求解：根据密码表翻译成摩斯密码，然后放到HashSet里，计数。想找摩斯密码的规律的话，看密码解密可能会有哪些字母的组合，这个难度有点大。。。

我的代码

public class E_804_UniqueMorseCodeWords {
    public int uniqueMorseRepresentations(String[] words) {
        String[] table = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",
                ".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        HashSet<String> set = new HashSet<>();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            char[] chars = word.toCharArray();
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < chars.length; j++) {
                sb.append(table[chars[j] - 'a']);
            }
            set.add(sb.toString());
        }
        return set.size();
    }
}

100% 看来也就如此了，也没什么更好的办法了。

最优解

class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String[] MORSE = {".-","-...","-.-.","-..",".","..-.","--.",
                         "....","..",".---","-.-",".-..","--","-.",
                         "---",".--.","--.-",".-.","...","-","..-",
                         "...-",".--","-..-","-.--","--.."};

        Set<String> seen = new HashSet();
        for (String word: words) {
            StringBuilder code = new StringBuilder();
            for (char c: word.toCharArray())
                code.append(MORSE[c - 'a']);
            seen.add(code.toString());
        }

        return seen.size();
    }
}

基本跟我完全一样。就是loop时没用fori，用了iter而已。

P806. Number of Lines To Write String (Easy)

写一个字符串，每个字母的宽度通过一个数组给出。每行的宽度是100个单位。判断写这个字符串需要几行，最后一行多宽。

我的思路

比较简单，每个字母去查一下表，把宽度累加起来即可。需要注意的是，不能简单地把总宽度算出来。因为到行尾有可能放不下一个字母了，就要换行。所有每次累加时要验证一下是否超过了100。

我的代码

public class E_806_NumberOfLinesToWriteString {
    public int[] numberOfLines(int[] widths, String S) {
        char[] chars = S.toCharArray();
        int lines = 1;
        int currentWidth = 0;
        for (char c : chars) {
            currentWidth += widths[c - 'a'];
            if (currentWidth > 100) {
                lines++;
                currentWidth = widths[c - 'a'];
            }
        }

        int[] ans = {lines, currentWidth};
        return ans;
    }
}

100%

最优解

class Solution {
    public int[] numberOfLines(int[] widths, String S) {
        int line = 1;
        int count = 0;
        for (int i = 0; i < S.length(); i++) {
            int w = widths[S.charAt(i) - 'a'];
            if (count + w > 100) {
                count = w;
                line++;
            } else {
                count += w;
            }
        }

        return new int[]{line, count};
    }
}

差不多。简单题基本上思路都一样。

P811. Subdomain Visit Count (Easy)

给一组字符串，用来表示每个域名的访问次数。比如”9001 discuss.leetcode.com”代表这个网址被访问了9001次。 访问域名时，其所有层级的父域名也被同时访问，比如leetcode.com和com。计算所有域名的访问次数。

我的思路

hashmap计数即可。

我的代码

public class E_811_SubdomainVisitCount {
    public List<String> subdomainVisits(String[] cpdomains) {
        HashMap<String, Integer> map = new HashMap<>();
        for (String cpdomain : cpdomains) {
            String[] split = cpdomain.split(" ");
            while (split[1].contains(".")) {
                map.put(split[1], Integer.parseInt(split[0]) + map.getOrDefault(split[1], 0));
                split[1] = split[1].substring(split[1].indexOf(".") + 1);
            }
            map.put(split[1], Integer.parseInt(split[0]) + map.getOrDefault(split[1], 0));
        }
        List<String> list = new ArrayList<>();
        for (Map.Entry<String, Integer> stringIntegerEntry : map.entrySet()) {
            list.add(stringIntegerEntry.getValue() + " " + stringIntegerEntry.getKey());
        }
        return list;
    }
}

68%

最优解

class Solution {
    public List<String> subdomainVisits(String[] cpdomains) {
        Map<String, DomainInfo> cmap = new HashMap<>();
        for (String cpdomain : cpdomains) {
            addCpDomain(cmap, cpdomain);
        }
        ArrayList<String> result = new ArrayList<>(cmap.size());
        for (Map.Entry<String, DomainInfo> e : cmap.entrySet()) {
            result.add(e.getValue().count + " " + e.getKey());
        }
        return result;
    }

    void addCpDomain(Map<String, DomainInfo> cmap, String cpdomain) {
        int spaceIndex = cpdomain.indexOf(' ');
        int count = Integer.parseInt(cpdomain.substring(0, spaceIndex));
        String domain = cpdomain.substring(spaceIndex + 1);
        addInfo(cmap.get(domain), cmap, count, domain);
    }

    DomainInfo addInfo(DomainInfo d, Map<String, DomainInfo> cmap, int count,
                       String domain) {
        if (d == null) {
            // there is nothing to do if the domain is null too
            if (domain == null) {
                return null;
            }
            final String updomain = getUpDomain(domain);
            d = new DomainInfo(count, addInfo(cmap.get(updomain), cmap, count, updomain));
            cmap.put(domain, d);
        } else {
            d.count += count;
            for (DomainInfo tmp = d.updomain; tmp != null; tmp = tmp.updomain) {
                tmp.count += count;
            }
        }
        return d;
    }

    String getUpDomain(String domain) {
        int dotIndex = domain.indexOf('.');
        if (dotIndex >= 0) {
            return domain.substring(dotIndex + 1);
        }
        return null;
    }

    static class DomainInfo {
        int count;
        DomainInfo updomain;

        DomainInfo(int count, DomainInfo updomain) {
            this.count = count;
            this.updomain = updomain;
        }
    }
}

P812. Largest Triangle Area (Easy)

在平面上有一些点，任意三个点，可以组成的三角形中，最大面积是多少。

答案

public class E_812_LargestTriangleArea {
    public double largestTriangleArea(int[][] points) {
        double ans = 0;
        int n = points.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    ans = Math.max(ans, area(points[i], points[j], points[k]));
                }
            }
        }
        return ans;
    }

    private double area(int[] P, int[] Q, int[] R) {
        return 0.5 * Math.abs(P[0] * Q[1] + Q[0] * R[1] + R[0] * P[1] -
                P[1] * Q[0] - Q[1] * R[0] - R[1] * P[0]);
    }
}

鞋带算法求面积。

P819. Most Common Word (Easy)

给一段文字，还有一组禁止的词。找出所有没被禁的词中，出现频率最高的一个。

我的思路

HashSet,HashMap

我的代码

public class E_819_MostCommonWord {
    public String mostCommonWord(String paragraph, String[] banned) {
        HashSet<String> set = new HashSet<>();
        Collections.addAll(set, banned);
        int max = 0;
        String ans = null;
        String lowerCase = paragraph.toLowerCase();
        String[] strings = lowerCase.split("[^\\w]");
        HashMap<String, Integer> map = new HashMap<>();
        for (String string : strings) {
            if (!string.equals("") && !set.contains(string)) {
                int count = map.getOrDefault(string, 0) + 1;
                if (count > max) {
                    max = count;
                    ans = string;
                }
                map.put(string, count);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        String[] banned = {"hit"};
        new E_819_MostCommonWord().mostCommonWord("Bob hit a ball, the hit BALL flew far after it was hit.", banned);
    }
}

24%

最优解

class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {
        //insert banned words into trie
        Trie root = new Trie();
        Trie cur = root;
        for(String b:banned){
            for(char c:b.toCharArray()){
                if(cur.next[c-'a'] == null){
                    cur.next[c-'a'] = new Trie();
                }
                cur = cur.next[c-'a'];
            }
            cur.ban = true;
            cur = root;
        }
        String maxWord = "";
        int maxFreq = 0;
        String para = paragraph.toLowerCase();
        char[] p = para.toCharArray();
        int n = p.length;
        int start = 0, end = 0;
        for(start = 0; start < n; start = end+1){
            //move past non alphabetic characters
            while(start < n && (p[start] < 'a' || p[start] > 'z')){
                start++;
            }
            for(end = start; end < n && p[end] >= 'a' && p[end] <= 'z'; end++){
                char c = p[end];
                if(cur.next[c-'a'] == null){
                    cur.next[c-'a'] = new Trie();
                }
                cur = cur.next[c-'a'];
            }
            cur.freq++;

            if(cur.freq > maxFreq && !cur.ban){
                maxFreq = cur.freq;
                maxWord = para.substring(start,end);
            }

            cur = root;
        }
        return maxWord;
    }
}

    public class Trie{
        Trie[] next = new Trie[26];
        boolean ban;
        int freq;
    }

答案：

class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {
        paragraph += ".";

        Set<String> banset = new HashSet();
        for (String word: banned) banset.add(word);
        Map<String, Integer> count = new HashMap();

        String ans = "";
        int ansfreq = 0;

        StringBuilder word = new StringBuilder();
        for (char c: paragraph.toCharArray()) {
            if (Character.isLetter(c)) {
                word.append(Character.toLowerCase(c));
            } else if (word.length() > 0) {
                String finalword = word.toString();
                if (!banset.contains(finalword)) {
                    count.put(finalword, count.getOrDefault(finalword, 0) + 1);
                    if (count.get(finalword) > ansfreq) {
                        ans = finalword;
                        ansfreq = count.get(finalword);
                    }
                }
                word = new StringBuilder();
            }
        }

        return ans;
    }
}