11.26

目录

一.做题出错

1.

2.数组长度的一半

3.选择题

二.优先级队列(堆)

1.二叉树的顺序存储

1.1 存储方式

1.2下标关系

2.堆(heap)

2.1概念

2.2 操作-向下调整

三 建堆

四.优先级队列

1 概念

2 内部原理

3.操作-入队 offer()

4.操作-出队

五.计算糖果

---

一.做题出错

1.

如果直接返回null.会空指针异常

并且一开始我用的是LinkedList 会显示没用这个方法

因为只有ArrayLIST才有

2.数组长度的一半

利用众数和非众数消除原则

相同次数定义为1

定义一个后驱为0下标.从1下标开始遍历.如果相同就time++;如果不相同就减减

如果相同次数为0.就把后驱定义为新 的下标

import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution (int[] numbers) {
// write code here
        if(numbers==null||numbers.length==0) return 0;
        int time=1;
        int pre=numbers[0];
        for(int i=1;i
           if(time!=0){
            if(pre==numbers[i]){
                time++;
            }else{
                time--;
            }
          }else{
              pre=numbers[i];
              time++;
          }
        }
        return pre;
 
  }
}

3.选择题

b选项.接口里的方法都是为了被重写

私有化怎么被重写

子类的重写方法访问权限要大于等于父类的

Iterator是个迭代器.没有关系

final不能被重写.

void也不可以

都是关键字

1.System.arraycopy()

2.Arrays.copyof()

3.clone(

(13条消息) 如何在Java中复制/克隆数组_allway2的博客-CSDN博客_java 数组克隆

无参数的构造方法隐式调用super.所以当写了无参数的构造方法,有参数的就不需要显示调用

但是没有些无参的,就需要显示调用super

当父类无对应的就不需要用super帮助父类构造

但是如果你重写了构造法方法.那么无参的构造方法就会消失,所以这里就会显示报错.显示父类没有

二.优先级队列(堆)

1.二叉树的顺序存储

1.1 存储方式

使用数组保存二叉树结构，方式即将二叉树用层序遍历方式放入数组中。

一般只适合表示完全二叉树，因为非完全二叉树会有空间的浪费。

这种方式的主要用法就是堆的表示。

1.2下标关系

已知双亲(parent)的下标,则:

左下标(left)下标=2*parent+1;

右下标(right)下标=2*parent+2

已知孩子（不区分左右）(child)下标，则：

双亲(parent)下标 = (child - 1) / 2

2.堆(heap)

2.1概念

1.堆逻辑上是一颗完全二叉树

2.堆物理上是保存在数组中

3满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆

4反之，则是小堆，或者小根堆，或者最小

1. 堆的基本作用是，快速找集合中的最值

2.2 操作-向下调整

1.调整的开始就是从最后一课子树处罚的

2.每颗子树的调整都是向下调整的

2.3操作-向上调整

插入元素的时候,是放在数组结尾也就是最后一个

然后开始向上检查

三 建堆

我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

public class TestHeap {
    int[]elem;
    int usedSize;
    public TestHeap(){
        elem=new int[10];
    }

因为堆的底层是数组构成的

但是如果是一颗堆必须要是大根堆或者是小根堆,这里我们用大根堆表示

public void createHeap(int[] arr){
    elem= Arrays.copyOf(arr,arr.length);
    usedSize=arr.length;
    for (int parent=(usedSize-1-1)/2;parent>=0;parent--){
        shiftDown(parent,usedSize);//每一个都调整,从下网上调整
    }
}

我们放入数组.但是需要调整,这里我们就开始向下调整,从最后一个元素开始,把最后一个元素的父亲结点传过去

public void shiftDown(int parent,int len){//向下调整
    int child=2*parent+1;
    while(child
        //防止数组越界.如果没有右孩子.就不能往右加
        if(child+11]){
            child++;//保证左右孩子最大值的下标
        }//但是没有改变原有树的结构
        if(elem[child]>elem[parent]){
            int tmp=elem[child];
            elem[child]=elem[parent];
            elem[parent]=tmp;//交换
            //但是防止交换后下面的出现问题
            parent=child;//向下检查
            child=2*parent+1;//因为在这边改变的树的结构.所以需要检查
        }else{//假如是向下转型第二次到这,就说明上次的还是大.就可以直接跳出了
            break;//这次传递的parent没问题已经是大根堆
        }
    }
}

这里的时间复杂度,一般认为就是数组的高度因为一直往下检查所以就是O(logn);

 

调整高度

如果是第一层就需要调整h-1次

如果是第二层就需要调整h-2次

.

.

..

.如果是倒数第二层就需要调整一次,这是最坏的情况

把这个表达式乘以2错位相减

• log(n+1)会趋近于常数
• 所以时间复杂度就是n

四.优先级队列

priorityQueue

1 概念

在很多应用中，我们通常需要按照优先级情况对待处理对象进行处理，比如首先处理优先级最高的对象，然后处理次

高的对象。最简单的一个例子就是，在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。

在这种情况下，我们的数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这

种数据结构就是优先级队列(Priority Queue)

2 内部原理

优先级队列的实现方式有很多，但最常见的是使用堆来构建

3.操作-入队 offer()

入队的方式是向上调整

先放在最后一个元素,然后一个一个往上调整

public void shiftUp(int child){
    int parent =(child-1)/2;
    while(child>0){//检查到最上面也就是child移到0下标.
       /* if(child+1
            break;
        }*/
        if(elem[child]>elem[parent]){
            int tmp=elem[child];
            elem[child]=elem[parent];
            elem[parent]=tmp;//交换
            child=parent;
            parent=(child-1)/2;//向上检查
        }else{
            break;//因为已经是一个完整的大根堆了,只要有一个满足就不需要再检查了
        }
    }
}
public void offer(int val){
    if(isFull()){
        //扩容
        elem=Arrays.copyOf(elem,elem.length*2);
    }
    elem[usedSize++]=val;
    shiftUp(elem[usedSize-1]);//把要放的元素放到最后的位置,然后向上调整
}

4.操作-出队

因为出的就是0号下标,就让0号和最后一个交换,然后删除最后一个,只要让usedsize--即可.在让0号下标向下调整即可

public int poll(){
     if(isEmpty()){
         throw new RuntimeException("堆为空");
     }
     int tmp=elem[0];
     elem[0]=elem[usedSize-1];
     elem[usedSize-1]=tmp;
      usedSize--;
    shiftDown(0,usedSize);
     return tmp;
}
public boolean isEmpty(){
    return usedSize==0;
}

五.计算糖果

这个题目如果不考虑存不存在就只要互相加就可以消除得到

但是这里又说就是可能不满足

我们发现

ac表达式只有A和B

bd表达式只有B和C

共同是B

所以我们只要看通过ac计算出来的B和bd计算的B相不相同如果不相同那就说明不存在

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();//A-B
            int b = in.nextInt();//B-C
            int c=  in.nextInt();//A+B
            int d=  in.nextInt();//B+C
            int A=(a+c)/2;
            int B=(c-a)/2;
            int B1=(b+d)/2;
            int C=(d-b)/2;
            if(B==B1){
            System.out.println(A +" "+B+" "+C);
            }else{
                System.out.println("No");
            }
        }
    }
}