## 118. Pascal’s Triangle

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%)

## 90. Subsets II

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:

## 84. Largest Rectangle in Histogram

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:

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

## 80. Remove Duplicates from Sorted Array II

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.

## 75. Sort Colors

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)

## 07/06/2017

Research:

• Remember to glDeleteTextures(1, &texId) in each cycle. Otherwise, it will cause memory overflow.
• GLuint textureId must be initialized to different numbers, if there are 2 textures:
• GLuint textureId;
• It will load the second texture for BOTH textures, the first texture will disappear.
• GLuint textureId = {0,0};
• It will load the second texture for BOTH textures, the first texture will disappear.
• GLuint textureId = {0,1};
• Good! This is the correct way!
• GL_PIXEL_UNPACK_BUFFER

## 74. Search a 2D Matrix

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.size() == 0) return false; int m = matrix.size(); int n = matrix.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

## 73. Set Matrix Zeroes

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.size() == 0) return; vector<int> zeroRow; vector<int> zeroColumn; vector<int> nonzeroRow; vector<int> nonzeroColumn;```

``` ```

```int m = matrix.size(); int n = matrix.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.size() == 0) return;```

``` int m = matrix.size(); int n = matrix.size(); ```

``` bool row_has_zero = false; bool col_has_zero = false; for (int i = 0; i < m; i++) if (matrix[i] == 0) { col_has_zero = true; break; } for (int j = 0; j < n; j++) if (matrix[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; matrix[j] = 0; } } } for (int i = 1; i < m;i++) { for (int j = 1; j < n;j++) { if (matrix[j] == 0 || matrix[i] == 0) matrix[i][j] = 0; } } if (row_has_zero) for (int j = 0; j < n; j++) matrix[j] = 0; if (col_has_zero) for (int i = 0; i < m; i++) matrix[i] = 0; } };```

## 66. PlusOne

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 = 1; result.push_back(end); } return result; } };```

Timing:

Fastest, 3ms.

O(n)