Author: xiaoxumeng

Description:

https://leetcode.com/problems/pascals-triangle-ii/#/description

Algorithm:

If we use only one vector and update the vector each cycle, we might have the problem of losing old data.

While using two vector will take extra time and space.

So we should use some techniques to calculate the elements!

Because we are afraid of missing result[i – 1], we can try to get result with decreasing index!

For example:

1, 3, 3, 1 -> 1,4, 6, 4, 1

If update with increasing index:

1, 3, 3, 1

1, 4, 3, 1

1, 4, 7, 1

1, 4, 7, 11, 1 -> wrong!

If update with decreasing index:

1, 3, 3, 1

1, 3, 3, 4, 1

1, 3, 6, 4, 1

1, 4, 6, 4, 1 -> correct!

Code:

class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> kthRow(rowIndex + 1, 0);
kthRow[0] = 1;
for (int row = 1; row <= rowIndex; row++)
for (int col = row; col > 0; col--)
kthRow[col] = kthRow[col - 1] + kthRow[col];
return kthRow;
}
};

Timing:

fastest, oms

Description:

https://leetcode.com/problems/pascals-triangle/#/description

Code:

class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> result;
for (int i = 1; i <= numRows;i++)
{
vector <int> row = vector<int>(i, 1);
if (i >= 3)
for (int j = 1; j < i - 1;j++)
row[j] = result[i - 2][j - 1] + result[i - 2][j];
result.push_back(row);
}
return result;
}
};

Timing:

3ms (beats 4.91%)

Description:

https://leetcode.com/problems/subsets-ii/#/description

Algorithm for 90. Subsets II:
Solution1:

Solution1 is similar to the solution of 78. Subsets. There are two choices: add the number to answer or not.

The key point is to sort the input, then sort + erase unique for the final answer.

Remeber: unique() only remove the adjacent duplicate elements. To remove all the duplicates, sort() must be applied to the vector.

Solution2:

Use for loop in the DFS function.

Code1:

class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> result;
vector<int>path;
helper(nums, path, 0, result);
result.erase(unique(result.begin(), result.end()), result.end());
result.erase(unique(result.begin(), result.end()), result.end());
return result;
}
private:
void helper(vector<int> &nums, vector<int> &path, int step, vector<vector<int>> &result)
{
if (step == nums.size())
{
result.push_back(path);
return;
}
helper(nums, path, step + 1, result);
path.push_back(nums[step]);
helper(nums, path, step + 1, result);
path.pop_back();
}
};

Code2:

class Solution2 {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
vector<int>path;
result.push_back({});
helper(nums, path, 0, result);
return result;
}
private:
void helper(vector<int> &nums, vector<int> &path, int step, vector<vector<int>> &result)
{
for (int i = step; i < nums.size();i++)
{
if (i > step && nums[i] == nums[i - 1])
continue;
path.push_back(nums[i]);
result.push_back(path);
helper(nums, path, i + 1, result);
path.pop_back();
}
}
};

Timing:

Description:

https://leetcode.com/problems/largest-rectangle-in-histogram/#/description

Algorithm:
Back tracking.
Use a stack to record the increasing heights.

Firstly, push a 0 back into the vector in case there are vectors containing only 1 element. (If there is only 1 element, there will be no chance to go back.)

• If heights[i] > top of stack
  • push back
  • i++
• If heights[i] > top of stack
  • pop out current height and calculate the area from current height to current end.
  • if the new area is  greater than the old one, replace old one with new area.

Code:
class Solution {
public:
int largestRectangleArea(vector &height) {
stack s;
height.push_back(0);
int result = 0;
for (int i = 0; i < height.size(); ) { if (s.empty() || height[i] > height[s.top()])
s.push(i++);
else {
int tmp = s.top();
s.pop();
result = max(result,
height[tmp] * (s.empty() ? i : i - s.top() - 1));
}
}
return result;
}
};

Timing & Space:
O(n) & O(n)

Description:

https://leetcode.com/problems/linked-list-cycle/#/description

https://leetcode.com/problems/linked-list-cycle-ii/#/description

Algorithm:

My solution:

As shown in Code1, set the node value to INT_MIN, and keep checking. If a INT_MIN is found, we consider we find a cycle. (kind of cheating…but passed the test cases…)

Official solution:

As shown in Code2, approach2 in https://leetcode.com/articles/linked-list-cycle/ is really amazing!

Code1:

class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *node = head;
while(node != NULL)
{
if (node->val == INT_MIN)
return true; // For 142, return node;
node ->val = INT_MIN;
node = node -> next;
}
return false; // For 142, return NULL;
}
};

Code2 (for 141):

public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}

Code2 (for 142):

class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(!head || !head->next)return NULL;
ListNode*hare,*tor;
tor=head;
hare=head;
while(hare && hare->next){
tor=tor->next;
hare=hare->next->next;
if(hare==tor)break;
}
if(!hare || !hare->next )return NULL;
tor=head;
while(tor!=hare){
tor=tor->next;
hare=hare->next;
}
return tor;
}
};

Timing & space:

O(n) & O(1)

This is the fastest problem I finished. Only 3 mins are spent:)

Description:

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/#/description

Algorithm:

Traverse. Count the duplicates, if duplicates > 2, erase the element and –i

Code:

class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int numDuplicate = 0;
for (int i = 0; i < nums.size();i++)
{
if (i == 0)
continue;
if (nums[i] == nums[i - 1])
numDuplicate++;
else
numDuplicate = 0;

if (numDuplicate > 1)
{
nums.erase(nums.begin() + i);
i--;
}
}
return nums.size();
}
};

Timing:

O(n).

13 ms, the fastest is 12ms.

Description:

https://leetcode.com/problems/sort-colors/#/description

Algorithm:

1. Cheat…use three int to record the number of each color, and print them out. Time is fastest.
2. sort. Traverse the vector
   1. if (num[i] == 0) -> swap with the head element
   2. if (num[i] == 1 ) -> do nothing
   3. if (num[i] ==2 ) -> swap with the tail element

Code1:

class Solution {
public:
void sortColors(vector<int>& nums) {
int red = 0;
int white = 0;
int blue = 0;
for (int i = 0; i < nums.size();i++)
{
if (nums[i] == 0)
red++;
else if(nums[i] == 1)
white++;
else
blue++;
}
for (int i = 0; i < red; i++)
nums[i] = 0;
for (int i = red; i < red + white; i++)
nums[i] = 1;
for (int i = red+white; i < red + white + blue; i++)
nums[i] = 2;
}
};

Code2:

class Solution {
public:

void sortColors(vector<int>& nums)
{
int start = 0;
int mid = 0;
int end = nums.size()-1;

while(mid<=end)
{
if(nums[mid]==0)
{
nums[mid] = nums[start];
nums[start] = 0;
start++;
mid++;
}
else if(nums[mid]==1)
{
mid++;
}
else if(nums[mid] ==2)
{
nums[mid] = nums[end];
nums[end] = 2;
end--; // Here we don't need to change the mid
}
}
}
};

Timing:

1. Cheat: O(n)
2. Sort: O(n)

 

Description:

https://leetcode.com/problems/search-a-2d-matrix/#/description

Algorithm:

1. Squeeze from up and down
2. Squeeze from left and right

Code:

class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.size() == 0 || matrix[0].size() == 0) return false;
int m = matrix.size();
int n = matrix[0].size();

int up = 0, down = m - 1;

int left = 0, right = n - 1;

while (up <= down)
{
int mid_ud = (up + down) / 2;
if (matrix[mid_ud][left] > target)
down = mid_ud - 1;
else if (matrix[mid_ud][right] < target)
up = mid_ud + 1;
else
{
while (left <= right)
{
int mid_lr = (left + right) / 2;
if (matrix[mid_ud][mid_lr] > target)
right = mid_lr - 1;
else if (matrix[mid_ud][mid_lr] < target)
left = mid_lr + 1;
else
return true;
}
return false;
}
}
return false;
}
};

Timing:

Fastest, 6ms

O(logm+logn) // m is the row and n is the column

Description:

https://leetcode.com/problems/set-matrix-zeroes/#/description

Algorithm:

O(m+n) space:

Traverse, record the zero row index and column index.

Set all the zero rows to zero;

Set all the zero columns to zero.

O(1) space:
Use the first row and first column to record whether there is zero in this col/row. (Don’t worry about lost of info, if there is a zero in this row/col, it will be set to zero anyway.)

Code:
1. O(mn)time, O(m+n)space
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
if (matrix.size() == 0 || matrix[0].size() == 0) return;
vector<int> zeroRow;
vector<int> zeroColumn;
vector<int> nonzeroRow;
vector<int> nonzeroColumn;

int m = matrix.size();
int n = matrix[0].size();
for (int i = 0; i < m;i++)
{
for (int j = 0; j < n; j++)
{
if (matrix[i][j] == 0)
{
zeroRow.push_back(i);
zeroColumn.push_back(j);
}
else
{
nonzeroRow.push_back(i);
nonzeroColumn.push_back(j);
}
}
}
zeroRow.erase(unique(zeroRow.begin(), zeroRow.end()), zeroRow.end());
zeroColumn.erase(unique(zeroColumn.begin(), zeroColumn.end()), zeroColumn.end());
for (int i = 0; i < zeroRow.size();i++)
{
matrix[zeroRow[i]] = vector<int>(n, 0);
}
for (int j = 0; j < zeroColumn.size();j++)
{
for (int i = 0; i < m; i++)
matrix[i][zeroColumn[j]] = 0;
}
}
};

2. O(mn) time, O(1)space
class Solution2 {
public:
void setZeroes(vector>& matrix) {
if (matrix.size() == 0 || matrix[0].size() == 0) return;

int m = matrix.size();
int n = matrix[0].size();

bool row_has_zero = false;
bool col_has_zero = false;
for (int i = 0; i < m; i++) if (matrix[i][0] == 0) { col_has_zero = true; break; } for (int j = 0; j < n; j++) if (matrix[0][j] == 0) { row_has_zero = true; break; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } for (int i = 1; i < m;i++) { for (int j = 1; j < n;j++) { if (matrix[0][j] == 0 || matrix[i][0] == 0) matrix[i][j] = 0; } } if (row_has_zero) for (int j = 0; j < n; j++) matrix[0][j] = 0; if (col_has_zero) for (int i = 0; i < m; i++) matrix[i][0] = 0; } };