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]

首先,对于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 };

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 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。

image

现在有两个指针,第一个指针,每走一次走一步,第二个指针每走一次走两步,如果他们走了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 }

Wednesday, November 20, 2013

[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

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]

一个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 }

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.分解至两个独立列表

 

image

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

Wednesday, November 13, 2013

[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]的值。基于上面递推式的解(第一行)明显是不合理的。而第二行经过调整的(红色数字),才是最优解。简单的说,就是当遇到一个波谷的时候,调整一下左边的下降序列就好了,但是要注意区分条件,上一个波峰只在有些条件下才需要更改(例一和例二的区别)。
image


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



Monday, November 11, 2013

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