青海医院网站的建设，赤峰浩诚网站建设公司能提供哪些服务？

青海医院网站建设公司,赤峰浩诚网站建设公司,纪念馆网站建设方案,中国建设人才网信息网证书是假的吗一、手动改写堆#xff08;非常重要#xff09;#xff01;系统提供的堆无法做到的事情#xff1a;1#xff09;已经入堆的元素#xff0c;如果参与排序的指标方法变化#xff0c;系统提供的堆无法做到时间复杂度O(logN)调整#xff01;都是O(N)的调整#xff01;2非常重要系统提供的堆无法做到的事情1已经入堆的元素如果参与排序的指标方法变化系统提供的堆无法做到时间复杂度O(logN)调整都是O(N)的调整2系统提供的堆只能弹出堆顶做不到自由删除任何一个堆中的元素或者说无法在时间复杂度O(logN)内完成一定会高于O(logN)根本原因无反向索引表二、加强堆的核心点1建立反向索引表indexMap2建立比较器3核心在于各种结构相互配合非常容易出错三、构建加强堆演示package class07;import java.util.ArrayList; import java.util.Comparator; import java.util.HashMap; import java.util.List;/*** 手写一个加强堆比系统自带的优先队列多了更多高效的获取元素查询动作* 注意泛型T一定要是非基础类型有基础类型需求包一层*/ public class HeapGreaterTrainT {//保存堆元素的集合public ArrayListT heap;//保存堆元素对应的索引位置 元素索引public HashMapT, Integer indexMap;//堆大小public int heapSize;//比较器自定义的比较器 ?匹配类型是T的父类 包括T本身public Comparator? super T comp;public HeapGreaterTrain(Comparator? super T c) {heap new ArrayList();indexMap new HashMapT, Integer();heapSize 0;comp c;}//判断堆是否为空public boolean isEmpty() {return heapSize 0;}//判断堆大小public int size() {return heapSize;}//判断堆中是否包含某个元素public boolean contains(T obj) {return indexMap.containsKey(obj);}//查询堆顶元素public T peek() {return heap.get(0);}//入堆操作public void push(T obj) {//直接进集合最后反向索引表创建关系后面再接着insert向上排序heap.add(obj);indexMap.put(obj, heapSize);heapInsert(heapSize);}//堆向上交换操作默认是小根堆的排序private void heapInsert(int i) {//通过业务创建加强堆自定义的比较器来定义排序假设返回小于0执行交换操作while (comp.compare(heap.get(i), heap.get((i - 1) / 2)) 0) {swap(i, (i - 1) / 2);i (i - 1) / 2;}}//出堆操作public T pop(){//出堆顶然后与最后一个元素交换再将最后一个元素从集合与反向索引表删除T ans heap.get(0);swap(0,--heapSize);heap.remove(heapSize);indexMap.remove(ans);heapify(0);return ans;}//堆向下沉操作 默认小根堆public void heapify(int i) {int left i *2 1;while(left heapSize){int smallest left1 heapSize comp.compare(heap.get(left1),heap.get(left))0?left1:left;smallest comp.compare(heap.get(smallest),heap.get(i))0?smallest:i;if(smallest i) break;swap(smallest,i);i smallest;left i *21;}}//移除任意一个元素 将最后一个元素交换到该元素位置然后再从该位置进行堆的上下调整排序操作public void remove(T obj){//获取集合中最后一个元素T end heap.get(heapSize-1);//获取要删除元素的索引int index indexMap.get(obj);//分别删除索引表该元素记录与集合中最后一个元素该元素前面已经保存下来indexMap.remove(obj);heap.remove(--heapSize);//注意如果删除元素不是最后一个元素再将该元素添加到index位置并增加反向索引表记录if(obj ! end){heap.set(index,end);indexMap.put(end,index);//调整完就需要判断该元素是否需要上移或下移,其中只会执行一句resign(end);}}public void resign(T end) {heapInsert(indexMap.get(end));heapify(indexMap.get(end));}//返回堆上所有元素public ListT getAllElements(){return heap;}private void swap(int i, int j) {//交换集合中的元素T o1 heap.get(i);T o2 heap.get(j);heap.set(i, o2);heap.set(j, o1);//重新设定反向索引表indexMap.put(o1, j);indexMap.put(o2, i);} } 四、加强堆应用用户颁奖问题给定一个整型数组int[] arr和一个布尔类型数组boolean[] op两个数组一定等长假设长度为Narr[i]表示客户编号op[i]表示客户操作arr [ 3 , 3 , 1 , 2, 1, 2, 5…op [T , T, T, T, F, T, F…依次表示3用户购买了一件商品3用户购买了一件商品1用户购买了一件商品2用户购买了一件商品1用户退货了一件商品2用户购买了一件商品5用户退货了一件商品…一对arr[i]和op[i]就代表一个事件用户号为arr[i]op[i] T就代表这个用户购买了一件商品op[i] F就代表这个用户退货了一件商品现在你作为电商平台负责人你想在每一个事件到来的时候都给购买次数最多的前K名用户颁奖。所以每个事件发生后你都需要一个得奖名单得奖区。得奖系统的规则1如果某个用户购买商品数为0但是又发生了退货事件 则认为该事件无效得奖名单和上一个事件发生后一致例子中的5用户2某用户发生购买商品事件购买商品数1发生退货事件购买商品数-13每次都是最多K个用户得奖K也为传入的参数 如果根据全部规则得奖人数确实不够K个那就以不够的情况输出结果4得奖系统分为得奖区和候选区任何用户只要购买数0 一定在这两个区域中的一个5购买数最大的前K名用户进入得奖区 在最初时如果得奖区没有到达K个用户那么新来的用户直接进入得奖区6如果购买数不足以进入得奖区的用户进入候选区7如果候选区购买数最多的用户已经足以进入得奖区 该用户就会替换得奖区中购买数最少的用户大于才能替换 如果得奖区中购买数最少的用户有多个就替换最早进入得奖区的用户 如果候选区中购买数最多的用户有多个机会会给最早进入候选区的用户8候选区和得奖区是两套时间 因用户只会在其中一个区域所以只会有一个区域的时间另一个没有 从得奖区出来进入候选区的用户得奖区时间删除 进入候选区的时间就是当前事件的时间可以理解为arr[i]和op[i]中的i 从候选区出来进入得奖区的用户候选区时间删除 进入得奖区的时间就是当前事件的时间可以理解为arr[i]和op[i]中的i9如果某用户购买数0不管在哪个区域都离开区域时间删除 离开是指彻底离开哪个区域也不会找到该用户 如果下次该用户又发生购买行为产生0的购买数 会再次根据之前规则回到某个区域中进入区域的时间重记请遍历arr数组和op数组遍历每一步输出一个得奖名单publicListListInteger topK(int[] arr, boolean[] op, int k)package class07;import java.util.ArrayList; import java.util.Comparator; import java.util.HashMap; import java.util.List;public class Code02_EveryStepShowBoss {public static class Customer {public int id;public int buy;public int enterTime;public Customer(int v, int b, int o) {id v;buy b;enterTime 0;}}public static class CandidateComparator implements ComparatorCustomer {Overridepublic int compare(Customer o1, Customer o2) {return o1.buy ! o2.buy ? (o2.buy - o1.buy) : (o1.enterTime - o2.enterTime);}}public static class DaddyComparator implements ComparatorCustomer {Overridepublic int compare(Customer o1, Customer o2) {return o1.buy ! o2.buy ? (o1.buy - o2.buy) : (o1.enterTime - o2.enterTime);}}public static class WhosYourDaddy {private HashMapInteger, Customer customers;private HeapGreaterTrainCustomer candHeap;private HeapGreaterTrainCustomer daddyHeap;private final int daddyLimit;public WhosYourDaddy(int limit) {customers new HashMapInteger, Customer();candHeap new HeapGreaterTrain(new CandidateComparator());daddyHeap new HeapGreaterTrain(new DaddyComparator());daddyLimit limit;}// 当前处理i号事件arr[i] - id, buyOrRefundpublic void operate(int time, int id, boolean buyOrRefund) {if (!buyOrRefund !customers.containsKey(id)) {return;}if (!customers.containsKey(id)) {customers.put(id, new Customer(id, 0, 0));}Customer c customers.get(id);if (buyOrRefund) {c.buy;} else {c.buy--;}if (c.buy 0) {customers.remove(id);}if (!candHeap.contains(c) !daddyHeap.contains(c)) {if (daddyHeap.size() daddyLimit) {c.enterTime time;daddyHeap.push(c);} else {c.enterTime time;candHeap.push(c);}} else if (candHeap.contains(c)) {if (c.buy 0) {candHeap.remove(c);} else {candHeap.resign(c);}} else {if (c.buy 0) {daddyHeap.remove(c);} else {daddyHeap.resign(c);}}daddyMove(time);}public ListInteger getDaddies() {ListCustomer customers daddyHeap.getAllElements();ListInteger ans new ArrayList();for (Customer c : customers) {ans.add(c.id);}return ans;}private void daddyMove(int time) {if (candHeap.isEmpty()) {return;}if (daddyHeap.size() daddyLimit) {Customer p candHeap.pop();p.enterTime time;daddyHeap.push(p);} else {if (candHeap.peek().buy daddyHeap.peek().buy) {Customer oldDaddy daddyHeap.pop();Customer newDaddy candHeap.pop();oldDaddy.enterTime time;newDaddy.enterTime time;daddyHeap.push(newDaddy);candHeap.push(oldDaddy);}}}}public static ListListInteger topK(int[] arr, boolean[] op, int k) {ListListInteger ans new ArrayList();WhosYourDaddy whoDaddies new WhosYourDaddy(k);for (int i 0; i arr.length; i) {whoDaddies.operate(i, arr[i], op[i]);ans.add(whoDaddies.getDaddies());}return ans;}// 干完所有的事模拟不优化public static ListListInteger compare(int[] arr, boolean[] op, int k) {HashMapInteger, Customer map new HashMap();ArrayListCustomer cands new ArrayList();ArrayListCustomer daddy new ArrayList();ListListInteger ans new ArrayList();for (int i 0; i arr.length; i) {int id arr[i];boolean buyOrRefund op[i];if (!buyOrRefund !map.containsKey(id)) {ans.add(getCurAns(daddy));continue;}// 没有发生用户购买数为0并且又退货了// 用户之前购买数是0此时买货事件// 用户之前购买数0 此时买货// 用户之前购买数0, 此时退货if (!map.containsKey(id)) {map.put(id, new Customer(id, 0, 0));}// 买、卖Customer c map.get(id);if (buyOrRefund) {c.buy;} else {c.buy--;}if (c.buy 0) {map.remove(id);}// c// 下面做if (!cands.contains(c) !daddy.contains(c)) {if (daddy.size() k) {c.enterTime i;daddy.add(c);} else {c.enterTime i;cands.add(c);}}cleanZeroBuy(cands);cleanZeroBuy(daddy);cands.sort(new CandidateComparator());daddy.sort(new DaddyComparator());move(cands, daddy, k, i);ans.add(getCurAns(daddy));}return ans;}public static void move(ArrayListCustomer cands, ArrayListCustomer daddy, int k, int time) {if (cands.isEmpty()) {return;}// 候选区不为空if (daddy.size() k) {Customer c cands.get(0);c.enterTime time;daddy.add(c);cands.remove(0);} else { // 等奖区满了候选区有东西if (cands.get(0).buy daddy.get(0).buy) {Customer oldDaddy daddy.get(0);daddy.remove(0);Customer newDaddy cands.get(0);cands.remove(0);newDaddy.enterTime time;oldDaddy.enterTime time;daddy.add(newDaddy);cands.add(oldDaddy);}}}public static void cleanZeroBuy(ArrayListCustomer arr) {ListCustomer noZero new ArrayListCustomer();for (Customer c : arr) {if (c.buy ! 0) {noZero.add(c);}}arr.clear();for (Customer c : noZero) {arr.add(c);}}public static ListInteger getCurAns(ArrayListCustomer daddy) {ListInteger ans new ArrayList();for (Customer c : daddy) {ans.add(c.id);}return ans;}// 为了测试public static class Data {public int[] arr;public boolean[] op;public Data(int[] a, boolean[] o) {arr a;op o;}}// 为了测试public static Data randomData(int maxValue, int maxLen) {int len (int) (Math.random() * maxLen) 1;int[] arr new int[len];boolean[] op new boolean[len];for (int i 0; i len; i) {arr[i] (int) (Math.random() * maxValue);op[i] Math.random() 0.5 ? true : false;}return new Data(arr, op);}// 为了测试public static boolean sameAnswer(ListListInteger ans1, ListListInteger ans2) {if (ans1.size() ! ans2.size()) {return false;}for (int i 0; i ans1.size(); i) {ListInteger cur1 ans1.get(i);ListInteger cur2 ans2.get(i);if (cur1.size() ! cur2.size()) {return false;}cur1.sort((a, b) - a - b);cur2.sort((a, b) - a - b);for (int j 0; j cur1.size(); j) {if (!cur1.get(j).equals(cur2.get(j))) {return false;}}}return true;}public static void main(String[] args) {int maxValue 10;int maxLen 100;int maxK 6;int testTimes 100000;System.out.println(测试开始);for (int i 0; i testTimes; i) {Data testData randomData(maxValue, maxLen);int k (int) (Math.random() * maxK) 1;int[] arr testData.arr;boolean[] op testData.op;ListListInteger ans1 topK(arr, op, k);ListListInteger ans2 compare(arr, op, k);if (!sameAnswer(ans1, ans2)) {for (int j 0; j arr.length; j) {System.out.println(arr[j] , op[j]);}System.out.println(k);System.out.println(ans1);System.out.println(ans2);System.out.println(出错了);break;}}System.out.println(测试结束);}}