19. Remove Nth Node From End of List

Description:

https://leetcode.com/problems/remove-nth-node-from-end-of-list/#/description

Boundary:

n == length: delete head

n > length: delete nothing

Algorithm:

My method:

Count to find length of the list -> get index of the node in front of the deleted node -> delete (beats 66%)

The optimized method:

Two pointers: pre and pos

Code:

My Code:

class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* node = head;
int length = 0;
while (node != NULL)
{
length++;
node = node->next;
};
if (n > length)
return NULL;
if (n == length) return head->next;

int idx = length – n;
node = head;
for (int i = 0; i < idx – 1; i++)
node = node->next;

// ListNode* tmp = node->next;
node->next = node->next->next;
// delete tmp;
return head;
}
};

 

Optimized Code:

class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* pre = head;
ListNode* pos = head;

while (pre != NULL)
{
if(n < 0)
{
pos = pos -> next;
}
pre = pre -> next;
n–;
};
if (n == 0) return head-> next;
if (n > 0) return NULL;

pos -> next = pos -> next -> next;
return head;
}
};

Timing:

O(n)

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;

  1. scan from left to right and find the left highest for each bar;
  2. scan from right to left and find the right highest for each bar;
  3. get the water area and add up.

Code:

class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
if (n < 2) return 0;
vector<int> left = vector<int>(n, -1);
vector<int> right = vector<int>(n, -1);
vector<int> thisHeight = vector<int>(n, -1);
left[0] = 0;
right[n – 1] = 0;

int left_rec = 0;
int right_rec = 0;
int total = 0;

for (int i = 1; i < n;i++)
{
if (height[i – 1] >= left_rec)
left_rec = height[i – 1];
left[i] = left_rec;
}
for (int i = n – 2; i >= 0;i–)
{
if (height[i + 1] >= right_rec)
right_rec = height[i + 1];
right[i] = right_rec;
}
for (int i = 0; i < n; i++)
{
int tmp = min(left[i], right[i]) – height[i];
thisHeight[i] = tmp > 0 ? tmp : 0;
total += thisHeight[i];
}
return total;
}
};

Timing:

Scan from left to right: O(n)

Scan from right to left: O(n)

add up: O(n)

Total: 3 * O(n) = O(n)

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 = vol > result ? vol:result;
if (height[left] < height[right])
left++;
else
right–;
}
return result;
}
};

 

Timing:

Scan once, O(n)

06/15/2017

Research:

LeetCode:

Parallel Computing Study:

  • Finish watching video of Lesson3: Fundamental GPU Algorithms
    • Reduce
      • Reduction Operator a) binary (two arguments)     b) associative
    • Scan
      • Input:
        • input array
        • binary associative operator
        • identity element [I op a = a]

Guitar:

  • practice

Others:

  • O(1) independent of size of inputs

Presentation next Monday:

  • Prepare the PPT

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