Author: xiaoxumeng

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

Description:

https://leetcode.com/problems/search-insert-position/#/description

Algorithm:

The searching for middle is the classic method.

Searching for the insert index will be the left.

Code:

class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if (nums.empty()) return 0;
int n = nums.size();
int left = 0, right = n – 1;
int middle;

while (left <= right)
{
middle = (left + right) / 2;
if (nums[middle] == target)
return middle;
else if (nums[middle] < target)
left = middle + 1;
else
right = middle – 1;
}
return left;
}
};

Timing:

O(logn)

Description:

I. https://leetcode.com/problems/search-in-rotated-sorted-array/#/description

II. https://leetcode.com/problems/search-in-rotated-sorted-array-ii/#/description

Algorithm:

|B ————————————— C | A —————————— (B – 1) |

C is the largest number, A is the minimum number.

Squeeze from left and right.

while (left <= right){

1. if ( middle == target ), return
2. else if ( middle in [B,C] region)
   1. if target in [B, middle) region => right = middle – 1;
   2. else (target in (middle, B]) => left = middle + 1
3. else ( middle in [A, (B-1)] region)
   1. if (target in (middle , (B-1)] region) =>left = middle + 1;
   2. else (target in [B, middle) region) => right = middle – 1;

}

if left > right => return -1 (cannot find target)

 

Code:

class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.empty()) return -1;
// nums.erase(unique(nums.begin(), nums.end()), nums.end()); // if II, use this function
int i = 0;
int n = nums.size();
int mid;
int high = n – 1;
while (i <= high) {
mid = (high + i) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < nums[high]) {
if (target > nums[mid] && nums[high] >= target) {
i = mid + 1;
}
else {
high = mid – 1;
}
}
else {
if (target >= nums[i] && nums[mid]>target) {
high = mid – 1;
}
else {
i = mid + 1;
}
}

 

}
return -1;
}
};

Time Complexity:

O(logn)

Description:

https://leetcode.com/problems/remove-element/#/description

Boundary:

• nums.size() = 0  return 0
• val > maximum  return nums.size()
• if cannot find return nums.size()

Algorithm:

1. sort
2. go through array and find the beginning index and end index of the val
3. nums.erase()

Code:

class Solution {
public:
int removeElement(vector<int>& nums, int val) {
if (nums.size() == 0) return 0;
sort(nums.begin(), nums.end());
if (val > nums[nums.size() – 1]) return nums.size();

int beginner = -1, ender = -1;
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] == val)
{
beginner = i;
ender = i;
while (i + 1 < nums.size() && nums[i] == nums[i + 1])
{
i++;
ender++;
}
break;
}
}
if (ender > -1)
nums.erase(nums.begin() + beginner, nums.begin() + ender + 1);
return nums.size();
}
};

Timing:

O(n)