Posts

Showing posts with the label acm

Trapping Rain Water

Image
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 res

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

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

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() { ro

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

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

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 &l

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

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);

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 you

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

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]); }

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 2n

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)

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 co

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);

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++) {

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);

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);

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)