Month: June 2017

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