## 4. Median of Two Sorted Arrays

Description:

https://leetcode.com/problems/median-of-two-sorted-arrays/#/description

Boundary & Algorithm:

Should separate odd and even.

Use recursion, so boundary includes:

• destination pos = 0: return directly
• destination pos = 1 : return min{A[0], B[0]}

Code:

class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size();
int n = nums2.size();
int total = m + n;
if (total & 0x1)
return find_kth(nums1, m, nums2, n, total / 2 + 1);
else
return (find_kth(nums1, m, nums2, n, total / 2)
+ find_kth(nums1, m, nums2, n, total / 2 + 1)) / 2;
}
private:
static double find_kth(vector<int> A, int m, vector<int> B, int n, int k) {
//always assume that m is equal or smaller than n
if (m > n) return find_kth(B, n, A, m, k);
if (m == 0) return B[k – 1];
if (k == 1) return min(A[0], B[0]);
//divide k into two parts
int pa = min(k / 2, m), pb = k – pa;
if (A[pa – 1] < B[pb – 1])
{
A.erase(A.begin(), A.begin() + pa);
return find_kth(A, m – pa, B, n, k – pa);
}
else if (A[pa – 1] > B[pb – 1])
{
B.erase(B.begin(), B.begin() + pb);
return find_kth(A, m, B, n – pb, k – pb);
}
else
return A[pa – 1];
}
};

## 5. Longest Palindromic Substring

Description:

https://leetcode.com/problems/longest-palindromic-substring/#/description

Boundary:

No

Algorithm:

1. DP (Easy to understand, but slow. Time complexity O(n^2) )
2. Manacher (fast, time complexity O(n)) http://www.cnblogs.com/grandyang/p/4475985.html

Code:

DP:

class Solution {
public:
string longestPalindrome(string s) {
int dp[s.size()][s.size()];
int left = 0,right = 0, len = 0;

for (int i = 0; i < s.size();i++)
{
for (int j = 0; j < i; j++)
{
dp[j][i] = s[i] == s[j] && (i-j < 2 || dp[j + 1][i – 1] == 1);
if(dp[j][i] && len < i – j + 1)
{
left = j;
right = i;
len = i – j + 1;
}
}
dp[i][i] = 1;
}
return s.substr(left, right – left + 1);
}
};

Manacher:

class Solution {
public:
// Transform S into T.
// For example, S = “abba”, T = “^#a#b#b#a#\$”.
// ^ and \$ signs are sentinels appended to each end to avoid bounds checking
string preProcess(string s) {
int n = s.length();
if (n == 0) return “^\$”;
string ret = “^”;
for (int i = 0; i < n; i++) ret += “#” + s.substr(i, 1);
ret += “#\$”;
return ret;
}
string longestPalindrome(string s) {
string T = preProcess(s);
const int n = T.length();
// 以T[i] 为中心，向左/右扩张的长度，不包含T[i] 自己，
// 因此P[i] 是源字符串中回文串的长度
vector<int> P = vector<int>(n,-1);
int C = 0, R = 0;
for (int i = 1; i < n – 1; i++) {
int i_mirror = 2 * C – i; // equals to i’ = C – (i-C)
P[i] = (R > i) ? min(R – i, P[i_mirror]) : 0;
// Attempt to expand palindrome centered at i
while (T[i + 1 + P[i]] == T[i – 1 – P[i]])
P[i]++;
// If palindrome centered at i expand past R,
// adjust center based on expanded palindrome.
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
// Find the maximum element in P.
int max_len = 0;
int center_index = 0;
for (int i = 1; i < n – 1; i++) {
if (P[i] > max_len) {
max_len = P[i];
center_index = i;
}
}
return s.substr((center_index – 1 – max_len) / 2, max_len);
}
};

Tips:

1. Get a substring of a string: s.substr(start, LengthOfString);

## 3. Longest Substring Without Repeating Characters

Description:

https://leetcode.com/problems/longest-substring-without-repeating-characters/#/description

Boundary:

when s.size() ==0

Algorithm:

Initially, I just thought about discard the previous longest string and calculate the new string.

However, we cannot discard the whole previous string, the elements may be useful in the following string, such as “dvdf” ‘s result is 3 rather than 2.

Code:

class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (!s.size()) return 0;
string cur = “”;
string pre = “”;
for (int k = 0; k < s.size();k++)
{
while (cur.find(s[k]) < cur.npos)
{
if (cur.size() >= pre.size())
pre = cur;
cur.erase(cur.begin());
}
cur += s[k];
}
if (cur.size() < pre.size())
return pre.size();
else
return cur.size();
}
};

Tip:

Beats 65.54%. The time complexity is O(n).

Description:

Boundary:

When one is NULL while the other is not

Algorithm:

Initially, I want to implement list2int and int2lis, however, I find that when the number gets overflow, it will get the wrong result for list2int.

Therefore, the problem should be finished as done for full adder.

When (l1 != NULL && l2 != NULL)

sum = l1 -> val+ l2 -> val + carry;

when (one is NULL and the other not)

sum = (l1 or l2) -> val + carry;

finally, if (carry), add carry to the end of list.

Code:

class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int carry = 0;
ListNode* tmp;
ListNode *start = NULL;
ListNode *node = start;
int n1, n2, sum;
while (l1 != NULL || l2 != NULL)
{
if (l1 == NULL)
{
n1 = 0;
}
else
{
n1 = l1->val;
l1 = l1->next;
}
if (l2 == NULL)
{
n2 = 0;
}
else
{
n2 = l2->val;
l2 = l2->next;
}
sum = n1 + n2 + carry;
carry = sum / 10;

if (start == NULL)
{
start = new ListNode(sum % 10);
node = start;
}
else
{
tmp = new ListNode(sum % 10);
node->next = tmp;
node = tmp;
}
}
if (carry)
{
tmp = new ListNode(carry);
node->next = tmp;
}
return start;
}
};

Tip:

My code is identical to the example code of the fastest. However, the fastest is 26ms while mine is 55ms! Why???

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