Weever's Road

Just another WordPress site

Category: Easy

242. Valid Anagram

242. Valid Anagram

Solution: if two String are anagram, they has some number of each letter. sort each String char, compare two String after sort.

1.sort

1
2
3
4
5
6
7
    public boolean isAnagram(String s, String t) {
        if(s == null && t == null) return true;
        if(s == null || t == null || s.length() != t.length()) return false;
        char[] ss = s.toCharArray(); Arrays.sort(ss);
        char[] tt = t.toCharArray(); Arrays.sort(tt);
        return String.valueOf(ss).equals(String.valueOf(tt));
    }

2.count:

100.Same Tree (Easy)

100. Same Tree

Solution: Recursive,
1.if both trees are null, then they are same
2.if one of them is null, they are not same
3.if they are not null and val is different, they are not same
Recursively check until last leafs on both left and(&&) right node

1
2
3
4
5
6
7
public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null)
            return true;
        if(p == null || q == null || p.val != q.val)
            return false;
        return isSameTree(p.left,q.left) && isSameTree(p.right, q.right);
    }

283. Move Zeroes (Easy)

238.Move Zeros

Solution: Compression with two pointers.

1
2
3
4
5
6
7
8
9
10
11
12
13
    public void moveZeroes(int[] nums) {
        if(nums == null || nums.length == 0)
            return;
        int current = 0, scan = 0;
        while(scan < nums.length){
            if(nums[scan] != 0)
                nums[current++] = nums[scan++];
            else
                scan++;
        }
        for(;current<nums.length;)
            nums[current++] = 0;
    }

226. Invert Binary Tree

226. Invert Binary Tree

Typical recursive.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
   public TreeNode invertTree(TreeNode root) {
        swap(root);
        return root;
   }
   
    private void swap(TreeNode root){
        if(root == null)
            return;
        swap(root.left);
        swap(root.right);
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }

104. Maximum Depth of Binary Tree (Easy)

104. Maximum Depth of Binary Tree
It’s simple depth first question using recursive to solve it.

1
2
3
4
5
6
7
8
9
10
11
public int maxDepth(TreeNode root) {
        return depth(root);
    }
   
    private int depth(TreeNode root){
        if(root == null)
            return 0;
        int left = depth(root.left) + 1;
        int right = depth(root.right) + 1;
        return Math.max(left,right);
    }

266. Palindrome Permutation (Easy)

Solution: here

1
2
3
4
5
6
7
8
9
10
11
 public boolean canPermutePalindrome(String s) {
     if(s == null)
       return false;
     Set<Character> set = new HashSet<Character>();
     for(char c : s.toCharArray()){
       if(!set.add(c)){
         set.remove(c);
       }
    }
     return set.size() <= 1;
   }

205. Isomorphic Strings (Easy)

205. Isomorphic Strings
1.Boundary condition, two strings length is not equals.
2.Solution: use Map to store two mapped Char, we should find the two mapped Char if it appears again in same index position. If they are new Char, store in map, but either one is already in Map, the return false.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean isIsomorphic(String s, String t) {
    if(s == null || t == null || s.length() != t.length())
        return false;
    Map<Character,Character> map = new HashMap<>();
    for(int i = 0; i&lt; s.length(); i++) {
        char sc = s.charAt(i);
        char tc = t.charAt(i);
        if(map.get(sc) == null ){
            if(map.containsValue(tc)) // if tc was already mapped
                return false;
            map.put(sc,tc);
        } else if(map.get(sc) != tc){
        return false;
        }
    }
    return true;
}

Powered by WordPress & Theme by Anders Norén