Trkly

算法

C++(8) CSS(3) HTML(11) Java(14) JavaScript(7) Python(2) 未归档(1) 杂项(1) 英语(3) 题解(28)

/ 注册

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

质数

质数的概念：大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。注：1即不是质数也不是合数 1.试除法判定质数 //判断一个数n是否是素数 bool isPrime(int n) { for(int i=2;i<=n/i;i++) { if(n...

基础数论

2020-07-17

0 429

线段树和树状数组

线段树引入1：有n个数（n<=50000）个数，m(m<=50000)次询问。每次询问区间L到R的数的和。要求输出每一次询问的结果...... 分析： 1.用前缀和问题进行求解：再开一个数组（暂且记为b[n],设n个数所组成的数组为a[n]），b[i]用来记录从a[1]到a[i]的所...

线段树-树状数组

2020-07-15

0 547

图和树

图-存储结构-邻接矩阵使用邻接矩阵存储图时需要两个数组，一个数组存放图中顶点本身的数据（一维数组），另外一个数组用于存储各顶点之间的关系（二维数组）。存储图中各顶点本身数据，使用一维数组就足够了；存储顶点之间的关系时，要记录每个顶点和其它所有顶点之间的关系，所以需要使用二维数组。不同类型的...

2020-07-14

0 549

前缀，中缀，后缀表达式求值

前缀表达式求值：对于一个前缀表达式的求值而言，首先要从右至左扫描表达式，从右边第一个字符开始判断，如果当前字符是数字则一直到数字串的末尾再记录下来，如果是运算符，则将右边离得最近的两个“数字串”作相应的运算，以此作为一个新的“数字串”并记录下来。一直扫描到表达式的最左端时，最后运算的值也就是表达...

2020-07-14

0 472

全排列问题

首先可以考虑自己写dfs函数对全排列问题进行求解。参考代码如下： #include<iostream> using namespace std; int a[10010],b[10010]; long long int total=0; int n; void dfs(int ...

2020-07-14

0 377

KMP算法总结

KMP算法是一种性能比较好的字符串匹配算法。首先，在理解性能比较好的KMP算法之前，我们首先要先想一下对于字符串匹配的朴素暴力做法我们一般是怎么做出来的。举个例子：对于主串s[n],子串p[m]。我们要计算子串p[m]在主串中出现的位置的话。核心代码一般是下面这个样子的: for(int i...

2020-07-14

0 456

最长公共子序列LCS

根据题目数据范围可以知道算法的时间复杂度应当是O(nlogn)。具体思路应当是将最长公共子序列问题转到最长上升子序列（LIS问题有时间复杂度O(nlogn)）。具体可以参考这篇文章：最长上升子序列例如：求上面两个序列的最长公共子序列，可以将上面的的序列 1 6 5 4 3 2 转换成 1 2...

DP

2020-07-13

0 672