Category: Leetcode

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

Description:

https://leetcode.com/problems/plus-one/#/description

Code:

class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int carry = 1;
vector<int>result = digits;
for (int i = digits.size() - 1; i >= 0 ;i--)
{
result[i] = (digits[i] + carry) % 10;
carry = (digits[i] + carry) / 10;
}
if (carry > 0)
{
int end = result[digits.size()-1];
for (int i = 0; i < digits.size(); i++)
{
result[i+1] = result[i];
}
result[0] = 1;
result.push_back(end);
}
return result;
}
};

Timing:

Fastest, 3ms.

O(n)

Description:

https://leetcode.com/problems/unique-paths-ii/#/description

Algorithm:

check obstacle:

• obstacle = 1   dp[i][j] = 0
• obstacle = 0  dp[i][j] = dp[i – 1][j] + dp[i][j – 1]

Code:

class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> dp = vector<vector<int>>(m, vector<int>(n, 1));
dp[0][0] = (1 - obstacleGrid[0][0]);
for (int i = 1; i < m; i++)
dp[i][0] = (1 - obstacleGrid[i][0]) * dp[i - 1][0];
for (int i = 1; i < n; i++)
dp[0][i] = (1 - obstacleGrid[0][i]) * dp[0][i - 1];
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
{
dp[i][j] = (1 - obstacleGrid[i][j]) * (dp[i - 1][j] + dp[i][j - 1]);
}
}
return dp[m - 1][n - 1];
}
};


Timing:

best, 3ms

Description:

https://leetcode.com/problems/unique-paths/#/description

Algorithm:

recursion: TLE

Use dp, dp is easy and fast

Code:

class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp = vector<vector<int>>(m, vector<int>(n, 1));
dp[0][0] = 1;
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
{
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
};

Timing:

best, 0ms