Month: June 2017

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!

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)

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

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.

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. 🙁

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

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

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