## Saturday, March 23, 2013

### [LeetCode] Path Sum, Solution

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and `sum = 22`,
```              5
/ \
4   8
/   / \
11  13  4
/  \      \
7    2      1
```
return true, as there exist a root-to-leaf path `5->4->11->2` which sum is 22.
» Solve this problem

[Thoughts]

[Code]
``````1:       bool hasPathSum(TreeNode *root, int sum) {
2:            return hasPathSum(root, 0, sum);
3:       }
4:       bool hasPathSum(TreeNode *root, int sum, int target) {
5:            if(root == NULL) return false;
6:            sum += root->val;
7:            if(root->left == NULL && root->right == NULL) //leaf
8:            {
9:                 if(sum == target)
10:                      return true;
11:                 else
12:                      return false;
13:            }
14:            return hasPathSum(root->left, sum, target)
15:                   || hasPathSum(root->right, sum, target);
16:       }
``````

## Friday, March 22, 2013

### [Interview] Serialize and De-serialize a tree

A very frequent interview question. Suppose you have a tree, how could you serialize it to file and revert it back?

for example,

1
/               \
2                 3
\          /
4        5
/       \
6        7

[Thoughts]

1
/               \
2                 3
/       \          /      \
#         4        5       #
/       \
6        7
/      \     /    \
#      #    #     #

void Serialize(TreeNode * node, vector<char> &output)
{
if(node == NULL)
{
output.push_back('#');
return;
}

output.push_back(node->val + '0');
Serialize(node->left, output);
Serialize(node->right, output);
}

TreeNode *Deserialize(vector<char> output, int &index)
{
if(index > output.size() || output[index] == '#') return NULL;

TreeNode *node = new TreeNode(output[index] -'0');
index ++;
node->left = Deserialize(output, index);
index++;
node->right = Deserialize(output, index);
return node;
}

### [LeetCode] Convert Sorted Array to Binary Search Tree, Solution

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
» Solve this problem

[Thoughts]
If we build BST from array, we can build it from top to bottom, like
1. choose the middle one as root,
2. build left sub BST via left part array
3. build right sub BST via right part array
4. do this recursively.

[Code]
``````1:       TreeNode *sortedArrayToBST(vector<int> &num) {
2:            return BuildTree(num, 0, num.size()-1);
3:       }
4:       TreeNode *BuildTree(vector<int> &num, int start, int end)
5:       {
6:            if(start>end) return NULL;
7:            if(start == end) return new TreeNode(num[start]);
8:            int mid = (start+end)/2;
9:            TreeNode *node = new TreeNode(num[mid]);
10:           node->left = BuildTree(num, start, mid-1);
11:           node->right = BuildTree(num, mid+1, end);
12:           return node;
13:       }
``````

## Thursday, March 21, 2013

### [LeetCode] Same Tree, Solution

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.
» Solve this problem

[Thoughts]

[Code]
``````1:    bool isSameTree(TreeNode *p, TreeNode *q) {
2:      if(!p && !q) return true;
3:      if(!p || !q) return false;
4:      return (p->val == q->val) &&
5:           isSameTree(p->left, q->left) &&
6:           isSameTree(p->right, q->right);
7:    }
``````

## Wednesday, March 20, 2013

### [LeetCode] Unique Binary Search Trees II, Solution

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
```   1         3     3      2      1
\       /     /      / \      \
3     2     1      1   3      2
/     /       \                 \
2     1         2                 3
```
confused what `"{1,#,2,3}"` means? > read more on how binary tree is serialized on OJ.
» Solve this problem

[Thoughts]

[Code]
``````1:       vector<TreeNode *> generateTrees(int n) {
2:            if(n ==0) return generate(1,0);
3:            return generate(1, n);
4:       }
5:       vector<TreeNode *> generate(int start, int end)
6:       {
7:            vector<TreeNode *> subTree;
8:            if(start>end)
9:            {
10:                 subTree.push_back(NULL);
11:                 return subTree;
12:            }
13:            for(int i =start; i<=end; i++)
14:            {
15:                 vector<TreeNode*> leftSubs = generate(start, i-1);
16:                 vector<TreeNode*> rightSubs = generate(i+1, end);
17:                 for(int j = 0; j< leftSubs.size(); j++)
18:                 {
19:                      for(int k=0; k<rightSubs.size(); k++)
20:                      {
21:                           TreeNode *node = new TreeNode(i);
22:                           node->left = leftSubs[j];
23:                           node->right = rightSubs[k];
24:                           subTree.push_back(node);
25:                      }
26:                 }
27:            }
28:            return subTree;
29:       }
``````

[Note]

``````1:       vector<TreeNode *> generateTrees(int n) {
2:            if(n ==0) return *generate(1,0);
3:            return *generate(1, n);
4:       }
5:       vector<TreeNode *>* generate(int start, int end)
6:       {
7:            vector<TreeNode *> *subTree = new vector<TreeNode*>();
8:            if(start>end)
9:            {
10:                 subTree->push_back(NULL);
11:                 return subTree;
12:            }
13:            for(int i =start; i<=end; i++)
14:            {
15:                 vector<TreeNode*> *leftSubs = generate(start, i-1);
16:                 vector<TreeNode*> *rightSubs = generate(i+1, end);
17:                 for(int j = 0; j< leftSubs->size(); j++)
18:                 {
19:                      for(int k=0; k<rightSubs->size(); k++)
20:                      {
21:                           TreeNode *node = new TreeNode(i);
22:                           node->left = (*leftSubs)[j];
23:                           node->right = (*rightSubs)[k];
24:                           subTree->push_back(node);
25:                      }
26:                 }
27:            }
28:            return subTree;
29:       }
``````

### [LeetCode] Unique Binary Search Trees, Solution

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.
```   1         3     3      2      1
\       /     /      / \      \
3     2     1      1   3      2
/     /       \                 \
2     1         2                 3
```
» Solve this problem

[Thoughts]

1                1                      2                       3             3
\                 \                 /      \                  /              /
3               2              1       3               2             1
/                   \                                       /                  \
2                       3                                   1                    2

Count[0] =1

Count[1] = 1

1                       2
\                    /
2                1
Count[2] = Count[0] * Count[1]   (1为根的情况)
+ Count[1] * Count[0]  (2为根的情况。

Count[3] = Count[0]*Count[2]  (1为根的情况)
+ Count[1]*Count[1]  (2为根的情况)
+ Count[2]*Count[0]  (3为根的情况)

Count[i] = ∑ Count[0...k] * [ k+1....i]     0<=k<i-1

[Code]
``````1:       int numTrees(int n) {
2:            vector<int> count(n+1, 0);
3:            count[0] =1;
4:            count[1] =1;
5:            for(int i =2; i<=n; i++)
6:            {
7:                 for(int j =0; j<i; j++)
8:                 {
9:                      count[i] += count[j]*count[i-j-1];
10:                 }
11:            }
12:            return count[n];
13:       }
``````

[Note]

## Monday, March 18, 2013

### [LeetCode] Remove Duplicates from Sorted List II, Solution

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given `1->2->3->3->4->4->5`, return `1->2->5`.
Given `1->1->1->2->3`, return `2->3`.
» Solve this problem

[Thoughts]

[Code]
``````1:       ListNode *deleteDuplicates(ListNode *head) {
3:            ListNode *G = new ListNode(INT_MIN);
5:            ListNode *cur = G, *pre = head;
6:            while(pre!=NULL)
7:            {
8:                 bool isDup = false;
9:                 while(pre->next!=NULL && pre->val == pre->next->val)
10:                 {
11:                      isDup = true;
12:                      ListNode *temp = pre;
13:                      pre = pre->next;
14:                      delete temp;
15:                 }
16:                 if(isDup)
17:                 {
18:                      ListNode *temp = pre;
19:                      pre = pre->next;
20:                      delete temp;
21:                      continue;
22:                 }
23:                 cur->next = pre;
24:                 cur = cur->next;
25:                 pre= pre->next;
26:            }
27:            cur->next = pre;
28:            ListNode *temp = G->next;
29:            delete G;
30:            return temp;
31:       }
``````

## Sunday, March 17, 2013

### [LeetCode] Search a 2D Matrix, Solution

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
```[
[1,   3,  5,  7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
```
Given target = `3`, return `true`.
» Solve this problem

[Thoughts]

[Code]
``````1:       bool searchMatrix(vector<vector<int> > &matrix, int target) {
2:            int row = matrix.size();
3:            if(row ==0) return false;
4:            int col = matrix[0].size();
5:            if(col ==0) return false;
6:            if(target< matrix[0][0]) return false;
7:            int start = 0, end = row-1;
8:            while(start<````=```` end)
9:            {
10:                 int mid = (start+end)/2;
11:                 if(matrix[mid][0] == target)
12:                      return true;
13:                 else if(matrix[mid][0] < target)
14:                      start = mid+1;
15:                 else
16:                      end = mid-1;
17:            }
18:            int targetRow = end;
19:            start =0;
20:            end = col-1;
21:            while(start <````=````end)
22:            {
23:                 int mid = (start+end)/2;
24:                 if(matrix[targetRow][mid] == target)
25:                      return true;
26:                 else if(matrix[targetRow][mid] < target)
27:                      start = mid+1;
28:                 else
29:                      end = mid-1;
30:            }
31:            return false;
32:       }
``````

## Saturday, March 16, 2013

### [LeetCode] Merge Two Sorted Lists, Solution

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
» Solve this problem

[Thoughts]

[Code]
``````1:    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
2:      if(l1 == NULL) return l2;
3:      if(l2 == NULL) return l1;
4:      ListNode *head = new ListNode(-1);
6:      while(l1 != NULL && l2!=NULL)
7:      {
8:          if(l1->val < l2->val)
9:          {
10:             p->next = l1;
11:             l1= l1->next;
12:          }
13:          else
14:          {
15:             p->next = l2;
16:             l2 = l2->next;
17:          }
18:          p = p->next;
19:      }
20:      if(l1 != NULL)
21:          p->next = l1;
22:      if(l2 != NULL)
23:          p->next = l2;
26:      return p;
27:    }
``````

Update 04/13/13 refactor code for succinct
``````1:       ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
2:            ListNode* head = new ListNode(-1);
4:            while(l1!=NULL || l2!= NULL)
5:            {
6:                 int val1 = l1==NULL?INT_MAX:l1->val;
7:                 int val2 = l2==NULL? INT_MAX:l2->val;
8:                 if(val1<=val2)
9:                 {
10:                      p->next = l1;
11:                      l1=l1->next;
12:                 }
13:                 else
14:                 {
15:                      p->next = l2;
16:                      l2 = l2->next;
17:                 }
18:                 p= p->next;
19:            }
22:            return p;
23:       }
``````

## Sunday, March 10, 2013

### [LeetCode] Longest Valid Parentheses, Solution

Given a string containing just the characters `'('` and `')'`, find the length of the longest valid (well-formed) parentheses substring.
For `"(()"`, the longest valid parentheses substring is `"()"`, which has length = 2.
Another example is `")()())"`, where the longest valid parentheses substring is `"()()"`, which has length = 4.
» Solve this problem

[Thoughts]

[Code]
``````1:       int longestValidParentheses(string s) {
2:            const char* str = s.c_str();
3:            int nMax=0;
4:            const char *p = str;
5:            vector<const char*> sta;
6:            while(*p !='\0')
7:            {
8:                 if(*p == '(')
9:                 {
10:                      sta.push_back(p);
11:                 }
12:                 else
13:                 {
14:                      if(!sta.empty() && *sta.back()=='(')
15:                      {
16:                           sta.pop_back();
17:                           nMax = max(nMax, p-(sta.empty()?str-1:sta.back()));
18:                      }
19:                      else
20:                      {
21:                           sta.push_back(p);
22:                      }
23:                 }
24:                 p++;
25:            }
26:            return nMax;
27:       }
``````

## Monday, March 4, 2013

### [LeetCode] Two Sum, Solution

Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
» Solve this problem

[Thoughts]

``````1:    vector<int> twoSum(vector<int> &numbers, int target) {
2:      map<int, int> mapping;
3:      vector<int> result;
4:      for(int i =0; i< numbers.size(); i++)
5:      {
6:        mapping[numbers[i]]=i;
7:      }
8:      for(int i =0; i< numbers.size(); i++)
9:      {
10:        int searched = target - numbers[i];
11:        if(mapping.find(searched) != mapping.end())
12:        {
13:          result.push_back(i+1);
14:          result.push_back(mapping[searched]+1);
15:          break;
16:        }
17:      }
18:      return result;
19:    }
``````

``````1:       struct Node
2:       {
3:            int val;
4:            int index;
5:            Node(int pVal, int pIndex):val(pVal), index(pIndex){}
6:       };
7:       static bool compare(const Node &left, const Node &right)
8:       {
9:            return left.val < right.val;
10:       }
11:       vector<int> twoSum(vector<int> &numbers, int target) {
12:            vector<Node> elements;
13:            for(int i =0; i< numbers.size(); i++)
14:            {
15:                 elements.push_back(Node(numbers[i], i));
16:            }
17:            std::sort(elements.begin(), elements.end(), compare);
18:            int start = 0, end = numbers.size()-1;
19:            vector<int> result;
20:            while(start < end)
21:            {
22:                 int sum = elements[start].val + elements[end].val;
23:                 if(sum == target)
24:                 {
25:                      result.push_back(elements[start].index+1);
26:                      if(elements[start].index < elements[end].index)
27:                           result.push_back(elements[end].index+1);
28:                      else
29:                           result.insert(result.begin(),elements[end].index+1);
30:                      break;
31:                 }
32:                 else if(sum > target)
33:                      end--;
34:                 else
35:                      start++;
36:            }
37:            return result;
38:       }
``````

### [LeetCode] Palindrome Partitioning II, Solution

Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = `"aab"`,
Return `1` since the palindrome partitioning `["aa","b"]` could be produced using 1 cut.
» Solve this problem

[Thoughts]

D[i,n] = 区间[i,n]之间最小的cut数，n为字符串长度

a   b   a   b   b   b   a   b   b   a   b   a
i                                  n

a   b   a   b   b   b   a   b   b   a   b   a
i                   j   j+1     n

D[i] = 区间[i,n]之间最小的cut数，n为字符串长度， 则,

D[i] = min(1+D[j+1] )    i<=j <n

P[i][j] = true if [i,j]为回文

P[i][j] = str[i] == str[j] && P[i+1][j-1];

``````1:       int minCut(string s) {
2:            int len = s.size();
3:            int D[len+1];
4:            bool P[len][len];
5:            //the worst case is cutting by each char
6:            for(int i = 0; i <= len; i++)
7:            D[i] = len-i;
8:            for(int i = 0; i < len; i++)
9:            for(int j = 0; j < len; j++)
10:            P[i][j] = false;
11:            for(int i = len-1; i >= 0; i--){
12:                 for(int j = i; j < len; j++){
13:                      if(s[i] == s[j] && (j-i<2 || P[i+1][j-1])){
14:                           P[i][j] = true;
15:                           D[i] = min(D[i],D[j+1]+1);
16:                      }
17:                 }
18:            }
19:            return D[0]-1;
20:       }
``````

``````1:    int minCut(string s) {
2:      int min = INT_MAX;
3:      DFS(s, 0, 0, min);
4:      return min;
5:    }
6:    void DFS(string &s, int start, int depth, int& min)
7:    {
8:      if(start == s.size())
9:      {
10:        if(min> depth-1)
11:          min = depth-1;
12:        return;
13:      }
14:      ````for(int i = s.size()-1; i>=start; i--)  //find the biggest palindrome first````
15:      {
16:        if(isPalindrome(s, start, i))
17:        {
18:          DFS(s, i+1, depth+1, min);
19:        }
20:        if(min!=INT_MAX)  ````//if get result, then stop search.````
21:          break;
22:      }
23:    }
24:    bool isPalindrome(string &s, int start, int end)
25:    {
26:      while(start< end)
27:      {
28:        if(s[start] != s[end])
29:          return false;
30:        start++; end--;
31:      }
32:      return true;
33:    }
``````

## Sunday, March 3, 2013

### [LeetCode] Palindrome Partitioning, Solution

Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = `"aab"`,
Return
```  [
["aa","b"],
["a","a","b"]
]
```
» Solve this problem

[Thoughts]

[Code]
``````1:       vector<vector<string>> partition(string s) {
2:            vector<vector<string>> result;
3:            vector<string> output;
4:            DFS(s, 0, output, result);
5:            return result;
6:       }
7:       void DFS(string &s, int start, vector<string>& output, vector<vector<string>> &result)
8:       {
9:            if(start == s.size())
10:            {
11:                 result.push_back(output);
12:                 return;
13:            }
14:            for(int i = start; i< s.size(); i++)
15:            {
16:                 if(isPalindrome(s, start, i))
17:                 {
18:                      output.push_back(s.substr(start, i-start+1));
19:                      DFS(s, i+1, output, result);
20:                      output.pop_back();
21:                 }
22:            }
23:       }
24:       bool isPalindrome(string &s, int start, int end)
25:       {
26:            while(start< end)
27:            {
28:                 if(s[start] != s[end])
29:                 return false;
30:                 start++; end--;
31:            }
32:            return true;
33:       }
``````

### [LeetCode] Surrounded Regions, Solution

Given a 2D board containing `'X'` and `'O'`, capture all regions surrounded by `'X'`.
A region is captured by flipping all `'O'`s into `'X'`s in that surrounded region .
For example,
```X X X X
X O O X
X X O X
X O X X
```
After running your function, the board should be:
```X X X X
X X X X
X X X X
X O X X
```
» Solve this problem

[解题思路]

``````1:    vector<int> xIndex;
2:    vector<int> yIndex;
3:    map<int, int> visited;
4:    void solve(vector<vector<char>> &board) {
5:      int row = board.size();
6:      if(row == 0) return;
7:      int col = board[0].size();
8:      for(int i =0; i < row; i++)
9:      {
10:        for(int j =0; j< col; j++)
11:        {
12:          if(board[i][j] == 'X' || IsVisited(i*row+j)) continue;
13:          visited.clear();
14:          bool surranded = true;
15:          xIndex.clear();
16:          xIndex.push_back(i);
17:          yIndex.clear();
18:          yIndex.push_back(j);
19:          int k =0;
20:          while(k<xIndex.size())
21:          {
22:            int x = xIndex[k];
23:            int y = yIndex[k];
24:            visited[x*row +y] =1;
25:            if(IsInBoundary(x, y, row, col)) surranded = false;
26:            if(x<row-1 && board[x+1][y] == 'O' && !IsVisited((x+1)*row+y)) {xIndex.push_back(x+1); yIndex.push_back(y);}
27:            if(y<col-1 && board[x][y+1] == 'O' && !IsVisited(x*row+y+1)) {xIndex.push_back(x); yIndex.push_back(y+1);}
28:            k++;
29:          }
30:          if(surranded) //clean the surranded mask
31:          {
32:            for(int m = 0; m<xIndex.size(); m++)
33:            {
34:              board[xIndex[m]][yIndex[m]] = 'X';
35:            }
36:          }
37:        }
38:      }
39:    }
40:    bool IsInBoundary(int x, int y, int row, int col)
41:    {
42:      if(x ==0 || x == row-1) return true;
43:      if(y ==0 || y == col-1) return true;
44:      return false;
45:    }
46:    bool IsVisited(int index)
47:    {
48:      if(visited.find(index) == visited.end()) return false;
49:      return true;
50:    }
``````

1. 从四条边上的O元素开始BFS，所有相连的O都赋个新值，比如‘Y’
2. 扫描整个数组，所有现存的O元素全部置为X，所有Y元素置为O

``````1:       vector<int> xIndex;
2:       vector<int> yIndex;
3:       void solve(vector<vector<char>> &board) {
4:            int row = board.size();
5:            if(row == 0) return;
6:            int col = board[0].size();
7:            xIndex.clear();
8:            yIndex.clear();
9:            for(int i =0; i< row; i++)
10:            {
11:                 if(board[i][0] == 'O')
12:                 {
13:                      xIndex.push_back(i);
14:                      yIndex.push_back(0);
15:                 }
16:                 if(board[i][col-1] == 'O')
17:                 {
18:                      xIndex.push_back(i);
19:                      yIndex.push_back(col-1);
20:                 }
21:            }
22:            for(int i =0; i< col; i++)
23:            {
24:                 if(board[0][i] == 'O')
25:                 {
26:                      xIndex.push_back(0);
27:                      yIndex.push_back(i);
28:                 }
29:                 if(board[row-1][i] == 'O')
30:                 {
31:                      xIndex.push_back(row-1);
32:                      yIndex.push_back(i);
33:                 }
34:            }
35:            int k =0;
36:            while(k<xIndex.size())
37:            {
38:                 int x = xIndex[k];
39:                 int y = yIndex[k];
40:                 board[x][y] = 'Y';
41:                 if(x>0 && board[x-1][y] == 'O' ) {xIndex.push_back(x-1); yIndex.push_back(y);}
42:                 if(x<row-1 && board[x+1][y] == 'O' ) {xIndex.push_back(x+1); yIndex.push_back(y);}
43:                 if(y>0 && board[x][y-1] == 'O' ) {xIndex.push_back(x); yIndex.push_back(y-1);}
44:                 if(y<col-1 && board[x][y+1] == 'O' ) {xIndex.push_back(x); yIndex.push_back(y+1);}
45:                 k++;
46:            }
47:            for(int i =0; i< row; i++)
48:            {
49:                 for(int j =0; j< col; j++)
50:                 {
51:                      if(board[i][j] =='O') board[i][j] = 'X';
52:                      if(board[i][j] == 'Y') board[i][j] = 'O';
53:                 }
54:            }
55:       }
``````