Author: xiaoxumeng

Description:

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

Boundary:

NO

Algorithm:

如果直接~num，C++直接进行补码取反。

因此需要设定mask，然后一位一位操作。

Reference: http://blog.chinaunix.net/uid-25909722-id-2856108.html

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

设置特定的位用| (OR);
清除特定的位用&(AND);
取反特定的位用^(XOR);
取反所有的位用~(NOT);

C++中bitset容器来操作位

可以通过to_string()成员函数将容器输出为一个string字符串；
可以通过to_long()成员函数将容器输出到传统的用于C风格的位容器中。

Code：

 

class Solution {
public:
int findComplement(int num) {
unsigned mask = ~0;
while (mask & num) mask <<= 1;
return ~mask & ~num;
}
};

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[0].size():0;
sums = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));

sums[1][1] = matrix[0][0];

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

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”.

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