# LeetCode习题集

Posted by Bill on June 26, 2022

# 1. Two sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums + nums == 9, we return [0, 1].
Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?


## 1.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// C++
// O(n2) Solution
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int i, j;
for (i = 0; i < nums.size(); i++) {
for (j = i + 1; j < nums.size();j++) {
if (nums[i] + nums[j] == target) {
return vector<int>{i,j};
}
}
}
return vector<int>{};
}
};


## 1.2 Go Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// go
// O(n1) Solution
type Multimap map[int][]int
type keyValues struct {
key    int
values []int
}

func (multimap Multimap) Add(key, value int) {
if len(multimap[key]) == 0 {
multimap[key] = []int{value}
} else {
multimap[key] = append(multimap[key], value)
}
}

func (multimap Multimap) Get(key int) []int {
if multimap == nil {
return nil
}
values := multimap[key]
return values
}

func twoSum(nums []int, target int) []int {
var myMap Multimap
myMap = make(Multimap);
for index, num := range nums {
}
for key, vals := range myMap {
if len(vals) > 1 && key * 2 == target {
return vals
}
if _, ok :=  myMap[target - key]; ok {
if target - key != key {
return append(myMap[key], myMap[target - key])
}
}
}
return nil
}


You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:
Input: l1 = , l2 = 
Output: 

Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.


## 2.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
// c++
#include<iostream>
#include<vector>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode* constructLists(vector<int>src) {
ListNode* prev = nullptr;
for (auto val : src) {
ListNode *current = new ListNode(val);
if (prev != nullptr) {
prev->next = current;
} else {
}
prev = current;
}
}

class Solution {
public:
Solution() {}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *ptr1 = l1;
ListNode *ptr2 = l2;
ListNode* prev = nullptr;
int carry = 0;
int sum = 0;
while (ptr1 != nullptr || ptr2 != nullptr || carry != 0) {
sum = (ptr1 != nullptr ? ptr1->val : 0) +
(ptr2 != nullptr ? ptr2->val : 0) + carry;
carry = sum / 10;
int val = sum % 10;
ListNode *current = new ListNode(val);
if (prev != nullptr) {
prev->next = current;
} else {
}
prev = current;
if (ptr1 != nullptr) {
ptr1 = ptr1->next;
}
if (ptr2 != nullptr) {
ptr2 = ptr2->next;
}
}
}
};

void test(vector<int> vec1, vector<int> vec2, vector<int>target) {
ListNode *list1 = constructLists(vec1);
ListNode *list2 = constructLists(vec2);
Solution *ptr = new Solution();
ListNode *expect = constructLists(target);

int ansSize = 0;
ListNode *sizeAnsPtr = ans;
while (sizeAnsPtr != nullptr) {
ansSize++;
sizeAnsPtr = sizeAnsPtr->next;
}
if (ansSize != target.size()) {
cout<<"size not matched! expect "<<target.size()<< " real size is "<<ansSize<<endl;
return;
}

ListNode *ansPtr = ans;
ListNode *expectPtr = expect;
bool testRet = true;
while (ansPtr != nullptr && expectPtr != nullptr) {
if (ansPtr->val != expectPtr->val) {
testRet = false;
break;
}
ansPtr = ansPtr->next;
expectPtr = expectPtr->next;
}
if (testRet) {
cout<<"test passed!"<<endl;
} else {
cout<<"test failed!"<<endl;
}
}

int main() {
test(vector<int>{2,4,3}, vector<int>{5,6,4}, vector<int>{7,0,8});
test(vector<int>{0}, vector<int>{0}, vector<int>{0});
test(vector<int>{9,9,9,9,9,9,9}, vector<int>{9,9,9,9}, vector<int>{8,9,9,9,0,0,0,1});
}


# 3. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Example 4:

Input: s = ""
Output: 0

Constraints:

0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.


## 3.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<string>
#include<set>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int left = 0, right = 0;
int len = s.length();
int ans = 0;
set<char> uniqueSet;
for (left = 0 ; left < len; left++) {
uniqueSet.clear();
right = left;
while (right < len) {
if (uniqueSet.count(s[right]) == 0) {
uniqueSet.insert(s[right++]);
continue;
}
else {
break;
}
}
int currentLen = uniqueSet.size();
if (currentLen > ans) {
ans = currentLen;
}
}
return ans;
}
};

void test(string input, int expect) {
Solution *solution = new Solution();
int ans = solution->lengthOfLongestSubstring(input);
if (ans == expect) {
cout<<"test passed!"<<endl;
} else {
cout<<"test failed!"<<endl;
}
delete solution;
}

int main() {
test(string("abcabcbb"), 3);
test(string("bbbbb"), 1);
test(string("pwwkew"), 3);
test(string(""), 0);
test(string("a"), 1);
test(string(" "), 1);
}


# 4. Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Example 1:

Input: nums1 = [1,3], nums2 = 
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Example 3:

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000
Example 4:

Input: nums1 = [], nums2 = 
Output: 1.00000
Example 5:

Input: nums1 = , nums2 = []
Output: 2.00000

Constraints:

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106


## 4.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<vector>
#include<set>
using namespace std;
class Solution {
public:
Solution() {}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int i = 0, j = 0;
int len = nums1.size() + nums2.size();
int target_size = 0;
if (len % 2 == 1) {
target_size = (len - 1)/ 2 + 1;
} else {
target_size = len / 2 + 1;
}
vector<int> ret;
vector<int>::iterator iter1 = nums1.begin();
vector<int>::iterator iter2 = nums2.begin();
while (ret.size() < target_size) {
if (iter1 == nums1.end()) {
ret.push_back(*iter2);
iter2++;
} else if (iter2 == nums2.end()) {
ret.push_back(*iter1);
iter1++;
} else if (*iter1 < *iter2) {
ret.push_back(*iter1);
iter1++;
} else {
ret.push_back(*iter2);
iter2++;
}
}
if (len % 2 == 1) {
return ret.back();
} else {
return (ret.back() + ret[ret.size() - 2]) / 2.0;
}
}
};

void test(vector<int> nums1, vector<int> nums2, double expect) {
Solution *a = new Solution();
double ret = a->findMedianSortedArrays(nums1, nums2);
cout<<"ret = "<<ret<<endl;
if (ret == expect) {
cout<<"tets passed!"<<endl;
} else {
cout<<"tets failed!"<<endl;
}
delete a;
}

int main() {
test(vector<int>{1,3}, vector<int>{2}, 2.00);
test(vector<int>{1,2}, vector<int>{3,4}, 2.5);
test(vector<int>{0}, vector<int>{0}, 0);
test(vector<int>{}, vector<int>{1}, 1);
test(vector<int>{2}, vector<int>{}, 2);
}


# 5. Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Example 1:

Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: s = "cbbd"
Output: "bb"
Example 3:

Input: s = "a"
Output: "a"
Example 4:

Input: s = "ac"
Output: "a"

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.


## 5.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
#include<string>
using namespace std;

class Solution {
public:
string longestPalindrome(string s) {
int left, right;
int max_len = 0;
int len = s.length();
const char pole = '?';
string fix_src(len * 2 - 1, pole);
for (int i = 0; i < len; i++) {
fix_src[2 * i] = s[i];
}
int max_left,max_right = 0;
int fix_len = fix_src.length();
for (int i = 0; i < fix_len; i++) {
left = right = i;
while (left >= 0 && right < fix_len && fix_src[left] == fix_src[right]) {
left--;
right++;
if (left < 0 || right >= fix_len) {
break;
}
}
left++;
right--;
int count_pole = 0;
for (char val : fix_src.substr(left, right - left + 1)){
if (val == pole) {
count_pole++;
}
}
if (right - left + 1 - count_pole > max_len) {
max_len = right - left + 1 - count_pole;
max_left = left;
max_right = right;
}
}
string str =  fix_src.substr(max_left, max_right - max_left + 1);
string ans;
for (int i = 0; i < str.length(); i++) {
if (str[i] != pole) {
char tmp = str[i];
ans.push_back(tmp);
}
}
return ans;
}
};

void test(string input, string expect) {
Solution s;
string ret = s.longestPalindrome(input);
cout<<"ret = "<<ret<<endl;
if (ret.compare(expect) == 0) {
cout<<"tests passed!"<<endl;
} else {
cout<<"tests failed!"<<endl;
}
}

int main() {
test(string("cbbd"), string("bb"));
test(string("a"), string("a"));
test(string("ac"), string("a"));
test(string("ccd"), string("cc"));
}


# 6. Zigzag Conversion

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P A H N A P L S I I G Y I R And then read line by line: “PAHNAPLSIIGYIR”

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I
Example 3:

Input: s = "A", numRows = 1
Output: "A"

Constraints:

1 <= s.length <= 1000
s consists of English letters (lower-case and upper-case), ',' and '.'.
1 <= numRows <= 1000


## 6.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
string convert(string s, int numRows) {
vector<string> zags;
vector<string> zigs;
vector<string> middle_vec;
int col_index = 0;
int zig_index = 0;
if (numRows == 1) {
return s;
}
for (int i = 0; i < s.length(); i += 2 * (numRows - 1)) {
zags.push_back(s.substr(i, numRows));
}
for (int i = numRows; i < s.length(); i += 2 * (numRows - 1)) {
string tmp = s.substr(i, numRows - 2);
reverse(tmp.begin(), tmp.end());
zigs.push_back(tmp);
}
while (col_index < zags.size() || zig_index < zigs.size()) {
if (col_index < zags.size()) {
if (zags[col_index].size() == numRows) {
end.push_back(zags[col_index][numRows - 1]);
}
if (zags[col_index].size() == numRows) {
middle_vec.push_back(zags[col_index].substr(1, numRows - 2));
} else {
middle_vec.push_back(zags[col_index].substr(1));
}
col_index++;
}
if (zig_index < zigs.size()) {
string tmp = zigs[zig_index];
middle_vec.push_back(zigs[zig_index++]);
}
}

for (int i = 0; i < numRows - 2; i++) {
int index = 0;
for (auto str : middle_vec) {
if (str.size() == numRows - 2) {
middle.push_back(str[i]);
} else {
if (index % 2 == 1){
if (i > numRows - 2 - str.size() - 1) {
middle.push_back(str[i - (numRows - 2 - str.size())]);
}
} else {
if (i < str.size()) {
middle.push_back(str[i]);
}
}
}
index++;
}
}
return header + middle + end;
}
};


# 7. Reverse Integer

Category Difficulty Likes Dislikes algorithms Medium (26.18%) 5870 8734 Tags Companies Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Example 1:

Input: x = 123
Output: 321
Example 2:

Input: x = -123
Output: -321
Example 3:

Input: x = 120
Output: 21
Example 4:

Input: x = 0
Output: 0

Constraints:

-231 <= x <= 231 - 1


## 7.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int reverse(int x) {
list <int> myList;
while (x) {
int digit = x % 10;
x = x / 10;
myList.push_back(digit);
}

long ans = 0;
while (!myList.empty()) {
ans = ans * 10 + myList.front();
myList.pop_front();
}
if (ans > INT_MAX || ans < INT_MIN) {
return 0;
}
return ans;
}
};


# 8. String to Integer (atoi)

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function).

The algorithm for myAtoi(string s) is as follows:

Read in and ignore any leading whitespace. Check if the next character (if not already at the end of the string) is ‘-‘ or ‘+’. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present. Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored. Convert these digits into an integer (i.e. “123” -> 123, “0032” -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2). If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1. Return the integer as the final result. Note:

Only the space character ‘ ‘ is considered a whitespace character. Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
Example 1:

Input: s = "42"
Output: 42
Explanation: The underlined characters are what is read in, the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
^
Step 3: "42" ("42" is read in)
^
The parsed integer is 42.
Since 42 is in the range [-231, 231 - 1], the final result is 42.
Example 2:

Input: s = "   -42"
Output: -42
Explanation:
^
Step 2: "   -42" ('-' is read, so the result should be negative)
^
Step 3: "   -42" ("42" is read in)
^
The parsed integer is -42.
Since -42 is in the range [-231, 231 - 1], the final result is -42.
Example 3:

Input: s = "4193 with words"
Output: 4193
Explanation:
Step 1: "4193 with words" (no characters read because there is no leading whitespace)
^
Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+')
^
Step 3: "4193 with words" ("4193" is read in; reading stops because the next character is a non-digit)
^
The parsed integer is 4193.
Since 4193 is in the range [-231, 231 - 1], the final result is 4193.
Example 4:

Input: s = "words and 987"
Output: 0
Explanation:
Step 1: "words and 987" (no characters read because there is no leading whitespace)
^
Step 2: "words and 987" (no characters read because there is neither a '-' nor '+')
^
Step 3: "words and 987" (reading stops immediately because there is a non-digit 'w')
^
The parsed integer is 0 because no digits were read.
Since 0 is in the range [-231, 231 - 1], the final result is 0.
Example 5:

Input: s = "-91283472332"
Output: -2147483648
Explanation:
Step 1: "-91283472332" (no characters read because there is no leading whitespace)
^
Step 2: "-91283472332" ('-' is read, so the result should be negative)
^
Step 3: "-91283472332" ("91283472332" is read in)
^
The parsed integer is -91283472332.
Since -91283472332 is less than the lower bound of the range [-231, 231 - 1], the final result is clamped to -231 = -2147483648.

Constraints:

0 <= s.length <= 200
s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.


## 8.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
int myAtoi(string s) {
bool is_negative = false;
bool sign_has_set = false;
bool has_met_digit = false;
long sum = 0, real_sum = 0;
for (auto character : s) {
if (isspace(character) && !has_met_digit && !sign_has_set) {
continue;
}
if (!sign_has_set && !has_met_digit) {
if (character == '-') {
is_negative = true;
sign_has_set = true;
continue;
} else if (character == '+') {
is_negative = false;
sign_has_set = true;
continue;
}
}

if (!isdigit(character)) {
return real_sum;
}

sum = 10 * sum + character - '0';
real_sum = is_negative ? -1 * sum : sum;
if (real_sum > INT_MAX) {
return INT_MAX;
}
if (real_sum < INT_MIN) {
return INT_MIN;
}
if (!has_met_digit) {
has_met_digit = true;
}
}
return real_sum;
}
};


# 9. Palindrome Number

Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward. For example, 121 is palindrome while 123 is not.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Example 1:

Input: x = 121
Output: true
Example 2:

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
Example 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
Example 4:

Input: x = -101
Output: false

Constraints:

-231 <= x <= 231 - 1


## 9.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0) {
return false;
} else {
char tmp;
sprintf(tmp, "%d", x);
string str = string(tmp);
int left = 0;
int right = str.length() - 1;
while (left < right) {
if (str[left] != str[right]) {
return false;
}
left++;
right--;
}
}
return true;
}
};


# 10. Regular Expression Matching

Given an input string s and a pattern p, implement regular expression matching with support for ‘.’ and ‘*’ where:

• ’.’ Matches any single character.​​​​
• ‘*’ Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:

Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:

Input: s = "aab", p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
Example 5:

Input: s = "mississippi", p = "mis*is*p*."
Output: false

Constraints:

1 <= s.length <= 20
1 <= p.length <= 30
s contains only lowercase English letters.
p contains only lowercase English letters, '.', and '*'.
It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.


## 10.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
bool isMatch(string s, string p) {
if (p.length() == 0) {
return s.length() == 0 ? true : false;
}
bool first_match = false;
if (s.length() > 0 && (p == '.' || p == s)) {
first_match = true;
}
if (p.length() >= 2 && p == '*') {
return isMatch(s, p.substr(2)) || (first_match && isMatch(s.substr(1), p));
} else {
return first_match && isMatch(s.substr(1), p.substr(1));
}
}
}


# 13. Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

1
2
3
4
5
6
7
8
Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000


For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9. X can be placed before L (50) and C (100) to make 40 and 90. C can be placed before D (500) and M (1000) to make 400 and 900. Given a roman numeral, convert it to an integer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Example 1:

Input: s = "III"
Output: 3
Explanation: III = 3.
Example 2:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 3:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.


## 13.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
Solution() {
init();
}
int romanToInt(string s) {
cout<<s<<endl;
if (s.length() == 1) {
return mymap[s];
}
if (s.length() == 2 && mymap.count(s) > 0) {
return mymap[s];
}

if (mymap.count(s.substr(0,2)) > 0) {
return mymap[s.substr(0,2)] + romanToInt(s.substr(2));
} else {
return mymap[s.substr(0,1)] + romanToInt(s.substr(1));
}
}
void init() {
mymap[string("I")] = 1;
mymap[string("IV")] = 4;
mymap[string("V")] = 5;
mymap[string("IX")] = 9;
mymap[string("X")] = 10;
mymap[string("XL")] = 40;
mymap[string("L")] = 50;
mymap[string("XC")] = 90;
mymap[string("C")] = 100;
mymap[string("CD")] = 400;
mymap[string("D")] = 500;
mymap[string("CM")] = 900;
mymap[string("M")] = 1000;
}
private:
std::map<string, int> mymap;
};


# 14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string “”.

1
2
3
4
5
6
7
8
9
10
11
Example 1:
Input: strs = ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Constraints:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lowercase English letters.


## 14.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
string longestCommonPrefix(vector <string>&strs) {
if (strs.empty()) {
return "";
}
if (strs.size() == 1) {
return strs;
}
string temp = strs;
int index;
for (index = 0; index < temp.size(); index++) {
for (int i = 1; i < strs.size(); i++) {
if (index >= strs[i].size() ||
strs[i][index] != temp[index]) {
return temp.substr(0, index);
}
}
}
return temp;
}
}


# 20. Valid Parentheses

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type.

1
2
3
4
5
6
7
8
9
10
11
12
Example 1:

Input: s = "()"
Output: true
Example 2:

Input: s = "()[]{}"
Output: true
Example 3:

Input: s = "(]"
Output: false


## 20.1 C++ solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
bool isValid(string s){
stack<char> parentheses;
for (auto character : s) {
switch(character){
case '(' :
case '[' :
case '{' :
parentheses.push(character);
break;
case ')':
if (parentheses.empty() || parentheses.top() != '(') {
return false;
}
if (!parentheses.empty()) {
parentheses.pop();
}
break;
case ']':
if (parentheses.empty() || parentheses.top() != '[') {
return false;
}
if (!parentheses.empty()) {
parentheses.pop();
}
break;
case '}':
if (parentheses.empty() || parentheses.top() != '{') {
return false;
}
if (!parentheses.empty()) {
parentheses.pop();
}
break;
}
}
return parentheses.empty();
}



# 21. Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists. 1
2
3
4
5
6
7
8
9
10
11
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:

Input: list1 = [], list2 = []
Output: []
Example 3:

Input: list1 = [], list2 = 
Output: 


## 21.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list1 == nullptr) {
return list2;
} else if (list2 == nullptr) {
return list1;
}
if (list1->val <= list2->val) {
} else {
}
}


# 26. Remove Duplicates from Sorted Array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Custom Judge:

The judge will test your solution with the following code:

1
2
3
4
5
6
7
8
9
int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}


If all assertions pass, then your solution will be accepted.

1
2
3
4
5
6
7
8
9
10
11
12
Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).


## 26.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int removeDuplicates(vector<int>& nums) {
if (nums.size() <= 1) return nums.size();
int len = 1;
for (int i = 0; i < nums.size(); i++) {
int j = i + 1;
while (j < nums.size() && nums[j] <= nums[i]) {
j++;
}
if (j != nums.size() /*&& (i + 1 != j)*/) {
swap(nums[i + 1], nums[j]);
len++;
} else if (j == nums.size()) {
break;
}
}
return len;
}


# 27.Remove Element

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Custom Judge:

The judge will test your solution with the following code:

1
2
3
4
5
6
7
8
9
10
11
12
int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
// It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}


If all assertions pass, then your solution will be accepted.

1
2
3
4
5
6
7
8
9
10
11
12
13
Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).


## 27.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int removeElement(vector<int>& nums, int val) {
int len = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != val) {
len++;
continue;
}
int j = i + 1;
while (j < nums.size() && nums[j] == val) {
j++;
}
if (j != nums.size()) {
swap(nums[i], nums[j]);
len++;
} else if (j == nums.size()) {
break;
}
}
return len;
}


# 35. Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

1
2
3
4
5
6
7
8
9
10
11
12
Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2
Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1
Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4


## 35.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int searchInsert(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left +1 < right) {
int mid = (left + right) / 2;
int val = nums[mid];
if (val == target) return mid;
else if (target < val && mid > 0) {
right = mid - 1;
} else if (target > val) {
left = mid + 1;
}
}
if (nums[left] < target && nums[right] > target){
return left + 1;
} else if (nums[left] == target) {
return left;
} else if (nums[right] == target) {
return right;
}  else if(nums[left] > target) {
return left;
} else {
return right + 1;
}
}


# 58. Length Of Last words

Given a string s consisting of words and spaces, return the length of the last word in the string.

A word is a maximal substring consisting of non-space characters only.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Example 1:

Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.
Example 2:

Input: s = "   fly me   to   the moon  "
Output: 4
Explanation: The last word is "moon" with length 4.
Example 3:

Input: s = "luffy is still joyboy"
Output: 6
Explanation: The last word is "joyboy" with length 6.


## 58.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int lengthOfLastWord(string s) {
auto riter = s.rbegin();
while (riter != s.rend()) {
if (isspace(*riter)) {
riter++;
continue;
} else {
break;
}
}
int length = 0;
while (riter != s.rend()) {
if (!isspace(*riter)) {
length++;
riter++;
} else {
break;
}
}
return length;
}


# 66.Plus One

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0’s.

Increment the large integer by one and return the resulting array of digits.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Example 1:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].
Example 2:

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].
Example 3:

Input: digits = 
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].


## 66.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> plusOne(vector<int>& digits) {
vector<int> ret;
auto iter = digits.rbegin();
int carry = 1;
stack<int> myStack;
while (iter != digits.rend()) {
int val = *iter + carry;
carry = val / 10;
myStack.push(val % 10);
iter++;
}
if (carry != 0) {
myStack.push(carry);
}
while (!myStack.empty()) {
ret.push_back(myStack.top());
myStack.pop();
}
return ret;
}


Given two binary strings a and b, return their sum as a binary string.

1
2
3
4
5
6
7
8
Example 1:

Input: a = "11", b = "1"
Output: "100"
Example 2:

Input: a = "1010", b = "1011"
Output: "10101"


## 67.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
string addBinary(string a, string b) {
int carry = 0;
auto a_iter = a.rbegin();
auto b_iter = b.rbegin();
stack<char> myStack;
while (a_iter != a.rend() || b_iter != b.rend() || carry != 0) {
int val = 0;
if (a_iter != a.rend() && b_iter != b.rend()) {
val = (*a_iter - '0') + (*b_iter - '0') + carry;
} else if (a_iter != a.rend() && b_iter == b.rend()) {
val = (*a_iter - '0')  + carry;
} else if (a_iter == a.rend() && b_iter != b.rend()) {
val = (*b_iter - '0')  + carry;
} else {
val = carry;
}
carry = val / 2;
myStack.push(val % 2 + '0');
if (a_iter != a.rend()) {
a_iter++;
}
if (b_iter != b.rend()) {
b_iter++;
}
}
string ret;
while (!myStack.empty()) {
ret.push_back(myStack.top());
myStack.pop();
}
return ret;
}


# 70. Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step


## 70.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int climbStairs(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
int left = 1;
int right = 2;
int cur = 0;
for (int i = 3; i <= n; i++) {
cur = left + right;
left = right;
right = cur;
}
return cur;
}


# 83. Remove Duplicates from Sorted List

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Example 1: Input: head = [1,1,2] Output: [1,2]

Example 2: Input: head = [1,1,2,3,3] Output: [1,2,3]

## 83.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode *last = nullptr;
set<int> mySet;
while (cur != nullptr) {
if (mySet.count(cur->val) == 0) {
mySet.insert(cur->val);
last = cur;
cur = cur->next;
} else {
cur = cur->next;
last->next = cur;
}
}
return ret;
}


# 94.Binary Tree Inorder Traversal

Given the root of a binary tree, return the inorder traversal of its nodes’ values. Example 1:

Input: root = [1,null,2,3] Output: [1,3,2] Example 2:

Input: root = [] Output: [] Example 3:

Input: root =  Output: 

## 94.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> inorderTraversal(TreeNode* root) {
vector<int>ret;
inorder(root, ret);
return ret;
}
void inorder(TreeNode* root, vector<int>&v){
if (root != nullptr) {
inorder(root->left, v);
v.push_back(root->val);
inorder(root->right, v);
}
}


## 94.2 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> inorderTraversal(TreeNode* root) {
vector<int> myVec;
TreeNode* cur = root;
stack<TreeNode *> myStack;
while (cur != nullptr || !myStack.empty()) {
while (cur != nullptr) {
myStack.push(cur);
cur = cur->left;
}
TreeNode *top = myStack.top();
myVec.push_back(top->val);
myStack.pop();
if (top->right != nullptr) {
cur = top->right;
}
}
return myVec;
}


# 108. Convert Sorted Array to Binary Search Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

Example 1 Input: nums = [-10,-3,0,5,9] Output: [0,-3,9,-10,null,5] Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2: Input: nums = [1,3] Output: [3,1] Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

## 108.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
TreeNode* sortedArrayToBST(vector<int>& nums) {
if (nums.empty()) {return nullptr;}
int idx = nums.size() / 2;
TreeNode* root = new TreeNode(nums[idx]);
vector<int>leftNums, rightNums;
for (int i = 0; i < idx; i++) {
leftNums.push_back(nums[i]);
}
for (int i = idx + 1; i < nums.size(); i++)
{
rightNums.push_back(nums[i]);
}

root->left = sortedArrayToBST(leftNums);
root->right = sortedArrayToBST(rightNums);
return root;
}


# 100. Same Tree

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Example 1:

Input:     1         1
/ \       / \
2   3     2   3

[1,2,3],   [1,2,3]

Output: true
Example 2:

Input:     1         1
/           \
2             2

[1,2],     [1,null,2]

Output: false
Example 3:

Input:     1         1
/ \       / \
2   1     1   2

[1,2,1],   [1,1,2]

Output: false


Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) return true;
if((p == null && q != null) || (p != null && q ==null))
return false;
if(p.val == q.val){
if(isNode(p) && isNode(q)){
return true;
}
else if((p.left == null && q.left != null) ||
(p.left != null&& q.left ==null) ||
(p.right == null && p.right != null) ||
(p.right != null && p.right == null)
){
return false;
}
else{
return isSameTree(p.left,q.left) &&
isSameTree(p.right,q.right);
}
}
else{
return false;
}
}

private boolean isNode(TreeNode node){
if(node.left == null && node.right == null){
return true;
}
else return false;
}
}


Approach 1: Recursion Intuition

The simplest strategy here is to use recursion. Check if p and q nodes are not None, and their values are equal. If all checks are OK, do the same for the child nodes recursively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
// p and q are both null
if (p == null && q == null) return true;
// one of p and q is null
if (q == null || p == null) return false;
if (p.val != q.val) return false;
return isSameTree(p.right, q.right) &&
isSameTree(p.left, q.left);
}
}


Complexity Analysis

• Time complexity : \mathcal{O}(N)O(N), where N is a number of nodes in the tree, since one visits each node exactly once.

• Space complexity : \mathcal{O}(\log(N))O(log(N)) in the best case of completely balanced tree and \mathcal{O}(N)O(N) in the worst case of completely unbalanced tree, to keep a recursion stack.

Approach 2: Iteration Intuition

Start from the root and then at each iteration pop the current node out of the deque. Then do the same checks as in the approach 1 :

p and p are not None,

p.val is equal to q.val,

and if checks are OK, push the child nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public boolean check(TreeNode p, TreeNode q) {
// p and q are null
if (p == null && q == null) return true;
// one of p and q is null
if (q == null || p == null) return false;
if (p.val != q.val) return false;
return true;
}

public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (!check(p, q)) return false;

// init deques
ArrayDeque<TreeNode> deqP = new ArrayDeque<TreeNode>();
ArrayDeque<TreeNode> deqQ = new ArrayDeque<TreeNode>();

while (!deqP.isEmpty()) {
p = deqP.removeFirst();
q = deqQ.removeFirst();

if (!check(p, q)) return false;
if (p != null) {
// in Java nulls are not allowed in Deque
if (!check(p.left, q.left)) return false;
if (p.left != null) {
}
if (!check(p.right, q.right)) return false;
if (p.right != null) {
}
}
}
return true;
}
}


Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

1
2
3
4
5
6
7
8
9
10
11
Example:

Input: The root of a Binary Search Tree like this:
5
/   \
2     13

Output: The root of a Greater Tree like this:
18
/   \
20     13


Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {

public TreeNode convertBST(TreeNode root) {
if(root == null){
return null;
}
getGreaterValList(root);
while(!myQueue.isEmpty()){
TreeNode tmp = myQueue.poll();
int sum = 0;
if(tmp.val < val){
sum += val;
}
}
tmp.val += sum;
if(tmp.left != null){
}
if(tmp.right != null){
}
}
return root;
}

void getGreaterValList(TreeNode root){
if(root != null){
}
if(root.left != null){
getGreaterValList(root.left);
}
if(root.right != null){
getGreaterValList(root.right);
}
}
}


Approach #1 Recursion [Accepted] Intuition

One way to perform a reverse in-order traversal is via recursion. By using the call stack to return to previous nodes, we can easily visit the nodes in reverse order.

Algorithm

For the recursive approach, we maintain some minor “global” state so each recursive call can access and modify the current total sum. Essentially, we ensure that the current node exists, recurse on the right subtree, visit the current node by updating its value and the total sum, and finally recurse on the left subtree. If we know that recursing on root.right properly updates the right subtree and that recursing on root.left properly updates the left subtree, then we are guaranteed to update all nodes with larger values before the current node and all nodes with smaller values after.

# 111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example 1: Input: root = [3,9,20,null,null,15,7] Output: 2

Example 2: Input: root = [2,null,3,null,4,null,5,null,6] Output: 5

## 111.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int minDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int left = minDepth(root->left);
int right = minDepth(root->right);
if (root->left == nullptr) {
return 1 + right;
} else if (root->right == nullptr) {
return 1 + left;
} else {
return min(left, right) + 1;
}
}


# 112. Path Sum

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1: Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true Explanation: The root-to-leaf path with the target sum is shown.

Example 2: Input: root = [1,2,3], targetSum = 5 Output: false Explanation: There two root-to-leaf paths in the tree: (1 –> 2): The sum is 3. (1 –> 3): The sum is 4. There is no root-to-leaf path with sum = 5.

Example 3:

Input: root = [], targetSum = 0 Output: false Explanation: Since the tree is empty, there are no root-to-leaf paths

## 112.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool hasPathSum(TreeNode* root, int targetSum) {
if (root == nullptr) {
return false;
}
int newSum = targetSum - root->val;
if (isLeaf(root) && newSum ==0 ) {
return true;
}
return hasPathSum(root->left, newSum) ||
hasPathSum(root->right, newSum);
}
bool isLeaf(TreeNode *node) {
return node != nullptr &&
node->left == nullptr && node->right == nullptr;
}


# 118. Pascal’s Triangle

Given an integer numRows, return the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: numRows = 5 Output: [,[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1 Output: []

## 118.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
vector<vector<int>> generate(int numRows) {
vector<vector<int>>  triangles;
vector<int> lastRow;
for (int i = 0; i < numRows; i++) {
vector<int> row;
if (i == 0) {
row.push_back(1);
}
int curRowNum = i + 1;
int j = 0;
if (!lastRow.empty()) {
while (j < curRowNum - 1) {
int left = 0;
if (j - 1 < 0) {
left = 0;
} else {
left = lastRow[j - 1];
}
row.push_back(lastRow[j] + left);
j++;
}
row.push_back(1);
}
triangles.push_back(row);
lastRow = row;
}
return triangles;
}


# 119. Pascal’s Triangle II

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: rowIndex = 3 Output: [1,3,3,1] Example 2:

Input: rowIndex = 0 Output:  Example 3:

Input: rowIndex = 1 Output: [1,1]

## 119.1 C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
vector<int> getRow(int rowIndex) {
vector<int> lastRow;
vector<int> row;
for (int i = 0; i < rowIndex + 1; i++) {
if (i == 0) {
row.push_back(1);
}
int curRowNum = i + 1;
int j = 0;
if (!lastRow.empty()) {
while (j < curRowNum - 1) {
int left = 0;
if (j - 1 < 0) {
left = 0;
} else {
left = lastRow[j - 1];
}
row.push_back(lastRow[j] + left);
j++;
}
row.push_back(1);
}
lastRow = row;
row.clear();
}
return lastRow;
}


# 344. Reverse String

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

1
2
3
4
5
6
7
8
Example 1:

Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
Example 2:

Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]


Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public void reverseString(char[] s) {
int tail = s.length - 1;
s[tail] = tmp;
tail--;
}
}
}


# 429. N-ary Tree Level Order Traversal

Given an n-ary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example, given a 3-ary tree: We should return its level order traversal:

[ , [3,2,4], [5,6] ]

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;

public Node() {}

public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
if(root == null) return myList;
int currentSize = 1;
int nextSize = 0;
while(!myQueue.isEmpty()){
Node tmp = myQueue.poll();

if(tmp.children != null){
for(int i = 0; i < tmp.children.size();i++){
}
nextSize += tmp.children.size();
}
currentSize = currentSize - 1;
if(currentSize == 0){
currentSize = nextSize;
nextSize = 0;
}

}
return myList;
}
}


# 476. Number Complement

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note: The given integer is guaranteed to fit within the range of a 32-bit signed integer. You could assume no leading zero bit in the integer’s binary representation.

1
2
3
4
5
6
7
8
Example 1:
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
Example 2:
Input: 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.


Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int findComplement(int num) {
int divisor = num;
Stack<Integer>mStack = new Stack<>();
while(divisor != 1){
int remainder = divisor % 2;
divisor /= 2;
remainder = remainder == 1 ? 0 : 1;
mStack.push(remainder);
}
mStack.push(0);
int sum = 0;
while(!mStack.isEmpty()){
sum = sum * 2 + mStack.pop();
}

return sum;
}
}


# 500. Keyboard Row

Given a List of words, return the words that can be typed using letters of alphabet on only one row’s of American keyboard like the image below. 1
2
3
4
Example:



Solutioni:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
private Set<Character> firstSet = new HashSet<>();
private Set<Character> secondSet = new HashSet<>();
private Set<Character> thirdSet = new HashSet<>();

String firstRow = "qwertyuiop";
String secondRow = "asdfghjkl";
String thirdRow = "zxcvbnm";

public void initSets(){
for (char mChar:firstRow.toCharArray()) {
}

for (char mChar:secondRow.toCharArray()) {
}

for (char mChar:thirdRow.toCharArray()) {
}
}

Solution(){
initSets();
}

public String[] findWords(String[] words) {
for(String str: words){
int []whichRows = {0,0,0};
for(char mChar:str.toCharArray()){
if(isFromFirstSets(mChar)){
whichRows = 1;
}
else if(isFromSecondSets(mChar)){
whichRows = 1;
}
else if (isFromThirdSets(mChar)){
whichRows = 1;
}
}
int sum = 0;
for(int ele:whichRows){
sum += ele;
}
if(sum == 1){
}
}
String []retStr = new String[ret.size()];
ret.toArray(retStr);
return retStr;
}

private Boolean isFromFirstSets(char mChar){
return firstSet.contains(mChar);
}

private Boolean isFromSecondSets(char mChar){
return secondSet.contains(mChar);
}

private Boolean isFromThirdSets(char mChar){
return thirdSet.contains(mChar);
}
}


# 509. Fibonacci Number

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

1
2
3
F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.
Given N, calculate F(N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Eample 1:

Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
Example 2:

Input: 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
Example 3:

Input: 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.


Solution:

recursion

1
2
3
4
5
6
7
8
9
public int fib(int N) {
if(N == 0){
return 0;
}
else if(N == 1){
return 1;
}
return fib(N-1) + fib(N-2);
}


iteration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int fib(int N) {
int fib_0 = 0;
int fib_1 = 1;
int ret = 0;
if(N == 0) return fib_0;
if(N == 1) return fib_1;
for(int i = 1; i < N;i++){
//fib(N) = fib(N-1) + fib(N-2)
int left = fib_0;
int right = fib_1;
ret = left + right;
fib_0 = right;
fib_1 = ret;
}
return ret;
}


# 538. Convert BST to Greater Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
private int sum = 0;

public TreeNode convertBST(TreeNode root) {
if (root != null) {
convertBST(root.right);
sum += root.val;
root.val = sum;
convertBST(root.left);
}
return root;
}
}


Complexity Analysis

• Time complexity : O(n)O(n)

A binary tree has no cycles by definition, so convertBST gets called on each node no more than once. Other than the recursive calls, convertBST does a constant amount of work, so a linear number of calls to convertBST will run in linear time.

• Space complexity : O(n)O(n)

Using the prior assertion that convertBST is called a linear number of times, we can also show that the entire algorithm has linear space complexity. Consider the worst case, a tree with only right (or only left) subtrees. The call stack will grow until the end of the longest path is reached, which in this case includes all nn nodes.

Approach #2 Iteration with a Stack [Accepted] Intuition

If we don’t want to use recursion, we can also perform a reverse in-order traversal via iteration and a literal stack to emulate the call stack.

Algorithm

One way to describe the iterative stack method is in terms of the intuitive recursive solution. First, we initialize an empty stack and set the current node to the root. Then, so long as there are unvisited nodes in the stack or node does not point to null, we push all of the nodes along the path to the rightmost leaf onto the stack. This is equivalent to always processing the right subtree first in the recursive solution, and is crucial for the guarantee of visiting nodes in order of decreasing value. Next, we visit the node on the top of our stack, and consider its left subtree. This is just like visiting the current node before recursing on the left subtree in the recursive solution. Eventually, our stack is empty and node points to the left null child of the tree’s minimum value node, so the loop terminates.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public TreeNode convertBST(TreeNode root) {
int sum = 0;
TreeNode node = root;
Stack<TreeNode> stack = new Stack<TreeNode>();

while (!stack.isEmpty() || node != null) {
/* push all nodes up to (and including) this subtree's maximum on
* the stack. */
while (node != null) {
node = node.right;
}

node = stack.pop();
sum += node.val;
node.val = sum;

/* all nodes with values between the current and its parent lie in
* the left subtree. */
node = node.left;
}

return root;
}
}


Approach #3 Reverse Morris In-order Traversal [Accepted] Intuition

There is a clever way to perform an in-order traversal using only linear time and constant space, first described by J. H. Morris in his 1979 paper “Traversing Binary Trees Simply and Cheaply”. In general, the recursive and iterative stack methods sacrifice linear space for the ability to return to a node after visiting its left subtree. The Morris traversal instead exploits the unused null pointer(s) of the tree’s leaves to create a temporary link out of the left subtree, allowing the traversal to be performed using only constant additional memory. To apply it to this problem, we can simply swap all “left” and “right” references, which will reverse the traversal.

Algorithm

First, we initialize node, which points to the root. Then, until node points to null (specifically, the left null of the tree’s minimum-value node), we repeat the following. First, consider whether the current node has a right subtree. If it does not have a right subtree, then there is no unvisited node with a greater value, so we can visit this node and move into the left subtree. If it does have a right subtree, then there is at least one unvisited node with a greater value, and thus we must visit first go to the right subtree. To do so, we obtain a reference to the in-order successor (the smallest-value node larger than the current) via our helper function getSuccessor. This successor node is the node that must be visited immediately before the current node, so it by definition has a null left pointer (otherwise it would not be the successor). Therefore, when we first find a node’s successor, we temporarily link it (via its left pointer) to the node and proceed to the node’s right subtree. Then, when we finish visiting the right subtree, the leftmost left pointer in it will be our temporary link that we can use to escape the subtree. After following this link, we have returned to the original node that we previously passed through, but did not visit. This time, when we find that the successor’s left pointer loops back to the current node, we know that we have visited the entire right subtree, so we can now erase the temporary link and move into the left subtree. The figure above shows an example of the modified tree during a reverse Morris traversal. Left pointers are illustrated in blue and right pointers in red. Dashed edges indicate temporary links generated at some point during the algorithm (which will be erased before it terminates). Notice that blue edges can be dashed, as we always exploit the empty left pointer of successor nodes. Additionally, notice that every node with a right subtree has a link from its in-order successor.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
/* Get the node with the smallest value greater than this one. */
private TreeNode getSuccessor(TreeNode node) {
TreeNode succ = node.right;
while (succ.left != null && succ.left != node) {
succ = succ.left;
}
return succ;
}

public TreeNode convertBST(TreeNode root) {
int sum = 0;
TreeNode node = root;

while (node != null) {
/*
* If there is no right subtree, then we can visit this node and
* continue traversing left.
*/
if (node.right == null) {
sum += node.val;
node.val = sum;
node = node.left;
}
/*
* If there is a right subtree, then there is at least one node that
* has a greater value than the current one. therefore, we must
* traverse that subtree first.
*/
else {
TreeNode succ = getSuccessor(node);
/*
* If the left subtree is null, then we have never been here before.
*/
if (succ.left == null) {
succ.left = node;
node = node.right;
}
/*
* If there is a left subtree, it is a link that we created on a
* previous pass, so we should unlink it and visit this node.
*/
else {
succ.left = null;
sum += node.val;
node.val = sum;
node = node.left;
}
}
}

return root;
}
}


# 543. Diameter of Binary Tree

iven a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

1
2
3
4
5
6
7
8
Example:
Given a binary tree
1
/ \
2   3
/ \
4   5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].


Note: The length of path between two nodes is represented by the number of edges between them.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int diameterOfBinaryTree(TreeNode root) {
if(root == null){
return 0;
}
int maxLeft = diameterOfBinaryTree(root.left);
int maxRight = diameterOfBinaryTree(root.right);
int max = maxLeft > maxRight ? maxLeft : maxRight;

int diameter = getDepth(root.left) + getDepth(root.right);
if(max < diameter){
return diameter;
}
else{
return max;
}
}

private int getDepth(TreeNode root){
if(root != null){
return Math.max(getDepth(root.left), getDepth(root.right)) + 1;
}
return 0;
}
}


Approach #1: Depth-First Search [Accepted] Intuition

Any path can be written as two arrows (in different directions) from some node, where an arrow is a path that starts at some node and only travels down to child nodes.

If we knew the maximum length arrows L, R for each child, then the best path touches L + R + 1 nodes.

Algorithm

Let’s calculate the depth of a node in the usual way: max(depth of node.left, depth of node.right) + 1. While we do, a path “through” this node uses 1 + (depth of node.left) + (depth of node.right) nodes. Let’s search each node and remember the highest number of nodes used in some path. The desired length is 1 minus this number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
int ans;
public int diameterOfBinaryTree(TreeNode root) {
ans = 1;
depth(root);
return ans - 1;
}
public int depth(TreeNode node) {
if (node == null) return 0;
int L = depth(node.left);
int R = depth(node.right);
ans = Math.max(ans, L+R+1);
return Math.max(L, R) + 1;
}
}


Complexity Analysis

• Time Complexity: O(N)O(N). We visit every node once.

• Space Complexity: O(N)O(N), the size of our implicit call stack during our depth-first search.

# 589. N-ary Tree Preorder Traversal

Given an n-ary tree, return the preorder traversal of its nodes’ values.

For example, given a 3-ary tree: Return its preorder traversal as: [1,3,5,6,2,4].

//Reverse Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// Definition for a Node.
class Node {
public int val;
public List<Node> children;

public Node() {}

public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
public class Solution {
List<Integer> myList;
Solution(){
}

public List<Integer> preorder(Node root) {
reversePreorder(root);
return myList;
}

private void reversePreorder(Node root){
if(root == null) return;
if(root.children == null){
}
else{
for(Node ele: root.children){
reversePreorder(ele);
}
}
}
}


//Iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public List<Integer> preorder(Node root) {
if(root == null) return myList;
while(!myDequeue.isEmpty()){
Node tmp = myDequeue.pollFirst();
if(tmp.children != null){
Collections.reverse(tmp.children);
for(Node ele: tmp.children){
}
}
}
return myList;
}
}


# 590. N-ary Tree Postorder Traversal

Given an n-ary tree, return the postorder traversal of its nodes’ values.

For example, given a 3-ary tree: Return its postorder traversal as: [5,6,3,2,4,1].

Note:

Recursive solution is trivial, could you do it iteratively?

//iterator Solution:

/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;

public Node() {}

public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> postorder(Node root) {
Stack<Node> myStack = new Stack<>();
if(root == null) return myList;
while(!myStack.isEmpty()){
Node tmp = myStack.pop();
if(tmp.children == null) continue;
for(Node node: tmp.children){
}
}
Collections.reverse(myList);
return myList;
}
}


//recursive Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public List<Integer> myList;
public List<Integer> postorder(Node root) {
postReverse(root);
return myList;
}
private void postReverse(Node root){
if(root == null) return;
if(root.children == null){
}
else{
for(Node node:root.children){
postReverse(node);
}
}
}
}


# 654. Maximum Binary Tree

Description

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

1
2
3
The root is the maximum number in the array.
The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.


Construct the maximum tree by the given array and output the root node of this tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
Example 1:

Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:

6
/   \
3     5
\    /
2  0
\
1



Note:

• The size of the given array will be in the range [1,1000].

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
if(nums.length == 0){
return null;
}
int maxIndex = 0;
int maxVal = nums;
for(int index = 0;index < nums.length; index++){
if(nums[index] > maxVal){
maxVal = nums[index];
maxIndex = index;
}
}
TreeNode root = new TreeNode(maxVal);
if(maxIndex - 1 >= 0){
root.left = constructMaximumBinaryTree(Arrays.copyOfRange(nums,0,maxIndex));
}
if(maxIndex + 1 <= nums.length - 1){
root.right = constructMaximumBinaryTree(Arrays.copyOfRange(nums,maxIndex + 1,nums.length));
}
return root;
}
}


A better Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
for(int i = 0; i < nums.length; i++) {
TreeNode curr = new TreeNode(nums[i]);
while(!stack.isEmpty() && stack.peek().val < nums[i]) {
curr.left = stack.pop();
}
if(!stack.isEmpty()) {
stack.peek().right = curr;
}
stack.push(curr);
}

return stack.isEmpty() ? null : stack.removeLast();
}
}


# 669. Trim a Binary Search Tree

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Example 1:
Input:
1
/ \
0   2

L = 1
R = 2

Output:
1
\
2
Example 2:
Input:
3
/ \
0   4
\
2
/
1

L = 1
R = 3

Output:
3
/
2
/
1


java Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if(root == null){
return root;
}

if(root.val > R){
return trimBST(root.left,L,R);
}
else if(root.val < L){
return trimBST(root.right,L,R);
}
else{
root.left = trimBST(root.left,L,R);
root.right = trimBST(root.right,L,R);
}
return root;
}
}


Kotlin Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fun trimBST(root: TreeNode?, L: Int, R: Int): TreeNode? {
if (root == null) {
return root
}

if (root.val > R) {
return trimBST(root.left, L, R)
} else if (root.val < L) {
return trimBST(root.right, L, R)
} else {
root.left = trimBST(root.left, L, R)
root.right = trimBST(root.right, L, R)
}
return root
}


# 728. Self Dividing Numbers

A self-dividing number is a number that is divisible by every digit it contains.

For example, 128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0.

Also, a self-dividing number is not allowed to contain the digit zero.

Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible.

Example 1: Input: left = 1, right = 22 Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22] Note:

The boundaries of each input argument are 1 <= left <= right <= 10000.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public List<Integer> selfDividingNumbers(int left, int right) {
for(int i = left;i <= right; i++){
int copy = i;
boolean isSelfDividing = true;
while(copy != 0 ){
int dividend = copy % 10;
copy = copy / 10;
if(dividend == 0 || i % dividend != 0){
isSelfDividing = false;
break;
}
}
if(isSelfDividing)
}

return myList;
}
}


# 804. Unique Morse Code Words

Description

International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows: “a” maps to “.-“, “b” maps to “-…”, “c” maps to “-.-.”, and so on.

For convenience, the full table for the 26 letters of the English alphabet is given below:

1
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]


Now, given a list of words, each word can be written as a concatenation of the Morse code of each letter. For example, “cba” can be written as “-.-.-….-“, (which is the concatenation “-.-.” + “-…” + “.-“). We’ll call such a concatenation, the transformation of a word.

Return the number of different transformations among all words we have.

1
2
3
4
5
6
7
8
9
Example:
Input: words = ["gin", "zen", "gig", "msg"]
Output: 2
Explanation:
The transformation of each word is:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."


There are 2 different transformations, “–…-.” and “–…–.”.

Note:

• The length of words will be at most 100.
• Each words[i] will have length in range [1, 12].
• words[i] will only consist of lowercase letters.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.HashSet;
import java.util.Set;

/**
* Created by bill on 11/13/18.
*/
public class Solution {
public final String []morseDict = {
".-","-...","-.-.","-..",".","..-.","--.","....","..",
".---","-.-",".-..","--","-.","---",".--.","--.-",".-.",
"...","-","..-","...-",".--","-..-","-.--","--.."};
public int uniqueMorseRepresentations(String[] words) {
Set<String> myHashSet = new HashSet<String>();
for(String word: words){
StringBuilder myStringBuilder = new StringBuilder();
for(char ele: word.toCharArray()){
myStringBuilder.append(morseDict[ele - 'a']);
}
String myStr = myStringBuilder.toString();
if(!myHashSet.contains(myStr)){
}
}
return myHashSet.size();
}
}


# 806. Number of Lines To Write String

We are to write the letters of a given string S, from left to right into lines. Each line has maximum width 100 units, and if writing a letter would cause the width of the line to exceed 100 units, it is written on the next line. We are given an array widths, an array where widths is the width of ‘a’, widths is the width of ‘b’, …, and widths is the width of ‘z’.

Now answer two questions: how many lines have at least one character from S, and what is the width used by the last such line? Return your answer as an integer list of length 2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Example :
Input:
widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "abcdefghijklmnopqrstuvwxyz"
Output: [3, 60]
Explanation:
All letters have the same length of 10. To write all 26 letters,
we need two full lines and one line with 60 units.
Example :
Input:
widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "bbbcccdddaaa"
Output: [2, 4]
Explanation:
All letters except 'a' have the same length of 10, and
"bbbcccdddaa" will cover 9 * 10 + 2 * 4 = 98 units.
For the last 'a', it is written on the second line because
there is only 2 units left in the first line.
So the answer is 2 lines, plus 4 units in the second line.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int[] numberOfLines(int[] widths, String S) {
int lines = 1;
int MAXLINE = 100;
int sum = 0;
for (char mChar:
S.toCharArray()) {
int num = widths[mChar - 'a'];
if( sum + num <= MAXLINE){
sum += num;
}
else{
lines++;
sum = num;
}
}
return new int[]{lines, sum};
}
}


# 811. Subdomain Visit Count

A website domain like “discuss.leetcode.com” consists of various subdomains. At the top level, we have “com”, at the next level, we have “leetcode.com”, and at the lowest level, “discuss.leetcode.com”. When we visit a domain like “discuss.leetcode.com”, we will also visit the parent domains “leetcode.com” and “com” implicitly.

Now, call a “count-paired domain” to be a count (representing the number of visits this domain received), followed by a space, followed by the address. An example of a count-paired domain might be “9001 discuss.leetcode.com”.

We are given a list cpdomains of count-paired domains. We would like a list of count-paired domains, (in the same format as the input, and in any order), that explicitly counts the number of visits to each subdomain.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Example 1:
Input:
["9001 discuss.leetcode.com"]
Output:
["9001 discuss.leetcode.com", "9001 leetcode.com", "9001 com"]
Explanation:
We only have one website domain: "discuss.leetcode.com". As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.

Example 2:
Input:
["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
Output:
["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
Explanation:
We will visit "google.mail.com" 900 times, "yahoo.com" 50 times, "intel.mail.com" once and "wiki.org" 5 times. For the subdomains, we will visit "mail.com" 900 + 1 = 901 times, "com" 900 + 50 + 1 = 951 times, and "org" 5 times.


Notes:

• The length of cpdomains will not exceed 100.
• The length of each domain name will not exceed 100.
• Each address will have either 1 or 2 “.” characters.
• The input count in any count-paired domain will not exceed 10000.
• The answer output can be returned in any order.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public List<String> subdomainVisits(String[] cpdomains) {
Map<String, Integer> myMap = new HashMap<>();
for(String domain: cpdomains){
String[]domainStr = domain.split(" ");
int value = Integer.valueOf(domainStr);
String key = domainStr;
if(!myMap.containsKey(key)){
myMap.put(key, value);
}
else{
int old = myMap.get(key);
myMap.put(key, old + value);
}
int tmp = key.indexOf(".");
String tmpDomain = key.substring(tmp + 1);
while(tmp > 0){
if(!myMap.containsKey(tmpDomain)){
myMap.put(tmpDomain, value);
}
else{
int old = myMap.get(tmpDomain);
myMap.put(tmpDomain, old + value);
}
tmp = tmpDomain.indexOf(".");
tmpDomain = tmpDomain.substring(tmp + 1);
}
}
Iterator<Map.Entry<String, Integer>> it = myMap.entrySet().iterator();
while(it.hasNext()){
Map.Entry<String ,Integer> entry = it.next();
StringBuilder myBuilder = new StringBuilder();
myBuilder.append(entry.getValue() + " "+ entry.getKey());
}
return myList;
}
}


# 821.Shortest Distance to a Character

Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.

1
2
3
4
Example 1:

Input: S = "loveleetcode", C = 'e'
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]


Note:

• S string length is in [1, 10000].
• C is a single character, and guaranteed to be in string S. All letters in S and C are lowercase.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int[] shortestToChar(String S, char C) {
int [] ret = new int[S.length()];
for (int i = 0; i < S.length();i++) {
if(S.charAt(i) == C){
}
}

for (int i = 0; i < S.length();i++) {
int min = S.length();
for (int ele: mQueue) {
int distance = Math.abs(ele - i);
if(min > distance){
min = distance;
}
}
ret[i] = min;
}
return ret;
}
}


# 832. Flipping an Image

Given a binary matrix A, we want to flip the image horizontally, then invert it, and return the resulting image.

To flip an image horizontally means that each row of the image is reversed. For example, flipping [1, 1, 0] horizontally results in [0, 1, 1].

To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [0, 1, 1] results in [1, 0, 0].

1
2
3
4
5
6
7
8
9
10
11
12
Example 1:

Input: [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]
Example 2:

Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]


Notes:

• 1 <= A.length = A.length <= 20
• 0 <= A[i][j] <= 1

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public int[][] flipAndInvertImage(int[][] A) {
for(int i = 0; i < A.length; i++){
A[i] = reverseRow(A[i]);
A[i] = invertRow(A[i]);
}
return A;
}

public int[] reverseRow(int[] input){
if(input.length <= 1) return input;
int tail = input.length - 1;
input[tail] = tmp;
tail--;
}
return input;
}

public int[] invertRow(int[] input){
if(input.length < 1) return input;
for(int i = 0; i < input.length; i++){
input[i] ^= 1;
}
return input;
}

}


# 893. Groups of Special-Equivalent Strings

You are given an array A of strings.

Two strings S and T are special-equivalent if after any number of moves, S == T.

A move consists of choosing two indices i and j with i % 2 == j % 2, and swapping S[i] with S[j].

Now, a group of special-equivalent strings from A is a non-empty subset S of A such that any string not in S is not special-equivalent with any string in S.

Return the number of groups of special-equivalent strings from A.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Example 1:

Input: ["a","b","c","a","c","c"]
Output: 3
Explanation: 3 groups ["a","a"], ["b"], ["c","c","c"]
Example 2:

Input: ["aa","bb","ab","ba"]
Output: 4
Explanation: 4 groups ["aa"], ["bb"], ["ab"], ["ba"]
Example 4:

Input: ["abc","acb","bac","bca","cab","cba"]
Output: 3
Explanation: 3 groups ["abc","cba"], ["acb","bca"], ["bac","cab"]
Example 4:

Output: 1


Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int numSpecialEquivGroups(String[] A) {
Set<String> seen = new HashSet();
for (String S: A) {
int[] count = new int;
for (int i = 0; i < S.length(); ++i)
count[S.charAt(i) - 'a' + 26 * (i % 2)]++;
}
return seen.size();
}
}


• What does S.charAt(i) - ‘a’ do? The character a is 97 in ASCII. By subtracting a from another letter in the alphabet, we can convert the ASCII to represent a as 0 instead - thereby making the alphabet 0-indexed.
• What does 26 * (i % 2) do? There are 26 letters in the alphabet i % 2 returns 0 if even and 1 if odd 26 * (i % 2) returns 0 if even and 26 if odd S.charAt(i) - a <— this brings the letter to be 0-indexed
• Where did 52 come from in int[] count = new int ? There are 26 letters in the alphabet A letter could be in an odd index or an even index. This makes 26 + 26 = 52 “kind of letters” The index of the count array represents the property of the letter –> 1. the value of the letter and 2. if it is odd of even If the string has two letter ‘a’s and both of the letters are at an even index, then count == 2.

# 897. Increasing Order Search Tree

Given a tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Example 1:
Input: [5,3,6,2,4,null,8,1,null,null,null,7,9]

5
/ \
3    6
/ \    \
2   4    8
/        / \
1        7   9

Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

1
\
2
\
3
\
4
\
5
\
6
\
7
\
8
\
9


Note:

The number of nodes in the given tree will be between 1 and 100. Each node will have a unique integer value from 0 to 1000.

1
2
3
4
5
6
7
8
9
10
11
public TreeNode increasingBST(TreeNode root) {
return increasingBST(root, null);
}

public TreeNode increasingBST(TreeNode root, TreeNode tail) {
if (root == null) return tail;
TreeNode res = increasingBST(root.left, root);
root.left = null;
root.right = increasingBST(root.right, tail);
return res;
}


# 908. Smallest Range I

Given an array A of integers, for each integer A[i] we may choose any x with -K <= x <= K, and add x to A[i].

After this process, we have some array B.

Return the smallest possible difference between the maximum value of B and the minimum value of B.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Example 1:

Input: A = , K = 0
Output: 0
Explanation: B = 
Example 2:

Input: A = [0,10], K = 2
Output: 6
Explanation: B = [2,8]
Example 3:

Input: A = [1,3,6], K = 3
Output: 0
Explanation: B = [3,3,3] or B = [4,4,4]


Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public int smallestRangeI(int[] A, int K) {
if(A.length <= 1)
return 0;
int size = A.length;
int[] tmpArray = A;

int min = tmpArray;
int max = tmpArray;
for(int i = 1;i < size;i++){
if(min > tmpArray[i])
min = tmpArray[i];
if(max < tmpArray[i])
max = tmpArray[i];
}

if(min + K >= max - K){
return 0;
}
else{
return max - min - 2 * K;
}
}

}


# 912. Sort an Array

Given an array of integers nums, sort the array in ascending order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

Constraints:

1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {

public:
vector<int> sortArray(vector<int>& nums) {
quick_sort(nums, 0, nums.size() - 1);
return nums;
}

void quick_sort(vector<int>& nums, int l, int r)
{

if (l < r)
{

int i = l, j = r, x = nums[l];
while (i < j)
{

while(i < j && nums[j] >= x)
j--;
if(i < j)
nums[i++] = nums[j];

while(i < j && nums[i] < x)
i++;
if(i < j)
nums[j--] = nums[i];
}
nums[i] = x;
quick_sort(nums, l, i - 1);
quick_sort(nums, i + 1, r);
}
}
};


# 938. Range Sum of BST

Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).

The binary search tree is guaranteed to have unique values.

1
2
3
4
5
6
7
8
Example 1:

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32
Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int sum;
public Solution(){
sum = 0;
}
public int rangeSumBST(TreeNode root, int L, int R) {
DFS(root, L, R);
return sum;
}

public void DFS(TreeNode root, int L, int R){
if(root != null){
if(root.val >= L && root.val <= R){
sum+=root.val;
}
if(root.val > L){
DFS(root.left, L, R);
}
if(root.val < R){
DFS(root.right, L, R);
}
}
}
}


# 944. Delete Columns to Make Sorted

We are given an array A of N lowercase letter strings, all of the same length.

Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.

For example, if we have an array A = [“abcdef”,”uvwxyz”] and deletion indices {0, 2, 3}, then the final array after deletions is [“bef”, “vyz”], and the remaining columns of A are [“b”,”v”], [“e”,”y”], and [“f”,”z”]. (Formally, the c-th column is [A[c], A[c], …, A[A.length-1][c]].)

Suppose we chose a set of deletion indices D such that after deletions, each remaining column in A is in non-decreasing sorted order.

Return the minimum possible value of D.length.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Example 1:

Input: ["cba","daf","ghi"]
Output: 1
Explanation:
After choosing D = {1}, each column ["c","d","g"] and ["a","f","i"] are in non-decreasing sorted order.
If we chose D = {}, then a column ["b","a","h"] would not be in non-decreasing sorted order.
Example 2:

Input: ["a","b"]
Output: 0
Explanation: D = {}
Example 3:

Input: ["zyx","wvu","tsr"]
Output: 3
Explanation: D = {0, 1, 2}

Note:

1 <= A.length <= 100
1 <= A[i].length <= 1000


Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int minDeletionSize(String[] A) {
int sum = 0;
int len = A.length;
int strLen = A.length();
for(int i = 0; i < strLen; i++){
char tmp = A.charAt(i);
for(int j = 1; j < len; j++){
if(tmp > A[j].charAt(i)){
sum++;
break;
}
tmp = A[j].charAt(i);
}
}

return sum;
}
}


# 961. N-Repeated Element in Size 2N Array

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.

Return the element repeated N times.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Example 1:

Input: [1,2,3,3]
Output: 3

Example 2:

Input: [2,1,2,5,3,2]
Output: 2

Example 3:

Input: [5,1,5,2,5,3,5,4]
Output: 5

Note:

4 <= A.length <= 10000
0 <= A[i] < 10000
A.length is even


Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.HashMap;
import java.util.Map;

/**
* Created by bill on 2/18/19.
*/
public class Solution {
Map<Integer, Integer> myMap = new HashMap();
public int repeatedNTimes(int[] A) {
int N = A.length/2;
for (int ele: A) {
int tmp = 0;
if(!myMap.containsKey(ele)){
myMap.put(ele,1);
}
else{
tmp = myMap.get(ele) + 1;
myMap.replace(ele,tmp);
}
if(tmp == N){ return ele;}
}
return -1;
}

public static void main(String[] args) {
Solution mySolution = new Solution();
int [] array = {2,1,2,5,3,2};
int ret = mySolution.repeatedNTimes(array);
System.out.println(ret);
}
}


# 965. Univalued Binary Tree

A binary tree is univalued if every node in the tree has the same value.

Return true if and only if the given tree is univalued. • Input: [1,1,1,1,1,null,1]
• Output: true • Input: [2,2,2,5,2]
• Output: false

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public boolean isUnivalTree(TreeNode root) {
int val = root.val;
if(root.left == null && root.right == null){
return true;
}
if(root.left == null){
return isUnivalTree(root.right) &&(root.val == root.right.val);
}
else if(root.right == null){
return isUnivalTree(root.left) &&(root.val == root.left.val);
}
else{
return isUnivalTree(root.left) && isUnivalTree(root.right)
&& (root.val == root.left.val) && (root.val == root.right.val);
}
}
}


# 973. K Closest Points to Origin

We have a list of points on the plane. Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Example 1:

Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].
Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)


Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
class point{
point(int x,int y){
this.x = x;
this.y = y;
}
int x;
int y;
}

class pointId{
pointId(point mid, int mDis){
id = mid;
distance = mDis;
}
point id;
int distance;
}

private Comparator<pointId> mComparator = new Comparator<pointId>(){
@Override
public int compare(pointId t1, pointId t2) {
return t1.distance - t2.distance;
}
};

public int[][] kClosest(int[][] points, int K) {
int len = points.length;
Queue<pointId> mQueue = new PriorityQueue<>(K, mComparator);
for (int []ele:points) {
int distance = EuclideanDistance(ele,ele,0,0);
pointId mId = new pointId(new point(ele,ele), distance);
}

int [][] closest = new int[K];
int i = 0;
while(i < K){
pointId tmp = mQueue.poll();
closest[i] = tmp.id.x;
closest[i] = tmp.id.y;
i++;
}
return closest;
}

private static int EuclideanDistance(int X, int Y, int oX, int oY){
int tmp = (X - oX) * (X - oX) + (Y - oY) * (Y - oY);
return tmp;
}
}


# 977. Squares of a Sorted Array

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Example 1:

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Example 2:

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A is sorted in non-decreasing order.


Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
private boolean less(int v, int w) {
return v < w;
}

private void exch(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}

public int[] sortedSquares(int[] A) {
int N = A.length;
int [] tmp = new int[N];
for (int i = 0; i < N; i++) {
tmp[i] = Math.abs(A[i]);
}

for(int i = 1 ; i < N; i++){
for(int j = i; j > 0 && less(tmp[j], tmp[j-1]);j--){
exch(tmp, j, j-1);
}
}

for (int i = 0; i <N; i++) {
int var = tmp[i];
tmp[i] = var * var;
}
return tmp;
}
}


# 985. Sum of Even Numbers After Queries

We have an array A of integers, and an array queries of queries.

For the i-th query val = queries[i], index = queries[i], we add val to A[index]. Then, the answer to the i-th query is the sum of the even values of A.

(Here, the given index = queries[i] is a 0-based index, and each query permanently modifies the array A.)

1
2
3
4
5
6
7
8
9
10
Example 1:

Input: A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
Output: [8,6,2,4]
Explanation:
At the beginning, the array is [1,2,3,4].
After adding 1 to A, the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8.
After adding -3 to A, the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6.
After adding -4 to A, the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2.
After adding 2 to A, the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.


Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public int[] sumEvenAfterQueries(int[] A, int[][] queries) {
int N = A.length;
int[] sumEventQueries = new int[N];
int num = queries.length;

for(int i = 0; i < num; i++){
int index = queries[i];
int val = queries[i];
A[index] = A[index] + val;
for(int ele: A){
if(isEvent(ele)){
sumEventQueries[i] += ele;
}
}
}
return sumEventQueries;
}

private boolean isEvent(int a){
if(a % 2 == 0){
return true;
}
else
return false;
}

}


# 993. Cousins in Binary Tree

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.

Two nodes of a binary tree are cousins if they have the same depth, but have different parents.

We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.

Return true if and only if the nodes corresponding to the values x and y are cousins.

Example 1: 1
2
Input: root = [1,2,3,4], x = 4, y = 3
Output: false


Example 2: 1
2
Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true


Example 3: 1
2
Input: root = [1,2,3,null,4], x = 2, y = 3
Output: false


Note:

The number of nodes in the tree will be between 2 and 100. Each node has a unique integer value from 1 to 100.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isCousins(TreeNode root, int x, int y) {
TreeNode ParentFirst = getParentWithChild(root, x);
TreeNode ParentSecond = getParentWithChild(root, y);

if(ParentFirst == null || ParentSecond == null){
return false;
}

if((ParentFirst.val != ParentSecond.val) &&
getDepth(root,ParentFirst) == getDepth(root,ParentSecond)){
return true;
}
else{
return false;
}
}

int getDepth(TreeNode root,TreeNode target){
if(root == null){
return -1;
}
if(root.val == target.val){
return 0;
}
int leftDepth = getDepth(root.left,target);
int righttDepth = getDepth(root.right,target);
if(leftDepth != -1){
return leftDepth + 1;
}
if(righttDepth != -1){
return righttDepth + 1;
}
return -1;
}

TreeNode getParentWithChild(TreeNode root, int x){
if(root == null){ return null;}
if((root.left != null && root.left.val == x) ||
(root.right!= null && root.right.val == x)){
return root;
}
TreeNode left = getParentWithChild(root.left,x);
TreeNode right = getParentWithChild(root.right,x);
if(left != null){
return left;
}
if(right != null){
return right;
}
return null;
}
}


# 999. Available Captures for Rook

On an 8 x 8 chessboard, there is one white rook. There also may be empty squares, white bishops, and black pawns. These are given as characters ‘R’, ‘.’, ‘B’, and ‘p’ respectively. Uppercase characters represent white pieces, and lowercase characters represent black pieces.

The rook moves as in the rules of Chess: it chooses one of four cardinal directions (north, east, west, and south), then moves in that direction until it chooses to stop, reaches the edge of the board, or captures an opposite colored pawn by moving to the same square it occupies. Also, rooks cannot move into the same square as other friendly bishops.

Return the number of pawns the rook can capture in one move.

Example 1: 1
2
3
4
Input: [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
Output: 3
Explanation:
In this example the rook is able to capture all the pawns.


Example 2: 1
2
3
4
Input: [[".",".",".",".",".",".",".","."],[".","p","p","p","p","p",".","."],[".","p","p","B","p","p",".","."],[".","p","B","R","B","p",".","."],[".","p","p","B","p","p",".","."],[".","p","p","p","p","p",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
Output: 0
Explanation:
Bishops are blocking the rook to capture any pawn.


Example 3: 1
2
3
4
Input: [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","p",".",".",".","."],["p","p",".","R",".","p","B","."],[".",".",".",".",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."]]
Output: 3
Explanation:
The rook can capture the pawns at positions b5, d6 and f5.


Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
public class Solution {

Boolean north = false;
Boolean south = false;
Boolean east = false;
Boolean west = false;
class Rooks extends Point{
Rooks(int x, int y){
super(x,y);
}
}

class Point{
Point(int x,int y){
this.x = x;
this.y = y;
}
int x;
int y;
}

Rooks mRooks;
public int numRookCaptures(char[][] board) {
int height = board.length;
int width = board.length;
int sum = 0;
for(int i = 0; i < height ;i++){
for(int j = 0; j < width ;j++) {
char tmp = board[i][j];
switch (tmp){
case 'R':
mRooks = new Rooks(i,j);
break;
case 'B':
break;
case 'p':
break;
default: break;
}
}
}
for(int i = 0; i < whiteBishops.size();i++){
if(whiteBishops.get(i).x == mRooks.x){
int whiteBishopsY = whiteBishops.get(i).y;
int max = whiteBishopsY > mRooks.y ? whiteBishopsY  : mRooks.y;
int min = whiteBishopsY < mRooks.y ? whiteBishopsY  : mRooks.y;
if(blackPawns.size() == 0){
if(whiteBishopsY > mRooks.y) {
if(!north){
north = true;
sum++;
}
}
if(whiteBishopsY < mRooks.y) {
if(!south){
south = true;
sum++;
}
}
continue;
}
Boolean hasBlackPawns = false;
for(int j = 0; j < blackPawns.size();j++){
int blackPawnsY = blackPawns.get(j).y;
if(blackPawns.get(j).x == mRooks.x){
if(blackPawnsY < max && blackPawnsY > min){
if(!north||!south){
hasBlackPawns = true;
break;
}
}
}
}

if(!hasBlackPawns){
if(whiteBishopsY > mRooks.y) {
if(!north){
north = true;
sum++;
}
}
if(whiteBishopsY < mRooks.y) {
if(!south){
south = true;
sum++;
}
}
}
}
}
for(int i = 0; i < whiteBishops.size();i++){
if(whiteBishops.get(i).y == mRooks.y){
int whiteBishopsX = whiteBishops.get(i).x;
int max = whiteBishopsX > mRooks.x ? whiteBishopsX : mRooks.x;
int min = whiteBishopsX < mRooks.x ? whiteBishopsX : mRooks.x;
if(blackPawns.size() == 0){
if(whiteBishopsX > mRooks.x) {
if(!east){
east = true;
sum++;
}
}
if(whiteBishopsX < mRooks.x) {
if(!west){
west = true;
sum++;
}
}
continue;
}
Boolean hasBlackPawns = false;
for(int j = 0; j < blackPawns.size();j++){
int blackPawnsX = blackPawns.get(j).x;
if(blackPawns.get(j).y == mRooks.y){
if(blackPawnsX < max && blackPawnsX > min){
if(!east||!west) {
hasBlackPawns = true;
break;
}
}
}
}
if(!hasBlackPawns){
if(whiteBishopsX > mRooks.x) {
if(!east){
east = true;
sum++;
}
}
if(whiteBishopsX < mRooks.x) {
if(!west){
west = true;
sum++;
}
}
}
}
}
return sum;
}
}


# 1002. Find Common Characters

Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates). For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer.

You may return the answer in any order.

1
2
3
4
5
6
7
8
Example 1:

Input: ["bella","label","roller"]
Output: ["e","l","l"]
Example 2:

Input: ["cool","lock","cook"]
Output: ["c","o"]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Solution {

public List<String> commonChars(String[] A) {
int len = A.length;
for(int i = 0;i < len; i++){
Integer[] myVal = new Integer;
for(int k = 0;k < 26;k++){
myVal[k] = 0;
}
String tmp = A[i];
for(int j = 0; j < tmp.length();j++){
myVal[tmp.charAt(j) - 'a']++;
}
}
for(int i = 0; i < 26 ;i++){
int min = Integer.MAX_VALUE;
for(Integer[] ele:myList){
int num = ele[i];
if(num == 0){
min = 0;
break;
}
if(num < min){
min = num;
}
}
for(int j = 0;j < min;j++){
}
}
return myString;
}
}


# 1480. Running Sum of 1d Array

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums…nums[i]).

Return the running sum of nums.

Example 1:

Input: nums = [1,2,3,4] Output: [1,3,6,10] Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4]. Example 2:

Input: nums = [1,1,1,1,1] Output: [1,2,3,4,5] Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1]. Example 3:

Input: nums = [3,1,2,10,1] Output: [3,4,6,16,17]

Constraints:

1 <= nums.length <= 1000 -10^6 <= nums[i] <= 10^6

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
vector<int> runningSum(vector<int>& nums) {
vector<int> ret;
int last = 0;
for(int i = 0 ; i < nums.size(); i++){
ret.push_back(last + nums[i]);
last = ret.back();
}
return ret;
}
};


# 1512. Number of Good Pairs

Given an array of integers nums.

A pair (i,j) is called good if nums[i] == nums[j] and i < j.

Return the number of good pairs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Example 1:

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.
Example 2:

Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array are good.
Example 3:

Input: nums = [1,2,3]
Output: 0


Constraints:

1 <= nums.length <= 100 1 <= nums[i] <= 100

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int numIdenticalPairs(vector<int>& nums) {
int ret = 0;
for(int i = 0; i < nums.size() - 1; i++){
for(int j = nums.size() - 1; j > i; j--){
if(nums[i] == nums[j]){
ret++;
}
}
}
return ret;
}
}; 