Month: July 2017

Description:

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

Algorithm:

Solution1: shift for k times

Solution2: use new vector. Initialize the new vector and reEvaluate the elements. The new offset = k % n; The new index = (i + n – offset) % n;

Solution3: use new vector. Push_back the new element one buy one. The new offset = n – k % n; The new index = (i + offset) % n;

Code:



#ifdef Solution1
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
int offset = k % n;
int tmp;
if (offset < n / 2)
for (int j = 0; j < offset; j++)
{
tmp = nums[n - 1];
for (int i = 0; i < nums.size();i++)
{
swap(nums[i], tmp);
}
}
else
for (int j = 0; j < n - offset; j++)
{
tmp = nums[0];
for (int i = nums.size() - 1; i >= 0;i--)
{
swap(nums[i], tmp);
}
}
}
};
#endif
#ifdef Solution2
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
vector<int> result = vector<int>(n, 0);
int offset = k % n;
for (int i = 0; i < nums.size();i++)
{
result[i] = nums[(i + n - offset) % n];
}nums = result;
}
};
#endif
#ifdef Solution3
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
int offset = n - k % n;
vector<int> result;
for (int i = 0; i < nums.size();i++)
result.push_back(nums[(i + offset) % n]);
nums = result;
}
};
#endif

 

Timing & Space:

• Solution1:
  • Time: Worst: O(n * n/2), Best O(n), Avg O(n * n/4)
  • Space: O(1)
• Solution2:
  • Time: O(n)
  • Space: O(n)
• Solution3:
  • Time: O(n)
  • Space: O(n)

Description:

https://leetcode.com/problems/majority-element-ii/#/description

Algorithm:

Traverse the array for 2 times.

The first pass:

Use two candidate to record the most recent words.

• if nums[i] == candidate, count++
• if nums[i] != candidate, count–

The second pass:
Check the number of appearance of the candidates.

Code:

class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int candidate1 = INT_MIN, candidate2 = INT_MIN;
int count1 = 0, count2 = 0;
for (int i = 0; i < nums.size();i++)
{
if (nums[i] == candidate1)
count1++;
else if (nums[i] == candidate2)
count2++;
else if (count1 == 0)
{
candidate1 = nums[i];
count1 = 1;
}
else if (count2 == 0)
{
candidate2 = nums[i];
count2 = 1;
}
else
{
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int i = 0; i < nums.size();i++)
{
if (nums[i] == candidate1)
count1++;
else if (nums[i] == candidate2) // Here it must be else if rather than if. If the array = {INT_MIN}, candidate1 and candidate2 would both be INT_MIN. And if you use if here, the word will be counted for two times.
count2++;
}
vector <int> result;
if (count1 > nums.size() / 3)
result.push_back(candidate1);
if (count2 > nums.size() / 3)
result.push_back(candidate2);
return result;
}
};

Timing & Space:

O(n) & O(1)

Description:

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

Algorithm:

use mapping

Code:

class Solution {
public:
int majorityElement(vector<int>& nums) {
map <int, int> mapping;
for (int i = 0; i < nums.size();i++)
{
mapping[nums[i]]++;
}
map<int, int>::iterator it;
for (it = mapping.begin(); it != mapping.end();it++)
{
if (it->second > nums.size() / 2)
return it->first;
}
return 0;
}
};

Timing & Space:

O(n) & O(n)

Description:

https://leetcode.com/problems/find-peak-element/#/description

Algorithm:

squeeze

Code:

class Solution {
public:
int findPeakElement(vector<int>& nums) {
int start = 0;
int end = nums.size() - 1;
while (start < end)
{
int middle = (start + end) / 2;
if (nums[middle] < nums[middle + 1])
start = middle + 1;
else
end = middle;
}
return start;
}
};

Timing & Space:

O(logn) & O(1)

Description:

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/#/description

Algorithm:

1. Same with 153. FindMinimuminRotatedSortedArray
2. Use squeeze from left and right to find result;

Code1:

class Solution {
public:
int findMin(vector<int>& nums) {
int minEle = INT_MIN;
for (int i = 0; i < nums.size() – 1;i++)
{
if (nums[i + 1] < nums[i])
minEle = nums[i + 1];
}
if (minEle == INT_MIN)
minEle = nums[0];
return minEle;
}
};

Code2:
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0;
int r = nums.size() – 1;

while (l < r) {
int m = l + ((r – l) >> 1);

if (nums[m] < nums[r]) {
r = m;
}
else if (nums[m] > nums[r]) {
l = m + 1;
}
else {
–r;
}
}

return nums[l];
}
};

Timing & Space:

O(n) / O(logn) & O(1)

Description:
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/#/description

Algorithm:
scan, if nums[i+1] < nums[i], nums[i+1] will be the minimum element

Code:
class Solution {
public:
int findMin(vector& nums) {
int minEle = INT_MIN;
for (int i = 0; i < nums.size() - 1;i++)
{
if (nums[i+1] < nums[i])
minEle = nums[i+1];
}
if (minEle == INT_MIN)
minEle = nums[0];
return minEle;
}
};
Timing & Space:
O(n) & O(1)

Description:

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

Algorithm:

This is subarray question again.

Should record maxProduct and minProduct

minProduct = min(min(temp_min * nums[i], temp_max * nums[i]), nums[i]);
maxProduct = max(max(temp_min * nums[i], temp_max * nums[i]), nums[i]);

Code:

class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
int result = nums[0];
int minProduct = nums[0];
int maxProduct = nums[0];
for (int i = 1; i < n;i++)
{
int temp_max = maxProduct;
int temp_min = minProduct;
minProduct = min(min(temp_min * nums[i], temp_max * nums[i]), nums[i]);
maxProduct = max(max(temp_min * nums[i], temp_max * nums[i]), nums[i]);
result = max(result, maxProduct);
}
return result;
}
};

Timing & Space:

O(n) & O(1)

Description:

https://leetcode.com/problems/triangle/#/description

Algorithm:

There are two ways:

Going from up to down or down to up.

There is no better ways. O(n^2) is the only choice.

Code 1:

class Solution1 {
public:
int minimumTotal(vector<vector<int>>& triangle) {
for (int i = triangle.size() - 2; i >= 0; i--)
{
for (int j = 0; j < i + 1; j++)
{
triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);
}
}
return triangle[0][0];
}
};

Code 2:
// go from up to down
class Solution2 {
public:
int minimumTotal(vector<vector<int>>& triangle) {
if (triangle.size() == 0) return 0;
if (triangle.size() == 1) return triangle[0][0];
int result = INT_MAX;
for (int i = 1; i < triangle.size(); i++)
{
triangle[i][0] += triangle[i - 1][0];
triangle[i][i] += triangle[i - 1][i - 1];
for (int j = 1; j < i; j++)
{
triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j]);
}
}
for (int j = 0; j < triangle.size();j++)
{
result = min(result, triangle[triangle.size() - 1][j]);
}
return result;
}
};

Timing & Space:
O(n^2) & O(1);

Description:

https://leetcode.com/problems/pascals-triangle-ii/#/description

Algorithm:

If we use only one vector and update the vector each cycle, we might have the problem of losing old data.

While using two vector will take extra time and space.

So we should use some techniques to calculate the elements!

Because we are afraid of missing result[i – 1], we can try to get result with decreasing index!

For example:

1, 3, 3, 1 -> 1,4, 6, 4, 1

If update with increasing index:

1, 3, 3, 1

1, 4, 3, 1

1, 4, 7, 1

1, 4, 7, 11, 1 -> wrong!

If update with decreasing index:

1, 3, 3, 1

1, 3, 3, 4, 1

1, 3, 6, 4, 1

1, 4, 6, 4, 1 -> correct!

Code:

class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> kthRow(rowIndex + 1, 0);
kthRow[0] = 1;
for (int row = 1; row <= rowIndex; row++)
for (int col = row; col > 0; col--)
kthRow[col] = kthRow[col - 1] + kthRow[col];
return kthRow;
}
};

Timing:

fastest, oms