[LeetCode] House Robber III

LeetCode House Robber III 

Problem:
the thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.

This is a Maximum Weight Independent Set Problem in disguise, which is NP-hard. However to find the max weight set in a tree is possible.

Given a node, if we use maxWith(node) denote the max weight with node in the set, maxWithout(node) denote the max weight without node in the set, max(node) is the max weight with the subtree rooted at node.

1. if node is in the solution, then maxWith(node) = sum of maxWithout(node.children) + node
2. if node is not in the solution, the maxWithout(node) = sum of max(node.child)

Then max(node) = max of maxWith(root), maxWithout(node)

This can be done using dynamic program to start the leaves first then go up to the tree to calculate the maxWithout() and max() for each node. To achieve this we use recursive post-order traversal.

minimum path sum of a number triangle

This is from leetcode: http://www.programcreek.com/2013/01/leetcode-triangle-java/

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). 

The key observation here is that viewing this triangle as a tree, for any given subtree, the minimum path sum is the minimum of all of its subtrees plus the number at the root. At the leaf level, the minimum path sum is the value at the leaves.

If we use dynamic programming, keep track of the minimum path sum at lower level, and then going up to calculate the min path sum at higher level.




Further observation of the dynamic programming solution is that we don't need a 2D table, in stead we can use an array and keep on updating it when going up.

N-queens puzzle

The n-queens puzzle is a classic dynamic programming puzzle. The problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[  [".Q..",  // Solution 1   "...Q",   "Q...",   "..Q."],  ["..Q.",  // Solution 2   "Q...",   "...Q",   ".Q.."] ]

public static void findAllValidQueenPositions(int k){
/*
* an array indicate the queens' column index position on each row
* e.g. if k = 2, array of 0, 1 means queens are placed at 0,0 and 1,1 cells
*/
int[] pos = new int[k];
for(int r = 0; r<pos.length; r++)
pos[r] = -1;
move(pos, 0);
}

private static void move(int[] pos, int row){
int length = pos.length;
if(row == length){//we finish the whole chess board
System.out.println(Arrays.toString(pos));
return;
}

/*
* go through each col on current row
*/
for(int col = 0; col<length; col++){
if(isValidMove(pos, col, row)){
int[] copy = Arrays.copyOf(pos, length);
copy[row] = col;
move(copy, row+1);
}
}

}


private static boolean isValidMove(int[] pos, int col, int row) {
if(row==0)
return true;
else{
for(int r = 0; r<row; r++){
if(Math.abs(pos[r] - col) == Math.abs(r - row) || pos[r] == col)
return false;
}
}

return true;

}

Longest Valid Parentheses

There is the longest valid parentheses problem definition.

We are given a string containing just parentheses of character ')' and '(' only, find the length of the longest valid (well-formed) parentheses substring. For example, for "(()", the longest valid parentheses substring is "()", output is 2. Anther example is ")()())", the longest valid parentheses substring is "()()", which has length of 4.

Approach I: dynamic programming

As usual many of the string related problems can be solved by dynamic problem. Given a substring from index at i to j, how can we find out the longest valid parentheses substring, which is not easy to construct the dynamic function. But we can convert this problem to another problem, that is, given substring S from index i to j, find out if all of the parentheses in the substring S form valid pair.

Here is how we construct isValid dynamic function based on index i and j, which is to break the substring(i,j) to two part: i,k and k+1, j. in which k = i+1, i+3, i+5, ..., j-2.

if(isValid(i,k) && isValid(k+1,j)) then isValid(i,j) = true.

Here is the java code:

public static int longestValidParentheses(String str){
int len = str.length();
boolean[][] isValid = new boolean[len][len];
int maxLen = 0;
for(int i =0; i< len-1; i++){
if(str.charAt(i)=='(' && str.charAt(i+1) == ')'){
isValid[i][i+1] = true;
maxLen = 2;
}
}

for(int step=3; step<len; step=step+2){ for(int i=0; i+step<len; i++){ int j = i+step;
if(isValid[i+1][j-1]&&isValid(str,i,j)) isValid[i][j] = true; for(int k=i+1; k<=j-2; k=k+2){ if(isValid[i][k] && isValid[k+1][j]) isValid[i][j] = true; if(isValid[i][j]){ maxLen = Math.max(maxLen, j - i + 1); break; } } } }
return maxLen;
}

private static boolean isValid(String str, int i, int j){
return str.charAt(i) == '(' && str.charAt(j) == ')';
}

Approach II: using stack

Stack is great data structure, the difference between stack and queue is that you update and query from the same place: the back, while in queue you have two places to update: insert at back, remove at front. That is the reason we can use stack is constructed data structure like max/min stack and max/min queue, in this case, the queue is built on top of stack, as well.

static class Node {
        int pos;
        char c;
        Node(int p, char c){
            this.pos = p;
            this.c = c;
        }
    }
    public static int maxValidParenthesis(String input){
        int max = 0;
        Stack<Node> s = new Stack<Node>();
        for(int i=0, j= input.length(); i<j; i++){
            char c = input.charAt(i);
            if(s.isEmpty() || c == '(' || s.peek().c == ')')
                s.push(new Node(i, c));
            else{
                s.pop();
                max = Math.max(i - (s.isEmpty()?-1:s.peek().pos), max);
            }
        }
        return max;
    }

 

Coins in a line

This problem is from leetcode: http://articles.leetcode.com/2011/02/coins-in-line.html.

Number of coins lined up, two persons take turn to pick up coins from both ends, what is the maximum total sum of money first person can pick?

Many of the gaming type problems can be solved by dynamic programming. Say DP[i, j] presents the maximum value one person can gather if he/she is presented with coins from position i to j. The final answer will be DP[0][numofcoin-1].

When person presented with coins from i to j, he/she can either pick coin at i or j, after that, second person will pick the coins and we will assume second person is smart and will always make best move, that is, will minimize the first person can gain on the next step:

So we have the following formula for dynamic programming: 
DP(i,j) = Max(
         *     Min(DP(i,j-2), DP(i+1,j-1))+coins[j],
         *     Min(DP(i+2,j), DP(i+1,j-1))+coins[i])


Here is the code:

public static int coinsInALine(int[] coins){
        //assume we have more than 4 coins, otherwise the problem becomes too easy
        /*
         * DP(i,j) = Max(
         *     Min(DP(i,j-2), DP(i+1,j-1))+coins[j],
         *     Min(DP(i+2,j), DP(i+1,j-1))+coins[i])
         */
        int[][] table = new int[coins.length][coins.length];
        int[][] moves = new int[coins.length][coins.length];
        for(int i = 0; i<coins.length; i++){
            table[i][i] = coins[i];
            moves[i][i] = i;
        }
      
        for(int i=0; i<coins.length-1; i++){
            table[i][i+1] = Math.max(coins[i], coins[i+1]);
            moves[i][i+1] = coins[i] > coins[i+1]? i : i+1;
        }
      
        for(int step = 2; step<coins.length; step++){          
            for(int i=0; i+step<coins.length; i++){
                int a = coins[i+step] + Math.min(table[i][i+step-2], table[i+1][i+step-1]);              
                int b = coins[i] + Math.min(table[i+2][i+step], table[i+1][i+step-1]);
                table[i][i+step] = Math.max(a, b);  
                moves[i][i+step] = a > b? i+step : i;
            }
        }
      
        int i=0, j=coins.length-1;
        while(i<j){
            System.out.println("move: " + moves[i][j]);
            if(moves[i][j] == i)
                i++;
            else
                j--;
        }
        System.out.println("done");
        return table[0][coins.length-1];
    }

Text Justification Algorithm - Dynamic programming and greedy algorithm

Problem: given a list of words and a window size of w, how to split them into multiple lines so that the fewest lines are used if possible.

Example: w = 10, input:  "given a list of words and a window size of w"

potential optimal alignment:

given      a
list         of
words and
a  window
size of    w

not a good alignment:

given
a  list
of words
and a
window
size of
w

This is a common problem faced by many editor application such as MS Words, Open Office.

First of all, given n words, there are 2^n-1 possible ways to alignment them in up to n lines.

Second, we need a way to measure the goodness or badness of each options. One way to measure goodness that is use the total length of words on each line divided by window size. The value is between 0 and 1, 1 means a perfect alignment, 0 means the worst one. Note value will always larger than 0. Another way to measure badness is to compute (w - length_of_words_on_each_line)^3, the higher the value is, the bad alignment is.

Let's assume we have a measurement of how good or bad each option is. A brute force solution is to exam all possible 2^n-1 options and find the best one based on the values mentioned above.  Simple, right? (Then we got fired by boss next day!)

Many of the string related problem can be solved by dynamic programming, e.g. longest substring problem, edit distance between two strings and etc. So let's try DP here.

If there is one word, measurement is easy, its badness is:
 if word.length > w, badness = INFINITY
 otherwise, badness = 0

If there are two words, w1, w2, how to calculate DP(w1) and DP(w2)?
DP(w2) is easy, see one word case above
DP(w1) = Min(badness(w1) + DP(w2), badness(w1, w2))

three words, w1, w2, w3,

DP(w3) is easy, see one word case above
DP(w2) see two words case above
DP(w1) = Min(badness(w1) + DP(w2), badness(w1, w2)+DP(w3), badness(w1, w2, w3))

Ok, I think we find the recursion formula! Let's code it up. Note in the following code, I use fullness or goodness measure. For badness measurement the logic will be the same except we will the maximize each DP value. And I provide sample badness measurement at the end too.

public static void textJustification(String[] words, int width){

int len = words.length;

double[] table = new double[len];

int[] indices = new int[len];

table[len-1] = fullness(words, len-1, len-1, width);

indices[len-1] = -1;

for(int k = len - 2; k<=0; k--){

table[k] = Integer.MIN_VALUE;

for(int i=0; k+i<len; i++){

double fullness = fullness(words, k, k+i, width);

if(fullness==0d)

break;

double dp = k+i+1<len?table[k+i+1]:0;

if(fullness + dp > table[k]){

table[k] = fullness + dp;

indices[k] = k+i+1;

}

}

}

for(int i = 0; i<len; i = indices[i]){

System.out.println(i);

}

}

public static double fullness(String[] words, int i, int j, int w){

int length = words[i].length();

for(int m = i+1; m<=j; m++)

length += words[i].length()+1;

return length<=w? (double)length/w :0;

}

//sample code for badness measurement

public static double badness(String[] words, int i, int j, int w){
 int length = words[i].length();
for(int m = i+1; m<=j; m++)
length += words[i].length()+1;
return length<=w? Math.pow(w - length, 3) : Integer.MAX_VALUE;
}

Find repeating sub-sequences in a string

This is a problem given by Peng Li (http://allenlipeng47.com/PersonalPage/index/list/1/nkey)
Given a string , find if there is any sub-sequence that repeats itself. Here, sub-sequence can be a non-contiguous pattern, with the same relative order. 

1. abab <------yes, ab is repeated
2. abba <---- No, a and b follow different order
3. acbdaghfb <-------- yes there is a followed by b at two places
4. abcdacb <----- yes a followed by b twice
5. aacc< ----yes, aacc, the underline ‘ac’ and red ‘ac’ are the repeating sub-sequences.

We can reduce this problem to the problem of finding common sub-sequence amount two strings, in this case, the two strings are identical. Also note the diagonal values of the DP table will be the string itself or identical sub-sequences which we should not consider.

For example:

negative example: abba

before and after we set diagonal values to 0

len(sub-seq)	a	b	b	a
a	1	1	1	2
b	1	2	2	2
b	1	2	3	3
a	1	2	3	4

len(sub-seq)	a	b	b	a
a	0	0	0	1
b	0	0	1	1
b	0	1	0	1
a	1	1	1	0

positive example: abab

len(sub-seq)	a	b	a	b
a	0	0	1	1
b	0	0	1	2
a	1	1	0	2
b	1	2	2	0

public static boolean findLongestSubsequence(String s1, String s2){

 int len1 = s1.length(), len2 = s2.length();

//part1 build DP table bottom-up

 int[][] table = new int[len1+1][len2+1];

     

 for(int i = 1; i<len1+1; i++){

     for(int j=1; j<len2+1; j++){

          if(i!=j){ <=== can not consider the subsequence sharing the same characters

          if(s1.charAt(i-1) == s2.charAt(j-1))

            table[i][j] = table[i-1][j-1]+1;

          else

            table[i][j] = Math.max(table[i-1][j], table[i][j-1]);        

          }

     }

 } 

  for(int i = 0; i<len2+1; i++){

     if(table[len1][i]>1)

        return true;

  }  

return false;

}