# LeetCode Decode Ways II

LeetCode Decode Ways II A message containing letters from A-Z is being encoded to numbers using the following mapping way:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Beyond that, now the encoded string can also contain the character ‘*’, which can be treated as one of the numbers from 1 to 9. Given the encoded message containing digits and the character ‘*’, return the total number of ways to decode it. Also, since the answer may be very large, you should return the output mod 109 + 7. Example 1:
Input: "*"
Output: 9
Explanation: The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I".

Example 2:
Input: "1*"
Output: 9 + 9 = 18

Note:
1. The length of the input string will fit in range [1, 105].
2. The input string will only contain the character ‘*’ and digits ‘0’ – ‘9’.

# LeetCode Find the Derangement of An Array

LeetCode Find the Derangement of An Array In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position. There’s originally an array consisting of n integers from 1 to n in ascending order, you need to find the number of derangement it can generate. Also, since the answer may be very large, you should return the output mod 109 + 7. Example 1:

Input: 3
Output: 2
Explanation: The original array is [1,2,3]. The two derangements are [2,3,1] and [3,1,2].

Note: n is in the range of [1, 106].

# LeetCode Valid Triangle Number

LeetCode Valid Triangle Number Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle. Example 1:

Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Note:
1. The length of the given array won’t exceed 1000.
2. The integers in the given array are in the range of [0, 1000].

# LeetCode Number of Boomerangs

LeetCode Number of Boomerangs Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between iand j equals the distance between i and k (the order of the tuple matters). Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive). Example:

Input:
[[0,0],[1,0],[2,0]]
Output:
2
Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

# LeetCode Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

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

class Solution {
public:
void work(vector<vector<int> >& ans, vector<int>& cand, vector<int>& nums, int step)
{
ans.push_back(cand);
for (int i = step; i < nums.size(); i++) {
if (i != step && nums[i] == nums[i – 1]) { // caution:i != step
continue;
}
cand.push_back(nums[i]);
work(ans, cand, nums, i + 1);
cand.pop_back();
}
}
vector<vector<int> > subsetsWithDup(vector<int>& nums)
{
vector<vector<int> > ans;
vector<int> cand;
sort(nums.begin(), nums.end()); // 先对原数组排序
work(ans, cand, nums, 0);
return ans;
}
};

# LeetCode Permutation Sequence

The set [1,2,3,...,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note:

• Given n will be between 1 and 9 inclusive.
• Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3
Output: "213"


Example 2:

Input: n = 4, k = 9
Output: "2314"

class Solution {
public:
vector<int> fact(int n)
{
vector<int> vFact;
vFact.push_back(1); // 0!=1
int ans = 1;
for (int i = 1; i <= n; i++) {
ans *= i;
vFact.push_back(ans);
}
return vFact;
}
char work(string& candidates, vector<int>& vFact, int& k)
{
int tmp = vFact[candidates.size() – 1];
int idx = ceil(k / float(tmp));
idx–;
char ans = candidates[idx];
candidates.erase(idx, 1);
k -= idx * tmp;
return ans;
}
string getPermutation(int n, int k)
{
vector<int> vFact = fact(n);
string candidates = string("123456789").substr(0, n);
string ans(n, ‘ ‘);
for (int i = 0; i < n; i++)
ans[i] = work(candidates, vFact, k);
return ans;
}
};

class Solution {
public:
void dfs(string &s, int n, vector<int>& visited, int k, int &m, string &ans) {
if (m == k)return;

if (s.size() == n) {
++m;
if (m == k)
ans = s;
return;
}
for (int i = 1; i <= n; ++i) {
if (visited[i] == 0) {
s.push_back('0' + i);
visited[i] = 1;
dfs(s, n, visited, k, m, ans);
s.pop_back();
visited[i] = 0;
}
}
}
string getPermutation(int n, int k) {
string s = "", ans = "";
vector<int> visited(n + 1, 0);
int m = 0;
dfs(s, n, visited, k, m, ans);
return ans;
}
};

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