Category: Leetcode

Description:

https://leetcode.com/problems/search-insert-position/#/description

Algorithm:

The searching for middle is the classic method.

Searching for the insert index will be the left.

Code:

class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if (nums.empty()) return 0;
int n = nums.size();
int left = 0, right = n – 1;
int middle;

while (left <= right)
{
middle = (left + right) / 2;
if (nums[middle] == target)
return middle;
else if (nums[middle] < target)
left = middle + 1;
else
right = middle – 1;
}
return left;
}
};

Timing:

O(logn)

Description:

I. https://leetcode.com/problems/search-in-rotated-sorted-array/#/description

II. https://leetcode.com/problems/search-in-rotated-sorted-array-ii/#/description

Algorithm:

|B ————————————— C | A —————————— (B – 1) |

C is the largest number, A is the minimum number.

Squeeze from left and right.

while (left <= right){

1. if ( middle == target ), return
2. else if ( middle in [B,C] region)
   1. if target in [B, middle) region => right = middle – 1;
   2. else (target in (middle, B]) => left = middle + 1
3. else ( middle in [A, (B-1)] region)
   1. if (target in (middle , (B-1)] region) =>left = middle + 1;
   2. else (target in [B, middle) region) => right = middle – 1;

}

if left > right => return -1 (cannot find target)

 

Code:

class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.empty()) return -1;
// nums.erase(unique(nums.begin(), nums.end()), nums.end()); // if II, use this function
int i = 0;
int n = nums.size();
int mid;
int high = n – 1;
while (i <= high) {
mid = (high + i) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < nums[high]) {
if (target > nums[mid] && nums[high] >= target) {
i = mid + 1;
}
else {
high = mid – 1;
}
}
else {
if (target >= nums[i] && nums[mid]>target) {
high = mid – 1;
}
else {
i = mid + 1;
}
}

 

}
return -1;
}
};

Time Complexity:

O(logn)

Description:

https://leetcode.com/problems/remove-element/#/description

Boundary:

• nums.size() = 0  return 0
• val > maximum  return nums.size()
• if cannot find return nums.size()

Algorithm:

1. sort
2. go through array and find the beginning index and end index of the val
3. nums.erase()

Code:

class Solution {
public:
int removeElement(vector<int>& nums, int val) {
if (nums.size() == 0) return 0;
sort(nums.begin(), nums.end());
if (val > nums[nums.size() – 1]) return nums.size();

int beginner = -1, ender = -1;
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] == val)
{
beginner = i;
ender = i;
while (i + 1 < nums.size() && nums[i] == nums[i + 1])
{
i++;
ender++;
}
break;
}
}
if (ender > -1)
nums.erase(nums.begin() + beginner, nums.begin() + ender + 1);
return nums.size();
}
};

Timing:

O(n)

Description:

https://leetcode.com/problems/letter-combinations-of-a-phone-number/#/description

Boundary:

No

Algorithm:

Nothing special.

Code:

class Solution {
public:
vector<string> letterCombinations(string digits) {
string mapping[10] = { ” “,””,”abc”,”def”,”ghi”,”jkl”,”mno”,”pqrs”,”tuv”,”wxyz” };
vector<string> result1, result2;

for (int i = 0; i < digits.size();i++)
{
int idx = (int)(digits[i]) – 48;
if (idx == 1) continue;
for (int j = 0; j < mapping[idx].size(); j++)
{
if (result1.size() > 0)
for (int k = 0; k < result1.size(); k++)
{
string tmp = “”;
tmp += result1[k] + mapping[idx].substr(j, 1);
result2.push_back(tmp);
}
else
result2.push_back(mapping[idx].substr(j, 1));
}

result1 = result2;
result2.clear();
}
return result1;
}
};

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)

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)

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)

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!

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;

};

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