## 566. Reshape the Matrix

Description:

https://leetcode.com/problems/reshape-the-matrix/#/description

Boundary:

r * c == r’ * c’?

Algorithm:

Store the data in one dim vector and evaluate the new r*c matrix

Code:

class Solution {
public:
vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
int m = nums.size();
int n = nums[0].size();

if (r * c != m * n)
return nums;

vector<int> nums_all;
vector<vector<int>> nums_new = vector<vector<int>>(r, vector<int>(c, -1));
for (int k = 0; k < m; k++)
nums_all.insert(nums_all.end(), nums[k].begin(), nums[k].end());
int count = 0;
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
nums_new[i][j] = nums_all[count++];
return nums_new;
}
};

Time:

## 500. Keyboard Row

Description:

https://leetcode.com/problems/keyboard-row/#/description

Boundary:

NO

Algorithm:

Not difficult. Use:

str.find() < str.nops

Code:

class Solution {
public:
vector<string> findWords(vector<string>& words) {
vector<string> result;
for (int k = 0; k < words.size(); k++)
{
if (line1_Big.find(words[k][0]) < line1_Big.size() || line1_Sml.find(words[k][0]) < line1_Sml.size())
{
if (ifExist(words[k], line1_Big, line1_Sml))
result.push_back(words[k]);
}
else if (line2_Big.find(words[k][0]) < line2_Big.size() || line2_Sml.find(words[k][0]) < line2_Sml.size())
{
if (ifExist(words[k], line2_Big, line2_Sml))
result.push_back(words[k]);
}
else
{
if (ifExist(words[k], line3_Big, line3_Sml))
result.push_back(words[k]);
}

}
return result;
}
private:
string line1_Big = “QWERTYUIOP”;
string line1_Sml = “qwertyuiop”;

string line2_Big = “ASDFGHJKL”;
string line2_Sml = “asdfghjkl”;

string line3_Big = “ZXCVBNM”;
string line3_Sml = “zxcvbnm”;
bool ifExist(string word, string big, string small)
{
for (int i = 1; i < word.size(); i++)
{
if (big.find(word[i]) > big.size() && small.find(word[i]) > small.size())
return false;
}
return true;
}
};

## 557. Reverse Words in a String III

Description:

https://leetcode.com/submissions/detail/105718837/

Boundary:

No boundary needs to be considered.

Algorithm:

Use a for loop to read the char in the string one by one, record the start and end of each word.

If meets a ‘ ‘, swap poistion and store in an new string.

Code:

class Solution {
public:
string reverseWords(string s) {
string s_new = s;
int counter = 0;
int start = 0;
for (int k = 0; k < s.size();k++)
{
if (s[k] == ‘ ‘)
{
for (int i = start; i < counter; i++)
{
char s1 = s[counter – 1 – (i – start)];
s_new[i] = s1;
}

start = counter + 1;
}
else if (k == s.size() – 1)
{
for (int i = start; i <= counter; i++)
{
char s1 = s[counter – (i – start)];
s_new[i] = s1;
}
}
counter++;
}
return s_new;
}
};

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

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

## 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)