饭后一道题,天天好心情~
题目:用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列,如:512234、412345等,要求:"4"不能在第三位,"3"与"5"不能相连。
这道题包含的东西比较多~
首先,作为面向对象的程序猿,下意识的就会用对象来存储数字~
然后有了对象后我们就很自然的想到用 HashSet来存储所有的Num,因为我们需要排除重复的数字组合,所以,重写hashCode和equal方法
然后就是稍微困难的分析过程,为了解析方便,我建了一个Nums的类来负责处理
这里可能就要问了,NumFilter是什么东西~
每当我们得到一种Num的组合,就要检查这种组合是否符合要求
然后问题的关键就变成了如何得到所有可能的组合,想想高中的排列组合题~总共的组合数为 6*5*4*3*2*1,也就是 6个里面选一个,然后从剩下的5个里面选,以此类推
最后的小问题就是具体的过滤器怎么实现了~~
纵观全题~包含的知识点还是不少的,目测这道题对于学妹来说难度应该偏大了点,所以我决定改造成填空题给她做~
完整代码:- package day8;
- import java.util.ArrayList;
- import java.util.Iterator;
- import java.util.List;
- /**
- * 题目如下:用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列, 如:512234、412345等,要求:"4"
- * 不能在第三位,"3"与"5"不能相连。
- *
- * @author yellowbaby
- *
- */
- public class Test {
- /**
- * @param args
- */
- public static void main(String[] args) {
-
- Integer[] figures = { 1, 2, 2, 3, 4, 5 };
-
- List<NumFilter> filters = new ArrayList<NumFilter>();
- filters.add(new Test().new NumFilter1());
- filters.add(new Test().new NumFilter2());
-
- Nums nums = new Nums(figures, filters);
-
- for(Iterator<Num> it = nums.getNumsSet().iterator();it.hasNext();){
- System.out.println(it.next());
- }
-
- System.out.println(nums.getNumsSet().size());
- }
-
- private class NumFilter1 implements NumFilter {
- @Override
- public boolean accpect(Num num) {
- if (num.get(3) != 4) {
- return true;
- }
- return false;
- }
- }
- private class NumFilter2 implements NumFilter {
- @Override
- public boolean accpect(Num num) {
- int index1 = num.getIndex(3);
- int index2 = num.getIndex(5);
- if (index1 == -1 || index2 == -1) {
- return true;
- }
- if (Math.abs(index1 - index2) != 1) {
- return true;
- }
- return false;
- }
- }
- }
复制代码- package day8;
- import java.util.Arrays;
- public class Num {
- private int[] nums;
- public Num(int[] nums) {
- this.nums = nums;
- }
- public int[] getNums() {
- return nums;
- }
- /**
- * 如果包含数字num,找出该数字在数组中的位置
- */
- public int getIndex(int num) {
- for (int i = 0; i < nums.length; i++) {
- if (nums[i] == num) {
- return i;
- }
- }
- return -1;
- }
- /**
- * 得到第 index 个数字
- */
- public int get(int index) {
- return this.nums[index - 1];
- }
- @Override
- public int hashCode() {
- int result = 17;
- result = 37 * result + intsHashCode(nums);
- return result;
- }
- private int intsHashCode(int[] aints) {
- int result = 17;
- for (int i : aints) {
- result = 37 * result + i;
- }
- return result;
- }
- @Override
- public boolean equals(Object obj) {
- if (obj == this) {
- return true;
- }
- if (obj instanceof Num) {
- Num num = (Num) obj;
- return Arrays.equals(num.getNums(), this.getNums());
- }
- return true;
- }
- @Override
- public String toString() {
- return Arrays.toString(nums);
- }
-
-
- }
复制代码- package day8;
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.HashSet;
- import java.util.List;
- import java.util.Set;
- public class Nums {
- private Integer[] figures;// 整数数组
- private List<NumFilter> filters;// 过滤器链
-
- private Set<Num> numSet = new HashSet<Num>();//存放整数的Set
- public Nums(Integer[] figures, List<NumFilter> filters) {
- this.figures = figures;
- this.filters = filters;
- List<Integer> list = Arrays.asList(figures);
- int num[] = new int[list.size()];
- getAllNums(list, num);
-
- }
- /**
- * 遍历过滤器链,看当前Num是否符合要求
- */
- private boolean check(Num num) {
- for (NumFilter filter : filters) {
- if (!filter.accpect(num)) {
- return false;
- }
- }
- return true;
- }
- /**
- * 递归调用找出所有符合要求的数
- */
- private void getAllNums(List<Integer> list, int[] num) {
- for (int i = 0; i < list.size(); i++) {
-
- num[list.size() - 1] = list.get(i);
- List<Integer> listCopy = new ArrayList<Integer>(list);
- listCopy.remove(i);
- if (listCopy.size() == 0) {
-
- int[] numCopy = num.clone();
- Num temp = new Num(numCopy);
-
- if(check(temp)){
- numSet.add(temp);
- }
-
- } else {
-
- getAllNums(listCopy, num);
-
- }
- }
- }
- public void setFilters(List<NumFilter> filters) {
- this.filters = filters;
- }
- public void setFigures(Integer[] figures) {
- this.figures = figures;
- }
- public Integer[] getFigures() {
- return figures;
- }
- public List<NumFilter> getFilters() {
- return filters;
- }
-
- public Set<Num> getNumsSet() {
- return numSet;
- }
-
- }
复制代码 |