A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 黄小贝 高级黑马   /  2012-10-24 16:36  /  2066 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

饭后一道题,天天好心情~

题目:用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个里面选,以此类推



最后的小问题就是具体的过滤器怎么实现了~~




纵观全题~包含的知识点还是不少的,目测这道题对于学妹来说难度应该偏大了点,所以我决定改造成填空题给她做~


完整代码:
  1. package day8;

  2. import java.util.ArrayList;
  3. import java.util.Iterator;
  4. import java.util.List;


  5. /**
  6. * 题目如下:用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列, 如:512234、412345等,要求:"4"
  7. * 不能在第三位,"3"与"5"不能相连。
  8. *
  9. * @author yellowbaby
  10. *
  11. */
  12. public class Test {

  13.         /**
  14.          * @param args
  15.          */
  16.         public static void main(String[] args) {
  17.                                                        
  18.                 Integer[] figures = { 1, 2, 2, 3, 4, 5 };
  19.                
  20.                 List<NumFilter> filters = new ArrayList<NumFilter>();
  21.                 filters.add(new Test().new NumFilter1());
  22.                 filters.add(new Test().new NumFilter2());
  23.                
  24.                 Nums nums = new Nums(figures, filters);
  25.                                
  26.                 for(Iterator<Num> it = nums.getNumsSet().iterator();it.hasNext();){
  27.                         System.out.println(it.next());
  28.                 }
  29.                
  30.                 System.out.println(nums.getNumsSet().size());
  31.         }
  32.        
  33.         private class NumFilter1 implements NumFilter {

  34.                 @Override
  35.                 public boolean accpect(Num num) {
  36.                         if (num.get(3) != 4) {
  37.                                 return true;
  38.                         }
  39.                         return false;
  40.                 }
  41.         }

  42.         private class NumFilter2 implements NumFilter {

  43.                 @Override
  44.                 public boolean accpect(Num num) {

  45.                         int index1 = num.getIndex(3);
  46.                         int index2 = num.getIndex(5);

  47.                         if (index1 == -1 || index2 == -1) {
  48.                                 return true;
  49.                         }

  50.                         if (Math.abs(index1 - index2) != 1) {
  51.                                 return true;
  52.                         }

  53.                         return false;
  54.                 }
  55.         }
  56. }
复制代码
  1. package day8;

  2. import java.util.Arrays;

  3. public class Num {

  4.         private int[] nums;

  5.         public Num(int[] nums) {
  6.                 this.nums = nums;
  7.         }

  8.         public int[] getNums() {
  9.                 return nums;
  10.         }

  11.         /**
  12.          * 如果包含数字num,找出该数字在数组中的位置
  13.          */
  14.         public int getIndex(int num) {
  15.                 for (int i = 0; i < nums.length; i++) {
  16.                         if (nums[i] == num) {
  17.                                 return i;
  18.                         }
  19.                 }
  20.                 return -1;
  21.         }

  22.         /**
  23.          * 得到第 index 个数字
  24.          */
  25.         public int get(int index) {
  26.                 return this.nums[index - 1];
  27.         }

  28.         @Override
  29.         public int hashCode() {
  30.                 int result = 17;
  31.                 result = 37 * result + intsHashCode(nums);
  32.                 return result;
  33.         }

  34.         private int intsHashCode(int[] aints) {
  35.                 int result = 17;
  36.                 for (int i : aints) {
  37.                         result = 37 * result + i;
  38.                 }
  39.                 return result;
  40.         }

  41.         @Override
  42.         public boolean equals(Object obj) {

  43.                 if (obj == this) {
  44.                         return true;
  45.                 }

  46.                 if (obj instanceof Num) {
  47.                         Num num = (Num) obj;
  48.                         return Arrays.equals(num.getNums(), this.getNums());
  49.                 }       
  50.                 return true;
  51.         }

  52.         @Override
  53.         public String toString() {
  54.                 return Arrays.toString(nums);
  55.         }
  56.        
  57.        

  58. }
复制代码
  1. package day8;

  2. import java.util.ArrayList;
  3. import java.util.Arrays;
  4. import java.util.HashSet;
  5. import java.util.List;
  6. import java.util.Set;

  7. public class Nums {

  8.         private Integer[] figures;// 整数数组
  9.         private List<NumFilter> filters;// 过滤器链
  10.        
  11.         private Set<Num> numSet = new HashSet<Num>();//存放整数的Set

  12.         public Nums(Integer[] figures, List<NumFilter> filters) {
  13.                 this.figures = figures;
  14.                 this.filters = filters;

  15.                 List<Integer> list = Arrays.asList(figures);
  16.                 int num[] = new int[list.size()];

  17.                 getAllNums(list, num);
  18.                
  19.         }

  20.         /**
  21.          * 遍历过滤器链,看当前Num是否符合要求
  22.          */
  23.         private boolean check(Num num) {
  24.                 for (NumFilter filter : filters) {
  25.                         if (!filter.accpect(num)) {
  26.                                 return false;
  27.                         }
  28.                 }
  29.                 return true;
  30.         }

  31.         /**
  32.          * 递归调用找出所有符合要求的数
  33.          */
  34.         private void getAllNums(List<Integer> list, int[] num) {

  35.                 for (int i = 0; i < list.size(); i++) {
  36.                        
  37.                         num[list.size() - 1] = list.get(i);
  38.                         List<Integer> listCopy = new ArrayList<Integer>(list);
  39.                         listCopy.remove(i);

  40.                         if (listCopy.size() == 0) {
  41.                                
  42.                                 int[] numCopy = num.clone();                       
  43.                                 Num temp = new Num(numCopy);
  44.                                
  45.                                 if(check(temp)){
  46.                                         numSet.add(temp);
  47.                                 }               
  48.                                
  49.                         } else {
  50.                                
  51.                                 getAllNums(listCopy, num);
  52.                                
  53.                         }
  54.                 }
  55.         }

  56.         public void setFilters(List<NumFilter> filters) {
  57.                 this.filters = filters;
  58.         }

  59.         public void setFigures(Integer[] figures) {
  60.                 this.figures = figures;
  61.         }

  62.         public Integer[] getFigures() {
  63.                 return figures;
  64.         }

  65.         public List<NumFilter> getFilters() {
  66.                 return filters;
  67.         }
  68.        
  69.         public Set<Num> getNumsSet() {
  70.                 return numSet;
  71.         }

  72.        

  73. }
复制代码

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马