18. 4Sum

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

16. 3Sum Closest

 

Description:

https://leetcode.com/problems/3sum-closest/#/description

Algirithm:

One for loop and squeeze from left and right. This is similar to the solution of ThreeSum.

Code: (6ms, the fastest 🙂 )

class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
if (nums.size() == 3)
return nums[0] + nums[1] + nums[2];

sort(nums.begin(), nums.end());
int result = 10000;
int result_tmp = 10000;
for (int i = 0; i < nums.size() – 2; i++)
{
int left = i + 1;
int right = nums.size() – 1;
while (left < right)
{
int tmp = nums[i] + nums[left] + nums[right] – target;
result_tmp = (abs(result_tmp) < abs(tmp)) ? result_tmp : tmp;
if (tmp < 0)
left++;
else if (tmp > 0)
right–;
else
return target;
}
}
return result_tmp + target;
}
};

06/07/2017

Research:

  • no research task today~~~lol~~~! Where is varshney?????

Leetcode:

Finished 5 leetcode problems.

  • Know the difference between vec.emplace_back() and vec.push_back().
    • https://stackoverflow.com/questions/4303513/push-back-vs-emplace-back

Parallel Computing Study:

  • Watch video of class2
    • https://classroom.udacity.com/courses/cs344/lessons/67054969/concepts/673560200923
    • Bill Dally mentioned that CPU is not getting faster…we use more parallelism now.
    • Four communication patterns:
      • map: all the inputs do the same calculation (efficient in GPU).
      • gather: calc average of several pixels.
      • scatter: write several memory units with one value.
      • stencil: tasks read input from a fixed neighborhood in an array.
    • Transpose:
      • reorder data elements in memory
      • Transpose: AoS [array of structures] vs.  SoA [structure of arrays]
    • Transpose: AoS [array of structures] vs.  SoA [structure of arrays]
  • install CUDA on my PC.

Website:

  • no

Guitar:

599. Minimum Index Sum of Two Lists

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

 

129. Sum Root to Leaf Numbers

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

40. Combination Sum II

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!

15. Three Sum

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