# LeetCode Sum of Square Numbers

LeetCode Sum of Square Numbers Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a2 + b2 = c. Example 1:

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:
Input: 3
Output: False

# LeetCode 4Sum

18. 4Sum

Given an array nums of n integers and an integer target, are there elements abc, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
[-1,  0, 0, 1],
[-2, -1, 1, 2],
[-2,  0, 0, 2]
]

class Solution {
public:
vector<vector<int> > fourSum(vector<int>& nums, int target)
{
int min_v = INT_MAX, max_v = INT_MIN;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] < min_v)
min_v = nums[i];
if (nums[i] > max_v)
max_v = nums[i];
}
vector<int> hash(max_v – min_v + 1, 0);
for (int i = 0; i < nums.size(); ++i) {
++hash[nums[i] – min_v];
}
vector<vector<int> > ans;
for (int i = 0; i < hash.size(); ++i) {
if (hash[i] == 0)
continue;
–hash[i];
for (int j = i; j < hash.size(); ++j) {
if (hash[j] == 0)
continue;
–hash[j];
int u = j, v = hash.size() – 1;
while (u <= v) {
while (u <= v && hash[u] == 0)
++u;
if (u > v)
break;
–hash[u];
while (u <= v && hash[v] == 0)
–v;
if (u > v) {
++hash[u];
break;
}
–hash[v];
int sum = i + j + u + v + 4 * min_v;
++hash[u];
++hash[v];
if (sum == target) {
ans.push_back({ i + min_v, j + min_v, u + min_v, v + min_v });
++u;
–v;
}
else if (sum < target)
++u;
else
–v;
}
++hash[j];
}
++hash[i];
}
return ans;
}
};

class Solution {
public:
vector<vector<int> > fourSum(vector<int>& nums, int target)
{
sort(nums.begin(), nums.end());
vector<vector<int> > ans;
int n = nums.size();
for (int i = 0; i < n – 3; ++i) {
if (i > 0 && nums[i] == nums[i - 1])
continue; // 防止nums[i]重复
for (int j = i + 1; j < n – 2; ++j) {
if (j > i + 1 && nums[j] == nums[j - 1])
continue; // 防止nums[j]重复
int u = j + 1, v = n – 1;
while (u < v) {
int sum = nums[i] + nums[j] + nums[u] + nums[v];
if (sum == target) {
ans.push_back({ nums[i], nums[j], nums[u], nums[v] });
int k = u + 1;
while (k < v && nums[k] == nums[u])
++k; // 防止nums[u]重复
u = k;
k = v – 1;
while (k > u && nums[k] == nums[v])
–k; // 防止nums[v]重复
v = k;
}
else if (sum < target)
++u;
else
–v;
}
}
}
return ans;
}
};

# LeetCode Reverse Words in a String

151. Reverse Words in a String

Given an input string, reverse the string word by word.

Example 1:

Input: "the sky is blue"
Output: "blue is sky the"


Example 2:

Input: "  hello world!  "
Output: "world! hello"


Example 3:

Input: "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.


Note:

• A word is defined as a sequence of non-space characters.
• Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
• You need to reduce multiple spaces between two words to a single space in the reversed string.

For C programmers, try to solve it in-place in O(1) extra space.

class Solution {
public:
void reverseWords(string& s)
{
string ans = "";
int start = 0, end = 0, n = s.size();
while (true) {
while (start < n && s[start] == ‘ ‘)
++start;
if (start >= n)
break;
end = start + 1;
while (end < n && s[end] != ‘ ‘)
++end;
if (end >= n)
break;
ans = s.substr(start, end – start) + " " + ans;
start = end + 1;
}
if (end > start)
ans = s.substr(start, end – start) + " " + ans;
s = ans.substr(0, ans.size() – 1);
}
};

class Solution {
public:
void reverseWords(string& s)
{
reverse(s.begin(), s.end());
//i,j为新字符串每个单词的首尾位置，u,v为旧字符串每个单词的首尾位置
int i = 0, j = 0, u = 0, v = 0, n = s.size();
while (true) {
while (u < n && s[u] == ‘ ‘)
++u;
if (u >= n)
break;
v = u;
while (v < n && s[v] != ‘ ‘)
s[j++] = s[v++];
reverse(s.begin() + i, s.begin() + j);
if (v >= n)
break;
s[j++] = ‘ ‘;
i = j;
u = v;
}
if (j == 0)
s = "";
else if (s[j – 1] == ‘ ‘)
s.resize(j – 1);
else
s.resize(j);
}
};

# LeetCode Reverse Vowels of a String

LeetCode Reverse Vowels of a String Write a function that takes a string as input and reverse only the vowels of a string. Example 1: Given s = “hello”, return “holle”. Example 2: Given s = “leetcode”, return “leotcede”. Note: The vowels does not include the letter “y”.

# LeetCode Two Sum II – Input array is sorted

167. Two Sum II – Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

• You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target)
{
int i = 0, j = numbers.size() – 1;
while (numbers[i] + numbers[j] != target) {
if (numbers[i] + numbers[j] > target)
–j;
else
++i;
}
return vector<int>({ i + 1, j + 1 });
}
};

# LeetCode Reverse String

LeetCode Reverse String Write a function that takes a string as input and returns the string reversed. Example: Given s = “hello”, return “olleh”.

# LeetCode Valid Palindrome

125. Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true


Example 2:

Input: "race a car"
Output: false

bool isAlphaNum(char c) { return (c >= ‘A’&& c <= ‘Z’) || (c >= ‘a’&& c <= ‘z’) || (c >= ‘0’&& c <= ‘9’); }
char upper2lower(char c)
{
if (c >= ‘A’&& c <= ‘Z’)
return c + 32;
return c;
}
class Solution {
public:
bool isPalindrome(string s)
{
int i = 0, j = s.size() – 1;
while (i < s.size() && j >= 0) {
while (!isAlphaNum(s[i]) && i < s.size())
i++;
if (i >= s.size())
break;
char c1 = upper2lower(s[i]);
while (!isAlphaNum(s[j]) && j >= 0)
j–;
if (j < 0)
break;
char c2 = upper2lower(s[j]);
if (c1 != c2)
return false;
i++;
j–;
}
return true;
}
};

bool isAlphaNum(char c) { return (c >= ‘A’&& c <= ‘Z’) || (c >= ‘a’&& c <= ‘z’) || (c >= ‘0’&& c <= ‘9’); }
char upper2lower(char c)
{
if (c >= ‘A’&& c <= ‘Z’)
return c + 32;
return c;
}
class Solution {
public:
bool isPalindrome(string s)
{
int i = 0, j = s.size() – 1;
while (i <= j) {
while (!isAlphaNum(s[i]) && i <= j)
i++;
if (i > j)
break;
char c1 = upper2lower(s[i]);
while (!isAlphaNum(s[j]) && i <= j)
j–;
if (i > j)
break;
char c2 = upper2lower(s[j]);
if (c1 != c2)
return false;
i++;
j–;
}
return true;
}
};

class Solution {
public:
bool IsValid(char c) {
return (c >= '0'&&c <= '9') || (c >= 'a'&&c <= 'z');
}
bool isPalindrome(string s) {
int n = s.size();
if (n == 0 || n == 1)return true;
int i = 0, j = n - 1;
while (i < j) {
s[i] = tolower(s[i]);
s[j] = tolower(s[j]);

if (!IsValid(s[i]))++i;
else if (!IsValid(s[j]))--j;
else {
if (s[i] != s[j])break;
else {
++i;
--j;
}
}
}
return i >= j;
}
};

# LeetCode Merge Sorted Array

88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

• The number of elements initialized in nums1 and nums2 are m and n respectively.
• You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

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

class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
{
if (n == 0)
return;
int i = 0;
while (i < m) {
int j = 0;
while (nums1[i] <= nums2[j] && i < m)
i++;
if (i >= m)
break;
swap(nums1[i], nums2[j]);
while (j < n – 1 && nums2[j] > nums2[j + 1]) {
swap(nums2[j], nums2[j + 1]);
j++;
}
i++;
}
for (int j = 0; j < n; j++) {
nums1[i++] = nums2[j];
}
}
};

class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
{
if (n == 0)
return;
int i = m – 1, j = n – 1, k = m + n – 1;
while (i >= 0 || j >= 0) {
int a = i >= 0 ? nums1[i] : INT_MIN;
int b = j >= 0 ? nums2[j] : INT_MIN;
if (a > b) {
nums1[k–] = a;
i–;
}
else {
nums1[k–] = b;
j–;
}
}
}
};

# LeetCode Sort Colors

75. Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Example:

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

• A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
• Could you come up with a one-pass algorithm using only constant space?

class Solution {
public:
void sortColors(vector<int>& nums)
{
int p0 = 0, p2 = nums.size() – 1; // p0和p2分别代表下一个0和2应该填入的位置
int n1 = 0; // 1的数量
for (int i = 0; i <= p2; i++) {
if (nums[i] == 0)
nums[p0++] = nums[i];
else if (nums[i] == 1)
n1++;
else {
swap(nums[i], nums[p2]);
p2–;
i–;
}
}
for (int i = 0; i < n1; i++)
nums[p0++] = 1;
}
};

class Solution {
public:
void sortColors(vector<int>& nums)
{
int zero = 0, second = nums.size() - 1;
int i = 0;
while (i <= second) {
while (i < second && nums[i] == 2) {
swap(nums[i], nums[second--]);
}
while (i > zero && nums[i] == 0) {
swap(nums[i], nums[zero++]);
}
++i;
}
}
};


# LeetCode Remove Element

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

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

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example 1:

Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.


Example 2:

Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}

class Solution {
public:
int removeElement(vector<int>& nums, int val)
{
if (nums.size() == 0)
return 0;
if (nums.size() == 1)
return (nums[0] != val) ? 1 : 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == val) {
for (int j = i + 1; j < nums.size(); j++) {
if (nums[j] != val) {
nums[i] = nums[j];
nums[j] = val;
break;
}
}
}
}
if (nums[0] == val)
return 0;
else {
int i;
for (i = nums.size() – 1; i >= 0; i–)
if (nums[i] != val)
break;
return i + 1;
}
}
};

class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n = nums.size(), i = -1;
for (int j = 0; j < n; ++j) {
if (nums[j] != val)nums[++i] = nums[j];
}
return i + 1;
}
};