[LeetCode Java Solution] – String/DFS – Generate Parentheses

Problem:

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

Method:

How to understand DFS? Determine how many branches we have? For each branch, we call recursive helper method. So overall, we will find out all the solutions for one branch and then go to another branch and do the same thing.

Remember: in each level, we have to make sure the variables are not changed, since we still need to go to the next branch.

Code:

public class Solution {
    ArrayList<String> res = new ArrayList<String>();
    
    public ArrayList<String> generateParenthesis(int n) {
        if (n == 0) return res;
        helper(n, n, "");
        return res;
    }
    
    public void helper(int left, int right, String item){
        if (left > right) return;
        if (left == 0 && right == 0){
            res.add(item);
        }
        if (left > 0){
            helper(left-1, right, item + "(");
            // remember that one each level, you can't change the variables.
        }
        if (right > 0){
            helper(left, right-1, item + ")");
        }
    }
}

[LeetCode Java Solution] – LinkedList – Swap nodes in pairs

Problem:

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Method:

1. This is a singly linked list, so we have to keep two pointers. One is pre-temp, one is temp. And insert the node at temp.next between pre-temp and temp.

Code:

/**
 * 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) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pretemp = dummy;
        ListNode temp = head;
        
        
        while (temp != null && temp.next != null){
            // the following three lines of code are very important.
            pretemp.next = temp.next;
            temp.next = pretemp.next.next;
            pretemp.next.next = temp;
            
            pretemp = temp;
            temp = temp.next;
            
        }
        
        return dummy.next;
        
        
    }
}

[LeetCode Java Solution] – DFS – Sum Root to Leaf Numbers

Problem:

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Method:

1. Use recursive method to implement DFS. Every time we input a temp sum and current node, and return the new updated temp sum.

2. Use a integer res to store the final summation. And this integer variable has to be outside of the two method.

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 // make an external variable res to store the value. 
public class Solution {
    int res = 0;  // this has to be outside of the two methods.
    public int sumNumbers(TreeNode root) {
        if (root == null) return 0;
        sum(root, 0);
        return res;
    }
    
    public void sum(TreeNode root, int tmpsum){
        if (root.left == null && root.right == null){
            res += tmpsum*10 + root.val;
        }
        if (root.left != null){
            sum(root.left, tmpsum*10 + root.val);
        }
        if (root.right != null){
            sum(root.right, tmpsum*10 + root.val);
        }
    }
}

[LeetCode Java Solution] – Two Pointers / Math – Add Binary

Problem:

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

Method:

1. How to add binary number?

From the right to left. If two digits add up to 1 or 0, just put it as 1 or 0. If the two digits add up to 2, make the digit 0, and carry 1. If the two digits add up to 3, make the digit 1, and carry 1.

2. Please pay attention to the while condition.

3. Don’t forget to check carry at last.

Code:

public class Solution {
    public String addBinary(String a, String b) {
        int i = a.length() - 1 ;
        int j = b.length() - 1 ;
        int c = 0;//
        String s = "";
        
        while (i >= 0 || j >= 0){
            int digit = 0;
            if (i >= 0){
                digit += a.charAt(i) - '0';
                i--;
            }
            if (j >= 0){
                digit += b.charAt(j) - '0';
                j--;
            }
            if (c != 0){
                digit += c;
            }
            
            if (digit == 0){
                s = "0" + s;
                c = 0;
            }else if (digit == 1 ){
                s = 1 + s;
                c = 0;
            }else if (digit == 2){
                s = "0" + s;
                c = 1;
            }else if (digit == 3){
                s = "1" + s;
                c = 1;
            }
        }
        
        if (c != 0){
            s = "1" + s;
        }
        
        return s;
    }
}

Method 2:

We could also use the StringBuilder to store the result. The related methods are the following:

1.

StringBuilder

append(char c) Appends the string representation of the char argument to this sequence.

2.

StringBuilder

insert(int offset, char c) Inserts the string representation of the char argument into this sequence.

3.

StringBuilder

reverse() Causes this character sequence to be replaced by the reverse of the sequence.

[LeetCode Java Solution] – Array/ Two Pointers – 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.

Method 1: 

Swap the element with given value with the last element in the array. Keep track of the last element in the array.

Code for method 1:

public class Solution {
    public int removeElement(int[] nums, int val) {
        if (nums.length == 0 ) return 0;
        
        int length = nums.length;// the index where to put the extra element
        int curIdx = 0; // the current index in the array
        
        
        while (curIdx < length ){
            if (nums[curIdx] == val ){
                nums[curIdx] = nums[length-1];
                length--;
            }else{
                curIdx ++;
            }
        }
        return length;
    }
}

Method 2:

Updating the array from left to right use two pointers. Only remain non-val elements.

Code for method 2:

public class Solution {
    public int removeElement(int[] nums, int val) {
        if (nums.length == 0) return 0;
        int i = 0;// old array
        int j = 0;// new array
        
        while (i < nums.length){
            if (nums[i] != val){
                nums[j] = nums[i];
                j++;
            }
            i++;
        }
        return j;
    }
}

[LeetCode Java Solution] – Math/String – 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.

Method:

1. This problem has to use HashMap, since we need to quickly look up what does each character mean.

2. Thoughts: if the current char has greater or equal value than the next char, add it; else, minus it.

Code:

public class Solution {
    public int romanToInt(String s) {
        HashMap<Character, Integer> dict = new HashMap<Character, Integer>();
        dict.put('I',1);
        dict.put('V',5);
        dict.put('X',10);
        dict.put('L',50);
        dict.put('C',100);
        dict.put('D',500);
        dict.put('M',1000);
        
        int res = 0;
        
        int i = 0;
        
        for (i = 0; i < s.length()-1; i++){
            if (dict.get(s.charAt(i)) >= dict.get(s.charAt(i+1))){
                res += dict.get(s.charAt(i));
            }else{
                res -= dict.get(s.charAt(i));
            }
        }
        
       res += dict.get(s.charAt(i));
       return res;
        
    }
}

[LeetCode] – Math/String – Integer to Roman

Problem:

Given an integer, convert it to a roman numeral.

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

Related Knowledge:

Roman Numbers:

I (1)

V (5)

X (10)

L (50)

C (100)

D (500)

M (1000)

Method:

The tricky is how to prepare the array. Consider there are totally 13 characters in roman number.

String[] str = {“M”,”CM”,”D”,”CD”,”C”,”XC”,”L”,”XL”,”X”,”IX”,”V”,”IV”,”I”};
int[] digit = {1000,900,500,400,100,90,50,40,10,9,5,4,1};

Code:

public class Solution {
    public String intToRoman(int num) {
        String[] str = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        int[] n = {1000,900,500,400,100,90,50,40,10,9,5,4,1 };
        StringBuilder s = new StringBuilder();
        
        for (int i = 0; i < str.length; i++){
            int repeat = num/n[i];
            
            for (; repeat >0; repeat--){
                s.append(str[i]);
            }
            num = num % n[i];
        }
        
        return new String(s);
    }
}

Method 2:

Get all digits into an ArrayList (Only 4 digits, since all < 3999). And then get one digit, append several strings.

1-3: use ‘one’

4: one + five

5: five

6-8: five +one

9: one + ten

The above rules apply for all 4 digits.

Code for method 2:

public class Solution {
    public String intToRoman(int num) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        int digit = 1000;
        while (digit > 0){
            res.add(num/digit);
            num = num % digit;
            digit = digit / 10;
        }
        StringBuilder s = new StringBuilder();
        
        s.append(convert(res.get(0),"M","",""));
        s.append(convert(res.get(1),"C","D","M"));
        s.append(convert(res.get(2),"X","L","C"));
        s.append(convert(res.get(3),"I","V","X"));
        
        return s.toString();
    }
    
    public String convert(int digit, String one, String five, String ten){
        switch (digit){
            case 0: break;
            case 1: return one;
            case 2: return one.concat(one);
            case 3: return one.concat(one).concat(one);
            case 4: return one.concat(five);
            case 5: return five;
            case 6: return five.concat(one);
            case 7: return five.concat(one).concat(one);
            case 8: return five.concat(one).concat(one).concat(one);
            case 9: return one.concat(ten);
        }
        return "";
    }
}

[LeetCode] – LinkedList/Math – Add Two Numbers

Problems:

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Methods:

Add from the front to the end.

Details:

• While condition better to be || instead of &&
• Last step is to check for flag!!!

Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode c1 = l1;
        ListNode c2 = l2;
        ListNode c = dummy;
        int flag = 0;
        int digit = 0;
        while (c1 != null || c2 != null){
            if (c1 != null){
                digit += c1.val;
                c1 = c1.next;
            }
            if (c2 != null){
                digit += c2.val;
                c2 = c2.next;
            }
            if (flag != 0){
                digit += flag;
                flag = 0;
            }
            
            if (digit < 10){
                ListNode nNode = new ListNode(digit);
                c.next = nNode;
                c = c.next;
            }else{
                ListNode nNode = new ListNode(digit-10);
                c.next = nNode;
                c = c.next;
                flag = 1;
            }
            digit = 0;
        }
        if (flag == 1){
            ListNode nNode = new ListNode(1);
            c.next = nNode;
        }
        return dummy.next;
    }
}

[LeetCode] – Binary Search / Math – Pow(x, n)

Problem:

Implement pow(x, n).

Method 1: 

Divide and Conquer. (Dividing n by 2)

Code:

public class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1.0;
        if (x == 0.0) return 0.0;
        
        if (n < 0){
            n = -n;
            x = 1/x;
        }
        
        double temp = myPow(x, n/2);
        
        return n%2==0 ? temp*temp: temp*temp*x; 
    }
}

Method 2:

Shifting n to the right.

Code:

public class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1.0;
        if (x == 0.0) return 0.0;
        if (n < 0){
            n = -n;
            x = 1/x;
        }
        double res = 1.0;
        while (n > 0){
            if (n%2 == 1){
                res *= x;
            }
            x *= x;
            n >>= 1;
        }
        return res;
    }
}

[LeetCode] – sort, merge – Merge Intervals

Problem:

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Method 1:

Use the code for ‘Insert Intervals’.

Code for Method 1:

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> merge(List<Interval> intervals) {
        ArrayList<Interval> res = new ArrayList<Interval>();
        for (int i = 0; i < intervals.size(); i++){
            res = insert(res, intervals.get(i));
        }
        return res;
    }
    
    public ArrayList<Interval> insert(List<Interval> intervals, Interval newInterval){
        ArrayList<Interval> res = new ArrayList<Interval>();
        ArrayList<Interval> resb = new ArrayList<Interval>();
        if (intervals.size() == 0 ){
            res.add(newInterval);
            return res;
        }
        
        for (Interval i: intervals){
            if (i.end < newInterval.start) res.add(i);
            else if (newInterval.end < i.start) resb.add(i);
            else {
                newInterval.start = Math.min (i.start, newInterval.start);
                newInterval.end = Math.max (i.end, newInterval.end);
            }
        }
        res.add(newInterval);
        res.addAll(resb);
        return res;
    }
}

Method 2:

First, sort all the intervals according to their starting values. Then, add one into res. (We always keep last one in the res to be unsure. ) Every time, we get the last element of res, compare it with the current Interval in the set intervals. Basically only compare the “end” value.
Code for method 2:

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> merge(List<Interval> intervals) {
        ArrayList<Interval> res = new ArrayList<Interval>();
        if (intervals == null || intervals.size() == 0) return res;
        
        Comparator<Interval> comp = new Comparator<Interval>(){
            public int compare(Interval i1, Interval i2){
                if (i1.start > i2.start) return 1;
                else if (i1.start < i2.start) return -1;
                else return 0;
            }
        };
        Collections.sort(intervals, comp);
        
        res.add(intervals.get(0));
        
        for (int i = 1; i < intervals.size(); i++){
            if (res.get(res.size()-1).end >= intervals.get(i).start){
                res.get(res.size()-1).end = Math.max(res.get(res.size()-1).end, intervals.get(i).end);
            }else{
                res.add(intervals.get(i));
            }
        }
        return res;
    }
}