[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] Single Number, Solution

Given an array of integers, every element appears twice 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]
不知道这个题从哪里来的，但是明显是针对计算机专业的。很简单，就是位操作，任意两个相同的数如果做异或(Exclusive Or)运算的话，结果为0.所以，这题的解法就是这么直白，从0开始到n，一路异或下去，最后剩下的值就是所求。

[Codes]

1:    int singleNumber(int A[], int n) {  
2:      int left = A[0];  
3:      for(int i =1; i< n; i++)  
4:      {  
5:        left = left ^ A[i];  
6:      }  
7:      return left;  
8:    }  

[LeetCode] Candy, Solution

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?
[Thoughts]
蛮好玩的题。感觉用dp简单点。定义Candy[i]为第i个孩子需要给的最少的糖数，
那么
Candy[i] =            Candy[i-1]+1  if ratings[i] > ratings[i-1] 递增序列，后面小孩需要的糖果是前一个小孩的糖果数+1
                           1                   if ratings[i] == ratings[i-1] 直线，按照题意，如果两个小孩rating一样多，后面的小孩可以只拿一个糖
                           Candy[i-1] –1 if ratings[i] < ratings[i-1] 递减序列。这个递推式显然是有缺陷，因为如果递减序列比较长的话，Candy[i]就可能出现负值了，负值显然是没有意义的。比如下图为例：
蓝线是rating变化曲线，数字是Candy[i]的值。基于上面递推式的解（第一行）明显是不合理的。而第二行经过调整的（红色数字），才是最优解。简单的说，就是当遇到一个波谷的时候，调整一下左边的下降序列就好了，但是要注意区分条件，上一个波峰只在有些条件下才需要更改（例一和例二的区别）。



[Code]

1:         int candy(vector<int> &ratings) {  
2:            vector<int> candy(ratings.size());  
3:            candy[0] = 1;  
4:            int i =1;  
5:            for (; i < ratings.size(); ++i)  
6:            {  
7:                 if (ratings[i] > ratings[i-1]) //递增  
8:                 {  
9:                      candy[i] = candy[i - 1] + 1;  
10:                 }  
11:                 if (ratings[i] == ratings[i-1]) //平行  
12:                 {  
13:                      candy[i] = 1;  
14:                 }  
15:                 if (ratings[i] < ratings[i - 1]) //递减  
16:                 {  
17:                      candy[i] = candy[i - 1] - 1;  
18:                 }  
19:                 if (i<ratings.size()-1 && ratings[i] < ratings[i-1] && ratings[i] <=ratings[i+1])  
20:                      ReAdjustCandy(ratings, candy, i);  
21:            }  
22:            if (ratings[i-1] < ratings[i-2])  
23:                 ReAdjustCandy(ratings, candy, ratings.size() - 1);  
24:            int total = 0;  
25:            std::for_each(candy.begin(), candy.end(), [&](int n){  
26:                 total += n;  
27:            });  
28:            return total;  
29:       }  
30:       void ReAdjustCandy(vector<int>& ratings, vector<int>& candy, int startIndex)  
31:       {  
32:            int k = startIndex;  
33:            int diff = 1 - candy[k];  
34:            while (k > 0 && ratings[k - 1] > ratings[k])  
35:            {  
36:                 candy[k] = candy[k] + diff;  
37:                 k--;  
38:            }  
39:            if (diff > 0) candy[k] += diff;  
40:       }  

[LeetCode] Gas Station, Solution

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

[Thoughts]

蛮精巧的一道题。最直白的解法就是从每一个点开始，遍历整个环，然后找出最后剩余油量最大的点。这个是O(n^2)的。但是这题明显不会无聊到让做题人写个两层循环这么简单。

仔细想一下，其实和以前求最大连续子数组和的题很像。

在任何一个节点，其实我们只关心油的损耗，定义：

diff[i] = gas[i] – cost[i]  0<=i <n

那么这题包含两个问题：

1. 能否在环上绕一圈？

2. 如果能，这个起点在哪里？

第一个问题，很简单，我对diff数组做个加和就好了，leftGas = ∑diff[i]， 如果最后leftGas是正值，那么肯定存在这么一个起始点。如果是负值，那说明，油的损耗大于油的供给，不可能有解。得到第一个问题的答案只需要O(n)。

对于第二个问题，起点在哪里？

假设，我们从环上取一个区间[i, j], j>i， 然后对于这个区间的diff加和，定义

sum[i,j] = ∑diff[k] where i<=k<j

如果sum[i,j]小于0，那么这个起点肯定不会在[i,j]这个区间里，跟第一个问题的原理一样。举个例子，假设i是[0,n]的解，那么我们知道 任意sum[k,i-1] (0<=k<i-1) 肯定是小于0的，否则解就应该是k。同理，sum[i,n]一定是大于0的，否则，解就不应该是i，而是i和n之间的某个点。所以第二题的答案，其实就是在0到n之间，找到第一个连续子序列（这个子序列的结尾必然是n）大于0的。

至此，两个问题都可以在一个循环中解决。

 

[Code]

   1:  class Solution {

   2:  public:

   3:      int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {

   4:          vector<int> diff(gas.size());

   5:          for(int i =0; i< gas.size(); ++i)

   6:          {

   7:              diff[i] = gas[i] - cost[i];

   8:          }

   9:          

  10:          int leftGas=0, sum =0, startnode=0;

  11:          for(int i =0; i<gas.size(); ++i)

  12:          {

  13:              leftGas += diff[i];

  14:              sum += diff[i];

  15:              if(sum <0) //只要小于0就不可能是解

  16:              {

  17:                  startnode = i+1;

  18:                  sum=0;

  19:              }

  20:          }

  21:          if(leftGas <0)

  22:              return -1;

  23:          else

  24:              return startnode;

  25:      }

  26:  };

[Microsoft] string permutation with upcase and lowcase

Give a string, which only contains a-z. List all the permutation of upcase and lowcase.
For example, str = "ab",  the output should be
"ab", "aB", "Ab", "AB"
for str = "abc", the output should be
"abc", "abC", "aBc", "aBC", "Abc", "AbC", "ABc", "ABC"

[Thoughts]
首先,肯定可以用递归来做，每一个节点有大小两种可能。代码可以简单的写成：

  1: void ListPermutation(string sample, int depth, string& result)
  2: {
  3:     if(depth == sample.size())
  4:     {
  5:         prinf("%s\r\n", result.c_str());
  6:         return;
  7:     }
  8:     
  9:     // process low-case char
 10:     result.push_back(sample[depth]);
 11:     ListPermutation(sample, depth+1, result);
 12:     result.pop_back();
 13:     
 14:     //process up-case char
 15:     result.push_back(sample[depth]-32);
 16:     ListPermutation(sample, depth+1, result);
 17:     result.pop_back();
 18: }

但是，如果考虑空间复杂度的话，这是个指数级的实现。如果字符串有几千行或者几万行，内存就不得了了。

如果换个思路想想的话，其实这个题有简单的解法。因为，大写和小写只有两种变化，其实就是0和1的变化。简单的说，如果字符串长L，那么遍历区间[0,2^L-1]，对于任意i，将其转换为长度为L的二进制表示，然后根据每一位二进制是0还是1，来决定输出大写还是小写。实现如下：

  1: void ListPermutation(string sample)
  2: {
  3:     int L = sample.size();
  4:     long end = pow(2, L) -1;
  5:     for(int i =0; i< end; i++)
  6:     {
  7:         // Convert Dec to Binary, 
  8:         // return a string to represent binary data with size L
  9:         string binaryRep = ConvertDecToBinany(i, L);
 10:         
 11:         string output;
 12:         for(int j=0; j<L; j++)
 13:         {
 14:             if(binaryRep[j] == '0') //low case
 15:             {
 16:                 output.push_back(sample[j]);
 17:             }
 18:             else
 19:             {
 20:                 output.push_back(sample[j]-32);
 21:             }        
 22:         }
 23:         printf("%s\r\n", output.c_str());
 24:     }
 25: }

这样的话，整体思路就更清晰，而且内存使用是O(L)。