## 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 res;
}
};

Tip:

if use:

res+=a[0][num%10];

res+=a[1][num/10%10];

res+=a[2][num/100%10];

res+=a[3][num/1000%10];

It will be much slower!

## 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   result += m[s[i]]

Code:

class Solution {
public:
int romanToInt(string s) {
if (s.size() == 0) return 0;
m[‘I’] = 1;
m[‘V’] = 5;
m[‘X’] = 10;
m[‘L’] = 50;
m[‘C’] = 100;
m[‘D’] = 500;
m[‘M’] = 1000;
int result = 0;
for (int i = 0; i < s.size() – 1; i++)
{
if (m[s[i]] < m[s[i + 1]])
result -= m[s[i]];
else
result += m[s[i]];
}
result += m[s[s.size() – 1]];
return result;
}
private:
unordered_map <char, int> m;

};

Tips:

Beats 85% , however
If I initialize m before considering boundary. It will be much slower (only beats 15%)

class Solution {
public:
int romanToInt(string s) {

m[‘I’] = 1;
m[‘V’] = 5;
m[‘X’] = 10;
m[‘L’] = 50;
m[‘C’] = 100;
m[‘D’] = 500;
m[‘M’] = 1000;

if (s.size() == 0) return 0;

int result = 0;
for (int i = 0; i < s.size() – 1; i++)
{
if (m[s[i]] < m[s[i + 1]])
result -= m[s[i]];
else
result += m[s[i]];
}
result += m[s[s.size() – 1]];
return result;
}
private:
unordered_map <char, int> m;

};

## 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);
}
else
{
result = -1 * reversePosNum(-x);
}
return result;
}
private:
int reversePosNum(int x)
{
int result = 0;
while (x > 0)
{
if (result > INT_MAX / 10 || 10 * result > INT_MAX – x % 10) return 0;
result = result * 10 + x % 10;
x /= 10;
}
return result;
}
};

## 06/14/2017

Research:

• Implement KFR with Optical Flow in OpenGL
• Cannot Output the model from Unity (only part of the model can be exported), but we can try to test FPS on KroEngine.
• Origin: 90 – 100 FPS
• GausBlur: 62 -69 FPS
• KFR: 58 – 65 FPS

LeetCode:

Parallel Computing Study:

• Finish watching video of Lesson2
• coalesced: access contiguous memory
• strided: access non-contiguous memory
• for floats, (a + b) + c  != a + (b + c), e.g. a = 1, b = 10^99, c = -10 ^ 99
• atomic functions are costly

Guitar:

• practice.

Others:

Presentation next Monday:

• Prepare the PPT

## 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 (total & 0x1)
return find_kth(nums1, m, nums2, n, total / 2 + 1);
else
return (find_kth(nums1, m, nums2, n, total / 2)
+ find_kth(nums1, m, nums2, n, total / 2 + 1)) / 2;
}
private:
static double find_kth(vector<int> A, int m, vector<int> B, int n, int k) {
//always assume that m is equal or smaller than n
if (m > n) return find_kth(B, n, A, m, k);
if (m == 0) return B[k – 1];
if (k == 1) return min(A[0], B[0]);
//divide k into two parts
int pa = min(k / 2, m), pb = k – pa;
if (A[pa – 1] < B[pb – 1])
{
A.erase(A.begin(), A.begin() + pa);
return find_kth(A, m – pa, B, n, k – pa);
}
else if (A[pa – 1] > B[pb – 1])
{
B.erase(B.begin(), B.begin() + pb);
return find_kth(A, m, B, n – pb, k – pb);
}
else
return A[pa – 1];
}
};

## 5. Longest Palindromic Substring

Description:

https://leetcode.com/problems/longest-palindromic-substring/#/description

Boundary:

No

Algorithm:

1. DP (Easy to understand, but slow. Time complexity O(n^2) )
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; j < i; j++)
{
dp[j][i] = s[i] == s[j] && (i-j < 2 || dp[j + 1][i – 1] == 1);
if(dp[j][i] && len < i – j + 1)
{
left = j;
right = i;
len = i – j + 1;
}
}
dp[i][i] = 1;
}
return s.substr(left, right – left + 1);
}
};

Manacher:

class Solution {
public:
// Transform S into T.
// For example, S = “abba”, T = “^#a#b#b#a#\$”.
// ^ and \$ signs are sentinels appended to each end to avoid bounds checking
string preProcess(string s) {
int n = s.length();
if (n == 0) return “^\$”;
string ret = “^”;
for (int i = 0; i < n; i++) ret += “#” + s.substr(i, 1);
ret += “#\$”;
return ret;
}
string longestPalindrome(string s) {
string T = preProcess(s);
const int n = T.length();
// 以T[i] 为中心，向左/右扩张的长度，不包含T[i] 自己，
// 因此P[i] 是源字符串中回文串的长度
vector<int> P = vector<int>(n,-1);
int C = 0, R = 0;
for (int i = 1; i < n – 1; i++) {
int i_mirror = 2 * C – i; // equals to i’ = C – (i-C)
P[i] = (R > i) ? min(R – i, P[i_mirror]) : 0;
// Attempt to expand palindrome centered at i
while (T[i + 1 + P[i]] == T[i – 1 – P[i]])
P[i]++;
// If palindrome centered at i expand past R,
// adjust center based on expanded palindrome.
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
// Find the maximum element in P.
int max_len = 0;
int center_index = 0;
for (int i = 1; i < n – 1; i++) {
if (P[i] > max_len) {
max_len = P[i];
center_index = i;
}
}
return s.substr((center_index – 1 – max_len) / 2, max_len);
}
};

Tips:

1. Get a substring of a string: s.substr(start, LengthOfString);

## 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 also use this to read the ith element in string in string format, you know, s[i] is char)

Parallel Computing Study:

• Finish watching video of Lesson2

Guitar:

• practice.

Others:

Presentation next Monday:

• Prepare the PPT

## 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:

• Cannot use list2num/num2list (overflow), should use full adder algorithm.
• 3. Longest Substring Without Repeating Characters
• “dvdf”

Parallel Computing Study:

• Finish watching video of Lesson2

733Code->C++:

• Panorama Maker

Guitar:

• practice.

Others:

Presentation next Monday:

• Prepare the PPT

## 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 lengthOfLongestSubstring(string s) {
if (!s.size()) return 0;
string cur = “”;
string pre = “”;
for (int k = 0; k < s.size();k++)
{
while (cur.find(s[k]) < cur.npos)
{
if (cur.size() >= pre.size())
pre = cur;
cur.erase(cur.begin());
}
cur += s[k];
}
if (cur.size() < pre.size())
return pre.size();
else
return cur.size();
}
};

Tip:

Beats 65.54%. The time complexity is O(n).

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 != NULL)

sum = l1 -> val+ l2 -> val + carry;

when (one is NULL and the other not)

sum = (l1 or l2) -> val + carry;

finally, if (carry), add carry to the end of list.

Code:

class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int carry = 0;
ListNode* tmp;
ListNode *start = NULL;
ListNode *node = start;
int n1, n2, sum;
while (l1 != NULL || l2 != NULL)
{
if (l1 == NULL)
{
n1 = 0;
}
else
{
n1 = l1->val;
l1 = l1->next;
}
if (l2 == NULL)
{
n2 = 0;
}
else
{
n2 = l2->val;
l2 = l2->next;
}
sum = n1 + n2 + carry;
carry = sum / 10;

if (start == NULL)
{
start = new ListNode(sum % 10);
node = start;
}
else
{
tmp = new ListNode(sum % 10);
node->next = tmp;
node = tmp;
}
}
if (carry)
{
tmp = new ListNode(carry);
node->next = tmp;
}
return start;
}
};

Tip:

My code is identical to the example code of the fastest. However, the fastest is 26ms while mine is 55ms! Why???