Category: Leetcode

565. Array Nesting

Description:

https://leetcode.com/problems/array-nesting/description/

Algorithm:

Actually we are separating the array into several groups by determining S[k]. The numbers inside of S[k] will form a cycle.

For example:

Input: A = [5,4,0,3,1,6,2]

Output: 4

Explanation:

A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.

One of the longest S[K]:

S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

S[5] = {A[5], A[6], A[2], A[0]} = {6, 2, 0, 5}

S[6] = {A[6], A[2], A[0], A[5]} = {2, 0, 5, 6}

S[2] = {A[2], A[0], A[5], A[6]} = {0, 5, 6, 2}

 

S[1] = {A[1], A[4]} = {4,1}

S[4] = {A[4], A[1]} = {1,4}

 

S[3] = {A[3]} = {3}

So just mark the used number in the finding process. If meets used number -> stop.

Code:

Timing & Space:

fastest

O(n) & O(1)

581. Shortest Unsorted Continuous Subarray

Description:

https://leetcode.com/problems/shortest-unsorted-continuous-subarray/#/description

Algorithm:

Only need to care about the start index and end index

Code:

Time & Space:
O(n) & O(1)

289. Game of Life

Description:

https://leetcode.com/problems/game-of-life/#/description

Algorithm:

Use state machine to finish in-place.

Code:

Time & Space:

O(n) & O(1)

283. Move Zeroes

Description:

https://leetcode.com/problems/move-zeroes/#/description

Algorithm:

  1. Use swap.

Code:

Time & Space:
O(n) & O(1)

268. Missing Number

Description:

https://leetcode.com/problems/missing-number/#/description

Algorithm:

  1. Use sum as shown in Code1.
  2. Use XOR

Code1:

Code2:

Time & Space:
O(n) & O(1)

238. Product of Array Except Self

Description:

https://leetcode.com/problems/product-of-array-except-self/#/description

Algorithm:

As shown in Code.

Code1 (62ms, beats 20.95%):

class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> fromLeft = vector<int>(n, 1);
vector<int> fromRight = vector<int>(n, 1);
vector<int> result = vector<int>(n, 1);

for (int i = 1; i < nums.size();i++)
{
fromLeft[i] = nums[i – 1] * fromLeft[i – 1];
}
for (int i = nums.size() – 2; i >= 0;i–)
{
fromRight[i] = nums[i + 1] * fromRight[i + 1];
}

for (int i = 0; i < nums.size();i++)
{
result[i] = fromLeft[i] * fromRight[i];
}
return result;
}
};

Code2 (46ms, fastest):

class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {

vector<int> res;

res.push_back(1);

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

int temp = res[i-1]*nums[i-1];

res.push_back(temp);

}

int right = 1;

for(int i = nums.size()-1; i>=0; i–){

res[i] *= right;

right *= nums[i];

}

return res;

}
};

79. Word Search

Description:

https://leetcode.com/problems/word-search/#/description

Algorithm:

main:

for each element in 2D vector

{

if (board[i][j] == word[0])

{

mark the element;

dfs(board, pos_x, pos_y, height, width, wordIdx, word);

unmark the element;

}

}

dfs:

if (wordIdx == word.size())if (wordIdx == word.size()) return true;

check the four surrounding letters

 

if (board[i][j] == word[0])

{

mark the element;

if  dfs(board, pos_x, pos_y, height, width, wordIdx + 1, word)

return true;

unmark the element;

}

Code:

Actually my algorithm is TOTALLY the same with the fastest one. However, mine takes 76ms while the fastest only takes 6ms. I optimized my code again and again and finally get the fastest. Here are all my codes and i will show the improvements.

Code1 (76ms, beats 17.34%):

Code2 (16ms, beats 64.74%):

Main change from Code1 to Code2 is the usage of newPos_x and newPos_y

Code3 (6ms, beats 99.61%):

Main change from Code2 to Code3 is to use string &word instead of string word.

220. Contains Duplicate III

Description:

https://leetcode.com/problems/contains-duplicate-iii/#/description

Algorithm:

  • Use vector<pair<int, int>> to solve this problem.
  • Learn how to define comparison rules for std::sort()
    • sort(pairs.begin(), pairs.end(), [](pair<int, int> p1, pair<int, int> p2) {return p1.first < p2.first; });

template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

comp:

Binary function that accepts two elements in the range as arguments, and returns a value convertible to bool.

The value returned indicates whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines.
The function shall not modify any of its arguments.
This can either be a function pointer or a function object.

Why there is a green []?????

Code:

class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
const int n = nums.size();
vector<pair<int, int>> pairs; // a vector of (value, index) pairs
pairs.reserve(n);
for (int i = 0; i < n; ++i)
pairs.emplace_back(nums[i], i);
sort(pairs.begin(), pairs.end(), [](pair<int, int> p1, pair<int, int> p2) {return p1.first < p2.first; });
for (int i = 0; i < n - 1; ++i)
for (int j = i + 1; j < n; ++j)
if ((long long)pairs[j].first - pairs[i].first <= t)
{
if (abs(pairs[j].second - pairs[i].second) <= k)
return true;
}
else
break;
return false;
}
};

Time & Space:

 

219. Contains Duplicate II

Description:

https://leetcode.com/problems/contains-duplicate-ii/#/description
Algorithm:

Easy

Code:

class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
if (nums.size() < 2) return false;
unordered_map <int, int> record;
for (int i = 0; i < nums.size();i++)
{
if (record.find(nums[i]) != record.end() && i - record[nums[i]] <= k)
return true;
else
record[nums[i]] = i;
}
return false;
}
};

Time & Space:

O(nlogn) & O(n)

map底层是红黑树实现的，因此它的find函数时间复杂度：O(logn)

300. Longest Increasing Subsequence

Description:

https://leetcode.com/problems/longest-increasing-subsequence/#/description

Algorithm:

About explanation of Code1, 3, please refer to:

https://leetcode.com/articles/longest-increasing-subsequence/

For Code2:

There are two steps:

  • Step1:
    • Use array to record the index of number which is larger than num[i], priority: position
    • Use another array to record the index of number which is larger than num[i], priority: value
  • Step2
    • from end to start, find the max length of array
      • length = max(lengths[posLarger[i]], lengths[valLarger[i]]) + 1;

Code1:

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.size() == 0) {
return 0;
}
vector<int> dp = vector<int>(nums.size(), 0);
dp[0] = 1;
int maxans = 1;
for (int i = 1; i < nums.size(); i++) {
int maxval = 0;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
maxval = max(maxval, dp[j]);
}
}
dp[i] = maxval + 1;
maxans = max(maxans, dp[i]);
}
return maxans;
}
};

Code2:

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> lengths = vector<int>(n, 1);
vector<int> posLarger = vector<int>(n, INT_MIN);
vector<int> valLarger = vector<int>(n, -1);
posLarger[n-1] = -1;
for (int i = 0; i < nums.size() - 1;i++)
{
for (int j = i + 1; j < nums.size();j++)
{
if (nums[j] > nums[i])
{
if (posLarger[i] == INT_MIN)
posLarger[i] = j;
if (valLarger[i] == -1)
valLarger[i] = j;
else if (nums[j] < nums[valLarger[i]])
valLarger[i] = j;
}
}
if (posLarger[i] == INT_MIN)
{
posLarger[i] = -1;
valLarger[i] = -1;
}
}
for (int i = nums.size() - 1; i >= 0;i--)
{
if (posLarger[i] >= 0)
lengths[i] = max(lengths[posLarger[i]], lengths[valLarger[i]]) + 1;
}
int result = 1;
for (int i = 0;i < nums.size();i++)
{
if (lengths[i] > result)
result = lengths[i];
}
return result;
}
};

Code3:

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> res;
for (int i = 0; i<nums.size(); i++) {
auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
if (it == res.end()) res.push_back(nums[i]);
else *it = nums[i];
}
return res.size();
}
};

Time & Space:

Code1:

// Simple DP solution, beats 10.42%
// Time: O(n2), Space: O(n)

Code2:

// My solution, beats 49.5%
// Time: O(n2), Space: O(n)

Code3:

Time: O(nlogn), Space: O(n)