头像

MyACValentine




离线:8小时前


最近来访(35)
用户头像
半瓶可乐
用户头像
yaneznm
用户头像
L_635
用户头像
雪落之声-2010
用户头像
和和
用户头像
sprDream
用户头像
y_l
用户头像
Theliser
用户头像
清风扰梦
用户头像
清清小苏打
用户头像
Amaryllis_
用户头像
谁来剪月光.
用户头像
wjq-AKIOI
用户头像
Egbert-Lannister.
用户头像
整个AcWing凑不出一个ikun
用户头像
QWQ686
用户头像
cilitoo
用户头像
Tiwwp8n24
用户头像
她与AC皆失
用户头像
AcWingYyyyyy


堆 课堂笔记

手写堆分析

笔记1.jpg

ph[]、hp[]映射关系

笔记2.jpg




MyACValentine
10小时前

分析

堆的实现是一颗二叉树(完全二叉树)
树严格满足根节点小于或等于左右子节点
堆顶为树的最小值,插入节点是从后面插入(尾插),主要是方便数组的操作。

模拟堆:

需要修改或删除其中任意一个元素

由于需要交换第k个插入元素的下标
所以需要引入ph[]数组
由于需要知道第k个插入元素的位置
所以需要引入hp[]数组

ph[]数组是第k个插入的元素位置映射到堆中的下标,一 一对应。
hp[]数字是堆中的下标映射到第k个插入的元素位置,一 一对应。
两者可以理解是互为反函数关系。

如何手写一个堆:

1.插入一个数
heap[++size]=x; up(size)
2.求集合中的最小值
heap[1]
3.删除最小值
heap[1]=heap[size];
size--;
down(1);
4.删除任意一个元素
heap[k]=heap[size];
size--;
down(k);
up(k);
5.修改任意一个元素
heap[k]=x;
down(k);
up(k);

过程分析图

时间复杂度O(nlogn)–>O(n)

从n/2往上开始down递归
时间复杂度2.png

ph[]、hp[]数组的引入

![hp[]、ph[]数组.png](https://cdn.acwing.com/media/article/image/2023/01/31/261358_245a91e8a1-hp[]、ph[]数组.png)

heap_swap的分析

分析heap_swap.jpg

代码

import java.util.*;
public class Main{
    static int N=100010;
    static int h[]=new int[N];
    static int ph[]=new int[N];
    static int hp[]=new int[N];
    static int size,m;
public static void main(String []args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    size=0;
    m=0;
    while(n-->0) {
        String s =in.next();
        if(s.equals("I")) {
            int x = in.nextInt();
            //size++;m++;
            ph[++m]=++size;//先确定第m个插入的元素在堆中的下标
            hp[size]=m;//再确定下标为size的位置为插入的第m个元素
            h[size]=x;//再将x进行尾插
            up(size);//将插入下标为size的元素进行up操作,往上递归。
        }

        else if(s.equals("PM")) {
            System.out.println(h[1]);//直接输出堆顶元素 
        }

        else if(s.equals("DM")) {
            heap_swap(1,size);//将堆顶元素和最后一个插入的元素进行交换。
            size--;//抹去最后一个元素的位置
            down(1);//再down操作,重新递归堆顶。
        }

        else if(s.equals("D")) {
            int k = in.nextInt();
            k=ph[k];//需要先知道第k个删除的数在堆中的下标的是多少,即ph[k];
            heap_swap(k,size);//再将k和size进行交换
            size--;//抹去最后一个元素的位置
            //为了省功夫,直接让删除的元素down,up一遍,有且只执行一个操作。
            up(k);
            down(k);
        }

        else {
            int k = in.nextInt();
            int x = in.nextInt();
            k=ph[k];//确定在堆中的位置
            h[k]=x;//将堆中第k个数修改为x
            //再down,up一遍
            up(k);
            down(k);
        }

    }
}
public static void down(int x){
    int u =x;
    if(2*x<=size&&h[2*x]<h[u])u=2*x;
    if(2*x+1<=size&&h[2*x+1]<h[u])u=2*x+1;
    if(u!=x){
        heap_swap(u,x);//调用heap_swap方法
        down(u);
    }
}

public static void up(int x){
    while(x/2>0&&h[x/2]>h[x]){
        heap_swap(x,x/2);
        x=x/2;//继续递归up上去
    }
}

//注意swap方法的参数需要加入数组名
//因为java中无引用和指针,所以直接写swap(h[hp[k]],ph[hp[t]])无效
public static void swap(int h[],int k,int t){
    int temp=h[k];
    h[k]=h[t];
    h[t]=temp;
    }
    public static void heap_swap(int k,int t){
        swap(ph,hp[k],hp[t]);//先将ph指向的位置,即在堆中元素的下标进行交换

        //由于需要知道是要交换的元素是第几个插入的元素
        //所以引入hp[]数组!
        swap(hp,k,t);//将第k个插入和第t个插入的元素位置进行交换

        swap(h,k,t);//直接将对应下标的元素进行交换
    }
}   



MyACValentine
10小时前

分析

堆的实现是一颗二叉树(完全二叉树)
树严格满足根节点小于或等于左右子节点
堆顶为树的最小值,插入节点是从后面插入(尾插),主要是方便数组的操作。

堆排序

(1)首先,进行down()操作,将递归处理的堆顶输出。
(2)其次,将该堆顶覆盖掉,即用最后的数将其覆盖,再将最后一个位置的数抹去。
(3)最后,重新将该覆盖的数进行down()操作,得到新的堆顶,再将堆顶输出。

注意!

java不像C++,无引用和指针。
在写swap函数时,参数应该是下标,通过下标访问数组元素,再进行交换。
参数如果是数组直接的两个数作为参数,则会报MLE错误。

代码

import java.util.*;
public  class Main{
    static int size;
    static int h[] = new int [100010];
    public static void main(String []args) {
        Scanner in = new Scanner(System.in);
        int  n = in.nextInt();
        int  m = in.nextInt();
        for(int i=1;i<=n;i++)h[i]=in.nextInt();
        size=n;//size等于n

        //由于栈的最后一层的节点数刚好等于上面所有层的节点数
        //所以,只需要down递归上面n/2的节点即可 即i=n/2;
        //又因为插入操作是从尾插入,所以递归也从尾开始 即i--;
        for(int i=n/2;i>=0;i--) {
            down(i);//递归处理元素
        }

        while(m-->0) {
            System.out.print(h[1]+" ");//输出堆顶元素
            h[1]=h[size];//先用最后插入的数将堆顶抹掉,每输出堆顶就把当前堆顶给抹掉。
            //依次输出前m个堆顶,前m个最小数。
            size--;//再将最后插入的数删掉
            down(1);//对堆顶进行递归
        }
    }
    public static void  down(int x )
    {   
        int u = x;//假设当前递归的数最小,
        //左节点2*n存在并且左节点小于当前的数,更新最小数
        if(2*x+1<=size&&h[2*x+1]<h[u])u=2*x+1;
        //右节点2*n+1存在并且右节点小于当前的数,更新最小数
        if(2*x<=size&&h[2*x]<h[u]) u=2*x;

        //以上两步只执行一步

        if(u!=x) {//当前数不是堆的最小数(堆顶)
            swap(x,u);//交换
            down(u);//继续递归u这个点的数    
        }   
    }
    //交换函数
    //这里写成下标作为参数不报MLE,直接交换会报mle
    public static void swap(int t,int k) {
        int temp=h[t];
        h[t]=h[k];
        h[k]=temp;
    }
}


活动打卡代码 AcWing 838. 堆排序

MyACValentine
10小时前

分析

堆的实现是一颗二叉树(完全二叉树)
树严格满足根节点小于或等于左右子节点
堆顶为树的最小值,插入节点是从后面插入(尾插),主要是方便数组的操作。

堆排序

(1)首先,进行down()操作,将递归处理的堆顶输出。
(2)其次,将该堆顶覆盖掉,即用最后的数将其覆盖,再将最后一个位置的数抹去。
(3)最后,重新将该覆盖的数进行down()操作,得到新的堆顶,再将堆顶输出。

注意!

java不像C++,无引用和指针。
在写swap函数时,参数应该是下标,通过下标访问数组元素,再进行交换。
参数如果是数组直接的两个数作为参数,则会报MLE错误。

代码

import java.util.*;
public  class Main{
    static int size;
    static int h[] = new int [100010];
    public static void main(String []args) {
        Scanner in = new Scanner(System.in);
        int  n = in.nextInt();
        int  m = in.nextInt();
        for(int i=1;i<=n;i++)h[i]=in.nextInt();
        size=n;//size等于n

        //由于栈的最后一层的节点数刚好等于上面所有层的节点数
        //所以,只需要down递归上面n/2的节点即可 即i=n/2;
        //又因为插入操作是从尾插入,所以递归也从尾开始 即i--;
        for(int i=n/2;i>=0;i--) {
            down(i);//递归处理元素
        }

        while(m-->0) {
            System.out.print(h[1]+" ");//输出堆顶元素
            h[1]=h[size];//先用最后插入的数将堆顶抹掉,每输出堆顶就把当前堆顶给抹掉。
            //依次输出前m个堆顶,前m个最小数。
            size--;//再将最后插入的数删掉
            down(1);//对堆顶进行递归
        }
    }
    public static void  down(int x )
    {   
        int u = x;//假设当前递归的数最小,
        //左节点2*n存在并且左节点小于当前的数,更新最小数
        if(2*x+1<=size&&h[2*x+1]<h[u])u=2*x+1;
        //右节点2*n+1存在并且右节点小于当前的数,更新最小数
        if(2*x<=size&&h[2*x]<h[u]) u=2*x;

        //以上两步只执行一步

        if(u!=x) {//当前数不是堆的最小数(堆顶)
            swap(x,u);//交换
            down(u);//继续递归u这个点的数    
        }   
    }
    //交换函数
    //这里写成下标作为参数不报MLE,直接交换会报mle
    public static void swap(int t,int k) {
        int temp=h[t];
        h[t]=h[k];
        h[k]=temp;
    }
}


活动打卡代码 AcWing 839. 模拟堆

MyACValentine
11小时前

分析

堆的实现是一颗二叉树(完全二叉树)
树严格满足根节点小于或等于左右子节点
堆顶为树的最小值,插入节点是从后面插入(尾插),主要是方便数组的操作。

模拟堆

需要修改或删除其中任意一个元素

由于需要交换第k个插入元素的下标
所以需要引入ph[]数组
由于需要知道第k个插入元素的位置
所以需要引入hp[]数组

ph[]数组是第k个插入的元素位置映射到堆中的下标,一 一对应。
hp[]数字是堆中的下标映射到第k个插入的元素位置,一 一对应。
两者可以理解是互为反函数关系。

如何手写一个堆:

1.插入一个数
heap[++size]=x; up(size)
2.求集合中的最小值
heap[1]
3.删除最小值
heap[1]=heap[size];
size--;
down(1);
4.删除任意一个元素
heap[k]=heap[size];
size--;
down(k);
up(k);
5.修改任意一个元素
heap[k]=x;
down(k);
up(k);

过程分析图

时间复杂度O(nlogn)–>O(n)

从n/2往上开始down递归
时间复杂度2.png

ph[]、hp[]数组的引入

![hp[]、ph[]数组.png](https://cdn.acwing.com/media/article/image/2023/01/31/261358_245a91e8a1-hp[]、ph[]数组.png)

heap_swap的分析

分析heap_swap.jpg

代码

import java.util.*;
public class Main{
    static int N=100010;
    static int h[]=new int[N];
    static int ph[]=new int[N];
    static int hp[]=new int[N];
    static int size,m;
public static void main(String []args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    size=0;
    m=0;
    while(n-->0) {
        String s =in.next();
        if(s.equals("I")) {
            int x = in.nextInt();
            //size++;m++;
            ph[++m]=++size;//先确定第m个插入的元素在堆中的下标
            hp[size]=m;//再确定下标为size的位置为插入的第m个元素
            h[size]=x;//再将x进行尾插
            up(size);//将插入下标为size的元素进行up操作,往上递归。
        }

        else if(s.equals("PM")) {
            System.out.println(h[1]);//直接输出堆顶元素 
        }

        else if(s.equals("DM")) {
            heap_swap(1,size);//将堆顶元素和最后一个插入的元素进行交换。
            size--;//抹去最后一个元素的位置
            down(1);//再down操作,重新递归堆顶。
        }

        else if(s.equals("D")) {
            int k = in.nextInt();
            k=ph[k];//需要先知道第k个删除的数在堆中的下标的是多少,即ph[k];
            heap_swap(k,size);//再将k和size进行交换
            size--;//抹去最后一个元素的位置
            //为了省功夫,直接让删除的元素down,up一遍,有且只执行一个操作。
            up(k);
            down(k);
        }

        else {
            int k = in.nextInt();
            int x = in.nextInt();
            k=ph[k];//确定在堆中的位置
            h[k]=x;//将堆中第k个数修改为x
            //再down,up一遍
            up(k);
            down(k);
        }

    }
}
public static void down(int x){
    int u =x;
    if(2*x<=size&&h[2*x]<h[u])u=2*x;
    if(2*x+1<=size&&h[2*x+1]<h[u])u=2*x+1;
    if(u!=x){
        heap_swap(u,x);//调用heap_swap方法
        down(u);
    }
}

public static void up(int x){
    while(x/2>0&&h[x/2]>h[x]){
        heap_swap(x,x/2);
        x=x/2;//继续递归up上去
    }
}

//注意swap方法的参数需要加入数组名
//因为java中无引用和指针,所以直接写swap(h[hp[k]],ph[hp[t]])无效
public static void swap(int h[],int k,int t){
    int temp=h[k];
    h[k]=h[t];
    h[t]=temp;
    }
    public static void heap_swap(int k,int t){
        swap(ph,hp[k],hp[t]);//先将ph指向的位置,即在堆中元素的下标进行交换

        //由于需要知道是要交换的元素是第几个插入的元素
        //所以引入hp[]数组!
        swap(hp,k,t);//将第k个插入和第t个插入的元素位置进行交换

        swap(h,k,t);//直接将对应下标的元素进行交换
    }
}   



分析

思想:运用并查集的思想,引入其他变量size[]等等。
1.初始化点的个数,先初始化每个点的个数为1。
2.连接两个点,即有边的为一个连通块,此时的点数为2,依次类推。
3.再去用size数组统计连通块中ab点的数量。
合并操作,即将a的size加上b的size
4.最后,判断:如果ab在一个集合中,输出Yes,否则输出No。

分析图

连通块中点的个数.jpg

代码

import java.util.*;
public class Main{
    static int  N=100010;
    static int p[]=new int[N];
    static int size[]=new int[N];
    public static int find(int x){
        if(p[x]!=x) p[x]=find(p[x]);
        return  p[x];
    }
    public static void main(String []args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        for(int i=1;i<=n;i++)
        {p[i]=i;  //初始化,让每个点指向它自己。
         size[i]=1; //初始化,每个点的点数均为1
        }
        while(m-->0){
        String s = in.next(); 
        if(s.equals("C")){ **** 
        int a=in.nextInt();
        int b=in.nextInt();
        if(find(a)!=find(b)){
        size[find(b)]+=size[find(a)]; //先将b的size加在a的size,合并a、b的size
        p[find(a)]=find(b); //a的祖宗节点指向b
        }
        }
        else if(s.equals("Q1")){
        int a=in.nextInt();
        int b=in.nextInt();
            if(find(a)==find(b)){
                System.out.println("Yes");
            }
            else{
                System.out.println("No");
            }
        }
        else{
          int a = in.nextInt();
          System.out.println(size[find(a)]);
        }
    }
}
}



分析

思想:运用并查集的思想,引入其他变量size[]等等。
1.初始化点的个数,先初始化每个点的个数为1。
2.连接两个点,即有边的为一个连通块,此时的点数为2,依次类推。
3.再去用size数组统计连通块中ab点的数量。
合并操作,即将a的size加上b的size
4.最后,判断:如果ab在一个集合中,输出Yes,否则输出No。

分析图

连通块中点的个数.jpg

代码

import java.util.*;
public class Main{
    static int  N=100010;
    static int p[]=new int[N];
    static int size[]=new int[N];
    public static int find(int x){
        if(p[x]!=x) p[x]=find(p[x]);
        return  p[x];
    }
    public static void main(String []args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        for(int i=1;i<=n;i++)
        {p[i]=i;  //初始化,让每个点指向它自己。
         size[i]=1; //初始化,每个点的点数均为1
        }
        while(m-->0){
        String s = in.next(); 
        if(s.equals("C")){
        int a=in.nextInt();
        int b=in.nextInt();
        if(find(a)!=find(b)){
        size[find(b)]+=size[find(a)]; //先将b的size加在a的size,合并a、b的size
        p[find(a)]=find(b); //a的祖宗节点指向b
        }
        }
        else if(s.equals("Q1")){
        int a=in.nextInt();
        int b=in.nextInt();
            if(find(a)==find(b)){
                System.out.println("Yes");
            }
            else{
                System.out.println("No");
            }
        }
        else{
          int a = in.nextInt();
          System.out.println(size[find(a)]);
        }
    }
}
}



并查集

基本思想:
每个集合用一颗树来表示,树根的编号就是整个集合的编号。
每个节点存储它的父节点,p[x]表示x的父节点。

三个问题

P1:如何判断树根
if(p[x]==x)即根节点和输入的集合编号(它本身)相等

P2:如何求x的集合编号
if(p[x]==x) return p[x];

P3:如何合并两个集合
p[x]是x的集合编号,p[y]是y的集合编号
那么,需要让p[x]接上y,即x的祖宗节点为y的一个子节点。

返回祖宗节点:

return p[x];
如果p[x]等于x的话,就返回p[x]即根节点x,此时的返回值为常量x。

路径压缩:

if(p[x]!=x)p[x]=find(p[x]);
代码解读:
如果p[x]不等于x的话,就进行路径压缩操作,即让每个p[x]与自身进行比较,很明显相等,返回的均是x,这样就实现了路径压缩。

分析过程图

过程图.jpg

代码

import java.util.*;
public class Main{
    static int N=100010;
    static int p[]=new int[N];
    public static int find(int x){//返回祖宗节点+路径压缩
        //条件:节点的父节点p[x]为x(祖宗节点)
        //换句话来说,即只有祖宗节点等于它本身x
        if(p[x]!=x)p[x]=find(p[x]);//路径压缩

        return p[x];//返回祖宗节点
    }

    //等同于如下代码:
    public static int  find (int x){
        if(p[x]==x)return x;
        else{
            p[x]=find p[x];
        }
        return p[x];
    }

    public static void main(String []args){
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int m=in.nextInt();
        //初始化:即让当前数据的父节点指向其本身,将父节点设置为自己。
        for(int i=1;i<=n;i++)p[i]=i;
        while(m-->0){
            String s=in.next();
            int a=in.nextInt();
            int b=in.nextInt();
            //合并,将a的祖宗节点作为b的一个子节点插入
            if(s.equals("M"))p[find(a)]=find(b);
            else{//查找b和a的集合编号是否一致
                if(find(b)==find(a)){
                    System.out.println("Yes");
                }
                else{
                    System.out.println("No");
                }
            }
        }
    }
}

参考资源

https://b23.tv/UDjPN9Y
https://b23.tv/13OXh8I



活动打卡代码 AcWing 836. 合并集合

并查集

基本思想:
每个集合用一颗树来表示,树根的编号就是整个集合的编号。
每个节点存储它的父节点,p[x]表示x的父节点。

三个问题

P1:如何判断树根
if(p[x]==x)即根节点和输入的集合编号(它本身)相等

P2:如何求x的集合编号
if(p[x]==x) return p[x];

P3:如何合并两个集合
p[x]是x的集合编号,p[y]是y的集合编号
那么,需要让p[x]接上y,即x的祖宗节点为y的一个子节点。

返回祖宗节点:

return p[x];
如果p[x]等于x的话,就返回p[x]即根节点x,此时的返回值为常量x。

路径压缩:

if(p[x]!=x)p[x]=find(p[x]);
代码解读:
如果p[x]不等于x的话,就进行路径压缩操作,即让每个p[x]与自身进行比较,很明显相等,返回的均是x,这样就实现了路径压缩。

分析过程图

过程图.jpg

代码

import java.util.*;
public class Main{
    static int N=100010;
    static int p[]=new int[N];
    public static int find(int x){//返回祖宗节点+路径压缩
        //条件:节点的父节点p[x]为x(祖宗节点)
        //换句话来说,即只有祖宗节点等于它本身x
        if(p[x]!=x)p[x]=find(p[x]);//路径压缩

        return p[x];//返回祖宗节点
    }

    //等同于如下代码:
    public static int  find (int x){
        if(p[x]==x)return x;
        else{
            p[x]=find p[x];
        }
        return p[x];
    }

    public static void main(String []args){
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int m=in.nextInt();
        //初始化:即让当前数据的父节点指向其本身,将父节点设置为自己。
        for(int i=1;i<=n;i++)p[i]=i;
        while(m-->0){
            String s=in.next();
            int a=in.nextInt();
            int b=in.nextInt();
            //合并,将a的祖宗节点作为b的一个子节点插入
            if(s.equals("M"))p[find(a)]=find(b);
            else{//查找b和a的集合编号是否一致
                if(find(b)==find(a)){
                    System.out.println("Yes");
                }
                else{
                    System.out.println("No");
                }
            }
        }
    }
}

参考资源

https://b23.tv/UDjPN9Y
https://b23.tv/13OXh8I




Trie树

特性:用于高效地存储和查找字符串集合的数据结构

分析

用Trie树存储字符串中的每个字符,形成一个Trie树。
再利用Trie树进行查找字符。

怎么存储字符?
(1)先设置头节点(根节点)为0
(2)再将字符数组中的每一个字符(a~z)转换成数字(0-25)
代码如下:
int u = str[i]-'a';
这样字符就映射成数字。
(3)对Trie树的节点进行处理
代码如下:
if(son[p][u]==0)son[p][u]=++idx;
p=son[p][u];

代码解读:

思想:如果该儿子节点为0,即没有进树,那么需要进树操作。
这里实际上是通过idx来进行标记的,每次进树后,需要更新p。
更新p的作用:
p值更新后,保存的是当前子节点的下标。
用于联系当前节点与子节点。

例:str[1][2]此时p为1
p = son[p][u]
表示的是下标1的节点(如b)和2(插入字符转换后的数字:例c)建立联系,
换句话来说,即插入字符后的节点c为下标1b的子节点。
综上:该子节点需要建立子节点,则再继续更新p。

最后,p保存的是存入树的最后一个字符,映射为数字,则只需统计数字出现多少次即可。

具体如下:

过程图:

过程图.jpg

代码

import java.util.*;
public class Main{
static  int N=100010;
static int son[][]=new int [N][26];
static int cnt[]=new int[N];
static char str[]=new char[N];
static int idx=0;
//插入操作
public static void insert(char str[]){
    int p=0;//头节点,根节点为0
    for(int i=0;i<str.length;i++){
        int u = str[i]-'a';//将输入的字符字母转换成数字0-25
        //如果该字符不存在,即为0,则该字符存入树中
        if(son[p][u]==0)son[p][u]=++idx;
        p=son[p][u];//最后一个字符节点对应的数字
    }
    cnt[p]++;//将字符串读到的最后一个节点数字做上标记,统计出现次数
}
public static int query(char str[]){
    int p=0;
    for(int i=0;i<str.length;i++){
        int u =str[i]-'a';
        //不存在则返回0
        if(son[p][u]==0)return 0;
        //存在则更新p为下一个字符节点
        p = son[p][u];//
    }
    return cnt[p];//返回字符串所出现的次数
}

public static void main(String []args){
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    String d = in.nextLine();//格式问题:换行
    while(n-->0){
        String s = in.nextLine();
        String []st=s.split(" ");
        String s1= st[0];
        String s2 =st[1];
        if(s1.equals("I")){
           insert(s2.toCharArray());
        }
        else{
            System.out.println(query(s2.toCharArray()));
        }
    }
}
}