Category: Leetcode

Description:

https://leetcode.com/problems/summary-ranges/#/description

Boundary:

No boundary condition needs to be considered.

Algorithm:

Traverse the whole array and …it is not difficult.

Code:

class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
vector<string> result;
char tmp[20];
while (nums.size() > 0)
{
int start = 0;
int end = start;
while(end != nums.size()-1 && nums[end + 1] == nums[end] + 1)
end++;

if (end == start)
sprintf(tmp, “%d”, nums[0]);
else
sprintf(tmp, “%d->%d”, nums[0], nums[end]);

result.push_back(tmp);
nums.erase(nums.begin(), nums.begin() + end + 1);
}
return result;
}
};

Description:

https://leetcode.com/problems/minimum-size-subarray-sum/#/description

Boundary:

• if sum of nums() < s, there is no proper subarray.

Algorithm:

My first solution:

Just gets sum of the 0-th element to the k-th element: sum[k+1]. Then the sum of the i-th element to the j-th element will be sum[j] – sum[i].

Then traverse i from 0 to nums.size()  to find the start of the subarray.

Then traverse j from i+1 to nums.size() + 1 to find the end of the subarray.

Find the min length, and replace the older one if shorter.

However, the timing is not good.

Whether to get sum initially? I remember some problems about subarray which got sum initially. However, we don’t need it in this problem.

Second solution ( O(n) ):

Count from the 0-th element and find sum[j] > s with min j.

Gradually shorten the subarray by subtracting the element at the beginning of the subarray until sum[j] < s.

Extend at the tail and shorten at the beginning.

Code:

class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int begin = 0;
int end = 0;
int n = nums.size();
int sum = 0;
int length = INT_MAX;
while (end < n)
{
sum += nums[end++];
while (sum >= s)
{
length = min(end – begin,length);
sum -= nums[begin++];
}
}
return length == INT_MAX ? 0: length;
}
};

Explanation:

Well, you may wonder how can it be O(n) since it contains an inner while loop. Well, the key is that the while loop executes at most once for each starting position start. Then start is increased by 1 and the while loop moves to the next element. Thus the inner while loop runs at most O(n) times during the whole for loop from 0 to n - 1. Thus both the for loop and while loop has O(n) time complexity in total and the overall running time is O(n). (Cited from: https://discuss.leetcode.com/topic/17063/4ms-o-n-8ms-o-nlogn-c)

Description:

https://leetcode.com/problems/4sum/#/description

Algorithm:

This is totally the same with [15. 3Sum], the elements in the array cannot be reused. And the duplicated elements should be passed.

Code:

class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
if (nums.size() < 4) return{};
int n = nums.size();
int tmp_sum;
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < n – 3; i++)
{
for (int j = i + 1; j < n – 2; j++)
{
int left = j + 1;
int right = n – 1;
while (left < right)
{
tmp_sum = nums[i] + nums[j] + nums[left] + nums[right] – target;
if (tmp_sum < 0)
left++;
else if (tmp_sum > 0)
right–;
else
{
result.push_back({ nums[i], nums[j], nums[left], nums[right] });
while (left < n – 1 && nums[left] == nums[left + 1]) // these are used for remove the duplicated elements.
left++;
while (right > 0 && nums[right] == nums[right – 1])
right–;
left++;
right–;
}

}
while (nums[j] == nums[j + 1])
j++;
}
while (nums[i] == nums[i + 1])
i++;
}
return result;
}

Description:

https://leetcode.com/problems/minimum-index-sum-of-two-lists/#/description

My first code: ( Time is not good)

class Solution {
public:
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
int sum = 2000;
vector<string> name;
for (int i = 0; i < list1.size();i++)
{
for (int j = 0; j < list2.size();j++)
{
if (list1[i] == list2[j] && i + j < sum)
{
sum = i+j;
name.clear();
name.push_back(list1[i]);
}
else if (list1[i] == list2[j] && i + j == sum)
{
sum = i+j;
name.push_back(list1[i]);
}
}
}
return name;
}
};

/*********************************************************************************************/

The algorithm can be optimized by using unordered map.

My Second code: 

class Solution {
public:
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
unordered_map<string, int> table;
table.reserve(list1.size());
for (int i = 0; i < list1.size(); ++i) {
table[list1[i]] = i;
}
int sum = list1.size() + list2.size();
for (int j = 0; j < list2.size(); ++j) {
auto it = table.find(list2[j]);
if (it != table.end() && it->second + j < sum) {
sum = it->second + j;
}
}
vector<string> results;
for (int j = 0; j < list2.size(); ++j) {
auto it = table.find(list2[j]);
if (it != table.end() && it->second + j == sum) {
results.emplace_back(list2[j]);
}
}
return results;
}
};

 

Description:

https://leetcode.com/problems/sum-root-to-leaf-numbers/#/description

Algorithm:

Just recursion, not difficult.

Code:

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {};
};
class binaryTree {
public:
TreeNode *root;
vector<int> treeElement;
int N;
public:
binaryTree(vector<int> treeElementInput) {
treeElement = treeElementInput;
N = treeElement.size();
root = new TreeNode(treeElement[0]);
makeNode(root, 0);
}
void makeNode(TreeNode *node, int index)
{
if (2 * index + 1 < N)
{
if (treeElement[2 * index + 1] != NULL)
{
TreeNode *T_left = new TreeNode(treeElement[2 * index + 1]);
node->left = T_left;
makeNode(node->left, 2 * index + 1);
}
else
{
node->left = NULL;
}
}
if (2 * index + 2 < N)
{
if (treeElement[2 * index + 2] != NULL)
{
TreeNode *T_right = new TreeNode(treeElement[2 * index + 2]);
node->right = T_right;
makeNode(node->right, 2 * index + 2);
}
else
{
node->right = NULL;
}
}
}
void printTreeNodes(TreeNode *node)
{
if (node != NULL)
{
cout << node->val << endl;
printTreeNodes(node->left);
printTreeNodes(node->right);
}
}
};
class Solution {
public:
int sumNumbers(TreeNode* root) {
if (!root)
return 0;
return helper(root, 0);
}
int helper(TreeNode* node, int sum)
{
if (!node)
return 0;
if (node->left == nullptr && node->right == nullptr) // leaf
return sum + node->val;
else if (node->left == nullptr && node->right != nullptr)
{
return helper(node->right, (sum + node->val) * 10);
}
else if (node->left != nullptr && node->right == nullptr)
{
return helper(node->left, (sum + node->val) * 10);
}
else
{
return helper(node->right, (sum + node->val) * 10) + helper(node->left, (sum + node->val) * 10);
}
}
};

Description:

https://leetcode.com/problems/combination-sum-ii/#/description

Actually this problem is quite similar to that of “Combination Sum”. The difference is that we cannot reuse elements and the result must be unique.

Generally,

The keypoint is to use the void() as the helper function and use result & intermediate as the parameters.
Another keypoint is to use the “start” to record the process.
Another point is to use the pop_back() function. I only remembered clear(), but there is no proper way to use clear.

class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<int> intermediate;
vector<vector<int>> result;
helper(candidates, target, 0, intermediate, result);
return result;
}
void helper(vector<int> candidates, int gap, int start, vector<int>& intermediate, vector<vector<int>>& result)
{
if (gap == 0)
{
result.push_back(intermediate);
return;
}
int i = start;
while(i < candidates.size())
{
if (gap < candidates[i])
return;
intermediate.push_back(candidates[i]);
helper(candidates, gap – candidates[i], i + 1, intermediate, result);
intermediate.pop_back();
while ((i < candidates.size() + 1) && candidates[i] == candidates[i + 1]) i++; // Use this, so we will not recalculate duplicate elements
i ++;
}
}
};

Time:

Beats 50.44% in c++. My algorithm is quite similar to the algorithm posted by others, which means that I’m learning something!

The description of the problem is : https://leetcode.com/problems/3sum/#/description

Generally, The time complexity is O(n^2). Use for loop and squeeze rule to solve this problem.

For boundary condition: consider when the number in candidates is less than 3, then there is no solution.

The solution:

class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
if (nums.size() < 3) return{};
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() – 2; i++)
{
if (nums[i] > 0)
break;
if (i > 0 && nums[i] == nums[i – 1])
continue;
int left = i + 1;
int right = nums.size() – 1;

while (left < right)
{
if (nums[right] < 0)
break;
int tmp = nums[i] + nums[left] + nums[right];
if (tmp == 0)
{
result.push_back({ nums[i], nums[left], nums[right] });
while (left < right && nums[left] == nums[left + 1])
left++;
while (left < right && nums[right] == nums[right – 1])
right–;
++left;
–right;
}
else if (tmp < 0)
left++;
else
right–;
}
}
return result;
}
};

Tips:

How to remove the duplicate elements in vector?

result.erase(std::unique(result.begin(), result.end()), result.end());