Author: xiaoxumeng

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