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

const int MOD = 1000000007;
class Solution {
public:
int findDerangement(int n) {
if (n == 0)return 1;
if (n == 1)return 0;
long long p = 0, pp = 1;
for (int i = 2; i <= n; ++i) {
long long cur = ((i - 1)*(p + pp)) % MOD;
pp = p;
p = cur;
}
return p;
}
};


# LeetCode Coin Change

LeetCode Coin Change
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
Example 2:
coins = [2], amount = 3
return -1.
Note:
You may assume that you have an infinite number of each kind of coin.

class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int mmax = amount + 1, ans = mmax;
vector<int> dp(amount + 1, mmax);
dp[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (int j = 0; j < coins.size(); ++j) {
if (i - coins[j] >= 0) {
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] >= mmax ? -1 : dp[amount];
}
};


# LeetCode K Inverse Pairs Array

LeetCode K Inverse Pairs Array
Given two integers n and k, find how many different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs.
We define an inverse pair as following: For ith and jth element in the array, if i < j and a[i] > a[j] then it's an inverse pair; Otherwise, it's not.
Since the answer may very large, the answer should be modulo 109 + 7.
Example 1:

Input: n = 3, k = 0
Output: 1
Explanation:
Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pair.


Example 2:

Input: n = 3, k = 1
Output: 2
Explanation:
The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.


Note:

1. The integer n is in the range [1, 1000] and k is in the range [0, 1000].

dp[n+1][k]=dp[n][k]+dp[n][k-1]+dp[n][k-2]+...+dp[n][k-n]

• 长度为n，且有k个逆序对的基础上，把第n+1个数放到原序列的末尾，则不增加逆序对，+dp[n][k]，xxxx*（xxxx表示原长度为n的序列，*表示新加入的数）
• 长度为n，且有k-1个逆序对的基础上，把第n+1个数插入到原序列倒数第一个空位上，xxx*x，因为插入的*是最大的数，和最后一个x形成一个逆序对，使得新的长度为n+1的序列的逆序对=k-1+1=k，所以+dp[n][k-1]
• 类似的，xx*xx，+dp[n][k-2]
• x*xxx，+dp[n][k-3]
• *xxxx，+dp[n][k-4]

const int kMOD = 1000000007;
class Solution {
public:
int kInversePairs(int n, int k) {
vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0));
dp[1][0] = 1; // 长度为1，逆序对为0，只有一种情况
for (int i = 2; i <= n; ++i) {
for (int j = 0; j <= k; ++j) {
for (int m = j; m >= 0 && m > j - i; --m) {
dp[i][j] += dp[i - 1][m];
}
dp[i][j] %= kMOD;
}
}
return dp[n][k];
}
};


# LeetCode Unique Substrings in Wraparound String

LeetCode Unique Substrings in Wraparound String
Consider the string s to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so s will look like this: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.
Note: p consists of only lowercase English letters and the size of p might be over 10000.
Example 1:

Input: "a"
Output: 1
Explanation: Only the substring "a" of string "a" is in the string s.


Example 2:

Input: "cac"
Output: 2
Explanation: There are two substrings "a", "c" of string "cac" in the string s.


Example 3:

Input: "zab"
Output: 6
Explanation: There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.

class Solution {
public:
int findSubstringInWraproundString(string p) {
vector<int> count(26, 0);
int len = 0;
for (int i = 0; i < p.size(); ++i) {
if (i > 0 && (p[i] - p[i - 1] == 1 || p[i] - p[i - 1] == -25))++len;
else len = 1;
count[p[i] - 'a'] = max(count[p[i] - 'a'], len);
}
int ans = 0;
for (int i = 0; i < 26; ++i)ans += count[i];
return ans;
}
};


# LeetCode Maximal Square

LeetCode Maximal Square
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0


Return 4.

0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0

0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 0 1 1 0
0 0 0 0 0

class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty())return 0;
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
int maxLen = 0;
for (size_t i = 0; i < m; ++i) {
dp[i][0] = (matrix[i][0] == '1' ? 1 : 0);
maxLen = max(maxLen, dp[i][0]);
}
for (size_t j = 0; j < n; ++j) {
dp[0][j] = (matrix[0][j] == '1' ? 1 : 0);
maxLen = max(maxLen, dp[0][j]);
}
for (size_t i = 1; i < m; ++i) {
for (size_t j = 1; j < n; ++j) {
if (matrix[i][j] == '1') {
dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
maxLen = max(maxLen, dp[i][j]);
}
}
}
return maxLen*maxLen;
}
};


class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty())return 0;
int m = matrix.size(), n = matrix[0].size();
vector<int> dp(n + 1, 0);
int maxLen = 0, last_topleft = 0; // dp[i][j]的左上角那个值
for (size_t i = 1; i <= m; ++i) {
for (size_t j = 1; j <= n; ++j) {
int tmp = dp[j];
if (matrix[i - 1][j - 1] == '1') {
dp[j] = min(min(dp[j], dp[j - 1]), last_topleft) + 1;
maxLen = max(maxLen, dp[j]);
}
else {
dp[j] = 0;
}
last_topleft = tmp;
}
}
return maxLen*maxLen;
}
};


# LeetCode Word Break

LeetCode Word Break
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> dict(wordDict.begin(), wordDict.end());
int n = s.size();
vector<int> dp(n + 1, 0);
dp[0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = i - 1; j >= 0; --j) {
if (dp[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
dp[i] = 1;
break;
}
}
}
return dp[n];
}
};


# LeetCode Rotate Function

LeetCode Rotate Function
Given an array of integers A and let n to be its length.
Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a "rotation function" F on A as follow:
F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].
Calculate the maximum value of F(0), F(1), ..., F(n-1).
Note:
n is guaranteed to be less than 105.
Example:

A = [4, 3, 2, 6]
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

class Solution {
public:
int maxRotateFunction(vector<int>& A) {
if (A.empty())return 0;
int ans = INT_MIN, n = A.size();
for (int k = 0; k < n; ++k) {
int cur = 0;
for (int i = 0; i < n; ++i) {
cur += ((k + i) % n)*A[i];
}
ans = max(ans, cur);
}
return ans;
}
};


class Solution {
public:
int maxRotateFunction(vector<int>& A) {
if (A.empty())return 0;
int n = A.size(), sum = 0, f0 = 0;
for (int i = 0; i < n; ++i) {
sum += A[i];
f0 += i*A[i];
}
int ans = f0, pre = f0;
for (int i = 1; i < n; ++i) {
int cur = pre + sum - n * A[n - i];
ans = max(ans, cur);
pre = cur;
}
return ans;
}
};


# LeetCode Palindrome Partitioning

LeetCode Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return

[
["aa","b"],
["a","a","b"]
]

DP求s[i,...,j]是否为回文串的过程是这样的，如果s[i]==s[j]，且dp[i+1][j-1]也是回文串，则dp[i][j]也是回文串。所以我们需要先求到长度比较短的s[i+1,j-1]是否为回文串，然后再求长度更长的是否为回文串。所以在helper函数的外层循环是子串的长度。

class Solution {
private:
void helper(const string& s, vector<vector<int>>& dp) {
int n = s.size();
for (int i = 0; i < n; ++i)dp[i][i] = 1; // 单个字符自身就是回文串
for (int len = 2; len <= n; ++len) {
for (int i = 0; i + len - 1 < n; ++i) {
if (s[i] == s[i + len - 1] && ((i + 1 <= i + len - 2 && dp[i + 1][i + len - 2] == 1) || i + 1 > i + len - 2)) {
dp[i][i + len - 1] = 1;
}
}
}
}
void dfs(const string& s, vector<vector<int>>& dp, vector<vector<string>>& ans, vector<string>& cand,int idx) {
if (idx == s.size()) {
ans.push_back(cand);
return;
}
for (int i = idx; i < s.size(); ++i) {
if (dp[idx][i] == 1) {
cand.push_back(s.substr(idx, i - idx + 1));
dfs(s, dp, ans, cand, i + 1);
cand.pop_back();
}
}
}
public:
vector<vector<string>> partition(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
helper(s, dp);
vector<vector<string>> ans;
vector<string> cand;
dfs(s, dp, ans, cand, 0);
return ans;
}
};


# LeetCode Largest Divisible Subset

LeetCode Largest Divisible Subset
Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.
If there are multiple solutions, return any subset is fine.
Example 1:

nums: [1,2,3]
Result: [1,2] (of course, [1,3] will also be ok)


Example 2:

nums: [1,2,4,8]
Result: [1,2,4,8]

class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
if (nums.empty())return{};
sort(nums.begin(), nums.end());
int n = nums.size(), maxLen = 0, maxIdx = 0;
vector<int> dp(n, 1), parent(n, -1);
for (int i = 0; i < n; ++i) {
for (int j = i - 1; j >= 0; --j) {
if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
parent[i] = j;
}
}
if (dp[i] > maxLen) {
maxLen = dp[i];
maxIdx = i;
}
}
vector<int> ans;
while (maxIdx != -1) {
ans.push_back(nums[maxIdx]);
maxIdx = parent[maxIdx];
}
return ans;
}
};


# LeetCode Combination Sum IV

LeetCode Combination Sum IV
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:

nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.


What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

class Solution {
private:
void dfs(vector<int>& nums, int sum, int& ans) {
if (sum == 0) {
++ans;
return;
}
if (sum < 0)return;
for (const auto &i : nums) {
if (sum >= i) {
dfs(nums, sum - i, ans);
}
}
}
public:
int combinationSum4(vector<int>& nums, int target) {
int ans = 0;
dfs(nums, target, ans);
return ans;
}
};


class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (int i = 0; i < nums.size(); ++i) { // 对每个数字
for (int j = target; j >= nums[i]; --j) {
dp[j] += dp[j - nums[i]]; // 取值；不取dp[j]保持不变；所以取和不取加起来就是+=dp[j-nums[i]]
}
}
return dp[target];
}
};


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