Weever's Road

Just another WordPress site

Month: November 2016 (Page 1 of 2)

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;
   }

292. Nim Game (Easy)

292. Nim Game

Solution: find here

1
2
3
public boolean canWinNim(int n) {
        return n % 4 != 0;
    }

344. Reverse String (Easy)

344. Reverse String

Solution: two pointer scan from both side, swap each other until middle position.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public String reverseString(String s) {
        if(s == null || s.length() == 1 )
            return s;
        char[] ss = s.toCharArray();
        int start = 0, end = s.length() - 1;
        while(start<end){
            char temp = ss[start];
            ss[start] = ss[end];
            ss[end] = temp;
            start++;
            end--;
        }
        return String.valueOf(ss);
    }

24. Swap Nodes in Pairs

24. Swap Nodes in Pairs

1. If no node or only one node, do not need swap.
2. New head start from second node, put a new point (java reference) as new list node head.
3. from head, if head has next, then swap this two node, second node points first node, and first node points to third node.
3. keep record of new second node as pre node, cause if we swap next pair, we need last pairs points to new pairs head after swap. we create pointer (java reference) every time in while loop, first step to set last pair tail (pre) points to this pair second node. After current pair swapped, update the pre to current pair tail.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode newHead = head.next;
        ListNode pre = new ListNode(0);
        while(head != null && head.next != null){
            ListNode first = head;
            ListNode second = head.next;
            pre.next = second;
            head = head.next.next;
            second.next=first;
            first.next = head;
            pre = first;
        }
        return newHead;
    }
}

365. Water and Jug Problem

365. Water and Jug Problem
It’s a pure math question, OMG, I am not math major, the only way is to remmber it.
Check B├ęzout’s identity and explain here.

1
2
3
4
5
6
7
    public boolean canMeasureWater(int x, int y, int z) {
        return x + y == z || (x + y > z ) && z % gcd(x,y) == 0;
    }
   
    private int gcd(int a,int b){
        return b==0? a: gcd(b,a%b);
    }

Page 1 of 2

Powered by WordPress & Theme by Anders Norén