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

06/13/2017

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

06/12/2017

Research: Merge the three scenes (KFR, Origin, GausOptFLow) into one program. Tried to measure time: have problem (the time are all the same) Tried to export mesh but failed. LeetCode: 2. Add Two Numbers Cannot use list2num/num2list (overflow), should use full adder algorithm. 3. Longest Substring Without Repeating Characters “dvdf” Parallel Computing Study: Finish watching video … Read more06/12/2017

3. Longest Substring Without Repeating Characters

Description: https://leetcode.com/problems/longest-substring-without-repeating-characters/#/description Boundary: when s.size() ==0 Algorithm: Initially, I just thought about discard the previous longest string and calculate the new string. However, we cannot discard the whole previous string, the elements may be useful in the following string, such as “dvdf” ‘s result is 3 rather than 2. Code: class Solution { public: int … Read more3. Longest Substring Without Repeating Characters

2. Add Two Numbers

Description: https://leetcode.com/problems/add-two-numbers/#/description Boundary: When one is NULL while the other is not Algorithm: Initially, I want to implement list2int and int2lis, however, I find that when the number gets overflow, it will get the wrong result for list2int. Therefore, the problem should be finished as done for full adder. When (l1 != NULL && l2 … Read more2. Add Two Numbers

566. Reshape the Matrix

Description: https://leetcode.com/problems/reshape-the-matrix/#/description Boundary: r * c == r’ * c’? Algorithm: Store the data in one dim vector and evaluate the new r*c matrix Code: class Solution { public: vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) { int m = nums.size(); int n = nums[0].size(); if (r * c != m * n) return nums; … Read more566. Reshape the Matrix

500. Keyboard Row

Description: https://leetcode.com/problems/keyboard-row/#/description Boundary: NO Algorithm: Not difficult. Use: str.find() < str.nops Code: class Solution { public: vector<string> findWords(vector<string>& words) { vector<string> result; for (int k = 0; k < words.size(); k++) { if (line1_Big.find(words[k][0]) < line1_Big.size() || line1_Sml.find(words[k][0]) < line1_Sml.size()) { if (ifExist(words[k], line1_Big, line1_Sml)) result.push_back(words[k]); } else if (line2_Big.find(words[k][0]) < line2_Big.size() || line2_Sml.find(words[k][0]) < … Read more500. Keyboard Row

557. Reverse Words in a String III

Description: https://leetcode.com/submissions/detail/105718837/ Boundary: No boundary needs to be considered. Algorithm: Use a for loop to read the char in the string one by one, record the start and end of each word. If meets a ‘ ‘, swap poistion and store in an new string. Code: class Solution { public: string reverseWords(string s) { string … Read more557. Reverse Words in a String III

476. Number Complement

Description: https://leetcode.com/problems/number-complement/#/description Boundary: NO Algorithm: 如果直接~num,C++直接进行补码取反。 因此需要设定mask,然后一位一位操作。 Reference: http://blog.chinaunix.net/uid-25909722-id-2856108.html C的位操作常常使用使用一个unsigned int变量来作为位容器。 设置特定的位用| (OR); 清除特定的位用&(AND); 取反特定的位用^(XOR); 取反所有的位用~(NOT); C++中bitset容器来操作位 可以通过to_string()成员函数将容器输出为一个string字符串; 可以通过to_long()成员函数将容器输出到传统的用于C风格的位容器中。 Code:   class Solution { public: int findComplement(int num) { unsigned mask = ~0; while (mask & num) mask <<= 1; return ~mask & ~num; } };