头像

清_1




离线:16天前



清_1
17天前

算法1

思路:辗转相除法,n%k得余数,

C++ 代码

class Solution {
public:
    int sumBase(int n, int k) {
        int res=0;
        while(n)res+=n%k,n/=k;
        return res;
    }
};




清_1
17天前
class Solution {
public:
    int sumBase(int n, int k) {
        int res=0;
        while(n)res+=n%k,n/=k;
        return res;
    }
};



清_1
19天前

算法1

思路:这是一道小根堆的题,小根堆就是叶子节点和他的父节点比较,如果小于父节点,上移,建议把down()函数背过,我们输入一组数,

down()-将小数上移

void down(int u)
{

    int t=u;//t表示根节点和他左右儿子,这三个点的最小值
    //如果有左儿子,并且左儿子小,让左儿子上移
    if(u*2<=cnt &&h[u*2]<h[t]) t=u*2;

    if(u*2+1<=cnt &&h[u*2+1]<h[t])t=u*2+1;//同理让右儿子上移
    if(u!=t)//如果当前根节点不是最小的那个数,就交换
    {
        swap(h[u],h[t]);
        down(t);
    }
}

C++ 代码

#include<iostream>

using namespace std;
const int N=100010;

int n,m;
int h[N],cnt;
void down(int u)
{

    int t=u;//t表示根节点和他左右儿子,这三个点的最小值
    //如果有左儿子,并且左儿子小,让左儿子上移
    if(u*2<=cnt &&h[u*2]<h[t]) t=u*2;

    if(u*2+1<=cnt &&h[u*2+1]<h[t])t=u*2+1;//同理让右儿子上移
    if(u!=t)//如果当前根节点不是最小的那个数,就交换
    {
        swap(h[u],h[t]);
        down(t);
    }
}
int main()
{

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&h[i]);

    cnt=n;
    for(int i=n/2;i;i--)down(i);//这是n/2,叶子节点占1/2n,将小数不断上移,构成小根堆

    while(m--)
    {

        printf("%d ",h[1]);//h[1]就是堆排序中最小的数
        h[1]=h[cnt];//cnt是最后一个节点,让最后一个点覆盖掉第一个点
        cnt--;//覆盖掉之后,节点数减减

        down(1);
    }


    return 0;
}



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

清_1
19天前
#include<iostream>

using namespace std;
const int N=100010;

int n,m;
int h[N],cnt;
void down(int u)
{

    int t=u;//t表示根节点和他左右儿子,这三个点的最小值
    //如果有左儿子,并且左儿子小,
    if(u*2<=cnt &&h[u*2]<h[t]) t=u*2;

    if(u*2+1<=cnt &&h[u*2+1]<h[t])t=u*2+1;
    if(u!=t)
    {
        swap(h[u],h[t]);
        down(t);
    }
}
int main()
{

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&h[i]);

    cnt=n;
    for(int i=n/2;i;i--)down(i);

    while(m--)
    {

        printf("%d ",h[1]);
        h[1]=h[cnt];
        cnt--;

        down(1);
    }


    return 0;
}



清_1
21天前
#include<iostream>

using namespace std;

const int N=100010;

int n,m;
int p[N],cnt[N];//cnt表示每个集合里的点的个数 

int find(int x)//路径压缩
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}

int main()
{

   cin>>n>>m;
   for(int i=1;i<=n;i++)
   {
       p[i]=i;
       cnt[i]=1;//最开始每个集合里面只有一个点
   }

    while(m--)
    {
        string op;
        int a,b;
        cin>>op;

        if(op=="C")//第一个询问是C,表示将两个集合构成一个连通图
        {
            cin>>a>>b;//输入a,b,这里的逻辑是这样的,如果a和a之间有一条边,a=find(a),即把
            //a之间形成一个闭环,同理b,如果ab之间不在一个集合,p[a]=b,将a连接到b上,此时连通图的
            //的数量就是以b根节点的连通图的点的个数
            a=find(a),b=find(b);
            if(a!=b)//如果a,b不在一个连通图
            {
                p[a]=b;
                cnt[b]+=cnt[a];
            }
        }
        else if(op=="Q1")//Q1是查询操作
        {
            cin>>a>>b;
            if(find(a)==find(b))puts("Yes");//如果查询中,ab在一个图中,输出yes
            else puts("No");
        }
        else//Q2操作是输出所求连通图中节点个数
        {
            cin>>a;
            cout<<cnt[find(a)]<<endl;
        }

    }
    return 0;
}









清_1
21天前

算法1

思路: 考察并查集
并查集考点:
1:将两个代码合并
2:询问两个元素是否在一个集合之中

基本原理:每个集合用一棵树来表示,树根的编号就是整个集合的编号
每个节点存储他的父节点,p[x]表示x的父节点

1:如何判断树根?if(p[x]==x)
2:如何求解x的编号?while(p[x]!=x)x=p[x];
3:如何合并两个集合?p[x]是x的集合编号,p[y]是y的集合编号,将x的父节点当做y的一个节点

优化:路径压缩模板


int find(int x)//返回x所在集合的编号+路径压缩
{
    if(p[x]!=x)p[x]=find(p[x]);//如果父节点不是根节点,就让父节点为祖宗节点 
    return p[x];
}

C++ 代码

#include<iostream>
using namespace std;

const int N=100010;
int n,m;
int p[N];

int find(int x)//返回x所在集合的编号+路径压缩
{
    if(p[x]!=x)p[x]=find(p[x]);//如果父节点不是根节点,就让父节点为祖宗节点 
    return p[x];
}

int main()
{
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)p[i]=i;
    while(m--)
    {

        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);

        if(op[0]=='M')p[find(a)]=find(b);//让a的祖宗节点的父亲,等于b的节点!!!
        else
        {
            if(find(a)==find(b) )puts("Yes");

            else puts("No");
        }

    }

    return 0;
}



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

清_1
21天前
#include<iostream>
using namespace std;

const int N=100010;
int n,m;
int p[N];

int find(int x)//返回x所在集合的编号+路径压缩
{
    if(p[x]!=x)p[x]=find(p[x]);//如果父节点不是根节点,就让父节点为祖宗节点 
    return p[x];
}

int main()
{
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)p[i]=i;
    while(m--)
    {

        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);

        if(op[0]=='M')p[find(a)]=find(b);//让a的祖宗节点的父亲,等于b的节点
        else
        {
            if(find(a)==find(b) )puts("Yes");

            else puts("No");
        }

    }

    return 0;
}



清_1
21天前

算法1

思路:trie树:高效存储和查询字符集合的数据结构,对于存储和查询都需要先遍历,
得到其下标,插入操作,如果当前树没有路,就创建路,怎么理解呢?
相当于我这个u=abc没有出现过,就需要建一条路径,这里++idx,相当于p++,
然后令这一支路位p=son[p][u],cnt[p]++;

查询操作同理,先遍历,得到每个单词的下标,如果找不到,返回0,找到了,返回cnt[p]

get小技巧

    之前在做题的时候,经常会遇到让你输入某种字母,实现某种操作,
比如这里的I,实现插入操作, 像这种情况,最好设置一个op[x]数组,
然后if,,,else去实现函数功能,代码简单逻辑分明

插入模板

void insert(char str[])//这里也可以写成void insert(char *str)
{

    int p=0;
    for(int i=0;str[i];i++)//遍历,是否走到结尾
    {

      int u = str[i] - 'a';//u表示当前节点的编号  
        if(!son[p][u])son[p][u]=++idx;//如果当前树没有路,就创建路
        p=son[p][u];//这是我的新路
    }
    cnt[p]++;//以p这个单词结尾的数量加加


}

关于查询模板

int query(char str[])
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!son[p][u]) return 0;// 如果查不到所要查找的单词

        p=son[p][u];

    }
    return cnt[p];
}

C++ 代码


#include<iostream>

using namespace std;
const int N=100010;
//下标是0的点,既是空节点,又是根节点
int son[N][26],cnt[N],idx;//son每个单词最多可连的子节最多有26个
//cnt表示以当前单词结尾的单纯有多少个,idx存下标
char str[N];
void insert(char str[])
{

    int p=0;
    for(int i=0;str[i];i++)//遍历,是否走到结尾
    {

      int u = str[i] - 'a';//u表示当前节点的编号  
        if(!son[p][u])son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]++;//以p这个单词结尾的数量加加


}
int query(char str[])
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!son[p][u]) return 0;// 如果查不到所要查找的单词

        p=son[p][u];

    }
    return cnt[p];
}
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        char op[2];
        scanf("%s%s",op,str);
        if(op[0]=='I')insert(str);
        else printf("%d\n",query(str));
    }
    return 0;

}




活动打卡代码 AcWing 835. Trie字符串统计

清_1
21天前
#include<iostream>

using namespace std;
const int N=100010;
//下标是0的点,既是空节点,又是根节点
int son[N][26],cnt[N],idx;//son每个单词最多可连的子节最多有26个
//cnt表示以当前单词结尾的单纯有多少个,idx存下标
char str[N];
void insert(char str[])
{

    int p=0;
    for(int i=0;str[i];i++)//遍历,是否走到结尾
    {

      int u = str[i] - 'a';//u表示当前节点的编号  
        if(!son[p][u])son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]++;//以p这个单词结尾的数量加加


}
int query(char str[])
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!son[p][u]) return 0;// 如果查不到所要查找的单词

        p=son[p][u];

    }
    return cnt[p];
}
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        char op[2];
        scanf("%s%s",op,str);
        if(op[0]=='I')insert(str);
        else printf("%d\n",query(str));
    }
    return 0;

}



清_1
21天前

算法1

思路:关于模式串匹配,最快的解决方式就是KMP,但是同样不好理解,实质就是求最大公共前缀,哔哩哔哩上有动态的讲解,看了很多版本的kmp讲解,B站上还是最容易理解的,关于kmp,我想最重要在于 代码实现,这个模板是真心不错,简单,容易理解,如果明白原理了,最好把这个模板背过,并能熟练写出来,就可以了

C++ 代码

#include<iostream>
using namespace std;

const int N=100010,M=1000010;
int n,m;

int ne[N];
char s[M],p[N];


int main()
{
    cin>>n>>p+1>>m>>s+1;

    for(int i=2,j=0;i<=n;i++)
    {
        while(j &&p[i]!=p[j+1])j=ne[j];
        if(p[i]==p[j+1])j++;
        ne[i]=j;
    }

    for(int i=1,j=0;i<=m;i++)
    {
        while(j && s[i]!=p[j+1])j=ne[j];
        if(s[i]==p[j+1])j++;
        if(j==n)
        {
            printf("%d ",i-n);
            j=ne[j];
        }
    }

    return 0;
}