LeetCode(33) -- 748, 754, 762, 766, 783

P748. Shortest Completing Word (Easy)

找出最短的包含有牌照里所有字母的单词，忽略大小写。

我的思路

先处理一下牌照，把数据清洗干净，有两个方案，一是形成一个小写26个字母的int数组，记录每个字母出现的次数。在单词中如果出现了某个字母，就去字母表中查找，如果有就减1，最后查一遍26个字母的次数是否都变成了0。

第二个方案是牌照做成一个List, 单词中的每个字母都到这个list里查一遍，包含的话就删掉，最后看它的长度是否变成了0。

因为本身牌照最多6个字母，单词也不超过15个字母。纠结了半天，感觉还是第一个方案会快一点。

我的代码

public class E_748_ShortestCompletingWord {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        int minLength = Integer.MAX_VALUE;
        String ans = null;
        int[] alphabet = new int[26];
        char[] chars = licensePlate.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] >= 65 && chars[i] <= 90) {
                alphabet[chars[i] - 65]++;
            } else if (chars[i] >= 97 && chars[i] <= 122) {
                alphabet[chars[i] - 97]++;
            }
        }
        for (int i = 0; i < words.length; i++) {
            int[] copyOfAlphabet = alphabet.clone();
            String word = words[i];
            char[] wordChars = word.toCharArray();
            for (int j = 0; j < wordChars.length; j++) {
                if (copyOfAlphabet[wordChars[j] - 97] > 0) {
                    copyOfAlphabet[wordChars[j] - 97]--;
                }
            }
            boolean complete = true;
            for (int j = 0; j < copyOfAlphabet.length; j++) {
                if (copyOfAlphabet[j] != 0) {
                    complete = false;
                }
            }
            if (complete && word.length() < minLength) {
                minLength = word.length();
                ans = word;
            }
        }
        return ans;
    }
}

47%

最优解

class Solution {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        char[] cs = licensePlate.toCharArray();
        int size = 0;
        StringBuilder sb = new StringBuilder();
        for (char c : cs) {
            char key = '0';
            if (c >= 97 && c <= 122) {
                key = c;
            } else if (c >= 65 && c <= 90) {
                key = (char)(c + 32);
            }
            if (key != '0') {
                sb.append(key);
            }

        }

        String check = sb.toString();
        String result = null;
        int lgth = Integer.MAX_VALUE;
        for (String word : words) {
            if (word.length() < lgth && judge(check, word)) {
                result = word;
                lgth = word.length();
            }
        }
        return result;
    }

    private boolean judge(String ck, String wd) {
        if (wd.length() < ck.length()) {
            return false;
        }
        int[] ls = new int[26];
        for (char c : wd.toCharArray()) {
            ls[c - 'a'] ++;
        }
        for (char c : ck.toCharArray()) {
            if (ls[c - 'a'] == 0) {
                return false;
            }
            ls[c - 'a'] --;
        }
        return true;
    }
}

他把牌照清洗后放到一个String里面，然后先把单词做成字母频率数组。再去查牌照中的每个字母，如果没有就直接返回false了。这样比我最后再查一遍是否全是0要方便。还有一点值得学习的是，先查长度，只有长度比最小值还小时，再去查。这样大部分长单词就根本不用查了。

P754. Reach a Number (Easy)

在一个数轴上，可向左或向右移动。第n次可移动n个单位。问最少多少步可以移动到目标值。

我的思路

我一开始想先移动到接近目标值的地方，再一步一步往右走。结果是错的。

看了答案，最重要的一个概念就是，向右加到某个值时如果超过了target，就要看它跟target差多少，也就是超出了多少。如果超出的是偶数，那就直接得到答案了。因为我们只需要把前面的某个数从正数改成负数，结果就会减掉一个偶数。

如果差奇数，就再往前走一步。如果依然差奇数，就再往前走一步，就必然差偶数了。

答案

class Solution {
    public int reachNumber(int target) {
        target = Math.abs(target);
        int k = 0;
        while (target > 0)
            target -= ++k;
        return target % 2 == 0 ? k : k + 1 + k % 2;
    }
}

最优解

class Solution {
    /** 参考花花  */
    public int reachNumber(int target) {
        target = Math.abs(target);
        int k = (int)Math.sqrt(target*2);
        while(sum(k) < target) k++;
        int d = sum(k)-target;
        if(d%2 == 0) return k;
        return k+1+(k%2);
    }
    /** 分析：
        math题目
        看数据规模，应该不能用BFS或racing car的方法
    */

    private int sum(int k) {
        return k*(k+1)/2;
    }
}

P762. Prime Number of Set Bits in Binary Representation (Easy)

给两个整数L和R，代表一个范围。求在这个范围内的整数中，换成二进制后1的个数为质数的数有几个

我的思路

把前31个数全列出来，发现每增加一位数，其实就是上面所有的结果分别加1。

我的代码

public class E_762_PrimeNumberOfSetBitsInBinaryRepresentation {
    public int countPrimeSetBits(int L, int R) {
        int count = 0;
        for (int i = L; i <= R; i++) {
            if(isPrime(setBits(i))) {
                count++;
            }
        }
        return count;
    }

    private int setBits(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        int power = 1;
        while (n - power >= 0) {
            power *= 2;
        }
        return setBits(n - power / 2) + 1;
    }

    private boolean isPrime(int n) {
        if(n < 2) return false;
        if(n == 2) return true;
        if(n % 2 == 0) return false;

        for(int i = 3; i * i <= n; i += 2) {
            if(n % i == 0) return false;
        }
        return true;
    }

}

11%

最优解

class Solution {
    public int countPrimeSetBits(int l, int r) {
        int cnt = 0;
        for (int i = l; i <= r; i++) {
            int bits = Integer.bitCount(i);
            cnt += (665772 & (1 << bits)) != 0 ? 1 : 0;
        }
        return cnt;
    }
}

答案

class Solution {
    public int countPrimeSetBits(int L, int R) {
        int ans = 0;
        for (int x = L; x <= R; ++x)
            if (isSmallPrime(Integer.bitCount(x)))
                ans++;
        return ans;
    }
    public boolean isSmallPrime(int x) {
        return (x == 2 || x == 3 || x == 5 || x == 7 ||
                x == 11 || x == 13 || x == 17 || x == 19);
    }
}

P766. Toeplitz Matrix (Easy)

矩阵，从左上到右下所有斜线的值都一样，就叫Toeplitz

我的思路

以第一行和第一列为起点，分别往右下方递归，确定这一条斜线值一样就返回true。所有斜线全是true，整个函数才返回true。

我的代码

class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            if (!oneLine(matrix, i, 0)) return false;
        }
        for (int i = 0; i < matrix[0].length; i++) {
            if (!oneLine(matrix, 0, i)) return false;
        }
        return true;
    }

    private boolean oneLine(int[][] matrix, int row, int col) {
        if (row >= matrix.length - 1 || col >= matrix[0].length - 1) return true;
        return matrix[row][col] == matrix[row + 1][col + 1] && oneLine(matrix, row + 1, col + 1);
    }
}

100%

最优解

class Solution {
    private boolean checkDR(int[][] matrix, int sr, int sc) {
        for (int i = sr; i < matrix.length - 1; i++) {
            for (int j = sc; j < matrix[i].length - 1; j++) {
                if (matrix[i + 1][j + 1] != matrix[i][j])
                    return false;
            }
        }
        return true;
    }

    public boolean isToeplitzMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        for (int i = m - 1; i >= 0; i--) {
            if (!checkDR(matrix, i, 0)) return false;
        }

        for (int i = 1; i < n; i++) {
            if (!checkDR(matrix, 0, i)) return false;
        }

        return true;
    }
}

答案

class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        for (int r = 0; r < matrix.length; ++r)
            for (int c = 0; c < matrix[0].length; ++c)
                if (r > 0 && c > 0 && matrix[r-1][c-1] != matrix[r][c])
                    return false;
        return true;
    }
}

P783. Minimum Distance Between BST Nodes (Easy)

返回一个BST任意两个节点的差的最小值。

我的思路

中序遍历然后记录下最小值。

我的代码

public class E_783_MinimumDistanceBetweenBSTNodes {
    int min = Integer.MAX_VALUE;
    Integer prev = null;
    public int minDiffInBST(TreeNode root) {
        inorder(root);
        return min;
    }

    private void inorder(TreeNode node) {
        if (node == null) {
            return;
        }
        inorder(node.left);
        if (prev == null) {
            prev = node.val;
        } else {
            if (node.val - prev < min) {
                min = node.val - prev;
            }
            prev = node.val;
        }
        inorder(node.right);
    }

}

100% 一次过

最优解

class Solution {
    Integer prev;
    int min = Integer.MAX_VALUE;
    public void inOrder(TreeNode root){
        if(root==null) return;
        inOrder(root.left);
        if(prev!=null){
            min = Math.min(min,Math.abs(root.val-prev));
        }
        prev=root.val;
        inOrder(root.right);
    }
    public int minDiffInBST(TreeNode root) {
        inOrder(root);
        return min;

    }
}

这个代码看着更漂亮，因为无论如何都要更新prev，只是当prev不是第一个时，我才去比较。