[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:       }  

[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 };

[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:  }  

[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也在一条线上。解法就从这里来
取定一个点(x_k,y_k), 遍历所有节点(x_i, y_i), 然后统计斜率相同的点数，并求取最大值即可

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

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

首先，对于cache，如果希望有O(1)的查找复杂度，肯定要用hashmap来保存key和对象的映射。对于LRU而言，问题在于如何用O(1)解决cache entry的替换问题。

简单的说，cache的存储是一个链表的话，那么只要保证从头到尾的顺序就是cache从新到旧的顺序就好了，对于任何一个节点，如果被访问了，那么就将该节点移至头部。如果cache已满，那么就把尾部的删掉，从头部插入新节点。

所以，需要用到两个数据结构

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 tail
30                 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 head
52         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 };

[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:       }  

[LeetCode] Reorder List, Solution

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-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 list
20         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 lists
32         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.

Follow up:
Can you solve it without using extra space?

[Thoughts]

首先，比较直观的是，先使用Linked List Cycle I的办法，判断是否有cycle。如果有，则从头遍历节点，对于每一个节点，查询是否在环里面，是个O(n^2)的法子。但是仔细想一想，发现这是个数学题。

如下图，假设linked list有环，环长Y，环以外的长度是X。

现在有两个指针，第一个指针，每走一次走一步，第二个指针每走一次走两步，如果他们走了t次之后相遇在K点

那么       指针一  走的路是      t = X + nY + K        ①

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

把等式一代入到等式二中, 有

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

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

这就清晰了，X和K的关系是基于Y互补的。等于说，两个指针相遇以后，再往下走X步就回到Cycle的起点了。这就可以有O(n)的实现了。

 

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

[LeetCode] Linked List Cycle, Solution

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

Follow up:
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 space
14             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数组，如同WordBreak I里面的DP数组一样，用于记录区间拆分的可能性

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

加上剪枝以后，运行时间就大大减少了。（Line 5, 20, 23, 25,26为剪枝部分）

 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 space
15             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 search
21             {
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 false
26                     possible[i+1] = false;
27                 result.resize(result.size() - piece.size()-1);
28             }
29         }
30     }

suoyi

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

一个DP问题。定义possible[i] 为S字符串上[0,i]的子串是否可以被segmented by dictionary.

那么

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]

实现时前面加一个dummy节点，这样可以把三种情况统一到一个表达式里面。

 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     }

[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 pointer
13         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 links
23         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]

这个题有类似于single number的解法，即通过位运算，一遍扫描得到结果。还是读书的时候见过，大概是两个变量，相互做异或、补之类的运算，早不记得详情了。

现在的解法是比较普通的。因为题目已经说了，除了一个数字以外，其他的都出现了3次，如果我们把那个特殊的数剔除，并把剩下的数于每一位来加和的话，每一位上1出现的次数必然都是3的倍数。所以，解法就在这里，将每一位数字分解到32个bit上，统计每一个bit上1出现的次数。最后对于每一个bit上1出现的个数对3取模，剩下的就是结果。

 

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