## 476. Number Complement

Description:

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

Boundary:

NO

Algorithm:

C的位操作常常使用使用一个unsigned int变量来作为位容器。

C++中bitset容器来操作位

Code：

class Solution {
public:
int findComplement(int num) {
}
};

## 304. Range Sum Query 2D – Immutable

Description:

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

Boundary:

Should consider when the dimension of matirix is 0;

Algorithm:

1. Because there are many calls to sumRegion() function, we should pre-store the sums instead of calculating for each time
2. Should have 0 row and 0 column.

Code:

class NumMatrix {
public:
NumMatrix(vector<vector<int>> matrix) {
m = matrix.size();
n = m > 0 ? matrix.size():0;
sums = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));

sums = matrix;

for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] – sums[i][j] + matrix[i][j];
}
}

}

int sumRegion(int row1, int col1, int row2, int col2) {
return sums[row2 + 1][col2 + 1] – sums[row1][col2 + 1] – sums[row2 + 1][col1] + sums[row1][col1];
}
private:
int m, n;
vector<vector<int>> sums;
};

## 523. Continuous Subarray Sum

Description:

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

Boundary:

The boundary is really complex.

1. k = 0.If k == 0,  the answer will be TRUE if there are more than 2 components sum to 0. Otherwise, it will be FALSE.
2. k = 1 || k = -1
1. The answer will be TURE if there are more than 2 components in the array.
2. The answer will be FLASE if there is 0 or 1 components.
3. Otherwise
1. Go through the array to calculate sum[i] % k, and insert the residual in the array;
2. If there are continuous components summing to n*k, then the new residual will be found in the array;
3. Because we are looking for continuous subarray of size at least 2, the insertion of residual must be delayed. i.e. If there is a, b, c in the array, b%k ==0 and a,c %k !=0. The residual of a & a+b should be the same. But we need to make sure that when finding (a+b)%k in the array, a%k has not been inserted.

Algorithm:

1. Use for loop, in each cycle, calculate sum[i] by adding up nums[i]
2. If k != 0, calculate mod = sums[i]%k; otherwise, mod = sum[i]
3. Find if there is mod in the rsdl array, if found, return TRUE
4. insert the residual of the PREVIOUS cycle into the rsdl array.

Code:

class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
int n = nums.size(), sum = 0, pre = 0;
unordered_set<int> modk;
for (int i = 0; i < n; ++i) {
sum += nums[i];
int mod = k == 0 ? sum : sum % k;
if (modk.count(mod)) return true;
modk.insert(pre);
pre = mod;
}
return false;
}
};

Tips:

1. Learn to use unordered_set and its count() function.
2. Remember the beautiful technique of “delay of insertion”.

## 06/08/2017

Research:

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

Leetcode:

Finished 4 leetcode problems.

• 228. Summary Ranges (easy)

• 209. Minimum Size Subarray Sum
• 18. 4Sum
• sort, and squeeze from both sizes. Actually it will be faster to store the sum of two numbers by using hashmap.
• 373. Find K Pairs with Smallest Sums
• should use priority queue

Parallel Computing Study:

• Finish hw1.
• Finish watching video of Lesson2

Website:

• Installed plugin Crayon Syntax Highlighter, but actually I don’t know how to use it…

Guitar:

• Watch a new tutorial and practice.

## 228. Summary Ranges

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;
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);
else
sprintf(tmp, “%d->%d”, nums, nums[end]);

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

## 209. Minimum Size Subarray Sum

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)

## 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 + nums + nums;

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:

• Watch a new tutorial.