LeetCode(55) -- 958, 5, 819,

P958. Check Completeness of a Binary Tree (Easy)

Given a binary tree, determine if it is a complete binary tree.

最优解

public class M_958_CheckCompletenessofaBinaryTree {
    public boolean isCompleteTree(TreeNode root) {
        int total = countTotal(root);
        return isValid(root, 1, total);
    }

    private int countTotal(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + countTotal(root.left) + countTotal(root.right);
    }

    private boolean isValid (TreeNode node, int index, int total) {
        if (node == null) {
            return true;
        }
        if (index > total) {
            return false;
        }
        return isValid(node.left, index * 2, total) &&
                isValid(node.right, index * 2 + 1, total);
    }
}

一个complete tree, 每个节点的索引序号都有如下特征：

如果根节点序号为1，那么每个节点的左子节点，都是当前节点的两倍， 右子节点都是当然节点的2n+1

P5. Longest Palindromic Substring (Easy)

一个字符串，找出其中最长的palindrom子数组。

我的思路

遍历数组，每个字母向两侧扩散，找出最长的palindrom，然后随时更新最长的记录。

我的代码

class Solution {
    public String longestPalindrome(String s) {
        if (s.equals("")) {
            return "";
        }
        int longest = 0;
        int start = 0, end = 0;
        char[] chars = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            int l = i, r = i;
            while (l >= 0 && r < s.length() && chars[l] == chars[r]) {
                if (r - l + 1 > longest) {
                    longest = r - l + 1;
                    start = l;
                    end = r;
                }
                l--;
                r++;
            }
            if (i + 1 < s.length() && chars[i] == chars[i + 1]) {
                l = i;
                r = i + 1;
                while (l >= 0 && r < s.length() && chars[l] == chars[r]) {
                    if (r - l + 1 > longest) {
                        longest = r - l + 1;
                        start = l;
                        end = r;
                    }
                    l--;
                    r++;
                }
            }
        }
        return s.substring(start, end + 1);
    }
}

51%

最优解

class Solution {
    String result = "";
    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0) return s;
        int start = 0;
        while(start < s.length()) {
            start = helper(start, s);
        }
        return result;
    }

    public int helper(int start, String s) {
        int firstDif = start + 1;
        while(firstDif < s.length() && s.charAt(start) == s.charAt(firstDif)) {
            firstDif++;
        }
        int right = firstDif;
        int left = start - 1;
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        if(right - left - 1 > result.length()) {
            result = s.substring(left + 1, right);
        }
        return firstDif;

    }
}

这个方法其实也是向两边扩散，但是实现方法略有不同，先向右找到第一个不一样的字母，然后向左边移动一格，这样的话，夹在中间的那些字母完全一样，无论有奇数个还是偶数个，只需要继续向两侧比较就好了。

P819. Most Common Word (Easy)

给一段话，找出频率最高的单词，同时要排除那些禁止的单词。

我的思路

用Trie，每个节点包含一个banned属性和一个freq属性。每次走完一个单词，如果不是禁止的，就把它的freq加1，然后如果大于最大的freq，就把这个单词存起来，并且更新最大频率。

最优解

class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {
        Trie root = new Trie();
        Trie cur = root;
        for (String ban : banned) {
            for (char c : ban.toCharArray()) {
                if (cur.next[c - 'a'] == null) {
                    cur.next[c - 'a'] = new Trie();
                }
                cur = cur.next[c - 'a'];
            }
            cur.banned = true;
            cur = root;
        }
        int maxFreq = 0;
        String ans = "";
        String para = paragraph.toLowerCase();
        char[] chars = para.toCharArray();
        int length = chars.length;
        int j = 0;
        for (int i = 0; i < length; i = j + 1) {
            while (i < length && !Character.isLetter(chars[i])) {
                i++;
            }
            for (j = i; j < length && Character.isLetter(chars[j]); j++) {
                char c = chars[j];
                if (cur.next[c - 'a'] == null) {
                    cur.next[c - 'a'] = new Trie();
                }
                cur = cur.next[c - 'a'];
            }
            cur.freq++;
            if (cur.freq > maxFreq && !cur.banned) {
                maxFreq = cur.freq;
                ans = para.substring(i, j);
            }
            cur = root;
        }

        return ans;
    }

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