- 博客(28)
- 收藏
- 关注
RSS订阅原创 蓝桥杯ALGO-3 K好数
题目描述如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大，请你输出它对1000000007取模后的值。为啥能想到dp呢package 算法训练;/** * * k好数 * @author vccyb * */import java.io.*;import java.math.BigInteg
2020-07-15 15:12:05
137
原创 蓝桥杯ALGO-2 最大最小公倍数
题目描述已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。一开始我就是这样想的，但是不对注意点：用long、还有记得n%3的情况package 算法训练;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;/** * * * * @author vccyb * */public class P002 { p
2020-07-14 21:46:37
130
原创 蓝桥杯ALGO-1 区间k大数查询
题目描述给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个考察：排序package 算法训练;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;/** * * 区间k大数查询 * @author vccyb * 给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。 */p
2020-07-14 21:11:31
135
原创 动态规划——线性DP
文章目录数字三角形数字三角形package Chapter5;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;/** * * DP 数字三角形 * @author vccyb * */public class P898 { static final int N = 510; static i
2020-06-12 20:23:14
112
原创 数学知识——质数
文章目录质数试除法质数试除法题目给定n个正整数ai，判定每个数是否是质数。题解 static boolean is_prime(int n){ if(n<2) return false; for(int i=2;i<=n/i;i++){ if(n%i==0) return false; } return true; }...
2020-06-01 21:31:56
166
原创 搜索与图论——BFS
文章目录BFS题解BFS宽搜题目：给定一个n*m的二维整数数组，用来表示一个迷宫，数组中只包含0或1，其中0表示可以走的路，1表示不可通过的墙壁。最初，有一个人位于左上角(1, 1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角(n, m)处，至少需要移动多少次。数据保证(1, 1)处和(n, m)处的数字为0，且一定至少存在一条通路。题解package Chapter3;import java.io.BufferedReader;
2020-05-30 15:01:20
258
原创 搜索与图论——DFS
文章目录DFS题解题解2总结DFSwhat DFS?DFS： 深度优先搜索用个全排列的问题来看题解package Chapter3;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class P842 { static final int N = 10; static int[] path = new int[N]; st
2020-05-30 11:13:34
181
原创 数据结构——哈希表
文章目录哈希表题解哈希表哈希表：就是把一堆数据映射到从零到n映射的函数就是哈希函数，一般是取模二大类：开放寻址发拉链法题目题解维护一个集合，支持如下几种操作：“I x”，插入一个数x；“Q x”，询问数x是否在集合中出现过；现在要进行N次操作，对于每个询问操作输出对应的结果。1≤N≤105−109≤x≤109109 太大了，开一个这样的数组浪费，所以可以用的哈希表...
2020-05-29 15:31:11
200
原创 数据结构——堆
文章目录堆题解堆堆的基础操作：down和up题目输入一个长度为n的整数数列，从小到大输出前m小的数用到的堆操作：down操作即可，把堆构建处理就OK输出min heap[1],heap[1]=heap[n–],down(1);题解...
2020-05-27 22:16:36
150
原创 数据结构——并查集
文章目录并查集题解模板并查集并查集就两个操作：一个合并集合、一个查询是2个元素是否在同一集合内题目一共有n个数，编号是1~n，最开始每个数各自在一个集合中。现在要进行m个操作，操作共有两种：“M a b”，将编号为a和b的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；“Q a b”，询问编号为a和b的两个数是否在同一个集合中；题解这只是朴素并查集模板(1)朴素并查集： int p[N]; //存储每个点的祖宗节点 // 返回x的祖宗节点
2020-05-27 10:21:14
185
原创 数据结构——Trie字符串
文章目录Trie 字符串模板Trie 字符串Trie字符串:快速存储字符串集合那么它是怎么样的一种结构呢？？特点：字母的个数不会很多，why？来看代码的实现吧题目AcWing835 Trie字符串维护一个字符串集合，支持两种操作：“I x”向集合中插入一个字符串x；“Q x”询问一个字符串在集合中出现了多少次。共有N个操作，输入的字符串总长度不超过 105，字符串仅包含小写英文字母。模板 static int[][] son = new int[N][26];//只存储小
2020-05-26 15:58:06
196
原创 数据结构——kmp字符串
文章目录kmp字符串kmp字符串kmp是一种高效存储字符串匹配的算法简单来说就是给定一个模式（母）串S，以及一个模板（子）串P求出模板（子）串P在模式（母）串S中所有出现的位置的起始下标。当然你也可以暴力的去做，但是不如看看kmp的想法吧遇到两个字符不匹配的情况时，希望可以多跳几个字符，减少比较次数KMP算法的思想是：在模式串和主串匹配过程中，当遇到不匹配的字符时，对于主串和模式串中已对比过相同的前缀字符串，找到长度最长的相等前缀串，从而将模式串一次性滑动多位，并省略一些比较过程。看
2020-05-26 15:20:18
153
原创 数据结构——单调队列
文章目录单调队列题解单调队列队列我们知道，那么单调队列就是队列中存储一列上升或者下降的数单调队列的典型应用就是处理滑动窗口问题让我们来看看吧AcWing154 滑动窗口给定一个大小为n≤106的数组。有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。您只能在窗口中看到k个数字。每次滑动窗口向右移动一个位置。以下是一个例子：该数组为[1 3 -1 -3 5 3 6 7]，k为3。懂了不？这就是单调队列优化求解滑动窗口问题题解package Chapter2;im
2020-05-25 22:59:28
176
原创 数据结构——单调栈
文章目录单调栈题解单调栈单调栈可以用来优化最常用的情景：给定一个序列，找到序列每一个数左边离它最近且比他小的数题目给定一个长度为N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出-1。3 4 2 7 5-1 3 -1 2 2结论：我们用栈存储一列升序的数，取栈顶即可，当添加一个数时，也必须保证升序，将比他大的删除，即tt–题解模板import java.io.*;/** * P830 单调栈 * @author vccyb * */public clas
2020-05-25 09:40:38
193
原创 数据结构——模拟队列
文章目录模拟队列普通队列模板模拟队列队列是和栈相对的栈是后进先出，像一个有底的桶队列是先进先出，就像排队一样队列也有两种：普通队列循环队列普通队列有队头和队尾当队头大于队尾时说明当前队为空插入一个数、是从队尾插入、所以++tt弹出一个数、是从队头弹出，所以hh++题目：实现一个队列，队列初始为空，支持四种操作：(1) “push x” – 向队尾插入一个数x；(2) “pop” – 从队头弹出一个数；(3) “empty” – 判断队列是否为空；(4) “qu
2020-05-24 19:47:26
430
原创 数据结构——模拟栈
文章目录模拟栈题解模板模拟栈栈是一种什么结构,后进先出题解题目AcWing 828实现一个栈，栈初始为空，支持四种操作：(1) “push x” – 向栈顶插入一个数x；(2) “pop” – 从栈顶弹出一个数；(3) “empty” – 判断栈是否为空；(4) “query” – 查询栈顶元素。现在要对栈进行M个操作，其中的每个操作3和操作4都要输出相应的结果。模板 //1.定义一个 栈 private static final int N = 100010; priv
2020-05-24 17:16:34
189
原创 数据结构——双链表
文章目录双链表题解模板目标：掌握双链表的数据结构双链表来看看什么是双链表吧双链表与单链表的区别，单链表是单项的、而双链表是有左右的题目Acwing 827实现一个双链表，双链表初始为空，支持5种操作：(1) 在最左侧插入一个数；(2) 在最右侧插入一个数；(3) 将第k个插入的数删除；(4) 在第k个插入的数左侧插入一个数；(5) 在第k个插入的数右侧插入一个数现在要对该链表进行M次操作，进行完所有操作后，从左到右输出整个链表。注意:题目中第k个插入的数并不是指当前链表的第k
2020-05-24 15:22:04
240
原创 数据结构——单链表
文章目录单链表题解模板目标：掌握单链表的数据结构单链表单链表常用于存储树和图我们这里用用数组模拟单链表 用数组效率高，而且让我们更加的理解单链表的数据结构理解了我画的图，你就知道了单链表需要存储两个信息值下一个的索引单链表的操作ok，基础的操作就这三个、其余的操作也基本可以通过这三个得到题目AcWing826 单链表实现一个单链表，链表初始为空，支持三种操作：(1) 向链表头插入一个数；(2) 删除第k个插入的数后面的数；(3) 在第k个插入的数后插入一个数现在要
2020-05-24 14:50:52
166
原创 基本算法——区间合并
文章目录区间合并题解目标：掌握区间合并区间合并什么是区间合并？那么如何合并呢？按左端点排序，然后比较第一个的右端点和下一个的左端点、大于或者等于就合并，否则就又从新的区间开始，合并后呢？右端点就要更新哦题目题解给定 n 个区间 [li,ri]，要求合并所有有交集的区间。注意如果在端点处相交，也算有交集。输出合并完成后的区间个数。例如：[1,3]和[2,6]可以合并为一个区间[1,6]。...
2020-05-24 09:28:22
508
原创 基本算法——位运算
文章目录位运算目标：掌握位运算，这种一种小技巧位运算Integer.toBinaryString(i) //转化为2进制字符串Integer.bitCount(i) // 统计二进制中1的个数
2020-05-24 08:24:41
136
原创 基本算法——双指针算法
文章目录双指针算法模板题解目标:掌握双指针的解题方法注意:双指针的题目首先想暴力解法,然后想双指针的优化方法一般用双指针的前提是单调性双指针算法模板for (int i = 0, j = 0; i < n; i ++ ){ while (j < i && check(i, j)) j ++ ; // 具体问题的逻辑}常见问题分类： (1) 对于一个序列，用两个指针维护一段区间 (2) 对于两个序列，维护某种次序，比如归并排序中合
2020-05-23 22:31:14
264
原创 基本算法——差分
文章目录一维差分题解模板二维差分题解模板目标，掌握差分的概念、和解题的思路差分就是前缀和的逆过程!!!一维差分什么是一维差分?那么差分可以用来干嘛呢?让我们来看这样一个操作通过差分,我们可以快速对前缀和数组的一个区间的数进去操作再思考,如何构建差分呢??需要构建嘛题目输入一个长度为n的整数序列。接下来输入m个操作，每个操作包含三个整数l, r, c，表示将序列中[l, r]之间的每个数加上c。请你输出进行完所有操作后的序列。题解这里需要注意:我们构造差分的方法是in
2020-05-23 21:15:26
1785
原创 基本算法——前缀和
文章目录一维前缀和题解模板二维前缀和题解模板AcWing795 前缀和AcWing796 二维矩阵的和一维前缀和前缀和的概念：题目：输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对l, r。对于每个询问，输出原序列中从第l个数到第r个数的和。题解看到求区间和、就可以用到前缀和思路：前缀和数组的构建，利用前缀和性质快速求解区间和所以解题的步骤一般就两部前缀和数组的初始化 s[i] = s[i-1] + a[i]求解区间和模板// 1 维S[i]
2020-05-23 17:31:04
375
原创 基本算法——高精度问题
文章目录高精度问题目标：掌握java中高精度类的使用高精度问题主要就是使用大整数类BigInteger使用BigInteger就基本不用考虑很多问题了Chapter1;import java.io.*;import java.math.BigInteger;import java.util.*;public class Div { public static void main(String[] args)throws IOException { Buffered
2020-05-23 11:10:00
332
原创 基本算法——二分法
文章目录整数二分题解模板浮点二分题解目标：掌握整数二分和浮点二分，了解二分的思想AcWing789 数的范围 整数二分AcWing790 数的三次方根 浮点二分这里我要反思之前写的两篇博客，感觉内容上自己思考的太少、而且细节上确实很多点没有讲到以后会经量把自己的思路也加上去、希望大家能看的更加明白整数二分题目：给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。如果数组中不存在该元素，则返回“-1
2020-05-23 10:45:53
677
原创 基本算法——并归排序
掌握并归排序AcWing787 并归排序AcWing788 逆序对的数量目录并归排序并归排序的应用-逆序对的数量并归排序并归排序的核心思想是分治分界点递归左右并归分到不可再分后、合起来就是排序好的了// 输入和快排的一样public static void mergeSort(int[] arr, int l, int r){ //递归结束条件 if(l >= r) return; //1. 获得分界点，注意一定是mid,是索引，而不是值
2020-05-22 22:10:45
923
原创 基本算法——快速排序
基础算法——快速排序AcWing P785 快速排序AcWing P786 第k个数1. 快排快排的核心思想：确定分界点，可以是q[l],q[(l+r)/2]或q[r],我们选用q[l]调整区间，就是将就是把所有比分界点大的放到右边，所有比分界点小的放到左边如何调整？双指针，一个从左往右走知道找到比分界点大的，一个从右往左…找到后，交换，再继续走，直到两指针相遇递归处理 步骤2结束后，再次递归分界点两边的区间// 参数解释：// 1. int[] arr 需要排
2020-05-22 19:51:10
862
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人