Trapping Rain Water

Question:

http://www.lintcode.com/en/problem/trapping-rain-water/
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

Example

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

Answer

RunTime : 1272ms

class Solution {
public:
 /*
 * @param heights: a list of integers
 * @return: a integer
 */
 int trapRainWater(vector<int> &heights) {
  // write your code here
  if (heights.size() < 3)
   return 0;
  int result = 0;
  size_t l, r;
  l = 0;
  r = heights.size() - 1;
  while (l < r) {
   while (l < r && heights[l] == 0) l++;
   while (l < r && heights[r] == 0) r--;
   int min = heights[l] < heights[r] ? 

                                  heights[l] : heights[r];
   for (size_t i = l; i <= r; i++) {
    if (heights[i] >= min)
     heights[i] -= min;
    else {
     result += min - heights[i];
     heights[i] = 0;
    }
   }
  }
  return result;
 }
};

Word Break III

Question

http://www.lintcode.com/en/problem/word-break-iii/
Give a dictionary of words and a sentence with all whitespace removed, return the number of sentences you can form by inserting whitespaces to the sentence so that each word can be found in the dictionary.

Example

Given a String CatMat
Given a dictionary ["Cat", "Mat", "Ca", "tM", "at", "C", "Dog", "og", "Do"]
return 3
we can form 3 sentences, as follows:
CatMat = Cat Mat
CatMat = Ca tM at
CatMat = C at Mat

Answer

RunTime : 288ms

class Solution {
public:
 /*
 * @param s: A string
 * @param dict: A dictionary of words dict
 * @return: A boolean
 */
 int wordBreak3(string &s, unordered_set<string> &dict) {
  // write your code here
  if (s.length() <= 0)
   return 0;
  bool found = true;
  for (auto c : s) {
   bool in = false;
   for (auto d : dict) {
    if (in)
     break;
    for (auto e : d) {
     if (e == c) {
      in = true;
      break;
     }
    }
   }
   if (!in) {
    found = false;
    break;
   }
  }
  if (!found)
   return 0;
  Trie trie;
  for (auto d : dict)
   trie.insert(d);
  result = 0;
  wordBreakHelp(s, trie, 0);
  return result;
 }
private:
 int result;
 struct TrieNode {
  TrieNode() {
   for (int i = 0; i < 256; i++) {
    next[i] = 0;
   }
   s = 0;
  }
  int s;
  TrieNode* next[256];
 };
 class Trie {
 public:
  Trie() {
   root = new TrieNode();
  }
  inline void deleteHelper(TrieNode* root) {
   if (root) {
    for (int i = 0; i < 256; i++) {
     deleteHelper(root->next[i]);
    }
    delete root;
   }
  }
  ~Trie() {
   deleteHelper(root);
   root = 0;
  }
  void insert(string& s) {
   TrieNode* iter = root;
   for (auto c : s) {
    if (iter->next[c] == 0)
     iter->next[c] = new TrieNode();
    iter = iter->next[c];
   }
   iter->s = s.length();
  }
  unordered_set<int> search(string& s, int pos) {
   TrieNode* iter = root;
   unordered_set<int> words;
   for (size_t i = pos; i < s.length(); i++) {
    char c = s[i];
    if (iter->next[c] == 0)
     break;
    if (iter->s > 0) {
     words.insert(iter->s);
    }
    iter = iter->next[c];
   }
   if (iter->s > 0) {
    words.insert(iter->s);
   }
   return words;
  }
 private:
  TrieNode* root;
 };
 inline void wordBreakHelp(string& s, Trie& trie, int pos) {
  unordered_set<int> words = trie.search(s, pos);
  if (words.size() > 0) {
   for (auto word : words) {
    if ((pos + word) == s.length()) {
     result++;
    }
    else {
     wordBreakHelp(s, trie, pos + word);
    }
   }
  }
 }
};

Word Break II

Question

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.

Example

Gieve s = lintcode,
dict = ["de", "ding", "co", "code", "lint"].
A solution is ["lint code", "lint co de"].

Answer

RunTime : 902ms

class Solution {
public:
 /*
 * @param s: A string
 * @param dict: A dictionary of words dict
 * @return: A boolean
 */
 vector<string> wordBreak(string &s, unordered_set<string> &dict) {
  // write your code here
  result.clear();
  if (s.length() <= 0)
   return result;
  bool found = true;
  for (auto c : s) {
   bool in = false;
   for (auto d : dict) {
    if (in)
     break;
    for (auto e : d) {
     if (e == c) {
      in = true;
      break;
     }
    }
   }
   if (!in) {
    found = false;
    break;
   }
  }
  if (!found)
   return result;
  Trie trie;
  for (auto d : dict)
   trie.insert(d);
  string bw;
  wordBreakHelp(s, trie, 0, bw);
  return result;
 }
private:
 vector<string> result;
 struct TrieNode {
  TrieNode() {
   for (int i = 0; i < 26; i++) {
    next[i] = 0;
   }
   s = 0;
  }
  int s;
  TrieNode* next[26];
 };
 class Trie {
 public:
  Trie() {
   root = new TrieNode();
  }
  inline void deleteHelper(TrieNode* root) {
   if (root) {
    for (int i = 0; i < 26; i++) {
     deleteHelper(root->next[i]);
    }
    delete root;
   }
  }
  ~Trie() {
   deleteHelper(root);
   root = 0;
  }
  void insert(string& s) {
   TrieNode* iter = root;
   for (auto c : s) {
    if (iter->next[c - 'a'] == 0)
     iter->next[c - 'a'] = new TrieNode();
    iter = iter->next[c - 'a'];
   }
   iter->s = s.length();
  }
  unordered_set<int> search(string& s, int pos) {
   TrieNode* iter = root;
   unordered_set<int> words;
   for (size_t i = pos; i < s.length(); i++) {
    char c = s[i];
    if (iter->next[c - 'a'] == 0)
     break;
    if (iter->s > 0) {
     words.insert(iter->s);
    }
    iter = iter->next[c - 'a'];
   }
   if (iter->s > 0) {
    words.insert(iter->s);
   }
   return words;
  }
 private:
  TrieNode* root;
 };
 inline void wordBreakHelp(string& s, Trie& trie, int pos, string& bw) {
  unordered_set<int> words = trie.search(s, pos);
  if (words.size() > 0) {
   for (auto word : words) {
    string bwd = bw;
    if (bwd.empty())
     bwd = s.substr(pos, word);
    else {
     bwd.append(" ");
     bwd.append(s.substr(pos, word));
    }
    if ((pos + word) == s.length()) {
     result.push_back(bwd);
    }
    else {
     wordBreakHelp(s, trie, pos + word, bwd);
    }
   }
  }
 }
};

Word Break

Question

http://www.lintcode.com/en/problem/word-break/
Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words.

Example

Given s = "lintcode", dict = ["lint", "code"].
Return true because "lintcode" can be break as "lint code".

Answer

Run Time : 582ms 

class Solution {
public:
 /*
 * @param s: A string
 * @param dict: A dictionary of words dict
 * @return: A boolean
 */

 bool wordBreak(string &s, unordered_set<string> &dict) {
  // write your code here
  if (dict.size() <= 0) {
   if (s.length() <= 0)
    return true;
   return false;
  }
  Trie trie;
  for (auto d : dict)
   trie.insert(d);
  return wordBreakHelp(s, trie, 0);
 }
private:
 struct TrieNode {
  TrieNode() {
   for (int i = 0; i < 26; i++) {
    next[i] = 0;    
   }
   s = 0;
  }
  int s;
  TrieNode* next[26];
 };
 class Trie {
 public:
  Trie() {
   root = new TrieNode();
  }
  inline void deleteHelper(TrieNode* root) {
   if (root) {
    for (int i = 0; i < 26; i++) {
     deleteHelper(root->next[i]);
    }
    delete root;
   }
  }
  ~Trie() {
   deleteHelper(root);
   root = 0;
  }
  void insert(string& s) {
   TrieNode* iter = root;
   for (auto c : s) {
    if (iter->next[c - 'a'] == 0)
     iter->next[c - 'a'] = new TrieNode();
    iter = iter->next[c - 'a'];
   }
   iter->s = s.length();
  }
  unordered_set<int> search(string& s, int pos) {
   TrieNode* iter = root;
   unordered_set<int> words;
   for (int i = pos; i < s.length(); i++) {
    char c = s[i];
    if (iter->next[c - 'a'] == 0)
     break;
    if (iter->s > 0) {
     words.insert(iter->s);
    }
    iter = iter->next[c - 'a'];
   }
   if (iter->s > 0) {
    words.insert(iter->s);
   }
   return words;
  }
 private:
  TrieNode* root;
 };
 inline bool wordBreakHelp(string& s, Trie& trie, int pos) {
  unordered_set<int> words = trie.search(s, pos);
  if (s.length() > 0 && words.size() > 0) {
   for (auto word : words) {
    if ((pos + word) == s.length())
     return true;    
    if (wordBreakHelp(s, trie, pos+word))
     return true;
   }
  }
  return false;
 }
}; 

Unique Paths III

Question

http://www.lintcode.com/en/problem/unique-paths-iii/
Follow up for "Unique Paths II": https://acm.errong.win/uniquepathsii/
Now each grid contains a value, so each path also has a value. Find the sum of all the unique values paths.

Example

For example,
[
[1,1,2],
[1,2,3],
[3,2,4]
]
There are 2 unique value path:
[1,1,2,3,4] = 11
[1,1,2,2,4] = 10
return 21

Answer

class Solution {
public:
 /*
 * @param : an array of arrays
 * @return: the sum of all unique weighted paths
 */
 int uniqueWeightedPaths(vector<vector<int>> &obstacleGrid) {
  int m = obstacleGrid.size();
  if (m <= 0)
   return 0;
  int n = obstacleGrid[0].size();
  if (n <= 0)
   return 0;
  struct Up {
   int step;
   int sum;
   Up(int st, int su) : step(st), sum(su) {}
  };
  map<int, vector<Up>> sum_paths;
  sum_paths[0] = vector<Up>();
  sum_paths[0].push_back(Up(0, obstacleGrid[0][0]));
  for (int i = 1; i < m + n - 1; i++) {
   map<int, vector<Up>> new_sum_paths;
   for (auto sp : sum_paths) {
    int pos = sp.first;
    int x = pos / n;
    int y = pos % n;
    int nx = x + 1;
    int ny = y;    
    if (nx < m) {
     int npos = nx * n + ny;
     for (auto up : sp.second) {
      if (up.step < i) {
       Up nup = up;
       nup.sum += obstacleGrid[nx][ny];
       nup.step += 1;
       bool found = false;
       if (!new_sum_paths.count(npos)) {
        new_sum_paths[npos] = vector<Up>();
       }
       for (auto eup : new_sum_paths[npos]) {
        if (eup.sum == nup.sum) {
         found = true;
         break;
        }
       }
       if (!found)
        new_sum_paths[npos].push_back(nup);
      }
     }
    }
    nx = x;
    ny = y + 1;
    if (ny < n) {
     int npos = nx * n + ny;
     for (auto up : sp.second) {
      if (up.step < i) {
       Up nup = up;
       nup.sum += obstacleGrid[nx][ny];
       nup.step += 1;
       bool found = false;
       if (!new_sum_paths.count(npos)) {
        new_sum_paths[npos] = vector<Up>();
       }
       for (auto eup : new_sum_paths[npos]) {
        if (eup.sum == nup.sum) {
         found = true;
         break;
        }
       }
       if (!found)
        new_sum_paths[npos].push_back(nup);
      }
     }
    }
   }
   sum_paths = new_sum_paths;
  }
   int sum = 0;
  int pos = m*n - 1;
  for (auto sp : sum_paths[pos]) {
   sum += sp.sum;
  }
  return sum;
 }
};

Unique Paths II

Question

http://www.lintcode.com/en/problem/unique-paths-ii/
Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Example

For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.

Answer

class Solution {
public:
    /*
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */
    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) {
        int m = obstacleGrid.size();
        if (m <= 0)
            return 0;
        int n = obstacleGrid[0].size();
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1)
            return 0;
        vector<vector<int>> res(m, vector<int>(n, 0));
        res[0][0] = 1;
        for (int j = 1; j < n; j++) {
             if (obstacleGrid[0][j] == 1) {
                 for (int i = j; i < n; i++)
                      res[0][i] = 0;
                 break;
             } else
                 res[0][j] = 1;
        }
        for (int j = 1; j < m; j++) {
             if (obstacleGrid[j][0] == 1) {
                 for (int i = j; i < m; i++)
                      res[i][0] = 0;
                 break;
             } else {
                 res[j][0] = 1;
             }
        }
        for (int i = 1; i < m; i++) {
             for (int j = 1; j < n; j++) {
                 if (obstacleGrid[i][j] == 1)
                     res[i][j] = 0;
                 else
                     res[i][j] = res[i-1][j] + res[i][j-1];
             }
        }
        return res[m-1][n-1];
    }
};

Unique Paths

Question

http://www.lintcode.com/en/problem/unique-paths/
A robot is located at the top-left corner of a m x n grid.
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid.
How many possible unique paths are there?

Example

Given m = 3 and n = 3, return 6.
Given m = 4 and n = 5, return 35.
Given m = 6 end = 63, return 9657648

Answer

// brute force solution, Time Limit Exceeded
// help us get dp formula pattern
// res[i][j] = res[i-1][j] + res[i][j-1];
public int uniquePaths(int m, int n) {
    return helper(1, 1, m, n);
}
private int helper(int row, int col, int m, int n)
{
    if(row == m && col == n)
        return 1;  
    if( row > m || col > n)
        return 0;
    return helper(row+1, col, m, n) + helper(row, col+1, m, n);
}

// dp solution
class Solution {
public:
    /*
     * @param m: positive integer (1 <= m <= 100)
     * @param n: positive integer (1 <= n <= 100)
     * @return: An integer
     */
    int uniquePaths(int m, int n) {
        // write your code here
        if (m <= 0 || n <= 0)
            return 0;
        vector<int> res(n);
        res[0] = 1;
        for (int i = 0; i < m; i++) {
             for (int j = 1; j < n; j++) {
                  res[j] += res[j-1];
             }
        }
        return res[n-1];
    }
};

Next Sparse Number

Question

http://www.lintcode.com/en/problem/next-sparse-number/
A number is Sparse if there are no two adjacent 1s in its binary representation. Given a number n, find the smallest Sparse number which greater than or equal to n.
eg. 5 (binary representation: 101) is sparse, but 6 (binary representation: 110) is not sparse.

Example

Given n = 6, return 8
Next Sparse Number is 8

Given n = 4, return 4
Next Sparse Number is 4

Given n = 38, return 40
Next Sparse Number is 40

Given n = 44, return 64
Next Sparse Number is 64

Given n = 341381939, return 343932928
Next Sparse Number is 343932928

Answer

class Solution {
public:
    /*
     * @param : a number
     * @return: return the next sparse number behind x
     */
    int nextSparseNum(int x) {
        // write your code here
        if (x == 0 || x == 1) return x;
        string binary;
        int n = x;
        while (n) {
            if (n&1)
                binary.append("1");
            else
                binary.append("0");
            n >>= 1;
        }
        for (int i = 1; i < binary.length(); i++) {
            if (binary[i] == '1' && binary[i-1] == '1') {
                // plus 1 from i-1
                int c = 1;
                int j = i-1;
                while (c == 1 && j < binary.length()) {
                    int t = binary[j] - '0' + c;
                    if (t < 2) {
                        c = 0;
                        binary[j] = t + '0';
                    } else {
                        c = 1;
                        binary[j] = '0';
                    }
                    j++;
                }
                if (c == 1)
                    binary.append("1");
            }
        }
        int result = 0;
        for (int i = 0; i < binary.length() - 1; i++) {
            if (binary[i] == '1') {
                string nb = binary;
                nb[i] = '0';
                int nx = bintoint(nb);
                if (nx >= x) {
                    binary[i] = '0';
                    if (result == 0)
                        result = nx;
                    else if (result > nx)
                        result = nx;
                }
            }
        }
        if (result == 0)
            result = bintoint(binary);
        return result;
    }
    inline int bintoint(string& binary) {
       int result = 0;
       for (int i = binary.length(); i > 0; i--)
            result += (binary[i-1] - '0') << (i-1);
       return result;
    }
};

Maximum Subarray VI

Question

Given an array of integers. find the maximum XOR subarray value in given array.
What's the XOR: https://en.wikipedia.org/wiki/Exclusive_or

Notice

Expected time complexity O(n).

Answer

https://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems
Let's say F(L,R) is XOR of subarray from L to R.
Here we use the property that F(L,R)=F(1,R) XOR F(1,L-1). How?
Let's say our subarray with maximum XOR ended at position i. Now, we need to maximise F(L,i) ie. F(1,i) XOR F(1,L-1) where L<=i. Suppose, we inserted F(1,L-1) in our trie for all L<=i, then it's just problem1.

class Solution {
public:
    /*
     * @param : the array
     * @return: the max xor sum of the subarray in a given array
     */    
    int maxXorSubarray(vector<int> &nums) {
        // write code here
        int ans = INT_MIN;
        int pre = 0;
        Trie trie;
        for (auto n : nums) {
            pre = pre ^ n;
            trie.insert(pre);
            ans = max(ans, trie.query(pre));
        }
        return ans;
    }
private:    
    class Trie {
    public:
        Trie() {
            root = new TrieNode(0);
            INTBITS = sizeof(int) * 8;
        }
        void insert(int x) {
            TrieNode* iter = root;
            for (int i = INTBITS - 1; i >= 0; i--) {
                bool v = x & (1 << i);
                if (iter->arr[v] == 0)
                    iter->arr[v] = new TrieNode(0);
                iter = iter->arr[v];
            }
            iter->val = x;
        }
        int query(int x) {
            TrieNode* iter = root;
            for (int i = INTBITS - 1; i >= 0; i--) {
                bool v = x & (1 << i);
                if (iter->arr[1-v] != 0)
                    iter = iter->arr[1-v];
                else if (iter->arr[v] != 0)
                    iter = iter->arr[v];
            }
            return x ^ iter->val;
        }
    private:
        class TrieNode {
        public:
            int val;
            TrieNode *arr[2];
            TrieNode(int v)
                : val(v) {
                arr[0] = arr[1] = 0;
            }
        };
        TrieNode* root;
        int INTBITS;
    };    
};

Maximum Subarray III

Question:

http://www.lintcode.com/en/problem/maximum-subarray-iii/
Given an array of integers and a number k, find k non-overlapping subarrays which have the largest sum.
The number in each subarray should be contiguous.
Return the largest sum.

Answer

localMax[i][j], means the maximum sum we can get while select j subarrays 

from first i elements, including element i 

globalMax[i][j], means the maximum sum we can get while select j subarrays 

from first i elements, may not including element i 

// state transfer 

localMax[i][j] = max(localMax[i - 1][j] + nums[i - 1], globalMax[i - 1][j - 1] + nums[i - 1]) 

globalMax[i][j] = max(globalMax[i - 1][j], localMax[i][j]) 

class Solution {
public:
    /*
     * @param nums: A list of integers
     * @param k: An integer denote to find k non-overlapping subarrays
     * @return: An integer denote the sum of max k non-overlapping subarrays
     */
    int maxSubArray(vector<int> &nums, int k) {
        // write your code here
        int n = nums.size();
        if (n == 0 || k > n)
            return 0;
        // Use INT_MIN might cause numeric overflow 
        vector<vector<int>> localMax(n+1, vector<int>(k+1, INT_MIN/2));
        vector<vector<int>> globalMax(n+1, vector<int>(k+1, INT_MIN/2));

        localMax[0][0] = globalMax[0][0] = 0;

        for (int i = 1; i <= n; i++) {
             localMax[i][0] = 0;
             globalMax[i][0] = 0;
             for (int j = 1; j <= k; j++) {
                  localMax[i][j] = max(localMax[i-1][j] + nums[i-1], 
                                       globalMax[i-1][j-1] + nums[i-1]);
                  globalMax[i][j] = max(globalMax[i-1][j], localMax[i][j]);
             }
        }
        return globalMax[n][k];
    }
};

Maximum Subarray II

Question

Given an array of integers, find two non-overlapping subarrays which have the largest sum.
The number in each subarray should be contiguous.
Return the largest sum.

Notice

The subarray should contain at least one number

Answer

class Solution {
public:
    /*
     * @param nums: A list of integers
     * @return: An integer denotes the sum of max two non-overlapping subarrays
     */
    int maxTwoSubArrays(vector<int> &nums) {
        // write your code here
        int len = nums.size();
        vector<int> suml(len);
        int cur_max = nums[0];
        int max = cur_max;
        suml[0] = max;
        for (int i = 1; i < len; i++) {
            if (cur_max <= 0) {
                cur_max = nums[i];
            } else {
                cur_max += nums[i];
            }
            if (max < cur_max)
                max = cur_max;
            suml[i] = max;
        }
        vector<int> sumr(len);
        cur_max = nums[len-1];
        max = cur_max;
        sumr[len-1] = max;
        for (int i = len - 2; i >= 0; i--) {
             if (cur_max <= 0) {
                 cur_max = nums[i];
             } else {
                 cur_max += nums[i];
             }
             if (max < cur_max)
                 max = cur_max;
             sumr[i] = max;
        }
        int result = suml[0] + sumr[1];
        for (int i = 1; i < len - 1; i++) {
             int temp = suml[i] + sumr[i+1];
             if (result < temp)
                 result = temp;
        }
        return result;
    }
};

Candy

Question:

http://www.lintcode.com/en/problem/candy/
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?

Answer:

class Solution {
public:
    /*
     * @param ratings: Children's ratings
     * @return: the minimum candies you must give
     */
    int candy(vector<int> &ratings) {
        // write your code here
        vector<int> candys(ratings.size(), 1);
        for (int i = 0; i < ratings.size() - 1; i++) {
            if (ratings[i+1] > ratings[i])
                candys[i+1] = candys[i] + 1;
        }
        for (int i = ratings.size() - 1; i > 0; i--) {
            if (ratings[i-1] > ratings[i])
                candys[i-1] = max(candys[i] + 1, candys[i-1]);
        }
        int count = 0;
        for (auto i : candys)
            count += i;
        return count;
    }
};

Course Schedule III

Question:

http://www.lintcode.com/en/problem/course-schedule-iii/
There are ·n· different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on dth day. A course should be taken continuously for t days and must be finished before or on the dth day. You will start at the 1st day.
Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken.

Notice

The integer 1 <= d, t, n <= 10,000. You can't take two courses simultaneously. 

Example

Given [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
return 3
There're totally 4 courses, but you can take 3 courses at most:
First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day.
Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day.
The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.

Answer:

class Solution {
public:
    /*
     * @param : duration and close day of each course
     * @return: the maximal number of courses that can be taken
     */
    int scheduleCourse(vector<vector<int>> &courses) {
        // write your code here
        int curTime = 0;
        priority_queue<int> q;
        sort(courses.begin(), courses.end(), [](vector<int>& a, vector<int>& b) {return a[1] < b[1];});
        for (auto course : courses) {
            curTime += course[0];
            q.push(course[0]);
            if (curTime > course[1]) {
                curTime -= q.top(); q.pop();
            }
        }
        return q.size();
    }
};

Course Schedule II

Question:

http://www.lintcode.com/en/problem/course-schedule-ii/
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example

Given n = 2, prerequisites = [[1,0]]
Return [0,1]
Given n = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Return [0,1,2,3] or [0,2,1,3]

Answer:

class Solution {
public:
    /*
     * @param numCourses: a total of n courses
     * @param prerequisites: a list of prerequisite pairs
     * @return: the course order
     */
    vector<int> findOrder(int numCourses, vector<pair<int, int>> &prerequisites) {
        // write your code here
        vector<vector<int>> adj(numCourses);
        vector<int> indegree(numCourses);
        for (int i = 0; i < numCourses; i++)
             indegree[i] = 0;
        for (auto pq : prerequisites) {
            adj[pq.second].push_back(pq.first);
            indegree[pq.first]++;
        }
        stack<int> st;
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0)
                st.push(i);
        }
        int count = 0;
        vector<int> result;
        while (!st.empty()) {
            int v1 = st.top();
            st.pop();
            count++;
            result.push_back(v1);
            for (auto v2 : adj[v1]) {
                indegree[v2]--;
                if (indegree[v2] == 0)
                    st.push(v2);
            }
        }
        if (count != numCourses) {
            return vector<int>();
        }
        return result;
    }
};

Topological Sorting

Question:

http://www.lintcode.com/en/problem/topological-sorting/
Given an directed graph, a topological order of the graph nodes is defined as follow:
For each directed edge A -> B in graph, A must before B in the order list.
The first node in the order can be any node in the graph with no nodes direct to it.
Find any topological order for the given graph.

Answer:

class Solution {
public:
    /*
     * @param ratings: Children's ratings
     * @return: the minimum candies you must give
     */
    int candy(vector<int> &ratings) {
        // write your code here
        vector<int> candys(ratings.size(), 1);
        for (int i = 0; i < ratings.size() - 1; i++) {
            if (ratings[i+1] > ratings[i])
                candys[i+1] = candys[i] + 1;
        }
        for (int i = ratings.size() - 1; i > 0; i--) {
            if (ratings[i-1] > ratings[i])
                candys[i-1] = max(candys[i] + 1, candys[i-1]);
        }
        int count = 0;
        for (auto i : candys)
            count += i;
        return count;
    }
};

Course Schedule

Question:

http://www.lintcode.com/en/problem/course-schedule/
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Answer:

class Solution {
public:
    /*
     * @param numCourses: a total of n courses
     * @param prerequisites: a list of prerequisite pairs
     * @return: true if can finish all courses or false
     */
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        // Write your code here
        vector<vector<int>> adj(numCourses);
        vector<int> indegree(numCourses);
        for (int i = 0; i < numCourses; i++)
             indegree[i] = 0;
        for (auto pq : prerequisites) {
            adj[pq.first].push_back(pq.second);
            indegree[pq.second]++;
        }
        stack<int> st;
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0)
                st.push(i);
        }
        int count = 0;
        while (!st.empty()) {
            int v1 = st.top();
            st.pop();
            count++;
            for (auto v2 : adj[v1]) {
                indegree[v2]--;
                if (indegree[v2] == 0)
                    st.push(v2);
            }
        }
        return count == numCourses;
    }
}

Wildcard Matching

Question:
http://www.lintcode.com/en/problem/wildcard-matching/
Implement wildcard pattern matching with support for '?' and '*'.

    '?' Matches any single character. 

    '*' Matches any sequence of characters (including the empty sequence). 

The matching should cover the entire input string (not partial).


Answer:

class Solution {
public:
    /*
     * @param s: A string 
     * @param p: A string includes "?" and "*"
     * @return: is Match?
     */
    bool isMatch(string &s, string &p) {
        if (p.empty())
            return false;
        int n = s.length();
        int m = p.length();
        bool f[n + 1][m + 1];
        memset(f, false, sizeof(f));
        f[0][0] = true;
        for (int i = 1; i <= n; i++)
            f[i][0] = false;
        for (int i = 1; i <= m; i++)
            f[0][i] = f[0][i - 1] && p[i - 1] == '*';
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p[j - 1] == '*') {
                    f[i][j] = f[i - 1][j] || f[i][j - 1];
                } else if (p[j - 1] == '?') {
                    f[i][j] = f[i - 1][j - 1];
                } else {
                    f[i][j] = f[i - 1][j - 1] && (s[i - 1] == p[j - 1]);
                }
            }
        } 
        return f[n][m];
    }
}; 

Maximum Gap

Question:
http://www.lintcode.com/en/problem/maximum-gap/
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Return 0 if the array contains less than 2 elements.
Sort is easy but will cost O(nlogn) time. Try to solve it in linear time and space.
Answer:

class Solution {  
public:  
    int maximumGap(vector<int> &num) {  
       if (num.size() < 2) return 0;  
        int maxNum = num[0];  
        int minNum = num[0];  
        for (int x : num) {  
            maxNum = max(maxNum, x);  
            minNum = min(minNum, x);  
        }  
        int len = (maxNum - minNum) / num.size() + 1;  
        vector<vector<int>> buckets((maxNum - minNum) / len + 1);  
        for (int x : num) {  
            int i = (x - minNum) / len;  
            if (buckets[i].empty()) {  
                buckets[i].reserve(2);  
                buckets[i].push_back(x);  
                buckets[i].push_back(x);  
            } else {  
                if (x < buckets[i][0]) buckets[i][0] = x;  
                if (x > buckets[i][1]) buckets[i][1] = x;  
            }  
        }  
        int gap = 0;  
        int prev = 0;  
        for (int i = 1; i < buckets.size(); i++) {  
            if (buckets[i].empty()) continue;  
            gap = max(gap, buckets[i][0] - buckets[prev][1]);  
            prev = i;  
        }  
        return gap;  
    }  
};

Wiggle Sort II

Question:
http://www.lintcode.com/en/problem/wiggle-sort-ii/
Given an unsorted array nums, reorder it such that
nums[0] < nums[1] > nums[2] < nums[3]....

Answer:

class Solution {
public:
    /*
     * @param nums: A list of integers
     * @return: nothing
     */
    inline int partion(vector<int> &nums, int left, int right) {
        int pivot = nums[left];
        int i = left - 1;
        int j = right + 1;
        while (1) {
            do {
                i = i + 1;
            } while (nums[i] < pivot);
            do {
                j = j -1;
            } while (nums[j] > pivot);
            if (i >= j)
                return j;
            int temp = nums[i];            
            nums[i] = nums[j];            
            nums[j] = temp;             
        }
    }
    inline void qsort(vector<int> &nums,  int left, int right) {
        if (left >= right)
            return;
        int p = partion(nums, left, right);
        qsort(nums, left, p);
        qsort(nums, p+1, right);
    }     
    void wiggleSort(vector<int> &nums) {
        // write your code here
        vector<int> temp(nums.size());
        qsort(nums, 0, nums.size()-1);
        int s = (nums.size() + 1) >> 1;
        int t = nums.size();
        for (int i = 0; i < nums.size(); i++) {
            temp[i] = (i & 1) == 0 ?  nums[--s] : nums[--t] ;
        }
        nums = temp;
    }
};

Wiggle Sort

Question:
http://www.lintcode.com/en/problem/wiggle-sort/
Given an unsorted array nums, reorder it in-place such that
nums[0] <= nums[1] >= nums[2] <= nums[3]....
Example
Given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].

Answer:

class Solution {
public:
    /*
     * @param nums: A list of integers
     * @return: nothing
     */
    inline int partion(vector<int> &nums, int left, int right) {
        int pivot = nums[left];
        int i = left - 1;
        int j = right + 1;
        while (1) {
            do {
                i = i + 1;
            } while (nums[i] < pivot);
            do {
                j = j -1;
            } while (nums[j] > pivot);
            if (i >= j)
                return j;
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp; 
        }
    }
    inline void qsort(vector<int> &nums,  int left, int right) {
        if (left >= right)
            return;
        int p = partion(nums, left, right);
        qsort(nums, left, p);
        qsort(nums, p+1, right);
    }
    void wiggleSort(vector<int> &nums) {
        // write your code here
        vector<int> sort = nums;
        int len = nums.size();
        qsort(sort, 0, len-1);
        int l = 0;
        int r = len - 1;
        nums.clear();
        while (l < r) {
          nums.push_back(sort[l]);
          nums.push_back(sort[r]);
          l++;
          r--;
        }
        if (l == r)
          nums.push_back(sort[l]);
    }
};