42. Trapping Rain Water

Description: https://leetcode.com/problems/trapping-rain-water/#/description Algorithm: Initially I thought about scan from left to right. and find the containers one by one. However, this doesn’t succeed because It may be trapped in local maximization rather than global maximization. The correct way is to; scan from left to right and find the left highest for each bar; scan from … Read more42. Trapping Rain Water

11. Container With Most Water

Description: https://leetcode.com/problems/container-with-most-water/#/description Algorithm: squeeze from left and right. and get the maximun height of left and right. Code: class Solution { public: int maxArea(vector<int>& height) { int left = 0; int right = height.size() – 1; int result = 0; while(left < right) { int vol = min(height[left], height[right]) * (right – left); result = … Read more11. Container With Most Water


Research: Read paper: Real-time Rendering on a Power Budget LeetCode: 12. Integer to Roman Initialiazation of the unordered map affects timing performance 11. Container With Most Water squeeze, O(n) 42. Trapping Rain Water Scan three times Parallel Computing Study: Finish watching video of Lesson3: Fundamental GPU Algorithms Reduce Reduction Operator a) binary (two arguments)     b) associative … Read more06/15/2017

12. Integer to Roman

Description: https://leetcode.com/problems/integer-to-roman/#/description Boundary: when num = 0, 10, 100, 1000 (actually it’s not boundary) Algorithm: There is no better way than hard-coding. Use a 2D array to store the candidates and select. Code: class Solution { public: string intToRoman(int num) { string res; char* a[4][10]={ {“”,”I”,”II”,”III”,”IV”,”V”,”VI”,”VII”,”VIII”,”IX”}, {“”,”X”,”XX”,”XXX”,”XL”,”L”,”LX”,”LXX”,”LXXX”,”XC”}, {“”,”C”,”CC”,”CCC”,”CD”,”D”,”DC”,”DCC”,”DCCC”,”CM”}, {“”,”M”,”MM”,”MMM”} }; res+=a[3][num/1000%10]; res+=a[2][num/100%10]; res+=a[1][num/10%10]; res+=a[0][num%10]; return … Read more12. Integer to Roman

13. Roman to Integer

Description:  https://leetcode.com/problems/roman-to-integer/#/description Boundary: s.size() = 0 Algorithm: Use unordered_map m<char, int> to construct the correspondence between character and number like: character numerical value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 Then check the string s one by one if m[s[i]] < m[s[i+1]]   result -= m[s[i]] else   … Read more13. Roman to Integer

7. Reverse Integer

Description: https://leetcode.com/problems/reverse-integer/#/description Boundary: Overflow Algorithm: The problem is not difficult, but ooverflow has to be considered. Check overflow: if (result > INT_MAX / 10 || 10 * result > INT_MAX – x % 10) return 0; Code: class Solution { public: int reverse(int x) { int result; if (x > 0) { result = reversePosNum(x); } … Read more7. Reverse Integer

4. Median of Two Sorted Arrays

Description: https://leetcode.com/problems/median-of-two-sorted-arrays/#/description Boundary & Algorithm: Should separate odd and even. Use recursion, so boundary includes: destination pos = 0: return directly destination pos = 1 : return min{A[0], B[0]} Code: class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int m = nums1.size(); int n = nums2.size(); int total = m + n; if … Read more4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

Description: https://leetcode.com/problems/longest-palindromic-substring/#/description Boundary: No Algorithm: DP (Easy to understand, but slow. Time complexity O(n^2) ) Manacher (fast, time complexity O(n)) http://www.cnblogs.com/grandyang/p/4475985.html Code: DP: class Solution { public: string longestPalindrome(string s) { int dp[s.size()][s.size()]; int left = 0,right = 0, len = 0; for (int i = 0; i < s.size();i++) { for (int j = 0; … Read more5. Longest Palindromic Substring


Research: Measure time of the three scenes (KFR, Origin, GausOptFlow). Origin: 32.2 fps KFR: 20.4 fps GausOptFlow: 20.2 fps LeetCode: 4. Median of Two Sorted Arrays Cannot use concatinate + sort because the time complexity goes beyond log(m+n). If time complexity is log(*), consider about dichotomy. 5. Longest Palindromic Substring Manacher DP s.substr(start, length) (can … Read more06/13/2017