前段时间朋友面试碰到过这样题,要在指定的短时间内实现起来有一定困难,网上也看到类似这样算法题,今天跟朋友同事一起讨论一下,现在把我的一些方法与想法实现代码贴出来,参考参考...先做个记录了
/**
*created by zxb
*date 2008-10-29 - 上午12:48:10
*zxb 开源测试项目 test算法研究
*to do TODO
*JDK5.0
**/
package com.test;
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
/**
* 题如下:指定500个人,编号从1-500,现在从1编号开始点名,当点到序号为7时,
* 让该人出列,后续接着继续开始点名从1开始,再次点到为7时,让该人出列,
* 一直点名直到最后只有一个为止,当点名到最后时,从新开始循环点名,
* 剩下的最后一个人的编号是多少?(一面试题,还是有点挑战性,抛砖引玉了)
* 解题思路:构造LinkedList<Integer>进行批量删除等的操作
* 循环设置出列点位置值为0,然后删除该点数据,循环至小于数据组长度小于7时,
* 重新调整开始点名数据组,始终把第一位点名的数字<人>放在实际所因位置也是第一位的位置
* 按照索引位置增量删除一个 因为每删除一个数据组少掉一个数
*
*
* 451
*@author zxb
*/
public class FiveHundred {
private LinkedList<Integer> l=null;
private List<Integer> list=null;
private static final int MAX=7;//指定点名的出列的编号数 固定范围内进行循环删除指定的索引位置
private int count=0; //多少个轮回次数
private static final int SUM=500;//待删除指定索引位置的数据组(1--500)
private static int size=0;//队列的动态个数
public FiveHundred(){
list=new ArrayList<Integer>();
for (int i = 1; i <= SUM; i++) {
list.add(Integer.valueOf(i));
}
l=new LinkedList<Integer>(list);
int m= l.size()%MAX;
if(m==0){
count=l.size()/MAX;
}else{
count=l.size()/MAX+1;
}
}
public void change(){
List<Integer> l_2=new ArrayList<Integer>();
int j=1;//叠加 根据后面补充
List<Integer> l_3=null;
//过滤掉为0的元素
int s1=l.size();
for (int i = 0; i < s1; i++) {
if(l.contains(new Integer(0))){
l.remove(l.indexOf(new Integer("0")));
}
}
//点名出列的临时设置为0 并且设置点名之后队伍列的数据组
int s2=l.size();
for (int i = 0; i < s2; i++) {
if(i==MAX*j-1 && j<=count){//
l.set(MAX*j-1, new Integer("0"));
j++;
}else{
l_2.add(l.get(i));
}
}
//截取数据从最后一个0开始往后 list数据
int lastIndexZero=l.lastIndexOf(new Integer("0"));
int size=l.size();
if(lastIndexZero<size-1){
l_3=l.subList(lastIndexZero+1, size);
}
if(l_2!=null && l_3!=null)
l=reverseList(l_2,l_3);
}
//反调过来进行 重新排序
public LinkedList<Integer> reverseList(Collection<Integer> c1,Collection<Integer> c2){
LinkedList<Integer> l=new LinkedList<Integer>();
c1.removeAll(c2);
l.addAll(c2);
l.addAll(c1);
return l;
}
//处理特殊的情况,当剩下的个数小于指定出列的索引位置时 这里即 小于7时
@SuppressWarnings("unchecked")
public void specialList(){
System.out.println(l);
int size=l.size();
List l1=new ArrayList<Integer>();
List l2=new ArrayList();
int count=0;
while(size!=1){
if((MAX-1) % size==0){
l.remove((MAX-1) % size);
}else{
//后补叠加替换
l.remove((MAX-1) % size);
l1=l.subList((MAX-1) % size, l.size());
LinkedList<Integer> l3=new LinkedList<Integer>();
l3=(LinkedList)l.clone();
l2=(l3.subList(0, (MAX-1) % size));
count=l1.size();
//使用删除Collection的删除方法 容易引起java.util.ConcurrentModificationException
//remove(),clear(); iterator.remove()
for (int i = 0; i < count; i++) {
l.set(i, (Integer) l1.get(i));
}
int s1=l2.size();
for (int i = 0; i < s1; i++) {
l.set(count+i, (Integer) l2.get(i));
}
}
size--;
System.out.println(l);
}/**/
System.out.println("获取到最后一个数字==="+l.get(0));
}
//程序启动测试
public static void main(String[] args) {
FiveHundred fh=new FiveHundred();
long lo1=System.currentTimeMillis();
size=fh.l.size();
do{
fh.change();
size--;
}while(size>1);
fh.specialList();
long lo2=System.currentTimeMillis();
System.out.println("计算花费时间==== "+(lo2-lo1)+" 毫秒");
}
}
分享到:
相关推荐
数据库面试题索引sql优化数据库面试题索引sql优化数据库面试题索引sql优化数据库面试题索引sql优化数据库面试题索引sql优化数据库面试题索引sql优化数据库面试题索引sql优化数据库面试题索引sql优化数据库面试题索引...
面试题包含了不同技术层面的面试问题,同时也能对一些没有面试开发经验的小白给予不可估量的包装, 让你的薪水绝对翻倍, 本人亲试有效.Java面试题84集、java面试专属及面试必问课程,所有的面试题有视屏讲解, 解答方案....
JAVA面试题MySQL索引原理及索引优化校招面试找工作笔试 目录: 基本概念 MySQL索引结构的分类 Hash索引、B+树索引、全文索引、RTree索引。 B+树索引 B+树介绍,为什么选择B+树,非聚集索引 聚集索引 第一点、第二点...
BAT面试深入理解Mysql索引底层数据结构与算法_1
BAT面试_深入理解Mysql索引底层数据结构与算法_4
大厂面试题第一季-阿里篇-001-P7程序员面试这样解题数据库索引-1.mp4 大厂面试题第一季-阿里篇-001-P7程序员面试这样解题数据库索引-2.mp4 大厂面试题第一季-阿里篇-001-P7程序员面试这样解题数据库索引-3.mp4 大厂...
这几道题带你了解索引的几个重要知识点 1. 什么是最左前缀原则? 以下回答全部是基于MySQL的InnoDB引擎 例如对于下面这一张表 如果我们按照 name 字段来建立索引的话,采用B+树的结构,大概的索引结构如下 如果...
诸葛_BAT面试_深入理解Mysql索引底层数据结构与算法_3
数据库:涉及常用的索引、索引底层、常用的锁,如悲观锁、乐观锁、行锁、排它锁等具体实现、常用的数据库优化、分库分表、MVCC等 JVM:涉及常用的内存泄漏、内存溢出、MAT、jstack的分析案例 Linux:涉及开发中常用...
基于拼音索引的中文模糊匹配算法,基于拼音索引的中文模糊匹配算法
2.数据库索引结构 3.公司用了哪些垃圾回收器 4.怎么查看gc日志5.缓存击穿、穿透、雪崩区别和解决方式6.分布式锁 9.分库分表有用过吗
mysql关于索引的面试题,适用于毕业找工作的人士。努力学习,加油!
都是一些常见的 mysql 面试题,包括数据库基础知识、索引、事务等方面 都是一些常见的 mysql 面试题,包括数据库基础知识、索引、事务等方面 都是一些常见的 mysql 面试题,包括数据库基础知识、索引、事务等方面 都...
面试题范围:MySQL的架构、数据类型、存储引擎、索引和优化、SQL查询、备份和恢复、MySQL事物处理、MySQL安全性以及MySQL监控。 MySQL面试题适合软件开发人员、Web程序员、数据库管理员以及其他有关数据库的相关职位...
mysql, 面试题, 数据库, 数据管理, 数据库管理, 数据库设计, sql, 数据查询, 数据库优化, 数据库安全, 数据库备份, 数据库恢复, 数据库性能, 数据库索引, 数据库事务, 数据库存储引擎, 数据库连接池, 数据库分库分表...
在面试过程中,常常会涉及到MySQL索引的相关问题,包括索引的原理、优化技巧以及索引失效的原因等。 首先,MySQL索引是一种数据结构,用于快速定位和访问数据库中的数据。它通过创建索引列和索引对象来实现,可以...
深入理解Mysql索引底层数据结构与算法.ppt
本套MySQL面试题,汇总了大量经典的MySQL程序员面试题以及答案,包含MySQL语言常见面试题、MySQL工程师高级面试题及一些大厂MySQL开发面试宝典,面试经验技巧等,应届生,实习生,企业工作者,都可参考学习!...
面对图数据管理中查询耗时高和空间占比大的难题,提出一种图数据二 级索引压缩算法——GComIdx。该算法利用有序的键值(Key-Value)结构将相关节点和边尽可能地以相邻的方式 存储,并为高效的属性查询和邻居查询分别...