一、关于manacher算法 马拉车算法,用于求出一个字符串中最长的回文串长度。 二、算法实现思路 1、Manacher算法首先对字符串做一个预处理,在所有的空隙位置(包括首尾)插入同样的符号,要求这个符号是不会在原串中出现的。这样会使得所有的串都是奇数长度的。以插入#号为例: 2、我们把一个回文串中最左或最右位置的字符与其对称轴的距离称为回文半径。Manacher定义了一个回文半径数组RL,用R...

动态规则:数塔问题 有形如下图所示的数塔,从顶部出发,在每一结点可以选择向左走或是向右走,一起走到底层,要求找出一条路径,使路径上的值最大。...

一、为什莫叫快速幂?矩阵快速幂又是什么? 快速幂,是根据幂的二进制最后一位0或1来加速进行乘法运算。 例如,在求5^19时,按照普通的求法就是要19个5相乘,这样虽然可以解出来,但当底数和指数都非常大时,这样计算的时间会很长,其时间复杂度为O(n)。但使用快速幂就要快速很多。其计算原理如下(下面底数用a表示,指数用n表示,下面的tmp初始为a,ans初始为1): n=19的二进制是10011, 此...

文章目录 一、引言 二、使用动态规划优化暴力方法 三、实战演示 下面在介绍动态规划的空间压缩法 一、引言 遇到一到动态规划题后,必须先自己思考找到一个暴力递归求解的方法,然后判断尝试过程是否有后效性。若无后效性,才可以套用动态规划题的模板。这里要说明的是,想出问题的暴力尝试方法这一步是最难的同时也是最重要的,而且没有固定的方法,只能通过不断做题才能又快又好的写出暴力解! 无后效性:是指一个递归状态...

广度优先搜索-BFS的一个常见应用是找出从根结点到目标结点的最短路径,通常这发生在树或图中。我们提供了一个示例来解释在 BFS 算法中是如何逐步应用队列的。 示例:这里我们提供一个示例来说明如何使用 BFS 来找出根结点 A 和目标结点 G 之间的最短路径。 1. 结点的处理顺序是 什么 ? 在第一轮中,处理根结点 在第二轮中,处理根结点旁边的结点; 在第三轮中,处理距根结点两步的结点; &hel...

题目 求解思路 获取输入 分割输入,放入字典中 计算都有哪些项(通过集合的并来实现) 计算这些项对应的值 注意:小数点后只有一位,若某项计算结果为0,则不输出 代码 结果 总结 还是要严谨些!...

子集生成

算法学习

  

2019-12-17 14:52:03

怎样输出一个集合所有的子集呢 1.增量构造法 今天妈妈买了一堆水果,JY非常想吃,但是妈妈想借此机会考验一下JY的智商,说:“你只有把这些水果的全部子集全部展示给我,并写一段代码输出他们所有的子集,你才可以得到这些水果,否则你一个也别想吃。” JY立刻就想到了解决的方法:把水果先放到一个盒子里(盒子A),这个盒子的每个格子都有自己的序号的,我现在想要得到这些水果所有的子集,...

蓝桥杯 K好数 Java

算法学习

  

2019-12-22 12:06:01

蓝桥杯 K好数 Java实现 题目描述 如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字,那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4,L = 2的时候,所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大,请你输出它对1000000007取模后的值。 输入格式 输入包含两个正整数,K和L。 输出格式 输出一个整数,表示答案对10...

解字谜

算法学习

  

2019-12-24 21:32:50

不知道咕咕了多久,我已经记不起来多久没更新了,主要是嘿嘿嘿,妹子太好康了,看着看着就不想写了。嗯,今天就先跟新一点,以后保持活跃呀。 问题介绍 其实是一个挺常见的问题哈,就是大家经常在说说里看到的——一张图,然后说什么第一眼看到的三个单词将会带给你好运啥的(主要是有时候我找了半天也找不出三个像样的单词很气),我们要实现一个利用DFS查找单词的程序。 简单的思路 利用for循...

 在写代码之前需要先了解什么是三次样条插值: 什么是三次样条插值? 所谓三次样条插值对于一个区间(a,b)将区间分成x0 = a < x1 ......xn-1 < b = xn 的n-1个区间,我们需要通过已知的n+1个点来模拟一个未知的函数,在三次样条插值中我们采用分段的方法来做这件事情。 三次样条插值得到的分段函数保证一下条件成立,而这些条件也是用来求解每一段样条插值的...

线段树

算法学习

  

2020-01-14 15:30:20

线段树能把区间上的任意一条长度为 L 的线段都分成不超过 2log L条线段。 因此对于查询或修改某个长度为 L的区间,我们只要在分解 出来的线段上操作,然后在合并这几个区间信息即可。 所以对于一般的操作,单次时间复杂度都是 O(log n) 每个节点维护一个闭区间[l,r] (l<=r)的信息。 根节点表示[1,n]的信息。 如果l==r就是叶子结点。 如果了l<r就是内部节点,他有...

算法的核心思想: 从起点开始,每次以最优解\color{red}{最优解}最优解的思想确认下一个点 思想误区:不是简单地每次取最短的!\color{red}{思想误区:不是简单地每次取最短的!}思想误区:不是简单地每次取最短的! 而是要在记录的基础上取最小的\color{red}{而是要在记录的基础上取最小的}而是要在记录的基础上取最小的 举例: 1.确认起点——A 2.确...

一个五子棋程序 在这种程序中 我们需要把五子棋转换为数组形式 如果需要一个保存内容 我们需要把内容存盘 但是这种11*11的数组 有大量的0 显然不是我们想要的 所以我们可以用稀疏数组来解决这种问题 稀疏数组介绍 稀疏数组也是一个二维数组 他是一个[X][3]的数组 如上图的二维数组可转化: 设 原二维数组是【[X][Y]】 第一列 [0] 代表二维数组的长度X [1]代表二位数组的宽度Y [2]...