新浦京网投站网止,澳门新浦京26999com

    欢迎访问澳门新浦京26999com~

  1. 加入收藏
  2. 设为主页
  3. 学校简介
澳门新浦京26999com

澳门新浦京26999com

  • 北大青鸟徐东校区
  • 北大青鸟光谷学院
  • 北大青鸟宏鹏IT学院
  • 荆州青鸟之家
  • 襄阳青鸟之家

15902769092

三分钟了解北大青鸟

×
  • 初中生学什么
  • 高中生学什么
  • 大学生学什么
  • 打工返乡人出路
  • 退伍军人出路
  • 女生学什么好
  • 男生学什么好

Java程序语言通用组合算法的实现

责任编辑:澳门新浦京26999com来源:澳门新浦京26999comJava技术教程发布时间:2013-01-25 15:49
导读:Java实现通用组合算法,存在一个类似{31311133,33113330}这样的集合,经过8取5组合,其他位置用非字母数字字符替代,比如使用*号,得到类似{3***1133,***13330,... ...}这样的集合。

Java实现通用组合算法,存在一个类似{31311133,33113330}这样的集合,经过8取5组合,其他位置用非字母数字字符替代,比如使用*号,得到类似{3***1133,***13330,... ...}这样的集合;

现在有这样的需求:

存在一个类似{31311133,33113330}这样的集合,经过8取5组合,其他位置用非字母数字字符替代,比如使用*号,得到类似{3***1133,***13330,... ...}这样的集合;

还要求对于{3***1133,***13330}这样的集合,再次经过5取3组合,其他位置用非字母数字字符替代,比如使用*号,得到类似{*****133,*****330,3***1*3*,... ...}这样的集合。

对于这样的要求,实现的思路如下:

先,主要思想是基于信息编码原理,通过扫描字符串,将10组合变为01组合。

其次,对于每个数字字符串,设置一个单线程,在单线程类中设置一个List用来存放待处理数字字符串(可能含有*号,或者不含有)中每个数字的(而非*号)索引位置值;

再次,设置BitSet来标志每个位置是否被*号替换得到新的组合字符串。

后,在扫描原始待处理数字字符串的过程中,根据设置的字符列表List中索引,来操作BitSet,对于每一个BitSet得到一个新的组合。

使用Java语言实现如下:

package org.shirdrn;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;

public class CommonSplitter {
private int starCount;
private boolean duplicate;
private Collection filteredContainer;
public Collection getFilteredContainer() {
return filteredContainer;
}

public CommonSplitter(Collection container, int starCount, boolean duplicate) {
this.duplicate = duplicate;
this.starCount = starCount;
if(this.duplicate) { // 根据指定是否去重的选择,选择创建容器
filteredContainer = Collections.synchronizedSet(new HashSet());
}
else {
filteredContainer = Collections.synchronizedList(new ArrayList());
}
Iterator it = container.iterator();
while(it.hasNext()) {
new Thread(new SplitterThread(it.next().trim())).start();
}
try {
Thread.sleep(50);
} catch (InterruptedException e) {
e.printStackTrace();
}
}

class SplitterThread implements Runnable {
private char[] charArray;
private int len; // 数字字符的个数
List occupyIndexList = new ArrayList(); // 统计字符串中没有带*的位置的索引
private List container = new ArrayList();
private BitSet startBitSet; // 比特集合起始状态
private BitSet endBitSet; // 比特集合终止状态,用来控制循环
public SplitterThread(String string) {
this.charArray = string.toCharArray();
this.len = string.replace("*", "").length();
this.startBitSet = new BitSet(len);
this.endBitSet = new BitSet(len);
// 初始化startBitSet,左侧占满*符号
int count = 0; //
for (int i=0; i
if(charArray[i] != '*') {
if(count < starCount) {
this.startBitSet.set(i, true);
count++;
}
occupyIndexList.add(i);
}
}
// 初始化endBit,右侧占满*符号
count =0;
for (int i = string.length()-1; i > 0; i--) {
if(charArray[i] != '*') {
if(count < starCount) {
this.endBitSet.set(i, true);
count++;
}
ccupyIndexList.add(i);
}
}
// 根据起始startBitSet,构造带*的组合字符串并加入容器
char[] charArrayClone = this.charArray.clone();
for (int i=0; i
if (this.startBitSet.get(i)) {
charArrayClone[i] = '*';
}
}
this.container.add(new String(charArrayClone));
}
public void run() {
this.split();
synchronized(filteredContainer) {
filteredContainer.addAll(this.container);
}}
public void split() {
while(!this.startBitSet.equals(this.endBitSet)) {
int zeroCount = 0; // 统计遇到10后,左边0的个数
int oneCount = 0; // 统计遇到10后,左边1的个数
int pos = 0; // 记录当前遇到10的索引位置
char[] charArrayClone = this.charArray.clone();
// 遍历startBitSet来确定10出现的位置
for (int i=0; i
if (!this.startBitSet.get(this.occupyIndexList.get(i))) {
zeroCount++;
}
if (this.startBitSet.get(this.occupyIndexList.get(i))
&& !this.startBitSet.get(this.occupyIndexList.get(i+1))) {
pos = i;
oneCount = i - zeroCount;
// 将10变为01
this.startBitSet.set(this.occupyIndexList.get(i), false);
this.startBitSet.set(this.occupyIndexList.get(i+1), true);
break;
}
}
// 将遇到10后,左侧的1部移动到左侧
int count = Math.min(zeroCount, oneCount);
int startIndex = this.occupyIndexList.get(0);
int endIndex = 0;
if(pos>1 && count>0) {
pos--;
endIndex = this.occupyIndexList.get(pos);
for (int i=0; i
this.startBitSet.set(startIndex, true);
this.startBitSet.set(endIndex, false);
startIndex = this.occupyIndexList.get(i+1);
pos--;
if(pos>0) {
endIndex = this.occupyIndexList.get(pos);
}
}}
// 将遇到1的位置用*替换
for (int i=0; i
if (this.startBitSet.get(this.occupyIndexList.get(i))) {
charArrayClone[this.occupyIndexList.get(i)] = '*';
}
}
this.container.add(new String(charArrayClone));
}
}}}

测试用例如下所示:

package org.shirdrn;
import java.util.ArrayList;
import java.util.Collection;
import junit.framework.TestCase;
import org.shirdrn.util.GoodTools;
public class TestCommonSplitter extends TestCase {
private CommonSplitter splitter;
public void setSplitter(Collection container, int starCount, boolean duplicate) {
this.splitter = new CommonSplitter(container, starCount, duplicate);
}
public void testSplliter() {
Collection container = new ArrayList();
container.add("1*10**");
int starCount = 2;
boolean duplicate = true;
this.setSplitter(container, starCount, duplicate);
System.out.println(this.splitter.getFilteredContainer());
}
public void testSplliter3() {
Collection container = new ArrayList();
container.add("1*10*1300*");
int starCount = 3;
boolean duplicate = true;
this.setSplitter(container, starCount, duplicate);
System.out.println(this.splitter.getFilteredContainer());
assertEquals(35, this.splitter.getFilteredContainer().size());
}
public void testNoStar() {
Collection container = new ArrayList();
container.add("3110330");
int starCount = 3;
boolean duplicate = true;
this.setSplitter(container, starCount, duplicate);
System.out.println(this.splitter.getFilteredContainer());
assertEquals(35, this.splitter.getFilteredContainer().size());
}
public void testSplitter_8_310() {
// 8 场:310
String multiSeq = "310,310,310,310,310,310,310,310";
Collection container = GoodTools.getNSingleList(multiSeq);
assertEquals(6561, container.size());
int starCount = 4;
boolean duplicate = false;
this.setSplitter(container, starCount, duplicate);
assertEquals(459270, this.splitter.getFilteredContainer().size());
}
}
上述测试耗时大约2s左右。

上述算法实现主要是针对两种条件进行实现的,即:

个是完数字字符串 ——> 带有*号的组合数字字符串;

第二个带有*号的组合数字字符串 ——> 在该基础上继续组合得到带有*号的组合数字字符串。

如果使用上述算法实现处理个条件,由于使用了列表List来记录索引,使执行速度略微低一点,比之于前面实现的不使用List列表来处理。

本文标题:Java程序语言通用组合算法的实现,责任编辑:澳门新浦京26999com,来源:武汉宏鹏,于2013年01月25日15时49分发布于澳门新浦京26999com。武汉澳门新浦京26999com专注计算机电脑IT编程培训。学校专注java培训,ui设计培训,web前端培训,python培训,大数据培训等,北大青鸟学校累计为企业培养和输送IT专业人才85万。

专业老师指导

专业老师指导

赵老师

从事IT教育培训十年有余,致力于帮助广大学子找到适合自己的专业。

培训咨询客服

培训咨询客服

陈老师

IT培训专业客服,用自己的真诚解决了无数学子的困惑。

本文地址:
文章标题:

热门课程

More+
  • Python+大数据学习

    Python+大数据学习

  • Java_9天快速掌握Java基础

    Java_9天快速掌握Java基础

  • PHP+H5_做全栈工程师

    PHP+H5_做全栈工程师

  • Web前端工程师_百日0基础入门

    Web前端工程师_百日0基础入门

  • 网络工程师BNENIT6.0

    网络工程师BNENIT6.0

  • UI课程_给你+1机会

    UI课程_给你+1机会

  • 学动漫_变二次元大神!

    学动漫_变二次元大神!

  • 大数据_9天快速入门基础

    大数据_9天快速入门基础

  • 启蒙星3.0_给你不一样的”薪“开始

    启蒙星3.0_给你不一样的”薪“开始

  • 学数字艺术,用兴趣描绘“钱途”

    学数字艺术,用兴趣描绘“钱途”

点我咨询
×
在线咨询更多问题

如您有任何疑问
在线咨询随时为您解答或拨打咨询热线:15902769092

×
  • 姓 名*
  • 手 机*
  • QQ号/微信号
  • 所报学科 *
  • 其他备注
  • 温馨提示:请保持手机畅通,咨询老师将为您提供专属的一对一报名服务。