头像

planter




离线:9小时前


最近来访(7)
用户头像
阿兔
用户头像
Jackle
用户头像
寒暄a
用户头像
禾小青
用户头像
hong1322
用户头像
optimjie
用户头像
我怀念的


planter
3天前

如题




planter
6天前

题目描述

实现一个双链表,双链表初始为空,支持 5 种操作:

在最左侧插入一个数;
在最右侧插入一个数;
将第 k 个插入的数删除;
在第 k 个插入的数左侧插入一个数;
在第 k 个插入的数右侧插入一个数
现在要对该链表进行 M 次操作,进行完所有操作后,从左到右输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数,则按照插入的时间顺序,这 n 个数依次为:第 1 个插入的数,第 2 个插入的数,…第 n 个插入的数。

输入格式
第一行包含整数 M,表示操作次数。

接下来 M 行,每行包含一个操作命令,操作命令可能为以下几种:

L x,表示在链表的最左端插入数 x。
R x,表示在链表的最右端插入数 x。
D k,表示将第 k 个插入的数删除。
IL k x,表示在第 k 个插入的数左侧插入一个数。
IR k x,表示在第 k 个插入的数右侧插入一个数。
输出格式
共一行,将整个链表从左到右输出。

数据范围
1≤M≤100000
所有操作保证合法。

样例

10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2

双链表.png

#include<iostream>
using namespace std;
const int N=100010;
int l[N],r[N],idx,e[N];
void init(){
    r[0]=1;l[1]=0;
    idx=2;
}
void insert(int k,int x){
    e[idx]=x;
    r[idx]=r[k];
    l[idx]=k;

    l[r[k]]=idx;r[k]=idx++;
}
void del(int k){
  r[l[k]]=r[k];  l[r[k]]=l[k];
}
int main(){
    int m;
    cin>>m;
    init();
    while(m--){
        string op;
        int x,k;
        cin>>op;
        if(op=="L"){
            cin>>x;
            insert(0,x);
        }
        if(op=="R"){
            cin>>x;
           insert(l[1],x);
        }
        if(op=="D"){
            cin>>k;
            del(k+1);
        }
        if(op=="IL"){
            cin>>k>>x;
            insert(l[k+1],x);
        }
        if(op=="IR"){
            cin>>k>>x;
            insert(k+1,x);
        }
    }
    for(int i=r[0];i!=1;i=r[i])cout<<e[i]<<" ";
    return 0;
}



活动打卡代码 AcWing 802. 区间和

planter
7天前

这是一道卡了我很久的题,一刷的时候觉得难,直接去学哈希表就跳过了,二刷的时候来补坑。

题目描述

假定有一个无限长的数轴,数轴上每个坐标上的数都是 0。

现在,我们首先进行 n 次操作,每次操作将某一位置 x 上的数加 c。

接下来,进行 m 次询问,每个询问包含两个整数 l 和 r,你需要求出在区间 [l,r] 之间的所有数的和。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行,每行包含两个整数 x 和 c。

再接下来 m 行,每行包含两个整数 l 和 r。

样例

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例:

8
0
5

离散化就是把稀疏的数据通过对应下标的方式存入到两个数组中,一个数组存放下标,一个数组存放下标所对应的值。
本题通过find函数返回离散化之前的值,再进行询问操作。

重点理解一下find(x)函数:

int find(int x) { //返回的是输入的坐标的离散化下标
    int l = 0, r = alls.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}

例子:find(x)时,在二分中将alls[mid]与x进行比较,对比的正是坐标的值。

之前并不懂的知识

auto

c++中for(auto count : counts)

counts 容器中的每一个元素从前往后枚举出来,并用 count 来表示

一些小tips
定义在一个auto序列的变量必须始终推导成同一类型。
`

例如:

auto a4 = 10, a5 = 20, a6 = 30;//正确

auto b4 = 10, b5 = 20.0, b6 = 'a';//错误,没有推导为同一类型

erase和unique

unique返回的是去重后的不重复数列中最后一个元素的下一个元素的地址

c.erase(b,e)----------------从c中删除迭代器对b和e所表示的范围中的元素,返回e

将这两个函数组合完就是将数组内重复的元素移除。先进行排序,排序之后,用unique把不重复元素的下一个元素地址返回,再用erase把这些重复的元素删除。

  sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

pair

pair是将2个数据组合成一组数据,当需要这样的需求时就可以使用pair
访问两个元素操作可以通过first和sencond访问:

离散化.png

完整代码(c++)

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int   N=300010;
typedef pair<int ,int >PII;
int a[N],s[N];
vector<int>alls;
vector<PII>add,query;
int find(int x){
    int l=0,r=alls.size()-1;
    while(l<r){
        int mid=l+r>>1;
        if(alls[mid]>=x)r=mid;
        else l=mid+1;
    }return l+1;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x,c;
        scanf("%d%d",&x,&c);
        add.push_back({x,c});
        alls.push_back(x);
    }
    for(int i=1;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        query.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);

    }
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    for(auto item:add){
        int x=find(item.first);
        a[x]+=item.second;
    }
    for(int i=1;i<=alls.size();i++)s[i]=s[i-1]+a[i];
    for(auto item:query){
        int l=find(item.first),r=find(item.second);
        cout<<s[r]-s[l-1]<<endl;
    }
    return 0;
}



planter
7天前

这是一道卡了我很久的题,一刷的时候觉得难,直接去学哈希表就跳过了,二刷的时候来补坑。

题目描述

假定有一个无限长的数轴,数轴上每个坐标上的数都是 0。

现在,我们首先进行 n 次操作,每次操作将某一位置 x 上的数加 c。

接下来,进行 m 次询问,每个询问包含两个整数 l 和 r,你需要求出在区间 [l,r] 之间的所有数的和。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行,每行包含两个整数 x 和 c。

再接下来 m 行,每行包含两个整数 l 和 r。

样例

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例:

8
0
5

离散化就是把稀疏的数据通过对应下标的方式存入到两个数组中,一个数组存放下标,一个数组存放下标所对应的值。
本题通过find函数返回离散化之前的值,再进行询问操作。

重点理解一下find(x)函数:

int find(int x) { //返回的是输入的坐标的离散化下标
    int l = 0, r = alls.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}

例子:find(x)时,在二分中将alls[mid]与x进行比较,对比的正是坐标的值。

之前并不懂的知识

auto

c++中for(auto count : counts)

counts 容器中的每一个元素从前往后枚举出来,并用 count 来表示

一些小tips
定义在一个auto序列的变量必须始终推导成同一类型。
`

例如:

auto a4 = 10, a5 = 20, a6 = 30;//正确

auto b4 = 10, b5 = 20.0, b6 = 'a';//错误,没有推导为同一类型

erase和unique

unique返回的是去重后的不重复数列中最后一个元素的下一个元素的地址

c.erase(b,e)----------------从c中删除迭代器对b和e所表示的范围中的元素,返回e

将这两个函数组合完就是将数组内重复的元素移除。先进行排序,排序之后,用unique把不重复元素的下一个元素地址返回,再用erase把这些重复的元素删除。

  sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

pair

pair是将2个数据组合成一组数据,当需要这样的需求时就可以使用pair
访问两个元素操作可以通过first和sencond访问:

离散化.png

完整代码(c++)

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int   N=300010;
typedef pair<int ,int >PII;
int a[N],s[N];
vector<int>alls;
vector<PII>add,query;
int find(int x){
    int l=0,r=alls.size()-1;
    while(l<r){
        int mid=l+r>>1;
        if(alls[mid]>=x)r=mid;
        else l=mid+1;
    }return l+1;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x,c;
        scanf("%d%d",&x,&c);
        add.push_back({x,c});
        alls.push_back(x);
    }
    for(int i=1;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        query.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);

    }
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    for(auto item:add){
        int x=find(item.first);
        a[x]+=item.second;
    }
    for(int i=1;i<=alls.size();i++)s[i]=s[i-1]+a[i];
    for(auto item:query){
        int l=find(item.first),r=find(item.second);
        cout<<s[r]-s[l-1]<<endl;
    }
    return 0;
}



planter
22天前

正文

遇到的问题: 把数组开在main函数的里面和外面到底有什么区别?

问题来自于开数组的区域不同
在运行代码的时候,操作系统会分配不同的内存区域来运行代码
栈区:由操作系统自动分配释放,存放函数的参数值,局部变量的值;不需要时系统会自动清除
堆区:由new分配的内存块,也就是说在代码中new一个数组,内存由堆区分配;堆区不由编译器管,由应用程序控制(相当于程序员控制。如果程序员没有释放掉,程序结束后,操作系统会自动回收
数据区:也称全局区或者静态区,存放全局的东西,比如全局变量
代码区:存放执行代码的地方,类似if else,while,for这种语句
也就是说,在main函数外面开一个数组,他的内存分配在数据区里;如果在main函数内部开数组,内存分配在栈区内。一般来说栈区的内存是比较小的,所以平常开一些小一点的数组是没问题的;但如果题目要求的数组比较大,那就会出现爆出的问题,程序无法访问内存就会出错;相对的,数据区的内存较大,所以开数组开在数据区/main函数外面,就不易出现这样的问题
————————————————
版权声明:本文为CSDN博主「Narcissus`小暮」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/qq_44654498/article/details/105043855




planter
24天前

给定两个非负整数(不含前导 0) A,B,请你计算 A/B 的商和余数。

输入格式

共两行,第一行包含整数 A,第二行包含整数 B。

输出格式

共两行,第一行输出所求的商,第二行输出所求余数。

数据范围

1≤A的长度≤100000,
1≤B≤10000,
B 一定不为 0

代码详解

 reverse(c.begin(),c.end()); 

为什么要reverse?
因为在除计算中,前导0
IMG_0173(20211224-200056)

完整代码、

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>div(vector<int>&A,int b,int &r){//&r表示带地址的余数r,&为取指针符号。
    vector<int>c;
    for(int i=A.size()-1;i>=0;i--){
        r=r*10+A[i];//余数转化为被除数的操作
        c.push_back(r/b);
        r%=b;
    }
    reverse(c.begin(),c.end());  //将整个数组逆转
    while(c.size()>1&&c.back()==0)c.pop_back();//去除前导零
    return c;
}
int main(){
    string a;
    int b,r=0;
    vector<int >A;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
    auto c=div(A,b,r);
    for(int i=c.size()-1;i>=0;i--)cout<<c[i];
    cout<<endl<<r;
    return 0;
}



planter
26天前

题目描述

给定两个正整数(不含前导 0),计算它们的和。

输入格式

共两行,每行包含一个整数。

输出格式

共一行,包含所求的和。


数据范围

1≤整数长度≤100000

分析题目

整数长度即输入的位数,比如说,整数长度是6,则可以输入100000-999999范围内的数。

思考几个问题

CF450F1E3A65CB15478FBF0C969B216B.png

答案

IMG_0169(20211222-211411)

向量(Vector)是一个封装了动态大小数组的顺序容器
可以简单的认为,向量是一个能够存放任意类型的动态数组。
void push_back(const T& x):向量尾部增加一个元素X

代码详解

auto C=add(A,B);
auto是c98中自动变量声明,在这里相当于是 <vector> int c


  for(int i=0;i<A.size()||i<B.size();i++){
          if(i<A.size())t+=A[i];
          if(i<B.size())t+=B[i];
          C.push_back(t%10);
          t/=10;
      }if(t)C.push_back(1);

for循环中以,A\B之间的最大值作为结束的依据。两个if来判断大数A、B是否遍历完,如果A、B之间有一个遍历完,就不用再进行相加操作。对10取模存入c数组。整除10作为进数。


C++ 代码

#include<iostream>
#include<vector>
using namespace std;
vector<int >add(vector<int>&A,vector<int>&B){

      vector<int>C;
      int t=0;
      for(int i=0;i<A.size()||i<B.size();i++){
          if(i<A.size())t+=A[i];
          if(i<B.size())t+=B[i];
          C.push_back(t%10);
          t/=10;
      }if(t)C.push_back(1);
      return C;
}
int main(){
    vector<int >A,B;
    string a,b;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
    for(int j=b.size()-1;j>=0;j--)B.push_back(b[j]-'0');
   auto C=add(A,B);
    for(int i=C.size()-1;i>=0;i--)cout<<C[i];
    return 0;
}



planter
26天前

二分查找

主要分为符合左边区间去判断和符合右边区间的性质去判断
IMG_0165

IMG_0166

代码分析

    while(l<r){//先判断左边区间的情况
    mid=l+r>>1;
    if(x<=q[mid])r=mid;

q[mid]表示符合条件的零界点,如果满足条件的话,就把原本【l,r】的区间,r更新为【l,mid】缩小范围进行二分,二分的主要思想也就是在这里,通过寻找符合条件的值缩小范围。else l=mid+1;
如果不满足条件的话,则说明就在边界点的另一边,就把原本【l,r】的区间改为【mid+1,r】这里之所以要mid+1是因为,不满足条件(x<=q[mid])则说明要求的点没在这个区间上。

while(l<r)
    {
    mid=l+r+1>>1;
    if(x>=q[mid])l=mid;
    else r=mid-1;
    }

这是二分的第二个模板,针对在右边范围的讨论。
有必要说明一下,这第二个模板mid为什么多了一个+1,因为在c++中,除法是向下取整的,比如:5/2=2。当 l=r-1时,mid=l.l=mid=l的话就进入死循环了,所以这里的mid需要再+1消除下取整,避免死循环。
if(x!=q[l])cout<<"-1 -1"<<endl;
因为当l=r的时候跳出循环,也就是q[l]离所求值最近的时候,如果q[l]=x的话,则说明存在要求的x,反之,要求的x不存在,则输出-1 -1

#include<iostream>
using namespace std;
const int N=100010;
int main(){
    int q[N],l,r,mid,x,m,n;
    cin>>m>>n;
    for(int i=0;i<m;i++)cin>>q[i];
    while(n--){
        cin>>x;
        l=0,r=m-1;
        while(l<r){//先判断左边区间的情况
            mid=l+r>>1;
            if(x<=q[mid])r=mid;
        }
        if(x!=q[l])cout<<"-1 -1"<<endl;
        else{
            cout<<l<<" ";
            l=0,r=m-1;
            while(l<r){
                mid=l+r+1>>1;
                if(x>=q[mid])l=mid;
                else r=mid-1;
            }cout<<l<<endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 77. 翻转单词顺序

planter
6个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 LeetCode 74. 搜索二维矩阵

planter
6个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~