java数组排列组合问题汇总

面试或笔试中，多次遇到以下4个关于排列组合的手撕算法，这里做个笔记，方法日后查阅：

1. 无重复元素的数组，求全排列；
2. 有重复元素的数组，求全排列；
3. 无重复元素的数组，求组合【子集】；
4. 有重复元素的数组，求组合；

以上四类题，可以用统一的模板实现，如下所示：

/*
 *【组合&&排列】
 *把一个数组里的数组合全部列出，比如1和2列出来为1,2,12,21.
 *这个题目可以扩展成四个：
 *1.无重复数字的数组，求组合
 *2.有重复数字的数组，求组合
 *3.无重复数字的数组，求全排列
 *4.有重复数字的数组，求全排列
 *【通用思路（递归）】：
 *定义一个函数：从候选集candicate中选取一个组合prefix
 *每次从候选集candicate中remove一个数，并加入前缀prefix，打印prefix；
 *再递归从新的candicate中remove下一个数，并加入prefix
 *【对于重复的控制】
 *采用hashset保存prefix，打印之前，判断hashset中是否包含当前生成的prefix，
 *没有则打印，并加入hashset；有则不打印
 *【组合--》排列】
 *只需在打印前加一个判断：若候选集candicate为空，表示遍历完一次，生成一个排列，可打印
 */

package xh.offer.practice;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

public class listAllGroup{
  public static void main(String[] args) {
    String [] array = {"1","2"};
    String [] repeate = {"1","2","1"};
    listAllGroup test = new listAllGroup();
    System.out.println("**********no repeate list*******");
    test.listAllNoRepeate(Arrays.asList(array),"");//初始化prefix = ""
    System.out.println("**********repeate list*******");
    HashSet<String> noRepeateSet = new HashSet<String>();
    test.listAllRepeate(Arrays.asList(repeate), "", noRepeateSet);
    System.out.println("**************no repeate premutation********************");
    test.premutationNoRepeate(Arrays.asList(array),"");
    System.out.println("*********************repeate premutation**********************");
    HashSet<String> repeateSet = new HashSet<String>();
    test.premutationRepeate(Arrays.asList(repeate),"", repeateSet);
  }
  //无重复的组合
  public void listAllNoRepeate(List<String> candicate,String prefix){
    if(prefix.length() != 0)
      System.out.println(prefix);//结果长度不为0,则打印输出该组合

    for(int i = 0;i < candicate.size();i++){
      //将list转换成linklist链表，方便操作
      List<String> tempList = new LinkedList<String>(candicate);
      //templist减少一个数字，并暂存templist中去除的数字
      String tempString = (String) tempList.remove(i);
      //递归
      listAllNoRepeate(tempList,prefix + tempString);
    }
  }

  //有重复的组合,加入hashset
  public void listAllRepeate(List<String> candicate,String prefix,HashSet<String> res){
    if(prefix.length() != 0 && !res.contains(prefix)){
      System.out.println(prefix);
      res.add(prefix);
    }

    for(int i = 0;i < candicate.size();i++){
      List<String> tempList = new LinkedList<String>(candicate);
      String tempString = tempList.remove(i);
      listAllRepeate(tempList, prefix+tempString, res);//递归
    }
  }

  //无重复的全排列，加入判断candicate.size() == 0
  public void premutationNoRepeate(List<String> candicate,String prefix){
    if(candicate.size() == 0){
      System.out.println(prefix);
    }

    for(int i = 0;i < candicate.size();i++){
      List<String> tempList = new LinkedList<String>(candicate);
      String tempString = tempList.remove(i);
      premutationNoRepeate(tempList,prefix+tempString);
    }
  }

  //有重复的全排列，加入hashset辅助判断输出
  public void premutationRepeate(List<String> candicate,String prefix,HashSet<String> res) {
    if(candicate.size() == 0 && !res.contains(prefix)){
      System.out.println(prefix);
      res.add(prefix);
    }

    for(int i = 0;i < candicate.size();i++){
      List<String> tempList = new LinkedList<String>(candicate);
      String tempString = tempList.remove(i);
      premutationRepeate(tempList, prefix+tempString, res);
    }
  }

  }

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

您可能感兴趣的文章:

  • 2018年java技术面试题整理
  • java中jvm逃逸问题分析
  • Java并发编程this逃逸问题总结
  • Java中的逃逸问题心得
  • Java编程一道多线程问题实例代码
  • java实现字符串排列组合问题
  • Java ArrayList扩容问题实例详解
  • Java面试题解析之判断以及防止SQL注入
  • java彩色瓷砖编程题分析
赞 (0)

相关推荐

  • Java编程一道多线程问题实例代码

    前面几篇博文基本上总结了一下java并发里的一些内容,这篇博文主要从一个问题入手,看看都能用到前面总结的哪些并发技术去解决. 题目描述: 模拟一个场景:处理16条日志记录,每条日志记录打印时间需要1秒,正常情况下如果将这16条记录去部打完需要16秒,现在为了提高效率,准备开启4个线程去打印,4秒钟打印完,实现这个demo. 先来分析一下这个题目,关于这16条日志记录,我们可以在主线程中产生出来,这没用什么难度,关键是开启4个线程去执行,现在有两种思路:一种是日志的产生和打印日志的线程在逻辑上分开

  • Java并发编程this逃逸问题总结

    this逃逸是指在构造函数返回之前其他线程就持有该对象的引用. 调用尚未构造完全的对象的方法可能引发令人疑惑的错误, 因此应该避免this逃逸的发生. this逃逸经常发生在构造函数中启动线程或注册监听器时, 如: public class ThisEscape { public ThisEscape() { new Thread(new EscapeRunnable()).start(); // ... } private class EscapeRunnable implements Run

  • java中jvm逃逸问题分析

    引言: 逃逸分析(Escape Analysis)是众多JVM技术中的一个使用不多的技术点,本文将通过一个实例来分析其使用场景. 概念 逃逸分析,是一种可以有效减少Java 程序中同步负载和内存堆分配压力的跨函数全局数据流分析算法.通过逃逸分析,Java Hotspot编译器能够分析出一个新的对象的引用的使用范围从而决定是否要将这个对象分配到堆上. 在计算机语言编译器优化原理中,逃逸分析是指分析指针动态范围的方法,它同编译器优化原理的指针分析和外形分析相关联.当变量(或者对象)在方法中分配后,其

  • Java面试题解析之判断以及防止SQL注入

    本文研究的主要是Java面试题中的一个比较常见的题目,判断及防止SQL注入的问题,具体介绍如下. SQL注入是目前黑客最常用的攻击手段,它的原理是利用数据库对特殊标识符的解析强行从页面向后台传入.改变SQL语句结构,达到扩展权限.创建高等级用户.强行修改用户资料等等操作. 那怎么判断是否被SQL注入了呢? 通过SQL注入的原理我们知道,判断SQL注入可以通过页面传入的数据,后台不应该相信从后台传入的任何数据特别是特殊整型参数和特殊字符参数! 防止SQL注入其实也很简单 1.检查变量数据类型和格式

  • Java中的逃逸问题心得

    大家一般认为new出来的对象都是被分配在堆上,但这并不是完全正确,通过对Java对象分配过程分析,我们发现对象除了可以被分配在堆上,还可以在栈或TLAB中分配空间.而栈上分配对象的技术基础是逃逸分析和标量替换,本文主要介绍下逃逸分析. 逃逸分析的定义 逃逸分析,是一种可以有效减少Java 程序中同步负载和内存堆分配压力的跨函数全局数据流分析算法. 通过逃逸分析,Java Hotspot编译器能够分析出一个新的对象的引用的使用范围从而决定是否要将这个对象分配到堆上. Java在Java SE 6u

  • java彩色瓷砖编程题分析

    牛牛喜欢彩色的东西,尤其是彩色的瓷砖.牛牛的房间内铺有L块正方形瓷砖.每块砖的颜色有四种可能:红.绿.蓝.黄.给定一个字符串S, 如果S的第i个字符是'R', 'G', 'B'或'Y',那么第i块瓷砖的颜色就分别是红.绿.蓝或者黄. 牛牛决定换掉一些瓷砖的颜色,使得相邻两块瓷砖的颜色均不相同.请帮牛牛计算他最少需要换掉的瓷砖数量. 输入描述: 输入包括一行,一个字符串S,字符串长度length(1 ≤ length ≤ 10),字符串中每个字符串都是'R', 'G', 'B'或者'Y'. 输出描

  • java实现字符串排列组合问题

    本文为大家介绍了java实现字符串排列组合问题,供大家参考,具体内容如下 import java.util.ArrayList; import java.util.Collections; /** * 输入一个字符串,按字典序打印出该字符串中字符的所有排列.例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac, * bca,cab和cba. * * @author pomay * */ public class Solution_stringarrange

  • 2018年java技术面试题整理

    1.servlet执行流程 客户端发出http请求,web服务器将请求转发到servlet容器,servlet容器解析url并根据web.xml找到相对应的servlet,并将request.response对象传递给找到的servlet,servlet根据request就可以知道是谁发出的请求,请求信息及其他信息,当servlet处理完业务逻辑后会将信息放入到response并响应到客户端. 2.springMVC的执行流程 springMVC是由dispatchservlet为核心的分层控制

  • Java ArrayList扩容问题实例详解

    本文研究的主要是Java ArrayList扩容问题实例详解的相关内容,具体介绍如下. 首先我们需要知道ArrayList里面的实质的其实是一个Object类型的数组,ArrayList的扩容问题其实就是这个Object类型的数组的扩容问题. transient Object[] elementData; 一.创建时,ArrayList的容量分配 创建一个ArrayList有三种情况 1.默认大小创建(默认为0) ArrayList al = new ArrayList(); 创建完成之后,al

  • java数组排列组合问题汇总

    面试或笔试中,多次遇到以下4个关于排列组合的手撕算法,这里做个笔记,方法日后查阅: 1. 无重复元素的数组,求全排列: 2. 有重复元素的数组,求全排列: 3. 无重复元素的数组,求组合[子集]: 4. 有重复元素的数组,求组合: 以上四类题,可以用统一的模板实现,如下所示: /* *[组合&&排列] *把一个数组里的数组合全部列出,比如1和2列出来为1,2,12,21. *这个题目可以扩展成四个: *1.无重复数字的数组,求组合 *2.有重复数字的数组,求组合 *3.无重复数字的数组,求

  • 如何用Java实现排列组合算法

    需求 我们的数据表有多个维度,任意多个维度组合后进行 group by 可能会产生一些"奇妙"的反应,由于不确定怎么组合,就需要将所有的组合都列出来进行尝试. 抽象一下就是从一个集合中取出任意元素,形成唯一的组合.如[a,b,c]可组合为[a].[b].[c].[ab].[bc].[ac].[abc]. 要求如下: 组合内的元素数大于 0 小于等于 数组大小: 组合内不能有重复元素,如 [aab] 是不符合要求的组合: 组合内元素的位置随意,即 [ab] 和 [ba] 视为同一种组合:

  • Java数组(Array)最全汇总(中篇）

    目录 前言 本章学习要点 Java二维数组详解 创建二维数组 初始化二维数组 例 1 例 2 获取全部元素 例 3 例 4 获取整行元素 例 5 获取整列元素 例 6 Java不规则数组 Java数组也是一种数据类型 Java中到底有没有多维数组(长篇神文)? 前言 本章是关于Java数组的最全汇总,本篇为汇总中篇,主要讲了二维数组和不规则的数组的相关内容. 数组是最常见的一种数据结构,它是相同类型的用一个标识符封装到一起的基本类型数据序列或者对象序列. 数组使用一个统一的数组名和不同的下标来唯

  • 高效的java版排列组合算法

    本文实例为大家分享了java排列组合算法的具体代码,供大家参考,具体内容如下 package BeanUtil; import java.util.ArrayList; import java.util.List; import com.work.core.exception.OurException; /** * 统计任三出现的最多的几率的组合 * * @author wangmingjie * @date 2009-1-1下午01:22:19 */ public class Copy_2_o

  • JS实现二维数组元素的排列组合运算简单示例

    JS实现二维数组元素的排列组合运算简单示例

    本文实例讲述了JS实现二维数组元素的排列组合运算.分享给大家供大家参考,具体如下: 用js实现二维数组里面的元素排列组合一个小demo: 源码: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3

  • Java获得一个数组的指定长度排列组合算法示例

    本文实例讲述了Java获得一个数组的指定长度排列组合算法.分享给大家供大家参考,具体如下: package demo; import java.util.Stack; /** * JAVA获得一个数组的指定长度的排列组合.<br> * * @author JAVA世纪网(java2000.net, laozizhu.com) */ public class TestSequenceAll { public static void main(String[] args) { TestSequen

  • Java实现多个数组间的排列组合

    Java多个数组之间的排列组合,具体内容如下 说明:有一批手机有各种颜色.各种尺寸.各种版本,然后要实现他们之间各种属性的组合. 定义各种属性 String[] color={"红色","白色","蓝色","金色"}; String[] size={"4.7寸","5.1寸","6.0寸"}; String[] version={"联通",&quo

  • Python2.7基于笛卡尔积算法实现N个数组的排列组合运算示例

    Python2.7基于笛卡尔积算法实现N个数组的排列组合运算示例

    本文实例讲述了Python2.7基于笛卡尔积算法实现N个数组的排列组合运算.分享给大家供大家参考,具体如下: 说明:本人前段时间遇到的求n个数组的所有排列组合的问题,发现笛卡尔积算法可以解决,但是网上搜索的只有Java版本的实现,于是自己试着用python实现,由于新手代码不太规范. 代码:本人封装了一个类Cartesian(笛卡尔),其中封装了变量和方法: 1.变量 datagroup : 表示n个list(python 中的list与其他编程中的数组定义类似)的集合,即一个二维数组 coun

  • 关于各种排列组合java算法实现方法

    一.利用二进制状态法求排列组合,此种方法比较容易懂,但是运行效率不高,小数据排列组合可以使用 复制代码 代码如下: import java.util.Arrays; //利用二进制算法进行全排列//count1:170187//count2:291656 public class test {    public static void main(String[] args) {        long start=System.currentTimeMillis();        count

  • Java排列组合字符串的方法

    例如 输入"abc",打印所有可能出现的组合情况,并且消除重复值. 所谓排列组合如下: 排列组合,字符串:abc bca acb abc cba bac cab 排列组合个数:6 实现代码(结合Java8 lambda表达式实现) import org.junit.Test; import java.util.ArrayList; import java.util.HashSet; import java.util.List; public class test2 { @Test pu

随机推荐