分类:学习基础算法

4 篇文章

初学主席树
今天学长心血来潮,跟我讲了主席树。 身为资深笨比的我从早上琢磨到第二天凌晨才过了主席树的洛谷板子题。赶紧整理一下。 主席树又叫做可持久化线段树,他可以解决区间第k大问题。 问题:给定一系列数,问这些书从第l个数到第r个数这段闭区间内,第k大数是多少。 基于朴素思路思考 最直接的思路就是暴力,每次询问都对这个区间排个序,排好了查一查。显然时间复杂度是…
快速排序和归并排序
最近在补习算法,学一学基础的算法知识 快速排序 快速排序的思路就是从当前的这堆数字里随便挑一个数字x,现在把这个x放在中间,通过某种变化,使得左面<=x,右面>=x能够成立,然后把左右两边也这样排序,递归即可得到最终解。 可以看出算法的步骤如下: 选一个分界数字x(咋选都可以,选第一个数字或者最后一个数字都行,一般选(l+r)/2中值数…
初学KMP
很久之前我一直看不懂KMP算法,看了一个视频里dalao的讲解,我还是没看懂。。。。。。 然后在暑假的某一天,睡觉的时候突然明白了一点点我以前不会的KMP算法,于是赶紧记下来。 如果我希望得知某一个字符串 p 在某一个字符串 s 中是否出现过,或者出现过几次,或者在哪里出现过,那么应该怎么办呢? BF算法 我上来一拍脑门就能想到一种暴力算法,也就是…
递归求全排列
如果现在有六个数字1 2 3 4 5 6,请列举出其所有的排列可能。 从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。显然,这是一个全排列问题。 全排列问题是递归的代表题型。 递归思想 如果我想对从1到6的六个数字做全排列,我可以: 首先,我固定第一个数字…