算法基础课-数据结构

单链表

题目链接：826. 单链表 - AcWing题库
思路：AcWing 826. 单链表---图解 - AcWing

需要注意的点在于理解ne[idx] = head，idx表示当前的点，意思是将当前的点链到头结点的后面，再将头结点链在当前idx的前面。

#include<bits/stdc++.h>

using namespace std;
const int N = 100010;
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert_to_head(int a)
{
    e[idx] = a;
    ne[idx] = head;
    head = idx ++ ;
}

void insert(int k,int a)
{
    e[idx] = a;
    ne[idx] = ne[k];
    ne[k] = idx ++ ;
}

// 将头结点删除，需要保证头结点存在
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

int main(){
    int m;
    cin>>m;
    init();
    while(m--){
        char a;
        cin>>a;
        int k,x;
        if(a=='H'){
            cin>>x;
            insert_to_head(x);
        }else if(a=='I'){
            cin>>k>>x;
            insert(k-1,x);
        }else{
            cin>>k;
            if(!k) head = ne[head];
            else remove(k-1);
        }
    }
    for(int i=head;i!=-1;i=ne[i]) cout<<e[i]<<" ";
    
    return 0;
}

双链表

题目链接：827. 双链表 - AcWing题库

思路：这个博客写的可好AcWing 827. 双链表 - AcWing。

需要注意的地方在于r数组和l数组的含义。r[idx]表示的是idx的右边，l[idx]表示idx的左边，开始时初始化0的左边是1，1的右边是左，所以r[0] = 1,l[1] = 0。

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

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

栈的应用

题目链接：3302. 表达式求值 - AcWing题库
思路：这个题解写的很好AcWing 3302. 表达式求值：多图讲解运算符优先级+详细代码注释 - AcWing。

主要的思路在符号栈上，符号栈内存储的符号优先级一定递增，即将进来的符号若小于当前栈顶优先级，则先对栈内高优先级符号进行运算，直到栈顶优先级低于待入栈符号优先级。

还需要注意的是，对于相同运算符来说，栈内的优先级大于栈外优先级，即遇到栈顶是一个加号，待入栈也是一个加号，先运算栈内加号，当栈为空或遇到更低优先级的符号时再将栈外加号入栈。

#include<bits/stdc++.h>

using namespace std;
stack<int> num;
stack<int> op;

unordered_map<char,int> h{{'+',1},{'-',1},{'*',2},{'/',2}};
void calc(){
    char ops = op.top();
    op.pop();
    int b = num.top();
    num.pop();
    int a = num.top();
    num.pop();
    
    if(ops == '+') num.push(a+b);
    if(ops == '-') num.push(a-b);
    if(ops == '*') num.push(a*b);
    if(ops == '/') num.push(a/b);
    
    return;
}

int main(){
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(isdigit(s[i])){  //遇到数字的情况
            int j = i;
            int val = 0;
            while(j<s.size()&&isdigit(s[j])){
                val = val*10 + s[j] - '0';
                j++;
            }
            i=j-1;
            num.push(val);
        }else{  //遇到字符的情况
            if(s[i] == '(') op.push('(');
            else if(s[i] == ')'){
                while(op.top()!='('){
                    calc();
                }
                op.pop();
            }else{
                while(op.size() && h[op.top()] >= h[s[i]]){
                    calc();
                }
                op.push(s[i]);
            }
        }
    }
    while(op.size())
        calc();
    cout<<num.top()<<endl;
    return 0;
}

单调栈

题目链接：830. 单调栈 - AcWing题库

思路：维护一个数字单调递增的栈，若下一个待入栈数字小于栈顶时，持续出栈。感觉跟表达式求值中栈内优先级高于栈外优先级有点像，hh。

常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}
#include<bits/stdc++.h>

using namespace std;
const int N = 100010;
int a[N];
int main(){
    int n;
    cin>>n;
    
    stack<int> stk;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++){
        while(stk.size()&&stk.top() >= a[i]) stk.pop();
        if(stk.size()) cout<<stk.top()<<" ";
        else cout<<-1<<" ";
        stk.push(a[i]);
    }
    
    return 0;
}

单调队列

题目链接：154. 滑动窗口 - AcWing题库
思路：排在后面的数字越小/大，越优秀，当这样的元素出现时，将右侧队列中的元素出队。由于要求队列能右侧出队，所以需要自己模拟队列（感觉可以使用双端队列实现）。

需要注意的点是队列中存储的是下标，是为了方便队头出队。

#include<bits/stdc++.h>

using namespace std;
const int N = 1e6+10;

int a[N];
int q[N];
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];
    int h=1,t=0;
    for(int i=0;i<n;i++){
        while(h<=t&&a[q[t]] >= a[i]) t--;
        q[++t] = i;
        if(q[h]<i-k+1) h++;
        if(i>=k-1) cout<<a[q[h]]<<" ";
    }
    h=1;t=0;
    cout<<endl;
    for(int i=0;i<n;i++){
        while(h<=t&&a[q[t]] <= a[i]) t--;
        q[++t] = i;
        if(q[h]<i-k+1) h++;
        if(i>=k-1) cout<<a[q[h]]<<" ";
    }
    return 0;
}

KMP

题目链接：831. KMP字符串 - AcWing题库

思路：对于模板串（短串）进行初始化ne数组，ne数组表示当前位置不匹配时，可以从哪个位置开始匹配。具体思路太复杂，放弃，可以考虑直接背过。时间复杂度为O(m+n)。

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+10;
const int M = 1e6+10;
char p[N],s[M];
int ne[M];
void init(char p[],int n,int m){
    // s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
    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;
    }
}

int main(){
    int n,m;
    cin>>n;
    cin>>p+1;
    cin>>m;
    cin>>s+1;
    init(p,n,m);
    // 匹配
    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)
        {
            cout<<i-n<<' ';
            j = ne[j];
            // 匹配成功后的逻辑
        }
    }
    return 0;
}

Trie（字典树）

题目链接：835. Trie字符串统计 - AcWing题库
思路：ch[0][2]=1表示从0号结点开始往2('c')走能走到1号节点。

#include<bits/stdc++.h>

using namespace std;
const int N = 100010;
int son[N][26],cnt[N],idx = 1;



void insert(string s){
    int p = 0;
    for(int i=0;i<s.size();i++){
        int u = s[i] - 'a';
        if(!son[p][u]) son[p][u] = idx++;
        p = son[p][u];
    }
    cnt[p]++;
}

int query(string s){
    int p = 0;
    for(int i=0;i<s.size();i++){
        int u = s[i] - 'a';
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main(){
    int n;
    cin>>n;
    while(n--){
        char op;
        string s;
        cin>>op>>s;
        if(op == 'I'){
            insert(s);
        }else cout<<query(s)<<endl;
    }
    return 0;
}

并查集

题目链接：836. 合并集合 - AcWing题库

思路：fa[i]表示i节点的父亲节点。开始时每个节点的父亲节点都是自己。

#include<bits/stdc++.h>

using namespace std;
const int N= 1e5+10;

int fa[N];  //下标表示当前点，数组值表示其父亲节点的下标

int find(int x){
    if(fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

void unionset(int x,int y){
    fa[find(x)] = find(y); 
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i] = i;
    
    while(m--){
        char op;
        cin>>op;
        int x,y;
        cin>>x>>y;
        if(op == 'M'){
            unionset(x,y);
        }else{
            if(find(x) == find(y)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}

堆

题目链接：838. 堆排序 - AcWing题库

思路：主要的操作包括up和down，up表示将节点上移，一般在新节点进入时使用，down表示将节点下移，一般在删除元素时使用。

需要注意的点在于一些小细节，例如递归边界，up和down都使用递归的形式，需要注意什么时候递归停止或是什么时候采用递归。

#include<bits/stdc++.h>

using namespace std;
const int N = 100010;
int a[N];
int cnt;
void up(int x){
    if(x/2&&a[x]<a[x/2]){
        swap(a[x],a[x/2]);
        up(x/2);
    }
}

void down(int x){
    int u = x;
    if(x*2<=cnt&&a[u]>a[x*2]) u = x*2;
    if(x*2+1<=cnt&&a[u]>a[x*2+1]) u = x*2+1;
    if(x!=u){
        swap(a[x],a[u]);
        down(u);
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>a[++cnt];
        up(cnt);

    }
    // for(int i=1;i<=cnt;i++) cout<<a[i]<<" ";
    // cout<<endl;
    while(m--){
        cout<<a[1]<<" ";
        swap(a[1],a[cnt]);
        cnt--;
        down(1);
        // for(int i=1;i<=cnt;i++) cout<<a[i]<<" ";
        // cout<<endl;
    }
    return 0;
}

哈希表

题目链接：841. 字符串哈希 - AcWing题库

思路：

#include<bits/stdc++.h>

using namespace std;
const int N = 100010;
typedef unsigned long long ULL;
ULL h[N],p[N];
int P = 131;
ULL getSeg(int l,int r){
    return h[r] - h[l-1] * p[r-l+1];
}
int main(){
    int n,m;
    cin>>n>>m;
    char s[N];
    cin>>s+1;
    p[0] = 1;
    for(int i=1;i<=n;i++){
        h[i] = h[i-1]*P + s[i];
        p[i] = p[i-1]*P;
    }
    while(m--){
        int l1,l2,r1,r2;
        cin>>l1>>r1>>l2>>r2;
        if(getSeg(l1,r1) == getSeg(l2,r2)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/354686.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

2024-01-24-redis4

2024-01-24-redis4

秒杀活动 需求&#xff1a;库存中有10件商品 商品的信息自定义 同时有100个人去抢购&#xff08;这里100个人的抢购由jmeter来模拟&#xff09; jmeter的使用 在idea中将后台代码实现 package org.aaa.controller;import org.apache.commons.lang3.StringUtils; import org.sp…
阅读更多...
goland课程管理(6)

goland课程管理(6)

项目目录结构如下图所示&#xff1a; core包下面&#xff1a; class.go package coreimport "github.com/gin-gonic/gin"func Class1(ctx *gin.Context) {}course.go package coreimport (. "cookie/database". "cookie/model""fmt"…
阅读更多...
服务端开发小记02——Maven

服务端开发小记02——Maven

这里写目录标题 Maven简介Maven在Linux下的安装Maven常用命令 Maven简介 Apache Maven Project是一个apache的开源项目&#xff0c;是用于构建和管理Java项目的工具包。 用Maven可以方便地创建项目&#xff0c;基于archetype可以创建多种类型的java项目&#xff1b;Maven仓库…
阅读更多...
华为三层交换机与防火墙对接配置上网示例

华为三层交换机与防火墙对接配置上网示例

三层交换机与防火墙对接上网配置示例 组网图形 图1 三层交换机与防火墙对接上网组网图 三层交换机简介配置注意事项组网需求配置思路操作步骤配置文件 三层交换机简介 三层交换机是具有路由功能的交换机&#xff0c;由于路由属于OSI模型中第三层网络层的功能&#xff0c;所以…
阅读更多...
VMware 虚拟机环境下的ubuntu 上安装mysql,并能远程访问数据库

VMware 虚拟机环境下的ubuntu 上安装mysql,并能远程访问数据库

需求&#xff1a;为了实现在linux上模拟服务器跑代码&#xff0c;并存储在mysql上&#xff0c;通过远程可视化mysql数据库软件查看linux上mysql数据库数据的实时动态。 1. 虚拟机和ubuntu的安装 这里我选择的是VMware workstation-v14, ubuntu-18.04.1。至于体流程网上很多&a…
阅读更多...
基于Java的高校运动会管理系统的设计与实现(源码+lw+部署文档+讲解等)

基于Java的高校运动会管理系统的设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言 详细视频演示 具体实现截图 技术栈 后端框架SpringBoot 前端框架Vue 持久层框架MyBaitsPlus 系统测试 系统测试目的 系统功能测试 系统测试结论 代码参考 数据库参考 源码获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、…
阅读更多...
Django ORM 框架中的表关系，你真的弄懂了吗？

Django ORM 框架中的表关系，你真的弄懂了吗？

Django ORM 框架中的表关系 前言 Django ORM 框架中的表关系 为了说清楚问题&#xff0c;我们设计一个 crm 系统&#xff0c;包含五张表&#xff1a; 1.tb_student 学生表 2.tb_student_detail 学生详情表 3.tb_salesman 课程顾问表 4.tb_course 课程表 5.tb_entry 报名表…
阅读更多...
Vue2.0+Element实现日历组件

Vue2.0+Element实现日历组件

(壹)博主介绍 &#x1f320;个人博客&#xff1a; 尔滨三皮⌛程序寄语&#xff1a;木秀于林&#xff0c;风必摧之&#xff1b;行高于人&#xff0c;众必非之。 (贰)文章内容 1、安装依赖 npm install moment2.29.4 --savenpm install lunar0.0.3 --savenpm install lunar-java…
阅读更多...
C语言数据结构——链表

C语言数据结构——链表

&#xff08;图像由AI生成&#xff09; 0.前言 在计算机科学中&#xff0c;数据结构是存储和组织数据的一种方式&#xff0c;它不仅影响数据的存储&#xff0c;也影响数据的检索和更新效率。C语言&#xff0c;作为一种经典的编程语言&#xff0c;提供了灵活的方式来处理数据…
阅读更多...
OkHttp完全解读

OkHttp完全解读

一&#xff0c;概述 OkHttp作为android非常流行的网络框架&#xff0c;笔者认为有必要剖析此框架实现原理&#xff0c;抽取并理解此框架优秀的设计模式。OkHttp有几个重要的作用&#xff0c;如桥接、缓存、连接复用等&#xff0c;本文笔者将从使用出发&#xff0c;解读源码&am…
阅读更多...
iOS 文件分割保存加密

iOS 文件分割保存加密

demo只是验证想法&#xff0c;没有做很多异常处理 默认文件是大于1KB的&#xff0c;对于小于1KB的没有做异常处理demo中文件只能分割成2个&#xff0c;可以做成可配置的N个文件分割拼接还可以使用固定的二进制数据&#xff0c;拼接文件开头或结尾 不论哪种拼法&#xff0c;目的…
阅读更多...
牛客周赛30

牛客周赛30

思路&#xff1a;先把x, y除以最大公约数变成最小值&#xff0c;然后同时乘以倍数cnt&#xff0c;只记录两个数都在[l,r]间的倍数。 代码&#xff1a; int gcd(int a,int b){return b ? gcd(b, a % b) : a; }void solve(){int x, y, l, r;cin >> x >> y >>…
阅读更多...
两两交换链表中的结点---链表OJ

两两交换链表中的结点---链表OJ

https://leetcode.cn/problems/swap-nodes-in-pairs/description/?envType=study-plan-v2&envId=top-100-liked 1、递归 创建newhead = head->next，然后将head->next->next作为递归参数,返回值用head->next接收；递归结束条件是：没有结点或者只有一…
阅读更多...
Python代码耗时统计

Python代码耗时统计

time模块 在代码执行前后各记录一个时间点&#xff0c;两个时间戳相减即程序运行耗时。这种方式虽然简单&#xff0c;但使用起来比较麻烦。 time.time() 函数返回的时间是相对于1970年1月1日的秒数 import timestart time.time() time.sleep(1) end time.time() print(f&…
阅读更多...
洛谷 P2150 [NOI2015] 寿司晚宴

洛谷 P2150 [NOI2015] 寿司晚宴

P2150 [NOI2015] 寿司晚宴 约定&#xff1a; n ≤ 500 n \leq 500 n≤500 题意 给定 2 → n 2 \rightarrow n 2→n 共 n − 1 n-1 n−1 个数字&#xff0c;现在两个人想分别取一些数字&#xff08;不一定全取完&#xff09;&#xff0c;如果他们两人取的数字中存在&#xf…
阅读更多...
05. java线程基础

05. java线程基础

05. java线程基础 01. 线程相关概念 1. 程序 ​ 是为完成特定任务、用某种语言编写的一组指令的集合。简单来说&#xff1a;就是我们写的代码 2. 进程 进程是指运行中的程序&#xff0c;比如我们使用微信&#xff0c;就启动了一个进程&#xff0c;操作系统会为该进程分配内…
阅读更多...
【代码随想录】LC 242. 有效的字母异位词

【代码随想录】LC 242. 有效的字母异位词

文章目录 前言一、题目1、原题链接2、题目描述 二、解题报告1、思路分析2、时间复杂度3、代码详解 前言 本专栏文章为《代码随想录》书籍的刷题题解以及读书笔记&#xff0c;如有侵权&#xff0c;立即删除。 一、题目 1、原题链接 242. 有效的字母异位词 2、题目描述 二、解题…
阅读更多...
一文理清楚-Docker 容器如何工作

一文理清楚-Docker 容器如何工作

Docker 容器如何工作 集装箱什么是虚拟机&#xff1f;虚拟化如何运作&#xff1f;什么是容器&#xff1f;什么是 Docker&#xff1f;总结 五星上将麦克阿瑟曾经说过&#xff1a;在docker面前&#xff0c;虚拟机就是个弟弟 集装箱 《盒子&#xff1a;集装箱如何让世界变得更小&…
阅读更多...
剑指offer——删除链表的节点

剑指offer——删除链表的节点

题目描述&#xff1a;给定单向链表的头指针和一个要删除的节点的值&#xff0c;定义一个函数删除该节点。返回删除后的链表的头节点。 数据范围&#xff1a; 0 <链表节点值 < 10000 0 <链表长度 < 10000 示例1&#xff1a; 输入&#xff1a;{2,5,1,9}&#xff…
阅读更多...
1.28寒假集训

1.28寒假集训

A: 解题思路&#xff1a; 移项就好v mv / (M - m) 下面是c代码&#xff1a; #include<iostream> using namespace std; int main() {int t;double M,m,v;cin >> t;while(t ! 0){cin >> M >> m >> v;printf("%.2lf\n",(m * v) / (M…
阅读更多...
最新文章

Copyright @ 2022~2023