组合算法
常用的排列数组合数、子集的个数问题
leetcode 46题 [1,2,3] 所有的全排列问题
这是一个不需要去重的全排列问题.
拿[1,2,3]举例子, 1,2,3 接着是 1,3,2 2,1,3 2,3,1 可以找出规律 2,3交换生成3,2....
每次交换 然后接着下一次进行
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result=new ArrayList<>();
permuteReclusive(result,nums, 0, nums.length-1);
return result;
}
public void permuteReclusive(List<List<Integer>> result, int[] nums, int start, int end){
if(start==end+1){ // 长度
List<Integer> param=new ArrayList<Integer>();
for(int i=0;i<nums.length;i++){
param.add(nums[i]);
}
result.add(param);
return ;
}
for(int i=start;i<=end;i++){
if(i!=start){ // 交换
int tmp=nums[i];
nums[i]=nums[start];
nums[start]=tmp;
}
// 接着下一波的数据
permuteReclusive(result, nums, start+1,end);
if(i!=start){ // 交换回来
int tmp=nums[i];
nums[i]=nums[start];
nums[start]=tmp;
}
}
}
}对于leetcode 31 本质上也是求全排列中的某个排列下的下一个排列
主要思路是先从尾部到头部找出nums[i]>nums[i-1]的第一次出现的位置设为d=i-1;
接着从尾部到头部找出大于nums[d]的第一个元素出现的位置, m. 把nums[m]和nums[d]交换, 然后再把d+1开始的数据逆序. 我们可以通过这种方法实现全排列问题.代码如下
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
int[] copy = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
copy[i] = nums[i];
}
boolean istart = true;
while (istart || isSame(copy, nums)) {
istart = false;
List<Integer> param = new ArrayList<Integer>();
for (int i = 0; i < nums.length; i++) {
param.add(nums[i]);
}
result.add(param);
nextPermute(nums);
}
return result;
}
public boolean isSame(int[] copy, int[] nums) {
for (int i = 0; i < nums.length; i++) {
if (copy[i] != nums[i]) return true;
}
return false;
}
public void nextPermute(int[] nums) {
int d = -1; // 表示分割点
int m = -1; // 表示大于点
int len = nums.length;
for (int i = len - 2; i >= 0; i--) {
if (nums[i + 1] > nums[i]) {
d = i;
break;
}
}
if (d == -1) {
for (int i = 0; i < (len - 1) / 2; i++) {
int tmp = nums[i];
nums[i] = nums[len - 1 - i];
nums[len - 1 - i] = tmp;
}
return;
}
for (int i = len - 1; i >= 0; i--) {
if (nums[i] > nums[d]) {
m = i;
break;
}
}
int tmp = nums[d];
nums[d] = nums[m];
nums[m] = tmp;
// 逆序
int dest = (len - 1 + d + 1) / 2;
for (int i = d + 1; i <= dest; i++) {
tmp = nums[i];
nums[i] = nums[len - 1 - i + d + 1];
nums[len - 1 - i + d + 1] = tmp;
}
}
}实现全排列代码
class Solution {
public List<List<integer>> permute(int[] nums) {</integer>
List<List<Integer>> result = new ArrayList<>();
int[] copy = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
copy[i] = nums[i];
}
boolean istart = true;
while (istart || isSame(copy, nums)) {
istart = false;
List<Integer> param = new ArrayList<Integer>();
for (int i = 0; i < nums.length; i++) {
param.add(nums[i]);
}
result.add(param);
nextPermute(nums);
}
return result;
}
public boolean isSame(int[] copy, int[] nums) {
for (int i = 0; i < nums.length; i++) {
if (copy[i] != nums[i]) return true;
}
return false;
}
public void nextPermute(int[] nums) {
int d = -1; // 表示分割点
int m = -1; // 表示大于点
int len = nums.length;
for (int i = len - 2; i >= 0; i--) {
if (nums[i + 1] > nums[i]) {
d = i;
break;
}
}
if (d == -1) {
for (int i = 0; i <=(len - 1) / 2; i++) {
int tmp = nums[i];
nums[i] = nums[len - 1 - i];
nums[len - 1 - i] = tmp;
}
return;
}
for (int i = len - 1; i >= 0; i--) {
if (nums[i] > nums[d]) {
m = i;
break;
}
}
int tmp = nums[d];
nums[d] = nums[m];
nums[m] = tmp;
// 逆序
int dest = (len - 1 + d + 1) / 2;
for (int i = d + 1; i <=dest; i++) {
tmp = nums[i];
nums[i] = nums[len - 1 - i + d + 1];
nums[len - 1 - i + d + 1] = tmp;
}
}}
leetcode 47 Permutations II 去重之后的全排列个数
这道题有两种解法
- 在46题基础上加一个判断是否已经存在相同元素， 存在就没必要再次交换。
public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> result=new ArrayList<>();
permuteReclusiveUnique(result, nums, 0);
return result;
}
public void permuteReclusiveUnique(List<List<Integer>>result, int[]nums, int start){
if(start==nums.length){
// 数据保存
List<Integer>params=new ArrayList<>();
for(int i=0;i<nums.length;i++){
params.add(nums[i]);
}
result.add(params);
}
for(int i=start;i<nums.length;i++){
if(!isOk(nums, start, i)){
continue;
}
if(i!=start){
int tmpt=nums[i];
nums[i]=nums[start];
nums[start]=tmpt;
}
permuteReclusiveUnique(result, nums, start+1);
if(i!=start){
int tmpt=nums[i];
nums[i]=nums[start];
nums[start]=tmpt;
}
}
}
public boolean isOk(int[]nums, int start, int end){
for(int i=start;i<end;i++){
if(nums[i]==nums[end]) return false;
}
return true;
}在31题基础上直接获取所有可能情况， 直到等于原来的情况.
public List<List<integer>> permuteUnique(int[] nums) {</integer>List<List<Integer>> result = new ArrayList<>(); int[] copy = new int[nums.length]; for (int i = 0; i < nums.length; i++) { copy[i] = nums[i]; } boolean istart = true; while (istart || isSame(copy, nums)) { istart = false; List<Integer> param = new ArrayList<Integer>(); for (int i = 0; i < nums.length; i++) { param.add(nums[i]); } result.add(param); nextPermute(nums); } return result;}
public boolean isSame(int[] copy, int[] nums) {
for (int i = 0; i < nums.length; i++) {
if (copy[i] != nums[i]) return true;
}
return false;
}
public void nextPermute(int[] nums) {
int d = -1; // 表示分割点
int m = -1; // 表示大于点
int len = nums.length;
for (int i = len - 2; i >= 0; i--) {
if (nums[i + 1] > nums[i]) {
d = i;
break;
}
}
if (d == -1) {
for (int i = 0; i <=(len - 1) / 2; i++) {
int tmp = nums[i];
nums[i] = nums[len - 1 - i];
nums[len - 1 - i] = tmp;
}
return;
}
for (int i = len - 1; i >= 0; i--) {
if (nums[i] > nums[d]) {
m = i;
break;
}
}
int tmp = nums[d];
nums[d] = nums[m];
nums[m] = tmp;
// 逆序
int dest = (len - 1 + d + 1) / 2;
for (int i = d + 1; i <=dest; i++) {
tmp = nums[i];
nums[i] = nums[len - 1 - i + d + 1];
nums[len - 1 - i + d + 1] = tmp;
}
}leetcode 78题 求所有子集
思路 本质上是每个元素取或者不取两种情况
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> results=new ArrayList<>();
List<Integer> param=new ArrayList<>();
ReclusiveTheSubSet(results, param, nums, 0);
return results;
}
public void ReclusiveTheSubSet(List<List<Integer>> results,List<Integer> param, int[] nums, int start){
results.add(new ArrayList<>(param));
for(int i=start;i<nums.length;i++){
param.add(nums[i]); // 取这个元素
ReclusiveTheSubSet(results, param, nums, i+1);
param.remove(param.size()-1); // 不取这个元素
}
}
}leetcode 90 subset去重
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>>results=new ArrayList<>();
// 必须先排序
Arrays.sort(nums);
List<Integer> param=new ArrayList<>();
ReclusiveTheSubset(results, param, nums, 0);
return results;
}
public void ReclusiveTheSubset(List<List<Integer>> results, List<Integer>param, int[]nums, int start){
results.add(new ArrayList<>(param));
for(int i=start;i<nums.length;i++){
// 去重操作
if(isOk(nums, start, i)){continue;}
param.add(nums[i]);
ReclusiveTheSubset(results, param, nums, i+1);
param.remove(param.size()-1);
}
}
public boolean isOk(int[]nums, int start, int end){
for(int i=start;i<end;i++){
if(nums[i]==nums[end]) return true;
}
return false;
}
}
