【基础算法模板梳理】再也不想学算法了！（待更新）

目录

1、【二分】

（1）r=mid —— 大于等于某数的最小值 

（2）l=mid —— 小于等于某数的最大值

2、【前缀和】

（1）一维前缀和

（2）二维前缀和

3、【差分】

（1）一维差分

（2）二维差分

4、【单调栈】

（1）单调递增栈

（2）单调递减栈

5、【并查集】

6、【BFS 求最短路】

为什么BFS可以求最短路？

7、【Dijkstra】

8、【spfa】

9、【floyd】

10、【kruskal】

11、【质数】

12、【约数】

1、【二分】

【蓝桥杯集训3】二分专题（3 / 5）-CSDN博客

  • l + r >> 1 —— 先 r = mid 后 l = mid+1 —— 寻找左边界 —— 找大于等于某数的最小值
  • l+r+1>>1 —— 先 l = mid 后 r = mid-1 —— 寻找右边界 —— 找小于等于某数的最大值

（1）r=mid —— 大于等于某数的最小值 

1 2 3 3 3 3 4 5

int l=0,r=n-1;

while(l<r)
{
    int mid=l+r>>1;

    if(a[mid]>=x) r=mid;
    else l=mid+1;
}

（2）l=mid —— 小于等于某数的最大值

1 2 3 3 3 3 4 5

int l=0,r=n-1;

{
    int mid=l+r+1>>1;

    if(a[mid]<=x) l=mid;
    else r=mid-1;
}

2、【前缀和】

【蓝桥杯集训1】前缀和专题（4 / 5）-CSDN博客

（1）一维前缀和

a数组下标从1开始，Si = Si-1 + ai

则 [ Al，Ar ]段的和 = s[r] - s[l-1]

for(int i=1;i<=n;i++)
{
    a[i]=sc.nextInt();
    s[i]=s[i-1]+a[i];
}
        
[Al,Ar]的和 = s[r]-s[l-1]

（2）二维前缀和

 

static int N=1010;
static int[][] a=new int[N][N],s=new int[N][N];
    
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        a[i][j]=sc.nextInt();
        s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
    }

while(q-->0)
{
    int x1=sc.nextInt(),y1=sc.nextInt(),x2=sc.nextInt(),y2=sc.nextInt();

    int res=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];

    System.out.println(res);
}

3、【差分】

【蓝桥杯集训2】差分专题（3 / 4）-CSDN博客

（1）一维差分

给a数组 [l,r] 区间的每个数+c，只需要给其差分数组b做如下操作即可

b[l]+=c;
b[r+1]-=c;

构造差分数组   \large b\left [ i \right ]=a\left [ i \right ]-a\left [ i-1 \right ]

int[] a=new int[N];
int[] b=new int[N];

for(int i=1;i<=n;i++)
{
    a[i]=sc.nextInt();
    b[i]=a[i]-a[i-1]; //构造差分数组
}

差分数组进行  \large b\left [ l \right ]+=c    \large b\left [ r+1 \right ]-=c 操作

int l,r,c;
while(k-->0)
{
    b[l]+=c;
    b[r+1]-=c;
}

最后求差分数组b的前缀和即为原数组在【l，r】段+c的数组

for(int i=1;i<=n;i++)
{
    a[i]=a[i-1]+b[i]; //b的前缀和是a
    System.out.print(a[i]+" ");
}

（2）二维差分

 初始化

static int N=1010;
static int[][] a=new int[N][N],b=new int[N][N];
 
public static void work(int x1,int y1,int x2,int y2,int c)
{
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}
 

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        a[i][j]=sc.nextInt();
        work(i,j,i,j,a[i][j]);
    }

求前缀和

work(x1,y1,x2,y2,c);
 
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=m;j++)
    {
        b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
        System.out.print(b[i][j]+" ");
    }
    System.out.println();
}

4、【单调栈】

【蓝桥杯集训9】单调栈、单调队列（模拟栈、模拟队列）专题（3 / 3）_Roye_ack的博客-CSDN博客

（1）单调递增栈

  • 在保持栈内元素单调递增前提下（如果栈顶元素大于待入栈元素，弹出栈顶），新元素入栈
  • 对于要入栈的元素，在对栈进行更新后，栈顶元素就是数组中左侧第一个比自己小的元素

（2）单调递减栈

  • 在保持栈内元素单调递减前提下（如果栈顶元素小于要待入栈元素，弹出栈顶），新元素入栈
  •  对于要入栈的元素，在对栈进行更新后，栈顶元素就是数组中左侧第一个比自己大的元素

题目：输出每个数左边第一个比自己小的数，如果不存在则输出-1 

class Main
{
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        Deque<Integer> stk=new LinkedList<>();

        while(n-->0)
        {
            int x=sc.nextInt();

            while(!stk.isEmpty()&&stk.peek()>=x) stk.pop();

            if(stk.isEmpty()) System.out.print("-1 ");
            else System.out.print(stk.peek()+" ");

            stk.push(x);
        }
    }
}

 

5、【并查集】

【蓝桥杯集训7】并查集专题（3 / 5）-CSDN博客

int find(int x) //返回x的祖宗结点+状态压缩
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
 
p[find(a)]=find(b); //合并操作 给a认个祖宗b
 
if(find(a)==find(b)) //a和b元素在同一个集合
 
for(int i=1;i<=n;i++) p[i]=i;
import java.util.*;
 
class Main
{
    static int N=100010;
    static int[] p=new int[N];
    
    public static int find(int x)
    {
        if(p[x]!=x) p[x]=find(p[x]); //如果不是祖宗，则向上查找
        return p[x];
    }
    
    public static void unite(int a,int b)
    {
        p[find(a)]=find(b); //给a认个祖宗b
    }
    
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        
        for(int i=1;i<=n;i++) p[i]=i;
        
        while(m-->0)
        {
            String s=sc.next();
            int a=sc.nextInt(),b=sc.nextInt();
            
            if(s.equals("M"))
            {
                if(find(a)!=find(b)) unite(a,b);
            }
            else 
            {
                if(find(a)==find(b)) System.out.println("Yes");
                else System.out.println("No");
            }
        }
    }
}

 

6、【BFS 求最短路】

【蓝桥杯集训11】BFS（4 / 4）_Roye_ack的博客-CSDN博客

为什么BFS可以求最短路？

为什么就算有多条通路，它总能输出最小距离？
因为当第一个点到达终点时，它一定是最短距离，并且会将终点标记，那么其他点再也无法到达终点，也更新不了初始点到终点的距离

将起点（0，0）入队，上下左右走，只要在合法的范围内且不碰到墙且没有走过，则入队

BFS就是将所有能走的路都走，第一条能走通的路一定是最短路

    static int[][] g=new int[110][110];
    static int[][] d=new int[110][110];  //记录该点到起点的最短距离
    static int[][] st=new int[110][110];  //标记走过的点
    static int[] dx={-1,1,0,0};
    static int[] dy={0,0,-1,1};    //方向数组
    public static int bfs()
    {
        d[0][0]=0;
        
        Queue<PII> q=new LinkedList<>();
        q.offer(new PII(0,0));
        
        while(!q.isEmpty())
        {
            PII t=q.poll();
            for(int i=0;i<4;i++)
            {
                int nx=t.x+dx[i];
                int ny=t.y+dy[i];
                if(nx>=0&&nx<n&&ny>=0&&ny<m&&g[nx][ny]==0&&st[nx][ny]==0)
                {
                    q.offer(new PII(nx,ny));
                    d[nx][ny]=d[t.x][t.y]+1;
                    st[nx][ny]=1;
                }
            }
        }
        return d[n-1][m-1];
    }

 

7、【Dijkstra】

8、【spfa】

9、【floyd】

10、【kruskal】

11、【质数】

12、【约数】

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

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

相关文章

Mac代码文本编辑器Sublime Text 4

Mac代码文本编辑器Sublime Text 4

Sublime Text 4 for Mac拥有快速响应的功能&#xff0c;可以快速加载文件和执行命令&#xff0c;并提供多种语言支持&#xff0c;包括C 、Java、Python、HTML、CSS等。此外&#xff0c;该编辑器还支持LaTeX、Markdown、JSON、XML等技术领域。 Sublime Text 4 for Mac的插件丰富…
阅读更多...
Ubuntu18.04.6共享文件夹的创建，以及在哪打开共享文件夹

Ubuntu18.04.6共享文件夹的创建，以及在哪打开共享文件夹

目录 1、打开虚拟机的设置页面 2、设置共享文件夹 3、确认是否成功设置共享文件夹 4、完成后在进入到/mnt/hgfs ls查看&#xff0c;发现共享文件夹已经出现可以使用 1、打开虚拟机的设置页面 两种方式&#xff1a; &#xff08;1&#xff09;直接点击“编辑虚拟机设置” …
阅读更多...
YOLO目标检测——海洋目标检测数据集下载分享【含对应voc、coco和yolo三种格式标签】

YOLO目标检测——海洋目标检测数据集下载分享【含对应voc、coco和yolo三种格式标签】

实际项目应用&#xff1a;海洋监管、海洋资源开发、海洋科学研究数据集说明&#xff1a;海洋目标检测数据集&#xff0c;真实场景的高质量图片数据&#xff0c;数据场景丰富&#xff0c;含有“金属”、“未知”、“橡胶”、“平台”、“塑料”、“木材”、“布”、“纸张”、“…
阅读更多...
SAP S4后的一些注意点(一)（更新中）

SAP S4后的一些注意点(一)（更新中）

SAP 此外&#xff0c;我们必须确保 P10 中所有新的 Unicore 代码都是云就绪的。因此&#xff0c;在 ATC 中增加了一项新的检查&#xff08;自定义&#xff09;&#xff0c;以证明代码的云就绪性。此外&#xff0c;我们还在 ADT 中安装了一个名为 ABAP Cleaner 的新插件&#xf…
阅读更多...
初探SVG

初探SVG

SVG&#xff0c;可缩放矢量图形&#xff08;Scalable Vector Graphics&#xff09;。使用XML格式定义图像。SVG有以下优点&#xff1a;1&#xff09;可被非常多的工具读取和修改&#xff1b;2&#xff09;比JPEG和GIF尺寸更小&#xff0c;可压缩性更强&#xff1b;3&#xff09…
阅读更多...
多门店民宿预定系统酒店预订管理系统源码/公寓/农家乐小程序源码

多门店民宿预定系统酒店预订管理系统源码/公寓/农家乐小程序源码

技术栈&#xff1a; thinkphpuniappmysql 支持H5APP小程序 主要功能介绍&#xff1a; 在线预订 支持在线支付或到店付&#xff0c;支持配置免费取消订单时长&#xff0c;支持到店付保留时长设置 房间搜索 支持按日期搜索房间状态&#xff0c;支持按日期区间搜索房间状态…
阅读更多...
置换环算法

置换环算法

参考该博客大佬的讲解 置换环 - TTS-S - 博客园 (cnblogs.com) 置换环&#xff1a;一般用于解决数组排序元素间所需最小交换次数这类问题。 置换环思想&#xff1a;置换环是将每个元素指向其应在的位置&#xff0c;最终相连成一个环(若元素就在其应在的位置&#xff0c;则自身…
阅读更多...
乡村振兴 品牌引领 “盘锦碱地柿子”亮相第二十届中国国际农产品交易会

乡村振兴 品牌引领 “盘锦碱地柿子”亮相第二十届中国国际农产品交易会

2023年11月9日&#xff0c;为期4天的第二十届中国国际农产品交易会在山东青岛成功举办。本次大会以“奋进新征程强农促振兴”为主题。农交会是经党中央、国务院批准&#xff0c;农业农村部主办的大型农业行业盛会&#xff0c;在宣传“三农”政策、展示农业农村发展成就、活跃农…
阅读更多...
OSG练习：模仿Ventsim制作三维矿井智能通风系统

OSG练习：模仿Ventsim制作三维矿井智能通风系统

1、效果 2、计划内容 1） 三维场景的加载显示；已实现 2）矿井巷道建模及纹理；已实现 3）矿井基础数据采集及修正；已实现 4）通风网络解算算法；已实现 5）通风设备及设施模型制作；未实现 6）风流模拟效果 ；进行中 7）火灾模拟效果；未实现 8）巷道属性查看栏；未实现 9）…
阅读更多...
【Linux网络】系统调优之时间同步，搭建内网时间同步服务器

【Linux网络】系统调优之时间同步，搭建内网时间同步服务器

目录 一、时间同步是什么 二、时间同步实验 pc1的chrony配置修改&#xff1a; pc2和pc3时间同步配置一样 关于时间调整再同步回来&#xff1a;ntpdate命令 最后&#xff0c;再总结一下&#xff08;关于服务端口&#xff09;&#xff1a; 三、命令记录 一、时间同步是什…
阅读更多...
[极客大挑战 2019]Upload 1

[极客大挑战 2019]Upload 1

题目环境&#xff1a; 根据题目和环境可知此题目是一道文件上传漏洞 编写一句话木马脚本<?php eval($_POST[shell]);?>将脚本文件更改为jpg图片文件我这里是flag.jpg上传文件并burpsuite抓包Repeater重放 报错一句话木马里面有<?字符 换一种一句话木马继续编写木马…
阅读更多...
【JAVA学习笔记】 68 - 网络——TCP编程、UDP编程

【JAVA学习笔记】 68 - 网络——TCP编程、UDP编程

项目代码 https://github.com/yinhai1114/Java_Learning_Code/tree/main/IDEA_Chapter21/src 网络 一、网络相关概念 1.网络通讯 1.概念:两台设备之间通过网络实现数据传输 2.网络通信:将数据通过网络从一台设备传输到另一台设备 3. java.net包下提供了一系列的类或接口&a…
阅读更多...
简单得令人尴尬的FSQ：“四舍五入”超越了VQ-VAE

简单得令人尴尬的FSQ：“四舍五入”超越了VQ-VAE

©PaperWeekly 原创 作者 | 苏剑林 单位 | 月之暗面 研究方向 | NLP、神经网络 正如 “XXX is all you need” 一样&#xff0c;有不少论文都以“简单得令人尴尬”命名&#xff08;An Embarrassingly Simple XXX&#xff09;&#xff0c;但在笔者看来&#xff0c;这些论文…
阅读更多...
Oracle（16）Managing Privileges

Oracle（16）Managing Privileges

目录 一、基础知识 1、Managing Privileges管理权限 2、System Privileges 系统特权 3、System Privileges : Example系统权限&#xff1a;示例 4、Who Can Grant or Revoke? 谁可以授予或撤销权限&#xff1f; 5、The PUBLIC 6、SYSDBA and SYSOPER 7、Revoke with A…
阅读更多...
3D模型人物换装系统

3D模型人物换装系统

3D模型人物换装系统 介绍遇到的问题问题修复具体实现换装1.准备所有模型部位和模型骨骼部位准备材质准备模型根骨骼准备创建文件夹将上述模型拖成预制体创建一个动画状态机给他们附上待机动画 2.脚本驱动Mesh合并代码 UCombineSkinnedMgr.cs创建Mesh以及实例化对象的代码 UChar…
阅读更多...
一文带你了解栈的基本概念以及栈的实现

一文带你了解栈的基本概念以及栈的实现

✏️✏️✏️今天给大家分享一下栈的基本概念、线性栈的自定义实现&#xff0c;以及栈的应用题目。 清风的CSDN博客 &#x1f61b;&#x1f61b;&#x1f61b;希望我的文章能对你有所帮助&#xff0c;有不足的地方还请各位看官多多指教&#xff0c;大家一起学习交流&#xff01…
阅读更多...
阿里云配置ECS实例的IPv6地址，开通公网IPv6

阿里云配置ECS实例的IPv6地址，开通公网IPv6

1.阿里云ECS服务器开通IPv6地址&#xff0c;开通公网IPv6 1.1.官网教程 配置ECS实例的IPv6地址 1.2.相关截图 1 2 3 4 5 6
阅读更多...
ElasticSearch中常见的分词器介绍

ElasticSearch中常见的分词器介绍

文章目录 ElasticSearch中常见的分词器介绍前言分词器的作用如何指定分词器分词器的组成分词器的类型标准分词器空格分词器简单分词器关键词分词器停用词分词器IK分词器NGram分词器正则匹配分词器语言分词器自定义分词器 ElasticSearch中常见的分词器介绍 前言 ElasticSearch是…
阅读更多...
抖音小程序开发：探索技术创新的代码之旅

抖音小程序开发：探索技术创新的代码之旅

随着抖音小程序的兴起&#xff0c;企业纷纷将目光投向这个充满活力的平台。抖音小程序开发不仅为品牌提供了更广泛的曝光机会&#xff0c;更是技术创新的舞台。本文将带领读者深入探索抖音小程序开发的技术要点&#xff0c;探讨如何通过代码实现个性化、高效的小程序。 1. 小…
阅读更多...
【2】Gradle-快速入门使用【Gradle项目结构概念】

【2】Gradle-快速入门使用【Gradle项目结构概念】

目录 【2】Gradle-快速入门使用【Gradle项目结构概念】安装本地安装先决条件 官网安装教程 Gradle 快速指南初始化项目查看Gradle的项目结构了解Gradle Wrapper调用Gradle包装器了解Gradle的项目结构了解settings文件了解构建脚本 IDEA中使用Gradle创建一个新项目创建一个Sprin…
阅读更多...
最新文章

Copyright @ 2022~2023