Tag Archives: 排列

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 Decode Ways的升级版本,引入了一个星号’*’,可以表示’1′-‘9’这9个数字。给定一个加密的字符串,问有多少种解密方法。 这个题说难也难,说简单也简单,我居然跪在了int上,把dp数组由int改为long long就AC了! 和前一题的思路差不多,对于每个字符,都有两种可能的选择,要么该字符单独解码,要么和前一个字符组合起来解码。 设dp[i]表示前i个字符总的解密数。 对于当前字符是数字,前一个字符也是数字的情况,和前一题的思路完全一样,如果是’1’-‘9’,则可以自行解码,dp[i]+=dp[i-1];如果前一个字符和当前字符组合的数字范围在[10,26],可以和前一个字符组合解码,dp[i]+=dp[i-2]。 如果当前字符是数字,但前一个字符是*。如果要和前一个字符组合,当前字符如果在[‘0′,’6’],则前一个*可以取’1’或者’2’,所以dp[i]+=dp[i-2]*2;如果当前字符是[‘7′,’9’],则前一个*只能取’1’,所以dp[i]+=dp[i-2]。 对于*需要特殊处理。如果当前字符是*,前一个字符不是*,要和前一个字符组合,则如果前一个是’1’,则当前*可以取[‘0′,’9’],所以dp[i]+=dp[i-2]*9;如果前一个是’2’,则当前*可以取[‘0′,’6’],所以dp[i]+=dp[i-2]*6。其他情况都不能组合。 如果当前字符和前一个字符都是*的情况,要组合,则**的情况只有15种,注意不是26种,因为要去掉那些个位数和包含0的十位数的情况,剩下就只有15种了。所以dp[i]+=dp[i-2]*15。 完整代码如下: [cpp] const int MOD = 1000000007; typedef long long ll; class Solution { public: int numDecodings(string s) { if (s == "" || s[0] == ‘0’)return 0; s = "^" + s; int n = s.size(); vector<ll> dp(n, 0); dp[0] = 1; if (s[1] == ‘*’)dp[1] = 9; else dp[1] = 1; for (int i = 2; i < n; i++) { if (s[i] >= ‘1’ && s[i] <= ‘9’) dp[i] += dp[i – 1] % MOD; // 独自解析 if ((s[i – 1] == ‘1’ && s[i] >= ‘0’ && s[i] <= ‘9’) || (s[i – 1] == ‘2’ && s[i] >= ‘0’ && s[i] <= ‘6’)) dp[i] += dp[i – 2] % MOD; if (s[i – 1] == ‘*’&&s[i] >= ‘0’&&s[i] <= ‘9’) { if (s[i] >= ‘0’&&s[i] <= ‘6’)dp[i] += dp[i – 2] * 2 % MOD; if (s[i] > ‘6’)dp[i] += dp[i – 2] % MOD; } if (s[i] == ‘*’) { dp[i] += dp[i – 1] * 9 % MOD; // 独自解析 if (s[i – 1] != ‘*’) { if (s[i – 1] == ‘1’)dp[i] += dp[i – 2] * 9 % MOD; else if (s[i – 1] == ‘2’)dp[i] += dp[i – 2] * 6 % MOD; } else { dp[i] += dp[i – 2] * 15 % MOD; } } dp[i] %= MOD; } return dp[n – 1]; } }; [/cpp] 本代码提交AC,用时72MS。比赛的时候dp数组用int存的,死活WA,比赛结束那一秒,改成long long之后就AC了,但是比赛已经结束了。。。 看了下TOP代码,思路比我的稍微清晰一点,原理都是一样的,重构我的代码如下: [cpp] class Solution { public: int numDecodings(string s) { if (s == "" || s[0] == ‘0’)return 0; s = "^" + s; int n = s.size(); vector<ll> dp(n, 0); dp[0] = 1; if (s[1] == ‘*’)dp[1] = 9; else dp[1] = 1; for (int i = 2; i < n; i++) { char cur = s[i], pre = s[i – 1]; ll &curCnt = dp[i], preCnt = dp[i – 1], prePreCnt = dp[i – 2]; if (cur == ‘0’) { if (pre == ‘1’|| pre == ‘2’)curCnt += prePreCnt % MOD; else if (pre == ‘*’)curCnt += prePreCnt * 2 % MOD; else return 0; } else if (cur == ‘*’) { curCnt += preCnt * 9 % MOD; if (pre == ‘1’)curCnt += prePreCnt * 9 % MOD; else if (pre == ‘2’)curCnt += prePreCnt * 6 % MOD; else if (pre == ‘*’)curCnt += prePreCnt * 15 % MOD; } else { // [‘1′,’9′] curCnt += preCnt % MOD; if(pre==’1’)curCnt += prePreCnt % MOD; else if (pre == ‘2’ && cur <= ‘6’)curCnt += prePreCnt % MOD; else if (pre == ‘*’) { if (cur <= ‘6’)curCnt += prePreCnt * 2 % MOD; else curCnt += prePreCnt % MOD; } } curCnt %= MOD; } return dp[n – 1]; } }; [/cpp] 本代码提交AC,用时105MS。]]>

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].
给定一个长度为n的数组[1,2,3,…,n],如果该数组的一个排列中,每个数字都不在它原来的位置了,我们称这个排列是原数组的一个Derangement(错排)。问长度为n的数组,有多少个Derangement。 维基百科关于错排问题有比较详细的解释。 假设dp[n]表示长度为n的数组的错排个数,显然dp[0]=1,dp[1]=0,dp[2]=1。如果已经知道dp[0,…,n-1],怎样求dp[n]。考虑第n个数,因为错排,它肯定不能放在第n位,假设n放在第k位,则有如下两种情况: 数字k放在了第n位,这时,相当于n和k交换了一下位置,还剩下n-2个数需要错排,所以+dp[n-2] 数字k不放在第n位,此时,可以理解为k原本的位置是n,也就是1不能放在第1位、2不能放在第2位、…、k不能放在第n位,也就相当于对n-1个数进行错排,所以+dp[n-1] 因为n可以放在1~n-1这n-1个位置,所以总的情况数等于dp[n]=(n-1)(dp[n-1]+dp[n-2])。 这就类似于求斐波那契数列的第n项了,维护前两个变量,不断滚动赋值就好了,时间复杂度O(n),代码如下: [cpp] 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; } }; [/cpp] 本代码提交AC,用时13MS。]]>

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

给定一个数组,问从中能取出所少个三元数组,使得取出的三个数能构成一个三角形。 首先明确三条线段构成三角形的条件是任意两边之和要大于第三遍。 先上暴力,直接dfs枚举出所有的三元组,判断能构成三角形,则方案数加1。代码如下: [cpp] class Solution { private: void dfs(int &ans, vector<int>& nums, vector<int>& cand, int idx) { if (cand.size() == 3) { int &a = cand[0], &b = cand[1], &c = cand[2]; if (a + b > c&&a + c > b&&b + c > a) { ++ans; //cout << a << "\t" << b << "\t" << c << endl; } return; } for (int i = idx; i < nums.size(); ++i) { if (cand.size() == 2 && cand[0] + cand[1] <= nums[i])return; cand.push_back(nums[i]); dfs(ans, nums, cand, i + 1); cand.pop_back(); } } public: int triangleNumber(vector<int>& nums) { int ans = 0; vector<int> cand; sort(nums.begin(), nums.end()); dfs(ans, nums, cand, 0); return ans; } }; [/cpp] 本代码提交TLE:219 / 243。数组最大长度是1000,则所有的组合数有1000*999*998=997002000,确实有点大。。。 后来我发现,报TLE的大数据,虽然有1000个数,但是有很多都是重复的,真正不同的数大概只有100个左右。所以我就想,先对数据去重,在所有互异的数中dfs。然后根据每条边重复的次数来求组合数。 比如样例中,互异的数是[2,3,4],dfs发现[2,3,4]可以构成三角形,则所有由[2,3,4]构成的三角形的个数应该是count[2]*count[3]*count[4]=2*1*1=2。 所以我们先对数组做个hash,统计数值及其出现频率的关系。注意,因为边的长度最大也只为1000,所以用一个1000长的数组来hash比用map或者unordered_map占用的内存更少,否则会MLE。 然后分三类情况进行计算:1. 三条边互不相同;2.有两条边的值相等;3.三条边的值都相等。 其中第一种情况用常规的DFS求解。第二种和第三种情况就是简单的枚举。 还需要注意一点是,边长为0的值需要过滤掉。 完整代码如下: [cpp] class Solution { private: void dfs(int& ans, vector<int>& count, vector<int>& nums, vector<int>& cand, int idx) { if (cand.size() == 3) { int &a = cand[0], &b = cand[1], &c = cand[2]; if (a + b > c&&a + c > b&&b + c > a) { ans += count[a] * count[b] * count[c]; // 三边各异 //cout << a << "\t" << b << "\t" << c << endl; } return; } for (int i = idx; i < nums.size(); ++i) { if (cand.size() == 2 && cand[0] + cand[1] <= nums[i])return; cand.push_back(nums[i]); dfs(ans, count, nums, cand, i + 1); cand.pop_back(); } } public: int triangleNumber(vector<int>& nums) { vector<int> mii(1001, 0); for (const auto& i : nums)++mii[i]; // hash vector<int> distinct; for (int i = 1; i < 1001; ++i) { if (mii[i] > 0)distinct.push_back(i); } int ans = 0; vector<int> cand; dfs(ans, mii, distinct, cand, 0); // 三边互不相同 int n = distinct.size(); for (int i = 0; i < n; ++i) { if (mii[distinct[i]] >= 3) { // 三边相同 int &d = mii[distinct[i]]; ans += (d*(d – 1)*(d – 2)) / 6; } for (int j = i + 1; j < n; ++j) { if (mii[distinct[i]] >= 2) { // 两条边一样 int &a = distinct[i], &b = distinct[i], &c = distinct[j]; if (a + b > c&&a + c > b&&b + c > a) { ans += (mii[a] * (mii[a] – 1) / 2)*mii[c]; } } if (mii[distinct[j]] >= 2) { // 两条边一样 int &a = distinct[i], &b = distinct[j], &c = distinct[j]; if (a + b > c&&a + c > b&&b + c > a) { ans += (mii[b] * (mii[b] – 1) / 2)*mii[a]; } } } } return ans; } }; [/cpp] 本代码提交AC,用时1589MS。]]>

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

给定一堆点集,问回飞镖的个数。一个回飞镖是一个三点集(i,j,k),且满足i到j和k的距离相等。 如果和i距离相等的点有n个,则这样的三点集有$$A_n^2=n(n-1)$$,也就是从n个点中拿两个点做排列。所以问题就转换为对每个点,都求其他所有点和该点的距离,求到距离相等的点的个数n,然后代入公式计算。 代码如下: [cpp] class Solution { public: int numberOfBoomerangs(vector<pair<int, int>>& points) { int ans = 0; for (int i = 0; i < points.size(); ++i) { unordered_map<int, int> dist_cnt; for (int j = 0; j < points.size(); ++j) { int xdiff = points[i].first – points[j].first; int ydiff = points[i].second – points[j].second; ++dist_cnt[xdiff*xdiff + ydiff*ydiff]; } for (auto it = dist_cnt.begin(); it != dist_cnt.end(); ++it)ans += it->second*(it->second – 1); } return ans; } }; [/cpp] 本代码提交AC,用时369MS。 因为题中说到所有点都是不相同的,所以第7行没必要限制j!=i,即使j==i,算出来的距离是0,dist_cnt[0]=1,也就是只有点x一个点和自己的距离是0。到第12行计算排列数时,n(n-1)=0,所以没关系。]]>

LeetCode Subsets II

90. 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],
  []
]

求一个“集合”的所有子集,和LeetCode Subsets的区别是本题中,原始“集合”可能包含重复元素,和LeetCode Permutations II很类似。
只需在LeetCode Subsets的基础上增加一个判断,如果在递归的时候发现某个元素和上一个元素相同,则不添加,即不再以该元素独立新开一个递归下去。
举个例子,样例中的{1,2,2},第一次递归的时候,我们会尝试分别以1,2和2递归,但是发现第二个2和前一个元素2相同,所以我们不再以第二个2开一个新的递归下去。但是我们在以第一个2开递归的时候,发现后面有一个2时,并不阻止这个2加到原有的集合中去,也就是子集{2,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;
    }
};

注意判断的条件是i!=step,而不是i!=0,因为如果是i!=0,则{2,2}这种情况也会被禁止掉。
本代码提交AC,用时6MS。

LeetCode Permutation Sequence

60. 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"

求1~n的所有排列中,第k大的数。肯定不可能先用LeetCode Permutations把所有排列找出来,然后sort取第k个,肯定TLE,所以换思路。

假设给的例子中,原数组为s=”123″,要求第5大的数,即”312″。我们首先找出这个数的首位数字是什么。我们知道以某个数字固定开头的排列个数=(n-1)!=2!=2,即以1和2开头的排列数共有2*2=4个,而我们要求的是第5大的数,所以这个数开头必须是3=5/2+1=ceil( k / (n-1)! )=m。
确定了第一位之后,把3从原数组s中删掉,然后递归查找剩余数组s=”12″中第5-2*2=1=k-(m-1)*(n-1)!位的排列。显然就是最小的“12”了,然后拼起来为”312″。

完整代码如下:

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

本代码提交AC,用时0MS。

二刷。直接DFS的过程就是从小到大排序的过程,DFS到第k个排列的时候返回即可:

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

本代码提交AC,用时1356MS,太慢了,还是用之前的方法吧。

LeetCode Next Permutation

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


本题要求一个序列的下一个更大的序列,比如1,2,3 → 1,3,2,如果一个序列是最大的序列,如3,2,1,则返回其最小序列1,2,3。 算法从后往前扫描序列,如果从后往前看一直是上升的,如3,2,1,则说明这是最大的序列,直接将其逆序即可。 否则直到找到一个下降的转折点,比如4876543,找到48是下降的,这样我们就可以把4换成更大的数,但又不能太大,Next Permutation必须是紧跟在原序列后面的一个序列,所以我们从4的后面找比4大的最小的数,这里就是5。然后交换4和5,得到5876443,此时5后面仍然是有序的,而且是最大的,所以还要把5后面的序列逆序一下,得到5344678。 完整代码如下:

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());
    }
};

本代码提交AC,用时12MS。

二刷。时隔三年再刷此题,还是不会啊。需要注意的是为什么交换5和4之后,5后面的数依然是有序的呢,因为找到的是5是大于4的最小的数,所以4放到5的位置之后,4肯定小于它前面的数。我们可以用反证法证明4也会大于等于它后面的数,如果4小于它后面的数的话,则后面的数又小于5,那么5就不是大于4的最小的数,产生矛盾。

另外,还需要考虑到可能存在多个5的情况,此时应该把最后面的5和开头的4互换,否则互换后后面那部分的数就不是降序的了,所以j的循环是从后往前的。

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

这道题和之前的Permutations很像,只不过此时包含有重复元素。 在Permutations里,我使用了一个一个往里加的思路,今天我使用另一个思路。
为了得到一个序列的所有排列,可以采用每个元素和当前第一个元素交换的思路。比如要得到1,2,3的所有排列,第一轮每个元素和第一个元素交换得到

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

此时每个元素都有打头的序列出现,再对每一个序列,除掉第一个元素,循环交换。比如对于1,2,3,此时把2,3作为一个新的序列,和此时的第一个元素2交换,得到序列:

  • 2,3
  • 3,2

然后再和之前的元素1拼接起来,得到以1开头的所有排列:

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

同理能得到以2,3打头的所有排列。用这种思路也可以求解Permutations这个题。当遇到有重复元素时,可以先对数组排序,在交换的时候,如果当前元素和前一个元素相同,则不再交换。最后再用set去重,完整代码如下:

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());
    }
};

本代码提交AC,用时48ms。速度比较慢,应该还有其他更优的算法。


新方法,使用和Permutations类似的dfs递归方法,只不过在递归的时候,判断一下,保证这次递归的元素不能和上一次相同。比如数组是[1,1,2],第一次从第一个1开始递归,那么在这层循环中,下一次递归就不能从第二个1开始了,但是下一层循环中还是应该可以选第二个1的。理解起来有点绕,假设我们把求[1,1,2]的全排列想象成从[1,1,2]中无放回的取数字,依先后顺序扔到3个格子中,每个格子只能放一个数字。那么第一次拿的数可能是1,1,2,则第一次拿第一个1和第二个1产生的全排列应该是完全一样的。

代码如下。第11行:用last记录本次循环中上一个递归的数,那么本次循环不再对同一个数递归了。因为先对数组排序了,所以所有相同的数字都会聚到一起,而且这样产生的全排列是按大小顺序排列的。

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

本代码提交AC,用时23MS,比前一种方法快,省掉了set去重。

二刷。上述解法固然正确,但是用INT_MAX来初始化last还是有风险的,万一数组中有INT_MAX呢。
更好的方法其实是,不用last记录上一次递归的值,二刷直接在内层if判断,如果i!=0且nums[i]==nums[i-1],说明这个数和上一个数相同,但是此时还不能continue,万一有[1,1,2]这种情况,在外层递归第二个1时,第一个1在上一轮是已经恢复了visited[0]=0的,所以这里可以加上一个visited[i-1]==0。完整代码如下:

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

本代码提交AC,用时23MS。

三刷。判断条件还可以再简单些,用pre记录上次递归的下标即可。

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

本代码提交AC,用时24MS。

LeetCode Permutations

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

这道题要产生一个数组的所有排列情况,可以使用递归的思想,一个一个元素往里加,直到达到个数要求。使用flag来标记是否添加过。和我最近在做的蛋白质搜索引擎中加修饰的情况很类似,实现如下:

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

本代码提交AC,用时21MS。

二刷。其实上述代码中不需要复制一个next数组的,代码如下:

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

本代码提交AC,用时9MS,击败79%。

还可以不需要visited和candidate数组,用交换的思路,代码如下:

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

本代码提交AC,用时16MS。