LeetCode(3) -- 242, 257, 263

LeetCode Day 3:

P242. Valid Anagram (Easy)

给出两个字符串s,t, 判断它们是否字母相同顺序不同。

我的思路

用每个字母在ASCII表中的位置作为索引，给每个字母出现计数。比较两个字符串计数的次数是否一样。

我一开始不确定是否只有26个小写字母，所以建了一个长度为128的数组用来存放所有可能的ASCII字符。看了一眼答案，只有26个小写字母，这就简单多了。另外借鉴了一下答案用S做加法，用T做减法，最后查看是否全是0。

我的代码

public class E_242_ValidAnagram {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] sChar = s.toCharArray();
        char[] tChar = t.toCharArray();
        int[] charsNumber = new int[26];
        for (int i = 0; i < sChar.length; i++) {
            charsNumber[sChar[i]-'a']++;
            charsNumber[tChar[i]-'a']--;
        }
        for (int i = 0; i < charsNumber.length; i++) {
            if (charsNumber[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

超过93%

最优解：

class Solution {
    public boolean isAnagram(String s, String t) {
         if (s == null || t == null) return false;

        if (s.length() != t.length()) return false;

        int[] counts = new int[26];

        for (char c : s.toCharArray()) {
            counts[c-'a']++;
        }

        for (char c : t.toCharArray()) {
            counts[c-'a']--;
        }

        for (int p : counts) {
            if(p!=0) return false;
        }

        return true;
    }
}

感觉跟我的代码没什么差别。

P257. Binary Tree Paths (Easy)

二叉树，返回所有根节点到叶节点的路径。

我的思路

递归遍历，拼装字符串。每个节点都去检查左右子节点是否为空，如果全是空，就把当前路径添加到List中。如果某一个子节点不为空，就把它的值拼接到当前路径下，并递归这个子树。

我的代码

public class E_257_BinaryTreePaths {
    List<String> list = new ArrayList<String>();

    public List<String> binaryTreePaths(TreeNode root) {
        if (root == null) {
            return list;
        }
        concatenate(root, String.valueOf(root.val));
        return list;
    }

    private void concatenate(TreeNode root, String path) {
        if (root.left == null && root.right == null) {
            list.add(path);
        }
        if (root.left != null) {
            concatenate(root.left, path + "->" + root.left.val );
        }
        if (root.right != null) {
            concatenate(root.right, path + "->" + root.right.val );
        }
    }
}

超过100%

最优解

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        List<String> res = new ArrayList<>();
        Helper(root, sb, res);
        return res;
    }

    public void Helper(TreeNode root, StringBuilder sb, List<String>res){
        if(root==null){
            return;
        }

        if(root.left==null&&root.right==null){
            int ori=sb.length();
            sb.append(root.val);
            res.add(sb.toString());
            sb.setLength(ori);
            return;
        }
        int ori=sb.length();
        sb.append(root.val);
        sb.append("->");
        Helper(root.left,sb,res);
        Helper(root.right,sb,res);
        sb.setLength(ori);
    }
}

P263. Ugly Number (Easy)

判断一个正整数的质因子是否只含有2，3，5。

我的思路

反复除以2，3，5，直到无法整除为止。然后判断它是否是1。

我的代码

public class E_263_UglyNumber {
    public boolean isUgly(int num) {
        while (num > 1 && num % 2 == 0) {
            num = num / 2;
        }
        while (num > 2 && num % 3 == 0) {
            num = num / 3;
        }
        while (num > 4 && num % 5 == 0) {
            num = num / 5;
        }
        return num == 1;
    }
}

超过100%

最优解

class Solution {
    public boolean isUgly(int num) {
        if (num <= 0) {
            return false;
        }
        while (num % 2 == 0) {
            num = num / 2;
        }
        while (num % 3 == 0) {
            num = num / 3;
        }
        while (num % 5 == 0) {
            num = num / 5;
        }
        return num == 1;
    }
}

看完答案发现其实不需要检查是否大于2，3，5，因为如果小于这个数，除以它的余数不是零，也就不需要讨论了。