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]

对于逆波兰式,一般都是用栈来处理,依次处理字符串,

如果是数值,则push到栈里面

如果是操作符,则从栈中pop出来两个元素,计算出值以后,再push到栈里面,

则最后栈里面剩下的元素即为所求。


[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]


这题和链表拷贝类似:http://fisherlei.blogspot.com/2013/11/leetcode-copy-list-with-random-pointer.html


所不同的是,在链表拷贝中,没有借助额外空间,通过多次链表遍历来拷贝、链接及拆分。


而这里图的拷贝,也可以通过多次遍历来插入拷贝节点,链接拷贝节点以及将拷贝节点拆分出来。但是同样的问题是,需要对图进行多次遍历。如果想在一次遍历中,完成拷贝的话,那就需要使用额外的内存来使用map存储源节点和拷贝节点之间的对应关系。有了这个关系之后,在遍历图的过程中,就可以同时处理访问节点及访问节点的拷贝节点,一次完成。详细看下面代码。


 


[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 cur
28 UndirectedGraphNode* neighbCopy = new UndirectedGraphNode(neighb->label);
29 nodeMap[cur]->neighbors.push_back(neighbCopy);
30 nodeMap[neighb] = neighbCopy;
31 visit.push(neighb);
32 }
33 else
34 {
35 // already a copy there. Associate it with the copy of cur
36 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次,但是,如果排序中每一个定位操作都要这样做的话,就太慢了。
所以,问题其实就是,如何能够节省链表节点的定位时间。如果采用merge sort的话,就可以通过递归的特性来避免这个时间损耗。具体看代码

[Code]
关键的部分已用红字标明。通过递归调用的顺序来保证节点的访问顺序。
1:    ListNode *sortList(ListNode *head) {  
2:      if(head == NULL) return NULL;  
3:      int len = 0;  
4:      ListNode* it = head;  
5:      while(it!= NULL)  
6:      {  
7:        len++;  
8:        it = it->next;  
9:      }  
10:      ListNode* newHead = Sort(&head, len);  
11:      return newHead;  
12:    }  
13:    ListNode* Sort(ListNode** head, int length)  
14:    {  
15:         if (length == 1)  
16:         {  
17:              ListNode* temp = *head;            
18:              *head = (*head)->next;  // 确保head每被访问一次,则向后移动一次
19:              temp->next = NULL; // 尾节点需要为NULL,否则Merge函数没法使用 
20:              return temp;  
21:         }  
22:         ListNode* leftHead = Sort(head, length / 2); 
23:         ListNode* rightHead = Sort(head, length - length / 2);  
24:         ListNode* newHead = Merge(leftHead, rightHead);  
25:         return newHead;  
26:    }  
27:    ListNode* Merge(ListNode* first, ListNode* second) // 普通的链表merge函数
28:    {  
29:      ListNode* head = new ListNode(-1);  
30:      ListNode* cur = head;  
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:      }  
47:      cur = head->next;  
48:      delete head;  
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  
3:       ListNode* p = head;  
4:       int len = 0;  
5:       while (p != NULL)  
6:       {  
7:            p = p->next;  
8:            len++;  
9:       }  
10:       ListNode* fakehead = new ListNode(-1);  
11:       fakehead->next = head;       
12:       for (int interval = 1; interval <= len; interval = interval * 2)  
13:       {  
14:            ListNode* pre = fakehead;  
15:            ListNode* slow = fakehead->next, *fast = fakehead->next;  
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:       }  
61:       ListNode* newhead = fakehead->next;  
62:       delete fakehead;  
63:       return newhead;  
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
假设,有两个点(x1,y1), (x2,y2),如果他们都在这条直线上则有
y1 = kx1 +b
y2 = kx2 +b
由此可以得到关系,k = (y2-y1)/(x2-x1)。即如果点c和点a的斜率为k, 而点b和点a的斜率也为k,那么由传递性,可以知道点c和点b也在一条线上。解法就从这里来
取定一个点(xk,yk), 遍历所有节点(xi, yi), 然后统计斜率相同的点数,并求取最大值即可

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