Remove Element

Problem: Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Thinking: We are only moving elements to the left, everywhere in between left and right pointers does not matter anymore because we will ignore them anyway.


public class Solution {
    public int removeElement(int[] A, int elem) {
        if (A.length == 0) return 0;
        int position = 0;
        for (int i = 0; i < A.length; i++) {
            A[position++] = A[i];
            if (A[i] == elem) position--;
        }
        return position;
    }
}
Advertisements

Valid Parentheses

Problem:  Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Thinking:

Assumption: {[()]}() is valid.

Since there are only brackets in the string, we can easily make assumption that if the length of the string is not an even number, there must be a lonely parenthesis that is not valid.

Look at the pattern, if we have one opening bracket, then if it is valid, there must be a closing bracket. And if it is valid, the closing bracket is gonna be checked after everything is checked in this corresponding bracket. Therefore it is a FIFO behavior, because we’re always checking the closest correspondence. Therefore using a stack to check which one is nearest is ideal. At the end, we just need to check if there is anything left in the stack.

 

 


public class Solution {
    public boolean isValid(String s) {
        if (s == null || s.length() ==0) return true;
        if (s.length() % 2 != 0) return false;
        
        Stack stack = new Stack();
        Map map = new HashMap();
        
        map.put('(', ')');
        map.put('{', '}');
        map.put('[', ']');
        
        for (int i = 0; i < s.length(); i++) {
            char current = s.charAt(i);
            Character correspondence = map.get(current);
            if (!stack.empty() && current == stack.peek()) {
                stack.pop();
            } else if (correspondence != null) {
                stack.push(correspondence);
            } else {
                return false;
            }
        }
        
        return stack.empty();
        
        
    }
}

HashMap vs. HashTable

When come to a time you need to choose from HashMap and HashTable, here is the differences.

1. HashMap is faster in single thread environment because it is not thread safe. On the other hand HashTable is thread safe, but performs slower than HashMap in single thread environment. Therefore for technical questions sake, mostly it is wise to choose HashMap.

2. HashMap allows null values whereas HashTable does not. Therefore if want to use a HashMap to check if a key has a correspondence, it will simply return null if there is no such correspondence.

3. “The third significant difference between HashMap vs HashTable is that Iterator in the HashMap is a fail-fast iterator while the enumerator for the HashTable is not and throw ConcurrentModificationException if any other Thread modifies the map structurally by adding or removing any element except Iterator’s own remove() method. ” – quote from MANISH CHHABRA’s blog. Therefore if in the case wanting to predict iteration order, HashMap can be swapped by one of its subclass LinkedHashMap.

Basically, unless synchronization is a issue, normally HashMap is a wiser choice.

Climbing Stairs

Problem: You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Thinking: this is a question reforms Fibonacci numbers. The reason is that consider we have n stairs, then there are two subproblems we can accomplish such task. One is take one step on this level, which leaves the rest n-1 stairs, or we can take 2 steps this level, which leaves that rest n-2 stairs.

Then this routine goes on and on until we have one stairs and no stairs, which both have only one way to climb. Therefore it is identical to Fibonacci numbers. For space complexity, use dynamic programming to solve it.


public class Solution {
    public int climbStairs(int n) {
        int i = 1;
        int j = 1;
        
        for (int x = 0; x < n - 1; x++) {
            int temp = i + j;
            i = j;
            j = temp;
        }
        
        return j;
    }
}

Remove Duplicates from Sorted List

Such a silly mistake I made.

Problem: Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return head;
        if (head.next == null) return head;
        ListNode current = head;
        ListNode nextOne = head.next;
        
        while(true) {
            
            if (current.val == nextOne.val) {
                ListNode temp = nextOne.next;
                current.next = temp;
                nextOne = temp;
            }else{
                current = current.next;
                
                nextOne = nextOne.next;
            }
            
            if (nextOne == null) break;
        }
        
        return head;
    }
}

Longest Common Prefix

Problem: Write a function to find the longest common prefix string amongst an array of strings.

 


public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0 || strs[0] == null || strs[0].length() == 0) return "";
        
        StringBuilder sb = new StringBuilder();
        
        int shortestLen = strs[0].length();
        
        for (int i = 1; i < strs.length; i++) {
            if (strs[i].length() == 0) return "";
            if (strs[i].length() < shortestLen) shortestLen = strs[i].length();
        }
        
        for (int i = 0; i < shortestLen; i++) {
            boolean flag = true;
            char current = strs[0].charAt(i);
            for (int j = 0; j < strs.length; j++) {
                if (strs[j].charAt(i) != current) {
                    flag = false;
                    break;
                }
            }
            if (!flag){
                break;
            }
            sb.append(current);
            
        }
        
        return sb.toString();
        
    }
}

Roman to Integer

Problem:

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

This problem is not hard on programming, but hard on if you know how Roman numbers work.

 


public class Solution {
    public int romanToInt(String s) {
        if (s==null) return 0;
        
        int sum = 0;
        
        for (int i = s.length() - 1; i >= 0; i--) {
            switch(s.charAt(i)){
                case 'I':
                    sum += (sum >= 5? -1 : 1);
                    break;
                case 'V':
                    sum += 5;
                    break;
                case 'X':
                    sum += (sum >= 50? -10 : 10);
                    break;
                case 'L':
                    sum += 50;
                    break;
                case 'C':
                    sum += (sum >= 500? -100 : 100);
                    break;
                case 'D':
                    sum += 500;
                    break;
                case 'M':
                    sum += 1000;
                    break;
            }
        }
        
        return sum;
    }
}

Reverse Integer

Problem:

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

Comment:

If the integer’s last digit is 0, what should the output be? ie, cases such as 10, 100. — Assume as 01 and 001

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases? — To return some default value, however leetcode does not have a case that causes overflow.

Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).

 


public class Solution {
    public int reverse(int x) {
        String X = Integer.toString(x);
        
        StringBuilder sb = new StringBuilder();
        
        int start = 0;
        
        if (X.charAt(start) == '-') {
            sb.append('-');
            start++;
        }
        
        for (int i = X.length() - 1; i >= start; i--) {
            sb.append(X.charAt(i));
        }
        
        return Integer.valueOf(sb.toString());
        
    }
}

Merge Sorted Array

If use a new array, this problem is fairly easy. The point, to my understanding, is how to do it in place.

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and nrespectively.


public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        if (n == 0) return;
        
        int pointer = m + n - 1;
        
        m--;
        n--;
        
        while (m >= 0 && n >= 0){
            if (A[m] > B[n]) {
                A[pointer--] = A[m--];
            }else{
                A[pointer--] = B[n--];
            }
        }
        while (m >= 0) {
            A[pointer--] = A[m--];
        }
        while (n >= 0) {
            A[pointer--] = B[n--];
        }
    }
}

In which, pointer can also be replaced by m+n. Therefore not even using new variables.

Same Tree

Was I saying that Max Depth of Binary tree is the easiest? I was wrong.

Problem: Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.


/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        //After this two lines, the only case that left is p != null && q != null
        
        if (p.val == q.val) return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        else return false;
    }
}