# LeetCode Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.


If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

class Solution {
public:
int maxSubArray(vector<int>& nums)
{
vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
int ans = nums[0];
for (int i = 1; i < nums.size(); i++) {
if (dp[i – 1] > 0)
dp[i] = dp[i – 1] + nums[i];
else
dp[i] = nums[i];
if (dp[i] > ans)
ans = dp[i];
}
return ans;
}
};

class Solution {
public:
int divide(vector<int>& nums, int left, int right)
{
if (left == right)
return nums[left];
if (left == right – 1)
return max(nums[left] + nums[right], max(nums[left], nums[right]));
int mid = (left + right) / 2;
int lmax = divide(nums, left, mid – 1);
int rmax = divide(nums, mid + 1, right);
int mmax = nums[mid], tmp = nums[mid];
for (int i = mid – 1; i >= left; i–) {
tmp += nums[i];
if (tmp > mmax)
mmax = tmp;
}
tmp = mmax;
for (int i = mid + 1; i <= right; i++) {
tmp += nums[i];
if (tmp > mmax)
mmax = tmp;
}
return max(mmax, max(lmax, rmax));
}
int maxSubArray(vector<int>& nums) { return divide(nums, 0, nums.size() – 1); }
};

class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int max_sum = INT_MIN, cur_sum = 0;
for (int i = 0; i < n; ++i) {
if (cur_sum >= 0) {
cur_sum += nums[i];
}
else {
cur_sum = nums[i];
}
max_sum = max(max_sum, cur_sum);
}
return max_sum;
}
};

# LeetCode Plus One

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.


Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

class Solution {
public:
vector<int> plusOne(vector<int>& digits)
{
vector<int> ans;
int n = digits.size() – 1;
digits[n]++;
while (digits[n] >= 10 && n > 0) {
digits[n] -= 10;
digits[n – 1]++;
n–;
}
if (n == 0 && digits[n] >= 10) {
ans.push_back(1);
digits[n] -= 10;
}
ans.insert(ans.end(), digits.begin(), digits.end());
return ans;
}
};

# LeetCode Combination Sum II

40. Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]


Example 2:

Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]

class Solution {
public:
void work(vector<vector<int> >& ans, vector<int>& candidates, int idx, vector<int>& sol, int target)
{
if (target == 0) {
ans.push_back(sol);
}
else {
for (int i = idx; i < candidates.size(); i++) {
if (candidates[i] > target)
break;
if (i != idx && candidates[i] == candidates[i – 1])
continue; // i != idx
sol.push_back(candidates[i]);
work(ans, candidates, i + 1, sol, target – candidates[i]); // i + 1
sol.pop_back();
}
}
}
vector<vector<int> > combinationSum2(vector<int>& candidates, int target)
{
vector<vector<int> > ans;
vector<int> sol;
sort(candidates.begin(), candidates.end());
work(ans, candidates, 0, sol, target);
return ans;
}
};

class Solution {
public:
void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& cur, int idx) {
if (target == 0) {
ans.push_back(cur);
return;
}
if (target < 0)return;
int i = idx;
while (i < candidates.size()) {
if (i > idx&&candidates[i] == candidates[i - 1]) {
++i;
continue;
}
target -= candidates[i];
cur.push_back(candidates[i]);
dfs(candidates, target, ans, cur, i + 1);
target += candidates[i];
cur.pop_back();
++i;
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> ans;
vector<int> cur;
sort(candidates.begin(), candidates.end());
dfs(candidates, target, ans, cur, 0);
return  ans;
}
};

# LeetCode Combination Sum

Given a set of candidate numbers (candidates(without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]


Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

class Solution {
public:
void work(set<vector<int> >& ans, vector<int>& candidates, vector<int>& sol, int target)
{
if (target == 0) {
vector<int> tmp = sol;
sort(tmp.begin(), tmp.end());
ans.insert(tmp);
}
else {
for (int i = 0; i < candidates.size(); i++) {
if (candidates[i] > target)
break;
sol.push_back(candidates[i]);
work(ans, candidates, sol, target – candidates[i]);
sol.pop_back();
}
}
}
vector<vector<int> > combinationSum(vector<int>& candidates, int target)
{
set<vector<int> > ans;
vector<int> sol;
sort(candidates.begin(), candidates.end());
work(ans, candidates, sol, target);
return vector<vector<int> >(ans.begin(), ans.end());
}
};

class Solution {
public:
void work(vector<vector<int> >& ans, vector<int>& candidates, vector<int>& sol, int target)
{
if (target == 0) {
ans.push_back(sol);
}
else {
for (int i = 0; i < candidates.size(); i++) {
if (candidates[i] > target || (sol.size() > 0 && candidates[i] < sol[sol.size() – 1]))
continue;
sol.push_back(candidates[i]);
work(ans, candidates, sol, target – candidates[i]);
sol.pop_back();
}
}
}
vector<vector<int> > combinationSum(vector<int>& candidates, int target)
{
vector<vector<int> > ans;
vector<int> sol;
sort(candidates.begin(), candidates.end());
work(ans, candidates, sol, target);
return ans;
}
};

class Solution {
public:
void work(vector<vector<int> >& ans, vector<int>& candidates, int idx, vector<int>& sol, int target)
{
if (target == 0) {
ans.push_back(sol);
}
else {
for (int i = idx; i < candidates.size(); i++) {
if (candidates[i] > target)
break;
sol.push_back(candidates[i]);
work(ans, candidates, i, sol, target – candidates[i]);
sol.pop_back();
}
}
}
vector<vector<int> > combinationSum(vector<int>& candidates, int target)
{
vector<vector<int> > ans;
vector<int> sol;
sort(candidates.begin(), candidates.end());
work(ans, candidates, 0, sol, target);
return ans;
}
};

class Solution {
public:
void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& cur, int idx) {
if (target == 0) {
ans.push_back(cur);
return;
}
if (target < 0)return;
for (int i = idx; i < candidates.size(); ++i) {
target -= candidates[i];
cur.push_back(candidates[i]);
dfs(candidates, target, ans, cur, i);
cur.pop_back();
target += candidates[i];
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;
vector<int> cur;
dfs(candidates, target, ans, cur, 0);
return ans;
}
};

# LeetCode Happy Number

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example:

Input: 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

class Solution {
public:
bool isHappy(int n)
{
set<int> nums;
while (true) {
if (nums.find(n) != nums.end())
return false;
nums.insert(n);
int sum = 0;
while (n != 0) {
int q = n % 10;
sum += q * q;
n = n / 10;
}
if (sum == 1)
return true;
else
n = sum;
}
}
};

# LeetCode Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

class Solution {
public:
void nextPermutation(vector<int>& nums)
{ // 4876543
for (int i = nums.size() – 1; i > 0; i–) {
if (nums[i] > nums[i – 1]) { // 8 > 4
int min_idx = i, min_val = INT_MAX;
for (int j = nums.size() – 1; j > i; j–) {
if (nums[j] > nums[i – 1] && nums[j] < min_val) { // 5 > 4
min_idx = j;
min_val = nums[j];
}
}
swap(nums[i – 1], nums[min_idx]); // 5876443
reverse(nums.begin() + i, nums.end()); // 5344678
return;
}
}
reverse(nums.begin(), nums.end());
}
};

# LeetCode Rotate Image

48. Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]


Example 2:

Given input matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],

rotate the input matrix in-place such that it becomes:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

class Solution {
public:
void rotate(vector<vector<int> >& matrix)
{
int offset = matrix.size() – 1, max_y = matrix.size() – 1;
for (int i = 0; i < matrix.size() / 2; i++) {
int x = offset, y = 0;
for (int j = i; j < max_y; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[i + x][j – y];
matrix[i + x][j – y] = matrix[i + x + y][j – y + x];
matrix[i + x + y][j – y + x] = matrix[i + y][j + x];
matrix[i + y][j + x] = tmp;
x–;
y++;
}
offset -= 2;
max_y–;
}
}
};

class Solution {
public:
void rotate(vector<vector<int> >& matrix)
{
reverse(matrix.begin(), matrix.end());
for (int i = 0; i < matrix.size(); ++i) {
for (int j = i + 1; j < matrix[0].size(); ++j) {
swap(matrix[i][j], matrix[j][i]);
}
}
}
};

# LeetCode Permutations II

47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

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

• 1,2,3
• 2,1,3
• 3,2,1

• 2,3
• 3,2

• 1,2,3
• 1,3,2

class Solution {
public:
void work(set<vector<int> >& ans, vector<int>& nums, int start)
{
if (start == nums.size()) {
ans.insert(nums);
}
else {
for (int i = start; i < nums.size(); i++) {
if (i != start && nums[i] == nums[i – 1])
continue;
swap(nums[i], nums[start]);
work(ans, nums, start + 1);
swap(nums[i], nums[start]);
}
}
}
vector<vector<int> > permuteUnique(vector<int>& nums)
{
sort(nums.begin(), nums.end());
set<vector<int> > ans;
work(ans, nums, 0);
return vector<vector<int> >(ans.begin(), ans.end());
}
};

class Solution {
private:
void dfs(const vector<int>& nums, vector<vector<int> >& ans, vector<int>& cand, vector<int>& visited)
{
if (cand.size() == nums.size()) {
ans.push_back(cand);
return;
}
int last = INT_MAX;
for (int i = 0; i < nums.size(); ++i) {
if (visited[i] == 0) {
if (i != 0 && nums[i] == last)
continue; // 不能和上一次递归的元素相同，否则产生冗余排列
cand.push_back(nums[i]);
last = nums[i];
visited[i] = 1;
dfs(nums, ans, cand, visited);
visited[i] = 0;
cand.pop_back();
}
}
}
public:
vector<vector<int> > permuteUnique(vector<int>& nums)
{
sort(nums.begin(), nums.end());
vector<vector<int> > ans;
vector<int> cand, visited(nums.size(), 0);
dfs(nums, ans, cand, visited);
return ans;
}
};

class Solution {
private:
void dfs(const vector<int>& nums, vector<vector<int> >& ans, vector<int>& cand, vector<int>& visited)
{
if (cand.size() == nums.size()) {
ans.push_back(cand);
return;
}
for (int i = 0; i < nums.size(); ++i) {
if (visited[i] == 0) {
if (i != 0 && nums[i] == nums[i – 1] && visited[i – 1] == 0)
continue;
cand.push_back(nums[i]);
visited[i] = 1;
dfs(nums, ans, cand, visited);
visited[i] = 0;
cand.pop_back();
}
}
}
public:
vector<vector<int> > permuteUnique(vector<int>& nums)
{
sort(nums.begin(), nums.end());
vector<vector<int> > ans;
vector<int> cand, visited(nums.size(), 0);
dfs(nums, ans, cand, visited);
return ans;
}
};

class Solution {
public:
void dfs(vector<int>& nums, vector<int>& visited, vector<vector<int>>& ans, vector<int>& cur) {
if (cur.size() == nums.size()) {
ans.push_back(cur);
return;
}
int pre = -1;
for (int i = 0; i < nums.size(); ++i) {
if (visited[i] == 0) {
if (pre != -1 && nums[i] == nums[pre])continue;
visited[i] = 1;
cur.push_back(nums[i]);
dfs(nums, visited, ans, cur);
cur.pop_back();
visited[i] = 0;
pre = i;
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
vector<int> visited(nums.size(), 0);
vector<int> cur;
dfs(nums, visited, ans, cur);
return ans;
}
};

# LeetCode Length of Last Word

58. Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word (last word means the last appearing word if we loop from left to right) in the string.

If the last word does not exist, return 0.

Note: A word is defined as a maximal substring consisting of non-space characters only.

Example:

Input: "Hello World"
Output: 5

class Solution {
public:
int lengthOfLastWord(string s)
{
int e = s.size() – 1;
while (e >= 0 && s[e] == ‘ ‘) {
e–;
}
if (e < s.size() – 1) {
s = s.substr(0, e + 1);
}
size_t tPos = s.find_last_of(‘ ‘);
if (tPos == string::npos)
return s.size();
return s.size() – tPos – 1;
}
};

class Solution {
public:
int lengthOfLastWord(string s)
{
int i = s.size() – 1;
while (i >= 0 && s[i] == ‘ ‘)
–i;
if (i < 0)
return 0;
int j = i – 1;
while (j >= 0 && s[j] != ‘ ‘)
–j;
return i – j;
}
};

# LeetCode Permutations

Given a collection of distinct integers, return all possible permutations.

Example:

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


class Solution {
public:
void work(vector<vector<int> >& ans, vector<int>& tmp, vector<int>& nums, vector<int>& flag)
{
if (tmp.size() == nums.size()) {
ans.push_back(tmp);
}
else {
for (int i = 0; i < flag.size(); i++) {
if (flag[i] == 1) {
vector<int> next = tmp;
next.push_back(nums[i]);
flag[i] = 0;
work(ans, next, nums, flag);
flag[i] = 1;
}
}
}
}
vector<vector<int> > permute(vector<int>& nums)
{
vector<int> flag(nums.size(), 1);
vector<vector<int> > ans;
vector<int> tmp;
work(ans, tmp, nums, flag);
return ans;
}
};

class Solution {
private:
void DFS(const vector<int>& nums, vector<int>& visited, vector<int>& candidate, vector<vector<int> >& ans)
{
if (candidate.size() == nums.size()) {
ans.push_back(candidate);
return;
}
for (int i = 0; i < nums.size(); ++i) {
if (visited[i] == 0) {
visited[i] = 1;
candidate.push_back(nums[i]);
DFS(nums, visited, candidate, ans);
visited[i] = 0;
candidate.pop_back();
}
}
}
public:
vector<vector<int> > permute(vector<int>& nums)
{
vector<int> visited(nums.size(), 0), candidate;
vector<vector<int> > ans;
DFS(nums, visited, candidate, ans);
return ans;
}
};

class Solution {
private:
void DFS(vector<int>& nums, vector<vector<int> >& ans, int start)
{
if (start == nums.size()) {
ans.push_back(nums);
return;
}
for (int i = start; i < nums.size(); ++i) {
swap(nums[i], nums[start]);
DFS(nums, ans, start + 1);
swap(nums[i], nums[start]);
}
}
public:
vector<vector<int> > permute(vector<int>& nums)
{
vector<vector<int> > ans;
DFS(nums, ans, 0);
return ans;
}
};