一) 贪心 题目 luoguP1155 双栈排序 (主要算法是二分图, 但后面输出方案时的贪心还是挺妙的) 二) 二分/三分 二分/三分答案, 二分/三分查找. 首先要确定函数有 单调性 或 为 单峰函数. 三分可以用二分的形式来做. 三) 搜索 算法dfs bfs 迭代加深搜索 双端队列搜索 记忆化搜索 ... 题目 NOIP2017 逛公园四) 小技巧前缀和 差分 题目 luoguP3943 星空 (异或差分)
时间复杂度表示代码的执行时间随着数据规模增长的趋势。使用O()表示【假设】每一行代码执行的时间都一样，都是unit_time。所有代码的总执行时间 T(n) 与每行代码的执行次数成正比。 1、只关注循环执行次数最多的一段代码def calc(n):"""分析这个代码执行时间，(3+2n)*unit_time，去掉常量，去掉高阶的系数，从而得出时间复杂度就是O(n)"""total = 0 # 执行1次for i in range(0, n + 1): # 执行n+1次total = total + i # 执行n+1...
个人理解 DFS（深度优先搜索）和BFS类似，也是一种简便的图搜索算法，它的主要思想是：访问每一个分支到最深位置，直到不能继续为止。 图解 现在我们要找到从A节点到G节点的路径（不一定是最优的），DFS步骤如下： 1、从根节点A开始，选择节点B的路径，并回溯，直到到达节点E，无法再深入 2、接下来回溯到A，选择节点C的路径，选择E节点时，发现E已经被访问过了，回溯到C节点 3、选择节点F的路径，并且回溯，直到到达G节点 4、这样...
个人理解 BFS是一种最简便的图搜索算法，通过遍历整张图直到找到目标节点； 从算法的角度看，所有因为展开节点而得到的字节点会被存储到一个FIFO的数据结构中，被遍历过的节点存储在一个容器中（一般是一个set），防止重复搜索 图解 如图所示，我们想要获取从S到E节点的最短路径，运用BFS，如何处理？？ 主要思想是：从节点S开始将其所有临近子节点存放到一个队列中，然后标记这些节点到最初顶点S的距离为1； ...
之前提到过的块状链表和在树状数组中提到的块状求前缀和都是用了分块的思想。 分块：将已知数组分成若干块，再进行处理，这样每次只用处理至多块个数个大块和两个边界块 例一：求l-r有多少个数是3的倍数不是6的倍数1<l,r<1e7（此题比较简单，但在这里用上述技巧做） 解：设定每个块的大小为1e3，那么第一个块记录的是1-1e3有多少个满足条件的数，第二个块是1e3+1-2e3，那么最多需要加上1e4左右个大块，在遍历两个边界即可 例二：...
This file is implementation of Common Common Computational Geometry Algorithms.Please please pay attention to input according to the specified data type. 个人实现的一些计算几何中常见的算法，包括点，线，多边形等；所有算法只依赖于C++标准库，不用包含任何其他第三方库，包含此头文件即可使用。使用时请注意按照规定的数据类型进行输入，目前只使用C++来实现算法，具体算法原理会陆续在Github上更新。 目前实现的算法...
问题： /** * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和,并顺序打印子序列。 * 示例: * 输入: [-2,1,-3,4,-1,2,1,-5,4], * 输出: 6，并打印连续子序列 * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 */ 测试main方法: public static void main(String[] args) {int[] data={1,-2,3,4,-8,12,2};System.out.println(subSequenceSum01(data));System.out.println(subSe...
$meet-in-the-middle$（又称折半搜索、双向搜索）对于$n<=40$的搜索类型题目，一般都可以采用该算法进行优化，很稳很暴力。$meet-in-the-middle$算法的主要思想是将搜索区域化为两个集合，分别由搜索树的两端向中间扩展，直到搜索树产生交集，此时即可得到我们的合法情况。通常适用于求经过$n$步变化，从A集合变到B集合需要的方案数问题。对于普通dfs来说，其一大弊端是随着搜索层数的不断增加，搜索的复杂度也会极速增长，而$meet...
离散化 就是把无限空间（在OI中就是很大的范围）里面的信息，映射到一个较小的空间里面 有时候需要保证仍然保留了一些信息，比如元素之间的大小关系，比如相邻两个元素的差（去重w） 一个对闭合区间离散化的小技巧有若干个区间$[L_i,R_i] $，把他们离散化成若干个区间：如何划分？ 集合Sp表示覆盖这个点p的区间编号 将数轴上的点划分成n个区间，每个区间的点等价（区间内的点被覆盖的区间相同，也就是集合Sp相同）； 举个例子： [1...
一、二分查找 1 def binary(binary_para, search):2 bi = int(len(binary_para)/2)3 if search == binary_para[0]:4 print(数存在，并存在在列表第一位)5 elif len(binary_para)>1:6 if binary_para[bi] > search:7 print(分段值（前）：,binary_para[bi])8 binary(binary_para[:bi],search)9 elif binary_para[bi] < search: 10 print(分段值（后）：,b...
Maximun Profit（每日一题） 外汇交易可以通过兑换不同国家货币以赚取汇率差，比如1美元兑换100日元时购入1000美元，在1美元兑换108日元时再卖出，这样就可以赚取差价，现在将某货币t时的价格Rt作为数据，算出Rj-Ri的最大值（j>i)输入 第一行一个整数n,接下来n行依次给证书Rt赋值 输出 单独一行输出最大值解题思路：其实看到这个题，我首先想到的时dp，但是我看这个题的难度系数，并没有那么高，所以想暴力，于是就有这个思路： fo...
所谓素数，是指恰好有2个约数的整数。因为n的约束都不超过n，所以只要检查2~n-1的所有整数是否整出n就能判定n是不是素数。在此，如果d是n的约数，那么n/d也是n的约数。由n=dn/d可知min(d,n/d)<=，所以只要检查2~的所有整数就够了。同理可知，整数分解和约数枚举都可以在时间完成，虽然还有更高效的算法（费马测试，算法，数域筛法等），不过多数情况下这已经足够了。——挑战程序设计竞赛p117 1.素数测试 给定一个整数n，请判断n是...
原文链接：http://www.cnblogs.com/bwzhangtao/p/6957815.html1. 冒泡排序法 * 思路分析：法如其名，就是像冒泡一样，每次从数组当中 冒一个最大的数出来。 * 比如：2,4,1 // 第一次 冒出的泡是4 * 2,1,4 // 第二次 冒出的泡是 2 * 1,2,4 // 最后就变成这样 $arr=array(1,43,54,62,21,66,32,78,36,76,39); function getpao($arr) { $len=count($arr);//设置一个空数组 用...
主要解决问题：包含问题。 例如：str1: abc123defstr2：123dstr1中是否包含有str2这个字串。（注意字串与子序列区别） 子序列：可以连续也可以不连续 子数组/子串：必须是连续的。 好了废话不多说了，我们上正菜。首先，想了解kmp的加速过程，要先知道一个数组叫next数组，这个数组中存放了str2中每个字符的前缀和后缀相匹配的最长长度（注意是前缀和后缀的最长的那个匹配长度）。什么意思呢？举例说下：图中str2中下标为0的字符它...
1、什么是JavaScript？ javaScript是一种脚本语言和解释性语言，还是弱类型语言 弱类型语言：数据的类型由变量值决定 2、JavaScript由什么组成？ javaScript由三部分组成，分别为：核心ECMAScript---核心语法 ，DOM---文档对象模型 ，BOM---浏览器对象模型； 3、怎么使用JavaScript？ javascript有三种使用方式： 内部样式---在Script的标签中写js代码 外部样式---在外部js文件中写js 代码 需要将js文件引入 行内样式---在标签的属...