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

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 梦缠绕的时候 于 2018-11-1 09:51 编辑

1.        题目要求
对Cache进行程序模拟操作,Cache最多容纳100个Item,进行新增和淘汰的处理逻辑。
1. Item:Cache item为单向链表结构,每秒钟所有Item的age加1。
2. 新增:每秒钟在队列的随机位置新增1~3个Item。
3. 淘汰:每秒钟至少淘汰一个item。
4. 淘汰条件是:
1) 要么item的age大于10。        
2) 要么Cache已满又无{age>10}的item,则淘汰第一个item。
2.        程序需求:
Cache单向链表中已有50个Item,写简单程序模拟新增和淘汰的过程,至少需模拟200个item的新增或淘汰。
Cache的Item基本结构,参考如下:
Item {         
int  id;                 // itemid
int  age;             // 表示过期时间
item next;             // 单向链表的下一个item
}
3.        举例:
一个单向链表,从第10秒到第11秒,数据链表上有三个变化:
a) 因Age>10、淘汰ID为8 Item
b) 随机位置新增ID为14 Item
c) 所有item age增加了1岁

4.        具体实现:代码清单1
  • package cn.itsource.entity;
  • /**
  • * 该类是单向链表结构
  • * @author lv
  • */
  • public class Item {
  •         private int  id;                 // item的id
  •         private int  age ;
  •         private Item next;             // 单向链表的下一个item
  •         public Item() {
  •                 super();
  •         }
  •         public Item(int id) {
  •                 this.id = id;
  •                 age++;
  •         }
  •         public int getId() {
  •                 return id;
  •         }
  •         public void setId(int id) {
  •                 this.id = id;
  •         }
  •         public int getAge() {
  •                 return age;
  •         }
  •         public void setAge(int age) {
  •                 this.age = age;
  •         }
  •         public void addAge(){
  •                 this.age++;
  •         }
  •         public Item getNext() {
  •                 return next;
  •         }
  •         public void setNext(Item next) {
  •                 this.next = next;
  •         }
  •         @Override
  •         public String toString() {
  •                 return id + "";
  •         }
  • }

[color=rgb(255, 178, 1) !important]复制代码

代码清单2
  • package cn.itsource.algorithm;
  • import java.util.NoSuchElementException;
  • import entity.Item;
  • /**
  • * Cache模拟
  • * @author lv
  • *
  • */
  • public class Cache<E> {
  •         private Item item;
  •         private int elementCount;                //元素个数
  •         private static int maxId = 1 ;        //管理每个Item的id
  •         public Cache(){
  •                 super();
  •         }
  •         /**
  •          * 获取当前链表的长度
  •          * @return
  •          */
  •         public synchronized int size(){
  •                 return elementCount;
  •         }
  •         /**
  •          *         检验Cache 是否为空
  •          * @return
  •          */
  •         public synchronized boolean isEmpty() {
  •                 return elementCount == 0;
  •          }
  •         /**
  •          * 插入节点到指定位置
  •          * @param index
  •          * @param item
  •          */
  •         public synchronized void insertItemByIndex(int index,Item item) {
  •                 if(item == null)
  •                         throw new IllegalArgumentException(item+":null值");
  •                 int size = this.size();
  •                 if(index <0) {
  •                         throw new ArrayIndexOutOfBoundsException(index+"下标越界");
  •                 } else if(index == 0){
  •                         if(size == 0)
  •                                 this.item = item;
  •                         else{
  •                                 Item oldItem = getItemByIndex(index);
  •                                 item.setNext(oldItem);
  •                                 this.item = item;
  •                         }
  •                         elementCount ++;
  •                         idController();
  •                 } else {
  •                         if(index < size){
  •                                 Item oldItem = getItemByIndex(index);
  •                                 Item oldItemParent = getItemByIndex(index-1);
  •                                 item.setNext(oldItem);
  •                                 oldItemParent.setNext(item);
  •                                 elementCount ++;
  •                                 idController();
  •                         } else if(index == size) {
  •                                 add(item);
  •                         } else {
  •                                 throw new ArrayIndexOutOfBoundsException(index+"下标越界");
  •                         }
  •                 }
  •         }
  •         /**
  •          *         队尾追加Item元素
  •          * @param item
  •          * @return
  •          */
  •         public synchronized boolean add(Item item){
  •                 if(size() == 0) {
  •                         this.item = item;
  •                 }else {
  •                         getItemByIndex(this.size()-1).setNext(item);
  •                 }
  •                 elementCount ++;
  •                 idController();
  •                 return true;
  •         }
  •         /**
  •          *  移除指定位置元素
  •          * @param index
  •          */
  •         public synchronized void removeItemByIndex(int index){
  •                 if(size() <= 0){
  •                         System.out.println("[ ]  : 单向链表为空");
  •                         return;
  •                 }
  •                 if(index <0) {
  •                         throw new ArrayIndexOutOfBoundsException(index+"下标越界");
  •                 }else if(index == 0) {
  •                         this.item = this.item.getNext();
  •                         elementCount --;
  •                 } else {
  •                         if(index < size()-1){
  •                                 Item oldItemNext = getItemByIndex(index+1);
  •                                 Item oldItemParent = getItemByIndex(index-1);
  •                                 oldItemParent.setNext(oldItemNext);
  •                                 elementCount --;
  •                         }else if(index == size()-1){
  •                                 Item oldItemParent = getItemByIndex(index-1);
  •                                 oldItemParent.setNext(null);
  •                                 elementCount --;
  •                         }else{
  •                                 throw new ArrayIndexOutOfBoundsException(index+"下标越界");
  •                         }
  •                 }
  •         }
  •         /**
  •          *         当item的age为maxAge是获取其下标并按下标删除
  •          * @param maxAge
  •          */
  •         public synchronized void removeItemByAge(int maxAge){
  •                 if(size() <= 0){
  •                         System.out.println("[ ]  : 单向链表为空");
  •                         return;
  •                 } else {
  •                         Item item = this.item;
  •                         int index = 0;
  •                         while(item != null){
  •                                 int age = item.getAge();
  •                                 if(age==maxAge){
  • //                                        System.out.println("age :  "+age+"  index  :  "+index);
  •                                         removeItemByIndex(index);
  •                                 } else {
  •                                         ++index;
  •                                 }
  •                                 if(item.getNext() != null){
  •                                         item = item.getNext();
  •                                 } else {
  •                                         break;
  •                                 }
  •                         }
  •                         return;
  •                 }
  •         }
  •         /**
  •          * 获取指定下标的Item元素
  •          * @param index
  •          * @return
  •          */
  •         public synchronized Item getItemByIndex(int index){
  •                 if(size() <0) {
  •                         throw new NoSuchElementException("Cache是空");
  •                 }
  •                 int count = 0;
  •                 if(index < 0) {
  •                         throw new ArrayIndexOutOfBoundsException(index+"下标越界");
  •                 } else if(index == 0) {
  •                         return this.item;
  •                 } else {
  •                         if(index > this.size()-1){
  • //                                System.out.println( "size    :"+this.size()+"     index    :"+index);
  •                                 throw new ArrayIndexOutOfBoundsException("[ "+index+" ]下标越界");
  •                         }
  •                         Item next = this.item.getNext();
  •                         while(next != null){
  •                                 count++;
  •                                 if(count == index){
  •                                         return next;
  •                                 }
  •                                 next = next.getNext();
  •                         }
  •                 }
  •                 return null;
  •         }
  •         /**
  •          *  打印Cache 中Item的 id 和 age
  •          * @throws Exception
  •          */
  •         public void printCache() throws Exception{
  •                 if(item == null){
  •                         System.out.println("[ ]");
  •                         return;
  •                 }
  •                 Item item = this.item;
  •                 while(item.getNext() != null){
  •                         System.out.println("itemID : "+item.getId()+"    itemAge : "+item.getAge());
  •                         item = item.getNext();
  •                 }
  •                 System.out.println("itemID : "+item.getId()+"    itemAge : "+item.getAge());
  •         }
  •         /**
  •          * 临时用来模拟50个Item
  •          * 创建 指定个数元素的 单向链表
  •          * @param size 指定个数元素
  •          */
  •         public void createItem(int size){
  •                 Item it = null;
  •                 for(int i = 1;i <= size; i++){
  •                         it = new Item(maxId);
  •                         if(i%10 == 0) {
  •                                 it.setAge(10);
  •                         } else {
  •                                 it.setAge(i%10);
  •                         }
  •                         add(it);
  • //                        System.out.println("id  : "+it.getId()+"   age :  "+it.getAge());
  •                 }
  •         }
  •         /**
  •          *         创建Item
  •          * @return
  •          */
  •         public synchronized Item createItem(){
  •                 Item item = new Item(maxId);
  •                 return item;
  •         }
  •         /**
  •          * 清空Cache
  •          */
  •         public synchronized void clear(){
  •                 elementCount = 0;
  •                 item = null;
  •         }
  •         /**
  •          *         id控制器 当id的值为 Integer.MAX_VALUE 时重新从 1 开始生成
  •          */
  •         public void idController(){
  •                 if(maxId == Integer.MAX_VALUE){
  •                         maxId = 1;
  •                         maxId++;
  •                 } else {
  •                         maxId++;
  • }
  •                 return;
  •         }
  •         /**
  •          * age控制器 ,所以Item的age+1
  •          */
  •         public synchronized void ageController(){
  •                 Item it = this.item;
  •                 while(it != null){
  •                         it.addAge();
  •                         if(it.getNext() != null) {
  •                                 it = it.getNext();
  •                         } else {
  •                                 break;
  •                         }
  •                 }
  •         }
  •         /**
  •          *         获取最大id值
  •          * @return
  •          */
  •         public static int getMaxId() {
  •                 return maxId;
  •         }
  • }

[color=rgb(255, 178, 1) !important]复制代码

代码清单3
  • package cn.itsource.algorithm;
  • import java.util.Random;
  • import entity.Item;
  • public class CacheTest {
  •         /**
  •          * @param args
  •          */
  •         public static void main(String[] args) {
  •                 Cache<Item> cache = new Cache<Item>();
  •                 try {
  •                         cache.createItem(50);
  •                         cache.clear();
  •                         cache.printCache();
  •                         System.out.println("********************");
  •                         cache.createItem(50);
  •                         cache.printCache();
  •                         // 可以用工具类Thread.sleep(1000)+循环200次控制
  •                         Random ran = new Random();
  •                         for(int i=0;i<200;i++){
  •                                 Thread.sleep(1000);
  •                                 cacheModel(cache, ran);
  •                         }
  •                 } catch (Exception e) {
  •                         e.printStackTrace();
  •                 }
  •         }
  •         /**
  •          *  模仿内存操作
  •          *  每秒钟要做的工作如下:
  •          *  1、先添加,添加之前,先获取cache的size,判断应该最多添加几个item,防止
  •          *           出现cache的size>100时,内存溢出的错误逻辑情况
  •          *  2、每个Item的age+1
  •          *  3、获取Item中age>10的元素删除,若无则再获取cache的size,判断应该最多删除几
  •          *           个item,防止cache的size=0时,还能删除的错误逻辑情况。
  •          *  注:(具体顺序也可以是 3、2、1或3、1、2)
  •          * @param cache
  •          * @param ran
  •          */
  •         public static void cacheModel(Cache<Item> cache,Random ran){
  •                 //由题意已知 cache.size()是>=50,故这里就不做合法性检验了
  •                 //        1、
  •                 int index = randomNumberGenerator(ran,cache.size());        //最大是99
  •                 System.out.println("=======cache.size===="+cache.size()+"===========");
  •                 Item item =  cache.createItem();
  •                 int pcs;
  •                 switch(index){
  •                         case 97:
  •                                 pcs = randomNumberGenerator(ran,2);        //最多新增Item2个
  •                                 randomNumberController(pcs, pcs, item, cache, ran);
  •                                 break;
  •                         case 98:
  •                                 pcs = randomNumberGenerator(ran,1);        //最多新增Item1个
  •                                 randomNumberController(pcs, pcs, item, cache, ran);
  •                                 break;
  •                         default:
  •                                 pcs = randomNumberGenerator(ran,3);        //新增Item3个
  •                                 randomNumberController(pcs, pcs, item, cache, ran);
  •                                 break;
  •                 }
  •                 try {
  •                         cache.printCache();
  •                         System.out.println("____________________________________________________");
  •                         // 2、age+1
  •                         cache.ageController();
  •                         cache.printCache();
  •                         // 3、删除满足条件的元素(两种情况)
  •                         cache.removeItemByAge(11);           // 情况一:age==11时,删除
  •                         cache.printCache();
  •                         if(cache.size()>=100){
  •                                 cache.removeItemByIndex(0); //情况二:cache.size()==100时,删除队首元素
  •                                 cache.printCache();
  •                         }
  •                 } catch (Exception e) {
  •                         e.printStackTrace();
  •                 }
  •         }
  •         /**
  •          * @param pcs                随机生成次数
  •          * @param index                cache下标
  •          * @param item                Item  实例
  •          * @param cache                Cache实例
  •          * @param ran                Random实例
  •          */
  •         public static void randomNumberController(int pcs,int index,Item item,Cache<Item> cache,Random ran){
  •                 System.out.println("……………最大3…………index : "+index + "  pcs : "+pcs);
  •                 if(pcs==1){
  •                         cache.insertItemByIndex(index, item);
  •                         System.out.println("………1…… cache.size : "+cache.size()+"…index…"+index);
  •                 }else if(pcs==2){
  •                         cache.insertItemByIndex(index, item);
  •                         System.out.println("……2-1… cache.size : "+cache.size()+"……index…"+index);
  •                         index = randomNumberGenerator(ran,cache.size());        //最大是99
  •                         item =  cache.createItem();
  •                         cache.insertItemByIndex(index, item);
  •                         System.out.println("……2-2…… cache.size : "+cache.size()+"…index…"+index);
  •                 }else{
  •                         cache.insertItemByIndex(index, item);
  •                         System.out.println("…3-1…… cache.size : "+cache.size()+"…index……"+index);
  •                         index = randomNumberGenerator(ran,cache.size());        //最大是99
  •                         item =  cache.createItem();
  •                         cache.insertItemByIndex(index, item);
  •                         System.out.println("…3-2…… cache.size : "+cache.size()+"…index……"+index);
  •                         index = randomNumberGenerator(ran,cache.size());        //最大是99
  •                         item =  cache.createItem();
  •                         cache.insertItemByIndex(index, item);
  •                         System.out.println("…3-3…… cache.size : "+cache.size()+"…index……"+index);
  •                 }
  •         }
  •         /**
  • * 随机数字生成器:用于随机生成新增多少个Item(1~3) 和 生成队列的随机位置(注意:应先
  • * 获取队列的size)
  •           * 每秒钟在队列的随机位置新增1~3个Item
  •           * @param        n 该参数是 随机生成数字的最大值
  •           * @param        ran
  •           * @return
  •           */
  •         public synchronized static int randomNumberGenerator(Random ran,int n){
  •                 if(ran == null) {
  •                         ran = new Random();
  •                 }
  •                 return ran.nextInt(n)+1;
  •         }
  • }



1 个回复

倒序浏览
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马