Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This question is easy. There are difficult ways to solve.

Solution

There are 2 ways to solve this problem. First and the easy one is to do recursion.

Second solution, also my original solution is to use a ‘fakeHead’ to help. Read this blog.

My code

Recursion:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else {
            if (l1.val < l2.val) {
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            } else {
                l2.next = mergeTwoLists(l1, l2.next);
                return l2;
            }
        }
    }
}

Temporary header + link operations

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if (l1 == null) cur.next = l2;
        else cur.next = l1;
        return pre.next;
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

Very standard permutation search. You can read more from this link.

My code

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>();
        if (n == 0) {
            return ans;
        }
        helper(ans, "", n, n);
        return ans;
    }

    private void helper(List<String> ans, String path, int left, int right) {
        if (left == 0 && right == 0) {
            ans.add(path);
            return;
        }
        // add either left or right parenthese
        if (left > 0) {
            helper(ans, path + "(", left - 1, right);
        }
        if (right > left) {
            helper(ans, path + ")", left, right - 1);
        }
    }
}

Question

link

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is exactly the same algorithm as 3Sum. The idea is for every value pair (a, b), find all (c, d) that makes the sum equals to the target.

Note that the final found result (a, b, c, d) is already in sorted order, no need to re-sort.

Solution

The solution works in O(n³), which is a very common solution. Read this blog for a O(n²) solution. Read it ONLY if you are interested.

My code

public class Solution {
    public List<List<Integer>> fourSum(int[] num, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if (num == null || num.length < 4) {
            return ans;
        }
        Arrays.sort(num);
        int len = num.length;
        for (int i = 0; i < len - 3; i++) {
            // make sure the first number is distinct 
            if (i != 0 && num[i - 1] == num[i]) {
                continue;
            }
            for (int j = i + 1; j < len - 2; j++) {
                // make sure the second number is distinct 
                if (j != i + 1 && num[j - 1] == num[j]) {
                    continue;
                }
                int balance = target - num[i] - num[j];
                int left = j + 1;
                int right = len - 1;
                while (left < right) {
                    int sum = num[left] + num[right];
                    if (sum == balance) {
                        List<Integer> lis = new ArrayList<Integer>();
                        lis.add(num[i]);
                        lis.add(num[j]);
                        lis.add(num[left]);
                        lis.add(num[right]);
                        ans.add(lis);
                    }
                    if (sum >= balance) {
                        // move right pointer left (to a unique value)
                        right--;
                        while (right >= 0 && num[right] == num[right + 1]) {
                            right--;
                        }
                    }
                    if (sum <= balance) {
                        // move left pointer right (to a unique value)
                        left++;
                        while (left < len && num[left] == num[left - 1]) {
                            left++;
                        }
                    }
                }
            }
        }
        return ans;
    }
}

We can also use HashMap to remove duplication. I personally would not recommend doing this, but it gives an interesting viwepoint. Check out this code.

public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
    Arrays.sort(num);
    HashSet<ArrayList<Integer>> hashSet = new HashSet<ArrayList<Integer>>();
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    for (int i = 0; i < num.length; i++) {
        for (int j = i + 1; j < num.length; j++) {
            int k = j + 1;
            int l = num.length - 1;
            while (k < l) {
                int sum = num[i] + num[j] + num[k] + num[l];
                if (sum > target) l--;
                else if (sum < target) k++;
                else if (sum == target) {
                    ArrayList<Integer> temp = 
                        new ArrayList<Integer>();
                    temp.add(num[i]);
                    temp.add(num[j]);
                    temp.add(num[k++]);
                    temp.add(num[l--]);
                    if (!hashSet.contains(temp)) {
                        hashSet.add(temp);
                        result.add(temp);
                    }
                }
            }
        }
    }
    return result;
}

Question

link

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

Note the special case: if the head node needs to be removed!

Solution

The code explains itself. Just don’t forget the special cases.

My code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        ListNode left = head;
        ListNode right = head;
        // important to note that head node can be removed as well!
        // advance right pointer now
        for (int i = 0; i < n; i++) {
            right = right.next;
            if (right == null) {
                right = head;
            }
        }
        // advance left and right pointer together
        while (right.next != null) {
            left = left.next;
            right = right.next;
        }
        // remove the node after left pointer
        // again, the below error check is not necessary
        if (left.next == null) {
            // need to remove the header in this case
            return head.next;
        } else {
            left.next = left.next.next;
            return head;
        }
    }
}

Question

link

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

There are 2 considerations associated with this question:

1. How to convert an number into a String (i.e. 2->‘abc’ etc.)

2. How the search works.

Convert number to string

There are 2 way: math way, or the hashmap way.

My initial idea is to calculate it mathematically:

private String getLetters(int key) {
    if (key <= 1 || key >= 10) return "";
    // key must be in the range of [2,9]
    char first = (char) ('a' + (key - 2) * 3);
    if (key >= 8) first++;
    String letters = "";
    for (int i = 0; i < 4; i++) {
        if (i == 3 && !(key == 7 || key == 9)) {
            break;
        }
        letters += first++;
    }
    return letters;
}
String letters = getLetters('3' - '0');

However, most people would use HashMap. It’s not the main issue anyway, so using HashMap is fine.

Solution

This is very typical “Permutation” question. Need to memorize clearly.

Refer to ninechap for the solution and a piece of very standard code.

My code

public class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<String>();
        if (digits == null || digits.length() == 0) {
            ans.add("");
            return ans;
        }
        int len = digits.length();
        // this type of DFS question is very standardized
        helper(ans, "", digits, 0, len);
        return ans;
    }

    private void helper(List<String> ans, String path, String digits, int pos, int len) {
        if (pos == len) {
            ans.add(path);
            return;
        }
        // check the char at position 'pos', and find all possible letters to insert
        String possibleLetters = getLetters(digits.charAt(pos));
        for (char letter: possibleLetters.toCharArray()) {
            helper(ans, path + letter, digits, pos + 1, len);
        }
    }

    private String getLetters(char digit) {
        // first convert char to integer
        int index = digit - '0';
        String[] map = new String[] {
            " ",
            "",
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz"
        };
        // second, find corresponding string from map
        return map[index];
    }
}

Question

link

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This question is a simplified version of [LeetCode 15] 3Sum. The required return is an integer instead of a list.

This makes life easier because we do not need to consider duplications (think about it, why?).

Solution

The code is 3Sum solution without duplication avoidance.

My code

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        if (num == null || num.length < 3) {
            return 0;
        }
        Arrays.sort(num);
        int len = num.length;
        int ans = num[0] + num[1] + num[2];
        for (int i = 0; i < len; i++) {
            // if (i != 0 && num[i - 1] == num[i]) {
            //     continue;
            // }
            // similar to 3sum question, but without dup avoidance
            int left = i + 1;
            int right = len - 1;
            while (left < right) {
                int sum = num[i] + num[left] + num[right];
                // if found triplet that sums to target, return!
                if (sum == target) {
                    return target;
                }
                // then update ans variable - if it's closer to target
                if (Math.abs(sum - target) < Math.abs(ans - target)) {
                    ans = sum;
                }
                // now move either left or right pointer
                if (sum >  target) {
                    right--;
                } else {
                    left++;
                }
            }
        }
        return ans;
    }
}

Question

link

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

First of all, the array must be sorted first.

This question is solved with O(n²) time. The idea is, for every integer, try to find a 2-integer pair so that the 3 numbers sum to 0. The method to use is 2-pointer scan.

Solution

Very important point of this question: there might be duplications in the result.

Eg. array = {-5, 2, 2, 3, 3}. When a = -5, we can choose 2, 3 and move pointers both by 1 position. Then we can choose 2, 3 again!

Solution is to increase the pointer to where the value is different. Pay special attention in writing the code. Because there are 3 parts that need duplication avoidance:

1. The pivot number that we select, must be distinct each time. Why? because this is the smallest of the triplet. It must not be same.

2. The left pointer and right pointer. They should point to a new value each time.

3. Note that when sum is too large, move left pointer, and vice versa. However when sum is == 0, we move both left and right pointer.

Point 3 is the reason why we have 2 conditions in seperate if-block:

if (sum >= 0) {...}

if (sum <= 0) {...}

My code

public class Solution {
    public List<List<Integer>> threeSum(int[] num) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if (num == null || num.length < 3) {
            return ans;
        }
        Arrays.sort(num);
        int len = num.length;
        int left, right;
        for (int i = 0; i < len; i++) {
            // duplication avoidance 1
            if (i != 0 && num[i] == num[i - 1]) {
                continue;
            }
            left = i + 1;
            right = len - 1;
            while (left < right) {
                int sum = num[i] + num[left] + num[right];
                if (sum == 0) {
                    // now one triplet is found, add it to ans list
                    List<Integer> triplet = new ArrayList<Integer>();
                    triplet.add(num[i]);
                    triplet.add(num[left]);
                    triplet.add(num[right]);
                    ans.add(triplet);
                }
                // shrink the range between left and right pointer
                // (until the 2 pointers met)
                if (sum >= 0) {
                    // move right pointer to the left
                    right--;
                    // duplication avoidance 2
                    while (right >= 0 && num[right] == num[right + 1]) {
                        right--;
                    }
                }
                if (sum <= 0) {
                    // move left pointer to the right
                    left++;
                    // duplication avoidance 3
                    while (left < len && num[left] == num[left - 1]) {
                        left++;
                    }
                }
            }
        }
        return ans;
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

Straight-forward solution. Will not go into details.

However, there’s another more generalized LCP array which is solved by use of Trie.

Solution

The code explains itself.

My code

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int p;
        for (p = 0; p < strs[0].length(); p++) {
            char c = strs[0].charAt(p);
            // check all strings in array strs
            for (int i = 0; i < strs.length; i++) {
                if (p == strs[i].length()) {
                    return strs[i];
                } else if (c != strs[i].charAt(p)) {
                    return strs[i].substring(0, p);
                }
            }
            // if all strings have the same prefix
            // continue checking it
        }
        // first string in array strs is the shortest common prefix
        return strs[0];
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This question is easier than [LeetCode 12] Integer to Roman.

The basic idea is to read 2 char (as pre and cur) and then check. If pre > cur, then OK, just do the addition. If pre < cur, we need to subtract (2 * pre) from the result.

The code is easy and concise if you have the idea.

Solution

The code explains itself.

My code

public class Solution {
    public int romanToInt(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int ans = 0;
        int pre = 0;
        int cur = 0;
        for (int i = 0; i < s.length(); i++) {
            cur = getNum(s.charAt(i));
            if (i == 0 || pre >= cur) {
                ans += cur;
            } else {
                ans += cur - (2 * pre);
            }
            pre = cur;
        }
        return ans;
    }

    private int getNum(char a){
        switch(a){
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
        }
        return 0;
    }
}

We can also do only adding. Someone posted the code in here. Read it ONLY if you are interested.

class Solution {
public:
    int romanToInt(string s) {
        // 4:IV, 9:IX, 40:XL, 90:XC, 400:CD, 900:CM,
        // 1:I, 10:X, 100:C, 1000:M
        int res=0;
        char pre = ' ';
        for(int i=0;i<s.size();i++){
            if (s[i]=='M' && pre!='C') {res+=1000;}
            if (s[i]=='C' && pre!='X') {res+=100;}
            if (s[i]=='X' && pre!='I') {res+=10;}

            if (s[i]=='M' && pre=='C') {res+=800;}
            if (s[i]=='C' && pre=='X') {res+=80;}
            if (s[i]=='X' && pre=='I') {res+=8;}

            if (s[i]=='I' ) {res+=1;}

            if (s[i]=='V' && pre!='I'){res+=5;}
            if (s[i]=='L' && pre!='X'){res+=50;}
            if (s[i]=='D' && pre!='C'){res+=500;}

            if (s[i]=='V' && pre=='I'){res+=3;}
            if (s[i]=='L' && pre=='X'){res+=30;}
            if (s[i]=='D' && pre=='C'){res+=300;}

            pre = s[i];
        }
        return res;
    }
};

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

Though Roman numerals looks complex, it’s actually converted bit by bit. For example 207=>CCVII. We can then construct the following relationship table:

So for each number, just do convert according to the above table.

9=>IX

400=>CD.

The question states that input is less than 3999.

Analysis

Before I present my solution, there is a very short code written by stackoverflow user bhlangonijr. This method makes use of Java TreeMap.floorKey. Read it ONLY if you are interested!

TreeMap.floorKey - Returns the greatest key less than or equal to the given key, or null if there is no such key.

public String intToRoman3(int num) {
    TreeMap<Integer, String> map = new TreeMap<Integer, String>();
    map.put(1000, "M");
    map.put(900, "CM");
    map.put(500, "D");
    map.put(400, "CD");
    map.put(100, "C");
    map.put(90, "XC");
    map.put(50, "L");
    map.put(40, "XL");
    map.put(10, "X");
    map.put(9, "IX");
    map.put(5, "V");
    map.put(4, "IV");
    map.put(1, "I");
    int l = map.floorKey(num);
    if (num == l) {
        return map.get(num);
    }
    return map.get(l) + intToRoman3(num - l);
}

Solution

I will present 2 solutions below.

First is an iterative solution. It’s comparatively shorter, and enjoys beter performance.

Second is my new idea. It has improved readability, but slightly worse performance, because it’s recursive.

My code

Code 1, iterative.

public class Solution {

    char[][] roman = {
        { 'I', 'V', 'X' }, 
        { 'X', 'L', 'C' }, 
        { 'C', 'D', 'M' },
        { 'M', '*', '*' } 
    };

    public String intToRoman(int num) {
        String ans = "";
        int base = 1, count = 0, temp = num;
        while (temp > 1) {
            base *= 10;
            count++;
            temp /= 10;
        }
        while (base > 0) {
            int cur = num / base;
            // now convert cur into roman string
            if (cur >= 6 && cur <= 8) {
                ans += roman[count][1];
                cur = cur % 5;
            }
            if (cur >= 1 && cur <= 3)
                for (int k = 0; k < cur; k++)
                    ans += roman[count][0];
            else if (cur == 5)
                ans += roman[count][1];
            else if (cur == 4)
                ans += roman[count][0] + "" + roman[count][1];
            else if (cur == 9)
                ans += roman[count][0] + "" + roman[count][2];
            num = num % base;
            base /= 10;
            count--;
        }
        return ans;
    }

}

Code 2, recursive.

public class Solution {

    HashMap<Integer, String> map = new HashMap<Integer, String>();

    public String intToRoman(int num) {

        map.put(1000, "M");
        map.put(500, "D");
        map.put(100, "C");
        map.put(50, "L");
        map.put(10, "X");
        map.put(5, "V");
        map.put(1, "I");

        String roman = "";
        int base = 1000;
        int digit = 0;
        while (num != 0) {
            digit = num / base;
            num = num % base;
            roman = roman + convert(digit, base);
            base /= 10;
        }
        return roman;
    }

    private String convert(int digit, int base) {
        String ans = "";
        String one = map.get(base);
        String five = map.get(base * 5);
        if (digit == 0) {
            return "";
        } else if (digit <= 3) {
            for (int i = 0; i < digit; i++) {
                ans += one;
            }
        } else if (digit == 4) {
            ans += one;
            ans += convert(5, base);
        } else if (digit == 5) {
            ans += five;
        } else if (digit <= 8) {
            ans += convert(5, base);
            ans += convert(digit - 5, base);
        } else if (digit == 9) {
            ans += one;
            ans += convert(1, base * 10);
        }
        return ans;
    }
}