图地芜湖

算法

JVM(5) linux(5) mysql(1) point(1) spring(1) 多线程(3) 好文(1) 我的坑(2) 源码(2) 计网(1) 记录(1) 设计模式(3)

/ 注册

全部文章 / 算法（共22篇）

【算法】lc323 无向图中连通分量的数目

原题链接题目大意 323. 无向图中连通分量的数目给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图中连通分量的数目。示例 1: 输入: n = 5 和 edges = [[0, 1], [1, 2], [3, 4]] 0...

并查集

2021-09-07

1 858

【算法】Acwing836 合并集合（并查集模板题）

原题链接题目大意一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。现在要进行 m 个操作，操作共有两种： M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作； Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中...

并查集

2021-09-07

0 427

【算法】acwing799最长连续不重复子序列双指针模板题

题目链接题目描述给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。输入格式第一行包含整数 n。第二行包含 n 个整数（均在 0∼105 范围内），表示整数序列。输出格式共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。数据范围...

双指针

2021-08-26

0 416

【算法】双指针模板

1、双指针算法的目的：根据单调性质来减少枚举的次数，从而达到时间复杂度的降低。 2、双指针算法的用途： (1)去重，找不重复的序列、数组等； (2)求区间之和或者长度满足条件等；(ps : 对于两个序列的双指针，注意不要超范围 for(;i <a.length &&...

双指针

2021-08-26

0 502

【算法】二分典型题

lc69 x的平方根实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。code class Solution { public int mySqrt(int x) { ...

二分

2021-08-25

0 427

【算法】acwing789 数的范围二分模板题

题目链接给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。如果数组中不存在该元素，则返回 -1 -1。输入格式第一行包含整数 n 和 q，表示数组长度和询问个数。第二行包含 n 个整数（...

二分

2021-08-25

0 415

【算法】二分模板

二分的本质是边界。假设在一个区间上定义了某种性质，整个区间可以被一分为二，使得这个性质在右半段区间满足而在左半段不满足。二分可以寻找边界，既可以找到左半段的右边界a，也可以找到右半段的左边界b l ab r xxxxxxxxxooooooooo...

二分

2021-08-25

1 429

【算法】lc516最长回文子序列区间dp

题目链接给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。经典区间dp题目思路：集合角度解决dp问题 ac code class Solut...

区间dp

2021-08-24

0 373

【算法】acwing 282 石子合并区间dp经典题

原题链接设有 N 堆石子排成一排，其编号为 1，2，3，…，N。每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相...

区间dp

2021-08-24

0 424

【算法】acwing788 逆序对的数量(模板题)

原题连接给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。输入格式第一行包含整数 n，表示数列的长度。第二行包含 n 个整数，表示整...

排序

2021-08-24

0 506