## 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. 重复节点。