现在有这样的需求:
存在一个类似{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; /** * 通用组合拆分类(基于单线程) * * 可以完成两种功能: * * 第一,可以将完全数字串拆分成为含有*号的字符串。 * 例如:输入集合{31311133,33113330},Splitter类会遍历该集合,对每个字符串,创建一个SplitterThread * 线程来处理,如果是2取1组合,即starCount=8-2=6,经过线程处理得到类似******33,*****1*3等结果 * * 第二,根据从带有*号的字符串经过拆分过滤后得到的字符串集合,对其中每一个字符串进行组合 * 例如:输入集合5取1组合字符串集合{3***1133,***113330} * * CommonSplitter类会遍历该集合,对每个带有*号的字符串,创建一个SplitterThread * 线程来处理,如果是2串1组合,即starCount=8-3-2=3,经过线程处理得到类似******33,*****1*3等结果 * * @author 时延军 * */ public class CommonSplitter { private int starCount; private boolean duplicate; private Collection public Collection return filteredContainer; } /** * 构造一个Spilitter实例 * * @param container 输入的待处理字符串集合 * @param starCount 如果对于长度为N的数字字符串,进行M组合(即N取M),则starCount=N-M * @param duplicate 是否去重 */ public CommonSplitter(Collection this.duplicate = duplicate; this.starCount = starCount; if(this.duplicate) { // 根据指定是否去重的选择,选择创建容器 filteredContainer = Collections.synchronizedSet(new HashSet } else { filteredContainer = Collections.synchronizedList(new ArrayList } Iterator while(it.hasNext()) { new Thread(new SplitterThread(it.next().trim())).start(); } try { Thread.sleep(50); } catch (InterruptedException e) { e.printStackTrace(); } }
/**
* 对一个指定的N场比赛的长度为N的单式投注字符串进行组合 * 输入单式投注注字符串string,例如31311133,组合得到类似******33,*****1*3,... ...结果的集合 * * @author 时延军 * */ class SplitterThread implements Runnable { private char[] charArray; private int len; // 数字字符的个数 List private List 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++; } occupyIndexList.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; } 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 this.splitter = new CommonSplitter(container, starCount, duplicate); } public void testSplliter() { Collection 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.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.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 assertEquals(6561, container.size()); int starCount = 4; boolean duplicate = false; this.setSplitter(container, starCount, duplicate); assertEquals(459270, this.splitter.getFilteredContainer().size()); } } 上述测试耗时大约2s左右。 上述算法实现主要是针对两种条件进行实现的,即: 第一个是完全数字字符串 ——> 带有*号的组合数字字符串; 第二个带有*号的组合数字字符串 ——> 在该基础上继续组合得到带有*号的组合数字字符串。 如果使用上述算法实现处理第一个条件,由于使用了列表List来记录索引,使执行速度略微低一点,比之于前面实现的不使用List列表来处理。 |
|