Friday, December 6, 2013

[LeetCode] Evaluate Reverse Polish Notation, Solution

Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are `+`, `-`, `*`, `/`. Each operand may be an integer or another expression.
Some examples:
```  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6```

[Thoughts]

[Code]

``````1:       int evalRPN(vector<string> &tokens) {
2:            stack<int> operand;
3:            for(int i =0; i< tokens.size(); i++)
4:            {
5:                 if ((tokens[i][0] == '-' && tokens[i].size()>1) //negative number
6:                           || (tokens[i][0] >= '0' && tokens[i][0] <= '9')) //positive number
7:                 {
8:                      operand.push(atoi(tokens[i].c_str()));
9:                      continue;
10:                 }
11:                 int op1 = operand.top();
12:                 operand.pop();
13:                 int op2 = operand.top();
14:                 operand.pop();
15:                 if(tokens[i] == "+") operand.push(op2+op1);
16:                 if(tokens[i] == "-") operand.push(op2-op1);
17:                 if(tokens[i] == "*") operand.push(op2*op1);
18:                 if(tokens[i] == "/") operand.push(op2/op1);
19:            }
20:            return operand.top();
21:       }
``````

Wednesday, December 4, 2013

[LeetCode] Clone Graph, Solution

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 `#`.

1. First node is labeled as `0`. Connect node `0` to both nodes `1` and `2`.
2. Second node is labeled as `1`. Connect node `1` to node `2`.
3. 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         / \         \_/`

[Thoughts]

[Code]

` 1 /** 2  * Definition for undirected graph. 3  * struct UndirectedGraphNode { 4  *     int label; 5  *     vector<UndirectedGraphNode *> neighbors; 6  *     UndirectedGraphNode(int x) : label(x) {}; 7  * }; 8  */ 9 class Solution {10 public:11     UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {12         if(node == NULL) return NULL;13         unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> nodeMap;14         queue<UndirectedGraphNode *> visit;15         visit.push(node);16         UndirectedGraphNode * nodeCopy = new UndirectedGraphNode(node->label);17         nodeMap[node] = nodeCopy;18         while (visit.size()>0)19         {20             UndirectedGraphNode * cur = visit.front();21             visit.pop();22             for (int i = 0; i< cur->neighbors.size(); ++i)23             {24                 UndirectedGraphNode * neighb = cur->neighbors[i];25                 if (nodeMap.find(neighb) == nodeMap.end())26                 {27                     // no copy of neighbor node yet. create one and associate with the copy of cur28                     UndirectedGraphNode* neighbCopy = new UndirectedGraphNode(neighb->label);29                     nodeMap[cur]->neighbors.push_back(neighbCopy);30                     nodeMap[neighb] = neighbCopy;31                     visit.push(neighb);32                 }33                 else34                 {35                     // already a copy there. Associate it with the copy of cur36                     nodeMap[cur]->neighbors.push_back(nodeMap[neighb]);37                 }38             }39         }40     41         return nodeCopy;42     }43 };`

Tuesday, December 3, 2013

[LeetCode] Sort List, Solution

Sort a linked list in O(n log n) time using constant space complexity.

[Thoughts]
O(nlgn)的排序算法没几个，无非就是quick sort， heap sort和merge sort. 对于链表排序来说，难点之一就是如何O(1)定位节点。如果是数组，那么可以通过下标直接找到节点，但是对于链表，很明显没有下标这个东西可以用，如果需要定位到第k个元素，只能从节点头部顺序的访问K次，但是，如果排序中每一个定位操作都要这样做的话，就太慢了。

[Code]

``````1:    ListNode *sortList(ListNode *head) {
2:      if(head == NULL) return NULL;
3:      int len = 0;
5:      while(it!= NULL)
6:      {
7:        len++;
8:        it = it->next;
9:      }
12:    }
13:    ListNode* Sort(ListNode````**```` head, int length)
14:    {
15:         if (length == 1)
16:         {
18:              ````*head = (*head)->next;````  // 确保head每被访问一次，则向后移动一次
19:              ````temp->next = NULL; // 尾节点需要为NULL，否则Merge函数没法使用````
20:              return temp;
21:         }
26:    }
27:    ListNode* Merge(ListNode* first, ListNode* second) // 普通的链表merge函数
28:    {
29:      ListNode* head = new ListNode(-1);
31:      while(first!=NULL || second!=NULL)
32:      {
33:        int fv = first == NULL? INT_MAX:first->val;
34:        int sv = second == NULL? INT_MAX:second->val;
35:        if(fv<=sv)
36:        {
37:          cur->next = first;
38:          first = first->next;
39:        }
40:        else
41:        {
42:          cur->next = second;
43:          second = second->next;
44:        }
45:        cur = cur->next;
46:      }
49:      return cur;
50:    }
``````

Update 08/23/2014
True. Recursion is not constant space. I didn't read the problem description carefully. Here, add an implementation via iteration.

Same idea as merge sort.  One example as below:

For each round, the iteration is O(n). And for merge sort, we totally need run the iteration for lg(n) round(the height of recursion tree). So, the total time complexity is  O(nlgn). Maybe someone can share a brief implementation. My current code is a bit fat.

``````1:  ListNode *sortList(ListNode *head) {
2:       // Get length first
4:       int len = 0;
5:       while (p != NULL)
6:       {
7:            p = p->next;
8:            len++;
9:       }
10:       ListNode* fakehead = new ListNode(-1);
12:       for (int interval = 1; interval <= len; interval = interval * 2)
13:       {
16:            while (fast != NULL || slow != NULL)
17:            {
18:                 int i = 0;
19:                 while (i< interval && fast != NULL)
20:                 {
21:                      fast = fast->next; //move fast pointer ahead 'interval' steps
22:                      i++;
23:                 }
24:                 //merge two lists, each has 'interval' length
25:                 int fvisit = 0, svisit = 0;
26:                 while (fvisit < interval && svisit<interval && fast != NULL && slow != NULL)
27:                 {
28:                      if (fast->val < slow->val)
29:                      {
30:                           pre->next = fast;
31:                           pre = fast;
32:                           fast = fast->next;
33:                           fvisit++;
34:                      }
35:                      else
36:                      {
37:                           pre->next = slow;
38:                           pre = slow;
39:                           slow = slow->next;
40:                           svisit++;
41:                      }
42:                 }
43:                 while (fvisit < interval && fast != NULL)
44:                 {
45:                      pre->next = fast;
46:                      pre = fast;
47:                      fast = fast->next;
48:                      fvisit++;
49:                 }
50:                 while (svisit < interval && slow != NULL)
51:                 {
52:                      pre->next = slow;
53:                      pre = slow;
54:                      slow = slow->next;
55:                      svisit++;
56:                 }
57:                 pre->next = fast;
58:                 slow = fast;
59:            }
60:       }
64:  }
``````

Monday, December 2, 2013

[LeetCode] Max Points on a Line, Solution

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
[Thoughts]

y = ax + b

y1 = kx1 +b
y2 = kx2 +b

[Code]
``````1:       int maxPoints(vector<Point> &points) {
2:            unordered_map<float, int> statistic;
3:            int maxNum = 0;
4:            for (int i = 0; i< points.size(); i++)
5:            {
6:                 statistic.clear();
7:                 statistic[INT_MIN] = 0; // for processing duplicate point
8:                 int duplicate = 1;
9:                 for (int j = 0; j<points.size(); j++)
10:                 {
11:                      if (j == i) continue;
12:                      if (points[j].x == points[i].x && points[j].y == points[i].y) // count duplicate
13:                      {
14:                           duplicate++;
15:                           continue;
16:                      }
17:                      float key = (points[j].x - points[i].x) == 0 ? INT_MAX :
18:                                     (float) (points[j].y - points[i].y) / (points[j].x - points[i].x);
19:                      statistic[key]++;
20:                 }
21:                 for (unordered_map<float, int>::iterator it = statistic.begin(); it != statistic.end(); ++it)
22:                 {
23:                      if (it->second + duplicate >maxNum)
24:                      {
25:                           maxNum = it->second + duplicate;
26:                      }
27:                 }
28:            }
29:            return maxNum;
30:       }
``````

1. 垂直曲线， 即斜率无穷大

2. 重复节点。

Wednesday, November 27, 2013

[LeetCode] LRU Cache, Solution

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: `get` and `set`.

`get(key)` - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
`set(key, value)` - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

[Thoughts]

1. hashmap， 保存key和对象位置的映射

2. list，保存对象新旧程度的序列。不一定是list，也可以用vector，不过list的好处是已经实现了头尾操作的api，vector的话，还要自己写，麻烦。

[Code]

` 1 class LRUCache{ 2 public: 3     struct CacheEntry 4     { 5     public: 6         int key; 7         int value; 8         CacheEntry(int k, int v) :key(k), value(v) {} 9     };10 11     LRUCache(int capacity) {12         m_capacity = capacity;13     }14 15     int get(int key) {16         if (m_map.find(key) == m_map.end())17             return -1;18 19         MoveToHead(key);20         return m_map[key]->value;21     }22 23     void set(int key, int value) {24         if (m_map.find(key) == m_map.end())25         {26             CacheEntry newItem(key, value);27             if (m_LRU_cache.size() >= m_capacity)28             {29                 //remove from tail30                 m_map.erase(m_LRU_cache.back().key);31                 m_LRU_cache.pop_back();                32             }33 34             // insert in head.35             m_LRU_cache.push_front(newItem);36             m_map[key] = m_LRU_cache.begin();37             return;38         }39 40         m_map[key]->value = value;41         MoveToHead(key);42     }43 44 private:45     unordered_map<int, list<CacheEntry>::iterator> m_map;46     list<CacheEntry> m_LRU_cache;47     int m_capacity;48 49     void MoveToHead(int key) 50     {51         //Move key from current location to head52         auto updateEntry = *m_map[key];53         m_LRU_cache.erase(m_map[key]);54         m_LRU_cache.push_front(updateEntry);55         m_map[key] = m_LRU_cache.begin();56     }57 58 };`

Monday, November 25, 2013

[LeetCode] Binary Tree Preorder Traversal, Solution

Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree `{1,#,2,3}`,
```   1
\
2
/
3```

return `[1,2,3]`.
Note: Recursive solution is trivial, could you do it iteratively?
[Thoughts]
PreOrder:
1. visit node
2. visit node->left
3. visit node->right

function preorder(root)

if root == NULL return;
print root;
preoder(node->left);
preOrder(node->right);

[Code]

``````1:  vector<int> preorderTraversal(TreeNode *root) {
2:       stack<TreeNode*> tStack;
3:       vector<int> result;
4:       while(tStack.size()>0 || root != NULL)
5:       {
6:            if(root != NULL)
7:            {
8:                 result.push_back(root->val);
9:                 if(root->right !=NULL)
10:                 tStack.push(root->right);
11:                 root = root->left;
12:            }
13:            else
14:            {
15:                 root = tStack.top();
16:                 tStack.pop();
17:            }
18:       }
19:       return result;
20:  }
``````

Update 08/20/2014. Another way to use stack

``````1:       vector<int> preorderTraversal(TreeNode *root) {
2:            stack<TreeNode*> stack;
3:            vector<int> result;
4:            TreeNode* cur = root;
5:            while(cur != NULL || stack.size() != 0)
6:            {
7:                 while(cur != NULL)
8:                 {
9:                      result.push_back(cur->val);
10:                      stack.push(cur);
11:                      cur = cur->left;
12:                 }
13:                 cur = stack.top();
14:                 stack.pop();
15:                 cur = cur->right;
16:            }
17:            return result;
18:       }
``````

Saturday, November 23, 2013

[LeetCode] Reorder List, Solution

Given a singly linked list L: L0L1→…→Ln-1Ln,
reorder it to: L0LnL1Ln-1L2Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given `{1,2,3,4}`, reorder it to `{1,4,2,3}`.

[Thoughts]

1. 找出中间节点

2. 把中间节点之后的后半部分链表反序

3. 把前半部分链表及后半部分链表合并

[Code]

` 1     void reorderList(ListNode *head) { 2         if(head == NULL) return; 3         // find the median node 4         ListNode* fast = head; 5         ListNode* slow = head; 6         while(true) 7         { 8             fast = fast->next; 9             if(fast == NULL)10                 break;11             fast = fast->next;12             if(fast == NULL)13                 break;14             slow = slow->next;15         }16         17         if(slow == NULL) return;18         19         // reverse second half of link list20         ListNode* cur = slow;21         ListNode* pre = slow->next;22         cur->next = NULL;23         while(pre!=NULL)24         {25             ListNode* temp = pre->next;26             pre->next = cur;27             cur = pre;28             pre = temp;29         }30         31         // merge two lists32         ListNode* first = head;33         ListNode* second = cur;34         35         while(second!= NULL&& first!=NULL && first!=second)36         {37             ListNode* temp = second->next;38             second->next = first->next;39             first->next = second;40             first = second->next;41             second = temp;42         }43     }`

[LeetCode] Linked List Cycle II, Solution

Given a linked list, return the node where the cycle begins. If there is no cycle, return `null`.

Can you solve it without using extra space?

[Thoughts]

指针二  走的路是     2t = X + mY+ K       ②          m,n为未知数

2X + 2nY + 2K = X + mY + K

=>   X+K  =  (m-2n)Y    ③

[Code]

` 1     ListNode *detectCycle(ListNode *head) { 2         ListNode * first = head; 3         ListNode * second = head; 4          5         while(first != NULL && second != NULL) 6         { 7             first = first->next; 8             second = second->next; 9             if(second != NULL)10                 second = second->next;11             if(first == second)12                 break;13         }14         15         if(second == NULL) return NULL;16         17         // 一起往下走X步，就找到节点了。18         first = head;19         while(first!=second)20         {21             first = first->next;22             second = second->next;23         }24         25         return second;26     }`

Wednesday, November 20, 2013

Given a linked list, determine if it has a cycle in it.

Can you solve it without using extra space?

[Thoughts]

[Code]

` 1     bool hasCycle(ListNode *head) { 2         if(head == NULL) return false; 3         ListNode* first = head; 4         ListNode* second = head->next; 5          6         while(first != NULL && second != NULL) 7         { 8             if(first == second) return true; 9             first = first->next;10             second = second->next;11             if(second == NULL)12                 return false;13             second = second->next;14         }15         return false;16     }`

[LeetCode] WordBreak II, Solution

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = `"catsanddog"`,
dict = `["cat", "cats", "and", "sand", "dog"]`.

A solution is `["cats and dog", "cat sand dog"]`.

[Thoughts]

[Code]

` 1     vector<string> wordBreak(string s, unordered_set<string> &dict) { 2         string result; 3         vector<string> solutions; 4         int len = s.size();         5         GetAllSolution(0, s, dict, len, result, solutions); 6         return solutions; 7     } 8      9     void GetAllSolution(int start, const string& s, const unordered_set<string> &dict, int len, string& result, vector<string>& solutions)10     {11         if (start == len)12         {13             solutions.push_back(result.substr(0, result.size()-1));//eliminate the last space14             return;15         }16         for (int i = start; i< len; ++i)17         {18             string piece = s.substr(start, i - start + 1);19             if (dict.find(piece) != dict.end() && possible[i+1])20             {21                 result.append(piece).append(" ");                22                 GetAllSolution(i + 1, s, dict, len, result, solutions);                23                 result.resize(result.size() - piece.size()-1);24             }25         }26     }`

Possible[i] = true 意味着 [i,n]这个区间上有解

` 1     vector<string> wordBreak(string s, unordered_set<string> &dict) { 2         string result; 3         vector<string> solutions; 4         int len = s.size(); 5         vector<bool> possible(len+1, true); // to record the search which has been executed once 6         GetAllSolution(0, s, dict, len, result, solutions, possible); 7         return solutions; 8     } 9     10     void GetAllSolution(int start, const string& s, const unordered_set<string> &dict, int len, string& result, vector<string>& solutions, vector<bool>& possible)11     {12         if (start == len)13         {14             solutions.push_back(result.substr(0, result.size()-1));//eliminate the last space15             return;16         }17         for (int i = start; i< len; ++i)18         {19             string piece = s.substr(start, i - start + 1);20             if (dict.find(piece) != dict.end() && possible[i+1]) // eliminate unnecessory search21             {22                 result.append(piece).append(" ");23                 int beforeChange = solutions.size();24                 GetAllSolution(i + 1, s, dict, len, result, solutions, possible);25                 if(solutions.size() == beforeChange) // if no solution, set the possible to false26                     possible[i+1] = false;27                 result.resize(result.size() - piece.size()-1);28             }29         }30     }`

suoyi

Monday, November 18, 2013

[LeetCode] Word Break, Solution

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"`.

[Thoughts]

possible[i] = true      if  S[0,i]在dictionary里面

= true      if   possible[k] == true 并且 S[k+1,j]在dictionary里面， 0<k<i

= false      if    no such k exist.

[Code]

` 1     bool wordBreak(string s, unordered_set<string> &dict) { 2         string s2 = '#' + s; 3         int len = s2.size(); 4         vector<bool> possible(len, 0); 5          6         possible[0] = true; 7         for(int i =1; i< len; ++i) 8         { 9             for(int k=0; k<i; ++k)10             {11                 possible[i] = possible[k] && 12                                 dict.find(s2.substr(k+1, i-k)) != dict.end();13                 if(possible[i]) break;14             }15         }16         17         return possible[len-1];18     }`

Sunday, November 17, 2013

[LeetCode] Copy List with Random Pointer, Solution

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

[Thoughts]

1. 插入拷贝节点

2. 复制random指针

3.分解至两个独立列表

[Code]

` 1     RandomListNode *copyRandomList(RandomListNode *head) { 2         //insert nodes 3         RandomListNode * cur = head; 4         while(cur!=NULL) 5         { 6             RandomListNode* temp = new RandomListNode(cur->label); 7             temp->next = cur->next; 8             cur->next = temp; 9             cur = temp->next;10         }11         12         // copy random pointer13         cur = head;14         while(cur != NULL)15         {16             RandomListNode* temp = cur->next;17             if(cur->random != NULL)18                 temp->random = cur->random->next;19             cur = temp->next;20         }21         22         //decouple two links23         cur = head;24         RandomListNode* dup = head == NULL? NULL:head->next;25         while(cur != NULL)26         {27             RandomListNode* temp = cur->next;28             cur->next = temp->next;29             if(temp->next!=NULL)30                 temp->next = temp->next->next;31             cur = cur->next;32         }33 34         return dup;35     }`

[LeetCode] Single Number II, Solution

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

[Thoughts]

[Code]

` 1     int singleNumber(int A[], int n) { 2         vector<int> bit(32,0); 3  4         for(int i =0; i< n; ++i) 5         { 6             int k=1; 7             for(int j =0; j<32; ++j) 8             { 9                 int rotated;10                 if((rotated = A[i]>>j) == 0) break;11                 bit[j] += rotated & k;12             }13         }14         15         int target=0;16         for(int i =0; i<32; ++i)17         {18             target += (bit[i]%3 <<i);19         }20         return target;21     }`