文档章节

IT公司100题-6-根据上排给出十个数,在其下排填出对应的十个数

关西大汉弹琵琶
 关西大汉弹琵琶
发布于 2015/11/02 22:16
字数 595
阅读 680
收藏 13

问题描述:

给你10分钟时间,根据上排给出十个数,在其下排填出对应的十个数
要求下排每个数都是先前上排那十个数在下排出现的次数。
上排的十个数如下:
【0,1,2,3,4,5,6,7,8,9】

举一个例子,
数值: 0,1,2,3,4,5,6,7,8,9
分配: 6,2,1,0,0,0,1,0,0,0
0在下排出现了6次,1在下排出现了2次,
2在下排出现了1次,3在下排出现了0次….
以此类推..  

问题分析:

它的原型跟八皇后有点类似,都是用回溯递归的方法去一次一次尝试,直到找出正确解。

具体的想法是:不断的去从下排数组中捉取在上排数组中对应位置中出现的个数,如果个数不对就更新下排数组中对应的值,只到找到正确值。(下排数组先初始为任意值)

如:

上排数组A:0,1,2,3,4,5,6,7,8,9
下排数组B:0,1,2,3,4,5,6,7,8,9
从上牌数组Index = 0开始,A[0] = 0,0在下排数组中的个数为1,那么下排数组B此时就要更新为:1,1,2,3,4,5,6,7,8,9

Index = 1, A[1] = 1, 1在下排数组中的个数为2,那么下排数组B此时就要更新为:1,2,2,3,4,5,6,7,8,9,从此不断的往下进行,只要找不到正确值就一直往下进行,如果Index >= 数组长度时,那么重新恢复Index = 0再往下进行测试直到找出正确解。

但这好像只能解决如上所述的情况,即连续的N个数。

代码实现:

package oschina.IT100;
/**
 * @project: oschina
 * @filename: IT6.java
 * @version: 0.10
 * @author: JM Han
 * @date: 21:46 2015/11/2
 * @comment: 数值: 0,1,2,3,4,5,6,7,8,9
 *           分配: 6,2,1,0,0,0,1,0,0,0
 * @result:
 */

import java.util.ArrayList;
import static tool.util.*;

public class IT6 {
   public static final int NUM = 10;
   ArrayList<Integer> lsta = new ArrayList<Integer>();
   ArrayList<Integer> lstb = new ArrayList<Integer>();
   boolean success;
   public IT6(){
      success = false;
      for (int i = 0; i < NUM; i++){
         lsta.add(i);
         lstb.add(i);
      }
   }
   ArrayList getB(){
      while(success != true){
         setNextB();
      }
      return lstb;
   }
   void setNextB(){
      boolean flag =true;
      for (int i=0; i < NUM; i++){
         int f = getFrequency(i);
         if(lstb.get(i) != f){
            lstb.set(i, f);
            flag = false;
         }
      }
      success = flag;
   }
   int getFrequency(int value){
      int count = 0;
      for(int i = 0; i < NUM; i++){
         if(lstb.get(i) == value)
            count++;
      }
      return count;
   }
   public static void main(String[] args) {
      IT6 test = new IT6();
      ArrayList<Integer> res = test.getB();
      printGenericIterator(test.lsta.iterator());
      System.out.println();
      printGenericIterator(test.lstb.iterator());

   }



}

代码输出:

0 1 2 3 4 5 6 7 8 9 
6 2 1 0 0 0 1 0 0 0


© 著作权归作者所有

关西大汉弹琵琶
粉丝 8
博文 41
码字总数 14221
作品 0
浦东
程序员
私信 提问
【4】

/===================================================== 第6题(数组) 腾讯面试题: 给你10分钟时间,根据上排给出十个数,在其下排填出对应的十个数 要求下排每个数都是先前上排那十个数...

SibylY
2016/07/31
1
0
面试题_腾讯根据上排给出十个数

给你10分钟时间,根据上排给出十个数,在其下排填出对应的十个数 要求下排每个数都是先前上排那十个数在下排出现的次数。 上排的十个数如下: 【0,1,2,3,4,5,6,7,8,9】 举一个例子,...

梦想游戏人
2015/07/01
56
0
次数统计-CountMap

题目: 根据上排给出十个数,在其下排填出对应的十个数,要求下排每个数都是先前上排那十个数在下排出现的次数。 上排的十个数如下: 【0,1,2,3,4,5,6,7,8,9】 举一个例子 数值: 0...

刀狂剑痴
2015/08/27
25
0
各大公司(Google,Microsoft,Baidu, Microsoft Research Asia etc.)实习生面试题总汇

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / 6 14 / / 4 8 12 1...

云栖希望。
2017/12/04
0
0
挑战数据结构与算法面试题——统计上排数在下排出现的次数

题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 分析: 本题应该是一个确定的问题,即上排的是个数是题目中给定的十个数。 其基本的解题过程为: ...

google19890102
2018/03/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

采坑指南——k8s域名解析coredns问题排查过程

正文 前几天,在ucloud上搭建的k8s集群(搭建教程后续会发出)。今天发现域名解析不了。 组件版本:k8s 1.15.0,coredns:1.3.1 过程是这样的: 首先用以下yaml文件创建了一个nginx服务 apiV...

码农实战
2分钟前
1
0
【2019年8月版本】OCP 071认证考试最新版本的考试原题-第6题

choose three Which three statements are true about indexes and their administration in an Orade database? A) An INVISIBLE index is not maintained when Data Manipulation Language......

oschina_5359
4分钟前
1
0
阿里巴巴开源 Dragonwell JDK 最新版本 8.1.1-GA 发布

导读:新版本主要有三大变化:同步了 OpenJDK 上游社区 jdk8u222-ga 的最新更新;带来了正式的 feature:G1ElasticHeap;发布了用户期待的 Windows 实验版本 Experimental Windows version。...

阿里巴巴云原生
9分钟前
1
0
教你玩转Linux—磁盘管理

Linux磁盘管理好坏直接关系到整个系统的性能问题,Linux磁盘管理常用三个命令为df、du和fdisk。 df df命令参数功能:检查文件系统的磁盘空间占用情况。可以利用该命令来获取硬盘被占用了多少...

xiangyunyan
12分钟前
3
0
js 让textarea的高度自适应父元素的高度

textarea按照普通元素设置height是没有作用的,可以这么来设置, 下面给上一段项目代码 JS代码: $.fn.extend({ txtaAutoHeight: function () { return this.each(function () {...

文文1
13分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部