## 59. Spiral Matrix II

Description:

https://leetcode.com/problems/spiral-matrix-ii/#/description

Algorithm:

Generally it is the same with 54. Spiral Matrix.

There is one point very important:

The route is right -> down -> left -> up

In down and up, don’t need to check break condition. To finish the matrix, we have to go left and up. So there is no way breaking the loop in left or up.

Code:
``` class Solution {class Solution {public: vector<vector<int>> generateMatrix(int n) {    if (n == 0) return{}; vector<vector<int>> result = vector<vector<int>>(n, vector<int>(n, -1)); int rowLow = 0, colLow = 0, rowHigh = n - 1, colHigh = n - 1; int element = 0; while (true) { for (int i = colLow; i <= colHigh; i++) { result[rowLow][i] = ++element; } if (++rowLow > rowHigh) break; for (int i = rowLow; i <= rowHigh; i++) { result[i][colHigh] = ++element; } if (--colHigh < colLow) break; for (int i = colHigh; i >= colLow; i--) { result[rowHigh][i] = ++element; }            --rowHigh; for (int i = rowHigh; i >= rowLow; i--) { result[i][colLow] = ++element; } ++colLow; } return result; }};```

Timing:

If check left and up, it will be 6ms

Don’t check left or up, it will be 3ms!

Fantastic!

## 54. Spiral Matrix

Description:

https://leetcode.com/problems/spiral-matrix/#/description

Algorithm:

right->down->left->up

• After finishing each direction, check if break

Code:

```class Solution {class Solution {public: vector<int> spiralOrder(vector<vector<int>>& matrix) { vector<int> result; int rowLow = 0, colLow = 0, rowHigh = matrix.size() - 1, colHigh = matrix[0].size() - 1; while (true) { for (int i = colLow; i <= colHigh; i++) {  result.push_back(matrix[rowLow][i]); cout << matrix[rowLow][i] << '\t'; } if (++rowLow > rowHigh) break; for (int i = rowLow; i <= rowHigh; i++) { result.push_back(matrix[i][colHigh]); cout << matrix[i][colHigh] << '\t'; } if (--colHigh < colLow) break; for (int i = colHigh; i >= colLow; i--) { result.push_back(matrix[rowHigh][i]); cout << matrix[rowHigh][i] << '\t'; } if (--rowHigh < rowLow) break; for (int i = rowHigh; i >= rowLow; i--) { result.push_back(matrix[i][colLow]); cout << matrix[i][colLow] << '\t'; } if (++colLow > colHigh) break; } return result; }};```

Timing:

O(n)

## 06/28/2017

Research:

• Finish CITI courses.
• Register in IRB

Leetcode:

• 53-maximum-subarray
• DP
• 48. Rotate Image

• Use new_i = …, new_j = … when updating i,j. Then i = new_i, j = new_j. Otherwise, the newly calculated i will affect the calculation of j
• 54. Spiral Matrix
• Check if break after each direction in each ring
• 59. Spiral Matrix II
• There is no need to check breaking in left and up route!!

Waiting:

• waiting for installation of softwares on chibwks04. So I can make tests on the PC
• waiting for HDMI ->VGA connector.
• wating for Eric about next steps

## 53. Maximum Subarray

Description:

https://leetcode.com/problems/maximum-subarray/#/description

Algorithm:

Use dp, if dp[i – 1] < 0, discard.

if dp[i – 1] > 0, dp[i] = dp[i] + nums[i]

Code:

`int maxSubArray(vector<int>& nums)`

``` { int maxSubArray(vector<int>& nums) { int n = nums.size(); vector<int> dp(n); dp[0] = nums[0]; int res = nums[0]; for (int i = 1; i < n; i++) { if (dp[i - 1] < 0) dp[i] = nums[i]; else dp[i] = dp[i - 1] + nums[i]; res = max(res, dp[i]); } return res; ```

`}`

Timing:

9ms, fastest

## 48. Rotate Image

Description:

https://leetcode.com/problems/rotate-image/#/description

Algorithm:

 4 4 4 4 4 4 -> 2 -> 4 4 2 0 2 4 4 <- 2 <- 4 4 4 4 4 4
• n is odd (in our example,  n = 5)
• the central blue one (n/2, n/2) = (2, 2) doesn’t move
• the k-th outer ring moves clockwise for 2 * k units, the k-th ring contains 8 * k units
• How to move?
• row index: i, col index j
• start from i = n/2 – k, j= n/2 – k and go for the whole ring
• move right:   if (i < m + k && j == m – k)  i = i + 1, j = j
• move down: if (i == m + k &&  j < m + k)  j = j + 1, i = i
• move left:     if (i > m – k && j == m + k)  i = i – 1, j = j
• move up:      if (i == m – k && j > m – k)  j = j – 1, i = i
• tmp = matrix[newIndex] AND matrix[newIndex] = matrix[oldIndex]
• oldIndex = newIndex
• n is even
• there is no central fixed uint!
• the k-th outer ring moves clockwise for 2 * k – 1 units, the k-th ring contains 8 * (k – 1) +4 units
• How to move?
• row index: i, col index j
• start from i = n/2 – k, j= n/2 – k and go for the whole ring
• move right:   if (i < m + k – 1 && j == m – k)  i = i + 1, j = j
• move down: if (i == m + k – 1 &&  j < m + k – 1)  j = j + 1, i = i
• move left:     if (i > m – k && j == m + k – 1)  i = i – 1, j = j
• move up:      if (i == m – k && j > m – k)  j = j – 1, i = i
• tmp = matrix[newIndex] AND matrix[newIndex] = matrix[oldIndex]
• oldIndex = newIndex

Code:
``` class Solution { public: void rotate(vector<vector>& matrix) { int m = matrix.size() / 2; if (m < 1) return; if (matrix.size() % 2) { for (int k = 1; k <= m; k++) { for (int l = 0; l < 2 * k; l++) ```

`              ``{ `

`                  int elementNum = 8 * k; int i = m - k; int j = m - k; int tmp = matrix[j][i]; `

```                  while (elementNum > 0) { int i_new = (i < m + k && j == m - k) ? i + 1 : (i > m - k && j == m + k) ? i - 1 : i; int j_new = (j < m + k && i == m + k) ? j + 1 : (j > m - k && i == m - k) ? j - 1 : j; swap(matrix[j_new][i_new], tmp); i = i_new; j = j_new; elementNum--; } } } } else { for (int k = 1; k <= m; k++) { for (int l = 0; l < k * 2 - 1; l++) { ```

`                   int elementNum = 8 * (k - 1) + 4; int i = m - k; int j = m - k; int tmp = matrix[j][i]; `

`    ``             ````while (elementNum > 0) { int i_new = (i < m - 1 + k && j == m - k) ? i + 1 : (i > m - k && j == m - 1 + k) ? i - 1 : i; int j_new = (j < m - 1 + k && i == m - 1 + k) ? j + 1 : (j > m - k && i == m - k) ? j - 1 : j; swap(matrix[j_new][i_new], tmp); i = i_new; j = j_new; elementNum--; } } } } } }; ```

Timing:

Luckily time is good…3ms (fastest)

complexity: O(n)

n is the number of elements.

## 06/27/2017

Research:

• Adjust the light field so it can focus
• Search about FR for light field (Keywords: foveated, lightfield) 1-4 pages in google scholar
• An interesting concept: Saccadic suppression

## 26. Remove Duplicates from Sorted Array

Description:

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

Algorithm:

Use swap.

Code:

`class Solution`` `

`{`

`public: `

`    int removeDuplicates(vector<int>& nums) `

`   ``{ `

`        if (nums.size() == 0) return 0; `

`        int length = 0; `

`        for (int i = 0; i < nums.size(); i++) { `

`        if (nums[length] != nums[i]) `

`           nums[++length] = nums[i]; `

`        } `

`        return length + 1; `

`    }`

`};`

Timing:

O(n)

Mine is 35ms (beats 35%). Actually I believe my code is the same with the code of 22ms, but I don’t know why I’m slower. 🙁

## 41. First Missing Positive

Description:

https://leetcode.com/problems/first-missing-positive/#/description

Algorithm:

I used unordered_map.

Go through the array to record the max number and min number.

Code:
``` class Solution { public: int firstMissingPositive(vector& nums) { unordered_map <int, int> mapping; int maxNum = 0; int minNum = INT_MAX; for (int i = 0; i < nums.size(); i++) { mapping[nums[i]] = 1; if (nums[i] > maxNum) maxNum = nums[i]; if (nums[i] < minNum) minNum = nums[i]; } if (maxNum < 1 || minNum > 1) return 1; for (int i = 1; i < maxNum; i++) { auto it2 = mapping.find(i); if (it2 == mapping.end()) return i; } return maxNum + 1; } };```

Timing:

Beats 2.82% (:( ) 9ms

Best 3ms code:

``` class Solution { public: int firstMissingPositive(vector& nums) { int n = nums.size(); for (int i = 0; i < n; i++) { while (nums[i] != i + 1) { if (nums[i] <= 0 || nums[i] > n || nums[i] == nums[nums[i] - 1]) break; swap(nums[i], nums[nums[i] - 1]); } } for (int i = 0; i < n; i++) { if (nums[i] != i + 1) return i + 1; } return n + 1; } };```

## 34. Search for a Range

Description:

https://leetcode.com/problems/search-for-a-range/#/description

Algorithm:

1. Use find() to determine whether the target is in the array.
2. Left = 0, right = size – 1;
3. Squeeze left and right to find middle s.t. nums[middle] == target
4. Squeeze left and middle to find left s.t.  nums[left] == target
5. Squeeze right and middle to find right s.t.  nums[right] == target

Code:

``` class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { vector <int> result; vector<int>::iterator iter = std::find(nums.begin(), nums.end(), target); if (iter == nums.end()) { result.push_back(-1); result.push_back(-1); return result; }```

``` int left = 0; int right = nums.size() - 1; int middle_left, middle_right; while (nums[left] < nums[right]) { int middle = (left + right) / 2; if (nums[middle] < target) left = middle + 1; else if (nums[middle] > target) right = middle - 1; else { int middle_save = middle; while (nums[left] < target) { middle_left = (middle + left) / 2; if (nums[middle_left] < target) left = middle_left + 1; else middle = middle_left - 1; } ```

```middle = middle_save; while (nums[right] > target) { middle_right = (middle + right) / 2; if (nums[middle_right] > target) right = middle_right - 1; else middle = middle_right + 1; } } } result.push_back(left); result.push_back(right); return result; } };```

Timing: beat 47.5%. 9ms

Best is 6ms.

Code for 6ms algorithm:

``` class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { vector<int> res(2, -1); if(nums.size()==0) return res; int left = 0, right = nums.size() - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) left = mid + 1; else right = mid; // Not symm here } if (nums[right] != target) return res; res[0] = right; right=nums.size()-1; while(left<=right){ int mid=(left+right)/2; if(nums[mid]>target) right=mid-1; else left=mid+1; } res[1]=right;```

``` ```

```return res; } };```

## 14. Longest Common Prefix

Description:

14. Longest Common Prefix

Code:

class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.size() == 0) return “”;
if (strs.size() == 1) return strs[0];

string checked = strs[0];
int k = 0;
bool ifEnd = false;
string result = “”;
while ( k < checked.size())
{
for (int i = 1; i < strs.size(); i++)
{
if (strs[i][k] != checked[k] || strs[i][k] == ‘\0’)
{
return result;
}
}
result += checked.substr(k,1);
k++;
}
return result;
}
};