LeetCode(14) -- 500, 501,

P500. Keyboard Row (Easy)

我们知道，美式键盘的字母有三行。给一个字符串数组，找出那些能用键盘上一行按键就能打出来的单词。

Input: ["Hello", "Alaska", "Dad", "Peace"]
Output: ["Alaska", "Dad"]
因为只需要第二行就能打出来

我的思路

把所有的字母对应的行数存到一个数组里，用ASCII码作为索引，这样只要给一个字母就能立即找到它在第几行，如果都相等就返回到结果集中。

从大写字母A(65)到小写字母z(122)一共有58个字符，除了26个字母，大小写52个字母外，中间还有6个其他的字符。

我的代码

public class E_500_KeyboardRow {
    public String[] findWords(String[] words) {
        int[] rowNumbers = new int[58];
        rowNumbers[0] = 2; rowNumbers[1] = 3; rowNumbers[2] = 3; rowNumbers[3] = 2; rowNumbers[4] = 1;
        rowNumbers[5] = 2; rowNumbers[6] = 2; rowNumbers[7] = 2; rowNumbers[8] = 1; rowNumbers[9] = 2;
        rowNumbers[10] = 2; rowNumbers[11] = 2; rowNumbers[12] = 3; rowNumbers[13] = 3; rowNumbers[14] = 1;
        rowNumbers[15] = 1; rowNumbers[16] = 1; rowNumbers[17] = 1; rowNumbers[18] = 2; rowNumbers[19] = 1;
        rowNumbers[20] = 1; rowNumbers[21] = 3; rowNumbers[22] = 1; rowNumbers[23] = 3; rowNumbers[24] = 1;
        rowNumbers[25] = 3;

        rowNumbers[32] = 2; rowNumbers[33] = 3; rowNumbers[34] = 3; rowNumbers[35] = 2; rowNumbers[36] = 1;
        rowNumbers[37] = 2; rowNumbers[38] = 2; rowNumbers[39] = 2; rowNumbers[40] = 1; rowNumbers[41] = 2;
        rowNumbers[42] = 2; rowNumbers[43] = 2; rowNumbers[44] = 3; rowNumbers[45] = 3; rowNumbers[46] = 1;
        rowNumbers[47] = 1; rowNumbers[48] = 1; rowNumbers[49] = 1; rowNumbers[50] = 2; rowNumbers[51] = 1;
        rowNumbers[52] = 1; rowNumbers[53] = 3; rowNumbers[54] = 1; rowNumbers[55] = 3; rowNumbers[56] = 1;
        rowNumbers[57] = 3;
        ArrayList<String> res = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            boolean isInOneRow = true;
            for (int j = 1; j < words[i].length(); j++) {
                if (rowNumbers[words[i].charAt(j) - 'A'] != rowNumbers[words[i].charAt(j-1) - 'A']) {
                    isInOneRow = false;
                    break;
                }
            }
            if (isInOneRow) {
                res.add(words[i]);
            }
        }
        return res.toArray(new String[0]);
    }
}

100%

最优解

class Solution {
    public String[] findWords(String[] words) {
        int[] R = {2,3,3,2,1,2,2,2,1,2,2,2,3,3,1,1,1,1,2,1,1,3,1,3,1,3};
        List<String> res = new ArrayList<>();
        for (String w: words) {
            boolean able = true;
            int line, l;
            if (w.length() >= 1) {
                if (w.charAt(0) <= 'Z') {
                    l = 0;
                } else {
                    l = 1;
                }
                line = R[(int)(w.charAt(0) - 'A' - l * ('a' - 'A'))];
                for (int i = 1; i < w.length() && able; ++i) {
                    if (w.charAt(i) <= 'Z') {
                        l = 0;
                    } else {
                        l = 1;
                    }
                    if (line != R[(int)(w.charAt(i)- 'A' - l * ('a' - 'A'))]) {
                        able = false;
                    }
                }
            }
            if (able) {
                res.add(w);
            }
        }
        String[] ress = new String[res.size()];
        for (int i=0;i<res.size();++i) {
            ress[i]=res.get(i);
        }

        return ress;
    }
}

一开始只初始化26个字母。 设置一个参数l，如果第一个字符是大写字母，l = 0, 否则 l = 1. 最后再看第一个字母在第几行。接着遍历这个单词的所有字母，如果不在这一行，able = false.

我的代码初始化时太蠢，而且判断是否在一行时，可以优化一下。

P501. Find Mode in Binary Search Tree (Easy)

给一个有重复值的BST, 找出所有的众数（出现次数最多的数）。

我的思路

因为是BST，所以重复的数一定是连着的。只要用递归返回它的长度即可。

写代码时发现刚才思路不清。每个节点的众数和它的子节点的众数是什么关系呢？我必须知道子节点每个数出现了多少次，然后再根据当前节点的值，看众数是否发生了改变。所以辅助方法应该返回一个HashMap, 记录下所有出现过的数的次数。

我的代码

public class E_501_FindModeInBST {

    private List<Integer> list = new ArrayList<>();

    public int[] findMode(TreeNode root) {
        HashMap<Integer, Integer> map = getMap(root);
        int max = Integer.MIN_VALUE;
        ArrayList<Integer> modes = new ArrayList<>();
        for (Integer value : map.values()) {
            if (value > max) {
                max = value;
            }
        }
        for (Integer integer : map.keySet()) {
            if (map.get(integer) == max) {
                modes.add(integer);
            }
        }
        int[] res = new int[modes.size()];
        for (int i = 0; i < modes.size(); i++) {
            res[i] = modes.get(i);
        }
        return res;
    }

    private HashMap<Integer, Integer> getMap(TreeNode root) {
        HashMap<Integer, Integer> map = new HashMap<>();
        if (root == null) {
            return map;
        }
        HashMap<Integer, Integer> leftMap = getMap(root.left);
        HashMap<Integer, Integer> rightMap = getMap(root.right);
        map.putAll(leftMap);
        rightMap.forEach((k,v) -> map.merge(k,v,Integer::sum));
        int val = root.val;
        if (map.containsKey(val)) {
            map.put(val, map.get(val) + 1);
        } else {
            map.put(val, 1);
        }
        return map;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        TreeNode left = root.left = new TreeNode(3);
        TreeNode right = root.right = new TreeNode(6);
        left.left = new TreeNode(2);
        left.right = new TreeNode(4);
        left = right.left = new TreeNode(6);
        right = right.right = new TreeNode(7);
        left.left = new TreeNode(4);
        right.left = new TreeNode(4);
        right.right = new TreeNode(6);

        new E_501_FindModeInBST().findMode(root);
    }
}

5%

最优解

class Solution {
    private List<Integer> temp = new ArrayList();
    private int count = 0;
    private TreeNode prev = null;
    private int prevC = 0;
    public int[] findMode(TreeNode root) {
        if (root == null) {
            return new int[]{};
        }
        helper(root);
        int[] res = new int[temp.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = temp.get(i);
        }
        return res;
    }

    private void helper(TreeNode node) {
        if (node == null) {
            return;
        }
        helper(node.left);
        if (prev != null && prev.val == node.val) {
            prevC ++;
        }else{
            prevC = 1;
        }
        if (prevC > count) {
            count = prevC;
            temp = new ArrayList();
        }
        if (prevC == count) {
            temp.add(node.val);
        }
        prev = node;
        helper(node.right);
    }
}

因为是BST，所以即使有重复的值，通过中序遍历也一定能维持从小到大的顺序。

那么只需要记录下来前一个数，以及前面的最大次数，按要求更新结果集即可。

自己重写的代码

public class E_501_FindModeInBST {

    private List<Integer> res = new ArrayList<>();
    private int count = 0;
    private int max = 0;
    private Integer prev = null;

    public int[] findMode(TreeNode root) {
        dfs(root);
        int[] array = new int[res.size()];
        for (int i = 0; i < array.length; i++) {
            array[i] = res.get(i);
        }
        return array;
    }

    private void dfs(TreeNode node) {
        if (node == null) {
            return;
        }

        dfs(node.left);

        if (prev == null) {
            prev = node.val;
            count = 1;
        } else if (prev == node.val){
            count++;
        } else {
            count = 1;
            prev = node.val;
        }

        if (count > max) {
            max = count;
            res.clear();
            res.add(node.val);
        } else if (count == max) {
            res.add(node.val);
        }
        dfs(node.right);
    }
}