Question:

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

Thinking:

It’s like a problem adding two numbers from the low digits to high digits. We need two variable to record the sum of current digit and whether it will incresce the next digit. Then what we should care about is to traverse the linked list and check whether it’s null pointer.

Solution:

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    int num1 = 0;
    int num2 = 0;
    int sum = 0;
    int flag = 0;

    if (l1 != null){
        num1 = l1.val;
        l1 = l1.next;
    }
    if (l2 != null){
        num2 = l2.val;
        l2 = l2.next;
    }
    sum = (num1 + num2) % 10;
    flag = (num1 + num2) / 10;
    ListNode head = new ListNode(sum);
    ListNode p = head;

    while (l1 != null || l2 != null){
        num1 = 0;
        num2 = 0;
        if (l1 != null) {
            num1 = l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            num2 = l2.val;
            l2 = l2.next;
        }

        sum = (num1 + num2 + flag) % 10;
        flag = (num1 + num2 + flag) / 10;
        p.next = new ListNode(sum);
        p = p.next;
    }

    if (flag == 1)
        p.next = new ListNode(1);

    return head;
}

Question:

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = “leetcode”,
dict = [“leet”, “code”].

Return true because “leetcode” can be segmented as “leet code”.

Thinking:

This question can be solved in dynamic programming. We can get parts of the string once and check if it’s in the dictionary words and then check the left. And we can store the result of previous substring with index in the array.

Solution:

public boolean wordBreak(String s, Set<String> wordDict) {
    boolean[] valid = new boolean[s.length()+1];

    valid[0] = true;

    for (int i = 1; i <= s.length(); i++) {
        for (int j = i-1; j >= 0; j--){
            if (valid[j] && wordDict.contains(s.substring(j, i))){
                valid[i] = true;
                break;
            }
        }
    }

    return valid[s.length()];

Reference: https://leetcode.com/discuss/18904/java-implementation-using-dp-in-two-ways

Question:

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ’s undirected graph serialization:
Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

   1
  / \
 /   \
0 --- 2
     / \
     \_/

Thinking:

In order to clone this graph, we need to traverse the graph either using DFS or BFS. In my solution, I use DFS and graph search which will hold a HashMap to record the explored nodes.

Solution:

HashMap<Integer, UndirectedGraphNode> exploredSet = new HashMap<Integer, UndirectedGraphNode>();
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    return clone(node);
}

private UndirectedGraphNode clone(UndirectedGraphNode node){
    if (node == null) return null;
    UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);

    exploredSet.put(node.label, newNode);

    for (UndirectedGraphNode n: node.neighbors) {
        if (exploredSet.containsKey(n.label)) {
            newNode.neighbors.add(exploredSet.get(n.label));
        } else {
            newNode.neighbors.add(clone(n));
        }
    }

    return newNode;
}

Question:

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

For example:
“112358” is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
“199100199” is also an additive number, the additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Given a string containing only digits ‘0’-‘9’, write a function to determine if it’s an additive number.

Follow up:
How would you handle overflow for very large input integers?

Thinking:

I noticed that it’s only different in the first time in the iteration becuase we know nothing about the first element. But when found it, we can use the previous two elements to check the next one. So in the first function, we enumerate the first two elements, and check the rest string if it’s valid recursively.

Solution:

public boolean isAdditiveNumber(String num) {

    int len = num.length();

    long num1 = 0;
    long num2 = 0;
    //find the first two elements first
    for (int i = 1; 2*i+1 <= len; i++){
        for (int j = 1; Math.max(i, j) <= len-i-j; j++){
            if (num.charAt(0) == '0' && i > 1)    return false;//if first char is 0, then it only can be 0
            num1 = Long.parseLong(num.substring(0, i));
            if (num.charAt(i) == '0' && j > 1)    break;//if second element start with 0, then it only can be 0
            num2 = Long.parseLong(num.substring(i, i+j));
            if (isValid(num1, num2, i+j, num))//check the rest recursively
                return true;
        }
    }

    return false;
}

private boolean isValid(long i, long j, int start, String num){
    if (start == num.length())    return true;//no rest chars left, success
    if (num.charAt(start) == '0')    return false;
    long sum = 0;
    for (int idx = start+1; idx <= num.length(); idx++){
        sum = Long.parseLong(num.substring(start, idx));
        if (sum - i > j)
            return false;
        if (sum - i == j)
            return isValid(j, sum, idx, num);
    }
    return false;
}

Question:

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

Thinking:

In order to solve this problem, we can use dp which check whether choose current coin to make sure it’s minimum. But using function recursively will waste a lot of time. So we need to use extra space avoiding waste time. Then, we should build up a dp array accroding to the amount of money. Then update the dp value of different amout from zero to the target amout. The DP expression is: dp[i + coins[j]] = Math.min(dp[i + coins[j]], dp[i] + 1)

Solution:

public int coinChange(int[] coins, int amount) {
    int dp[] = new int[amount + 1];
    for (int i = 1; i <= amount; i++) dp[i] = Integer.MAX_VALUE-1;
    for (int i = 0; i <= amount; i++) {
        for (int j = 0; j < coins.length; j++) {
            if (i + coins[j] <= amount)
                dp[i + coins[j]] = Math.min(dp[i + coins[j]], dp[i] + 1);
        }
    }
    return dp[amount] == Integer.MAX_VALUE-1 ? -1 : dp[amount];
}