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 (ie, for n = 3): 1. `"123"` 2. `"132"` 3. `"213"` 4. `"231"` 5. `"312"` 6. `"321"` Given n and k, return …

Given a collection of numbers that might contain duplicates, return all possible unique permutations.__ 思路：和leet code 46 类似，最后用set去个重即可。。 /* *********************************************** Author :111qqz Created Time :2017年04月13日 星期四 15时00分48秒 File Name :47.cpp ************************************************ */ class …

Given a collection of distinct numbers, return all possible permutations. 思路：调用n-1次 leetcode 31 解题报告 中提到的算法即可。。。 /* *********************************************** Author :111qqz Created Time :2017年04月13日 星期四 14时49分34秒 File Name :46.cpp ************************************************ */ class Solution { public: void …

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, do not allocate extra memory. Here are some …

hdu 2049 题目链接 题意：n个妹子和n个汉子对应。。然后让每个汉子取选一个妹子，不能重复，问恰好有m个汉子选错妹子的可能的方案数。 思路：从n个中选n-m个，然后做剩余m个错排即可。 答案就是c[n][n-m]*d[m] c[]为组合数公式，d为错排公式。 然而wa到死。。。 因为我用了double....有毒。。。 double表示整数也是会丢失精度的！！！ double表示整数也是会丢失精度的！！！ double表示整数也是会丢失精度的！！！ double表示整数也是会丢失精度的！！！ double表示整数也是会丢失精度的！！！ 我自杀去了，世界再见（x /* …

hdu2048 题目链接 题意:n个人不放回的从一个有n个每个人对应id的卡片的盒子取一张卡片，取的正好和自己的对应就算中奖。求所有人都没有中奖的概率。 思路：错排。。。 复习了一下错排公式。。。d[n] = (n-1)*(d[n-1]+d[n-2]) （d[1]=0,d[2]=1） 然后求概率的时候。。惊讶得发现概率稳定在了36.79%（1/e）附近。。。 这是因为。。。错排还有一个公式：D(n) = n! [(-1)^2/2! + … + (-1)^(n-1)/(n-1)! + (-1)^n/n!]. 求概率每次把n!除掉了。。剩下的。。其实就是e的泰勒展开，当x=-1时的值。 因为当n越大时。。这个概率越接近1/e 这道题 …

勤奋的Farmer John想要建造一个四面的栅栏来关住牛们。他有一块长为n（4<=n<=2500）的木板，他想把这块本板切成4块。这四块小木板可以是任何一个长度只要Farmer John能够把它们围成一个合理的四边形。他能够切出多少种不同的合理方案。注意： *只要大木板的切割点不同就当成是不同的方案（像全排列那样），不要担心另外的特殊情况，go ahead。 *栅栏的面积要大于0. *输出保证答案在longint范围内。 *整块木板都要用完。 思路：排列组合。。减法原则。长度为n的木板，有n-1个切点，那么n-1个切点切三刀的方案数就是C(n-1,3) ，但是这里面有不能构成四边形的。 构成四边形的条件是：任意三边之和 …

题目链接 题意；给出一个字符串，只由小写字母组成，可以任意排列，但是不能减少字符，问最多能得到多少个回文串，答案9+7 思路：排列组合题。 首先考虑无解的情况。统计出每个字母出现的次数，当字符串长度为奇数而且出现次数为奇数的字母的个数多于1个时无解，或者当字符串长度为偶数，出现次数为奇数的字母的个数多于0个时无解。 接下来，由于是回文串，只需要考虑len/2的情况，另一半是一一对应的。 其实就是一共有len/2的元素，其中有一些重复的，然后全排列。 多重元素的排列问题。 答案为(len/2)! % （cnt[1]!）% (cnt[2]!)...即可 哦要先把cnt降序排一下，只考虑cnt[i]>1的元素，然后因为是要考虑一半长 …