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 10⁹ + 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].

322. Coin Change 322. 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:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Note:
You may assume that you have an infinite number of each kind of coin. 322. Coin Change

给定一堆硬币数组coins和一个总数amount，问最少用多少个硬币能凑齐这amount的钱数。每种面值的硬币数量无限。
一开始想到用贪心，即为了使硬币数最少，我们总是用小于等于amount的最大面值的硬币去凑。但是这样得到的结果不是最优的，而且有时候还可能得不到结果。比如coins=[2,5,7,8], amount=19，如果用贪心的思路，首先取8，amount=19-8=11；再取8，amount=11-8=3；再取2，amount=3-2=1；没有硬币可取了，这样就凑不齐19。但是如果不取8，而是取19=7+7+5，则可以用3枚硬币凑齐。
一般不能用贪心得到全局最优解的时候，用DP总是能得到全局最优解的。
假设dp[i]表示凑齐钱数为i最少需要的硬币数，则dp[i]=min(dp[i-coins[j]]+1, dp[i])。这个递推式的意思是说，如果要凑齐钱数i，我们看看能不能用第j个硬币，如果能的话，用之前需要凑齐i-coins[j]的钱数，所以总的硬币数就是凑齐i-coins[j]的硬币数加上1，这个1就是j这个硬币。我们需要遍历所有j求最小。最后dp[amount]就是全局最优解。
完整代码如下：

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

本代码提交AC，用时33MS。

二刷。常规DP思路，类似于背包问题，假设dp[i][j]表示用前i类硬币，组成j元钱的最少硬币数目。有两种情况，一是这次不用第i类硬币，dp[i][j]=dp[i-1][j]；二是这次用第i类硬币，则还需要凑齐j-coins[i]块钱，因为每类硬币数量无限，所以用了i之后还可以用i，即dp[i][j]=dp[i][j-coins[i]]。两种情况取最小值即可。完整代码如下：

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

本代码提交AC，用时344MS。

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 10⁹ + 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.

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

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

• 长度为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]

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.

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

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

139. 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.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

给定一个词典和一个字符串，问字符串能否拆分成若干个词典中有的词。比如样例中词典中有leet和code，则给定的字符串leetcode就能拆分成leet和code，他们都在词典中。
使用DP思路。假设dp[j]表示字符串下标j之前的字符串能否拆分成词典中的词的组合。如果要求dp[i]，则我们可以看看i之前的所有j，如果有dp[j]是true的，且[j,i)的子串在dict中，说明[0,i)也能被拆分成词典中的词，所以dp[i]=true。最后我们只需要返回dp[n]即可。
对于s=”leetcode”，dp=1,0,0,0,1,0,0,0,1，所以dp[n]=1。
代码如下：

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

本代码提交AC，用时3MS。

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 10⁵. 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.

LeetCode Largest Divisible Subset Given a set of distinct positive integers, find the largest subset such that every pair (S_i, S_j) of elements in this subset satisfies: S_i % S_j = 0 or S_j % S_i = 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)

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