一、全排列问题（Permutation）
问题描写叙述：即给定{1,2,3},返回123,132,213,231,312,321
《Permutation》
1）无顺序的全排列问题：
将序列P(n) = {1….. n}的全排列问题看成P(n)={1,P(n-1)} + {2,P(n-1)}…..的问题，即确定第一个元素的值为1，然后和剩下n-1个元素的全排列结果组合到一起；然后再将1和剩下的每一个元素进行交换。然后和其剩下的n-1个元素排列结果进行组合；显然这是一个递归问题。
2）有反复值的全排列问题：
注意每次递归的时候去除反复值就可以。即有反复值就不进行交换。
3）找到下一个更大值（next_permutation）
即1342，找到下一个更大值1423；
解题思路：
基本思想是从后往前遍历，找到第一个递增的二元对（即a[j] < a[j+1]）;然后从后往前遍历到j+1位置，找到第一个k值a[k]>a[j]，交换k和j，然后将j+1后面的序列反转。
注意增序列则表示字典序较小，减序列则表示字典序较大；假设遍历找不到增序列。表示当前数值已经是最大值。
原理：
4）有顺序的全排列（能够看做非递归实现）
解题思路：使用next_permutation也以获得全排列。即不断调用next_permutation来获得更大值。然后依次输出
5）有特殊要求的全排列，比方要求4必须在3前面
解题思路：进行全排列。然后推断4和3的位置再进行输出。（？更好方法）
6）查找数字排列组合中的第k个组合：（Permutation Sequence）
解题思路：
即给定{1,2,3},和3,返回全排列(123,132,213,231,312,321)中的第三个，即213
注意：
这里不须要将全排列计算出来，然后再得到第k个；
最好的做法：是直接利用数学知识进行计算：
还是分为两层来看，第一位确定的话，后面P(n-1)的全排列为（n-1）!，则能够依据算法推断出第一位是哪个数值。剩下的类推。
一、二叉树问题汇总：
1）二叉树三种遍历非递归实现
2）重建二叉树
3）推断树A是否为树B的子树
4）二叉树镜像
5）从上往下打印二叉树
6）二叉搜索树的后序遍历
7）二叉搜索树转化为双向链表
8）二叉树中和为某一值的路径
9）求二叉树的深度
10）平衡二叉树
二、递归问题汇总
1）魔术索引问题
即一个递增序列，满足A[i]=i的称为魔术索引。
1>无反复值的魔术索引问题：二分法
2>有反复值：缩小范围法
2）跳台阶、斐波那契
3）机器人走方格：都注意使用空间存储来优化；
4）N皇后问题：
回溯法：由于每一行仅仅能有一个皇后，所以使用一个一维数组index[]来记录每一行的皇后的列的位置就可以,然后给数组中的每一个元素赋个初始值-1。表示当前行的位置还没有确定。
然后从第一个皇后開始赋值，从0開始，再给第二个皇后赋值，也是从0開始遍历，然后写一个推断当前index[]矩阵是否合法的函数，每次给一个皇后赋值的时候，都须要进行一次推断。假设合法，则继续给下一个皇后赋值；假设不合法，就取这一层相应的index里面的记录的数值比方说是m,然后给这个皇后赋值m+1，继续推断是否合法，反复之前操作；
假设在这一层。0-n-1全部都赋值完了，皇后仍然没有找到合法的位置，那就採用回溯法，把这一层的index值又一次置为-1。回到上一层设置上一层的皇后的位置，往右移一步。反复之间操作。
直到赋值到第N层。全部皇后位置都合法之后，再将结果输出。
由于可能的结果不止有一种。当输出一种结果之后，回溯到N-1层。又一次開始之前的设置。检查操作；
递归法：递归法比較简单，比方八皇后问题，就能够看成已知当中一个皇后位置，求其它7个的位置。然后再确定第二个皇后的位置，求剩下6个皇后的位置；以此类推进行递归。直至递归到最后一层，输出结果。
三、最远距离问题JumpGame：
即推断[3,1,3,1,1,0,4]是否可到达。
解决方法：非常easy。一直往前走，计算每一步能到达的最远位置index+A[index]；和之前记录的最远位置reach做比較，大于则更新reach值；循环的终点是到了终点即i==n了或者i>reach了。这个时候推断i==n(注意是n。由于在n-1后。还会再i++，然后循环才干推出)。
四、构造顺序矩阵和打印循环顺序矩阵Matrix：
《leetcode-54 Spiral Matrix 顺时针打印矩阵（《剑指offer》面试题20）》
《leetcode 58、Length of Last Word。59、Spiral Matrix II ；60、Permutation Sequence》
解题思路：定义上下左右四个维度的限定值，然后向右。向下，向左，向上进行遍历。并注意更新相应值。
五、连续子数组的最大和
解题思路：使用一个max记录当前最大值，使用一个curSum来记录遍历数组时候的暂时的和；
遍历数组，比方来到第i个元素。假设之前的curSum<0,那么curSum再加上a[i]仅仅会使得相加值更小。因此取更大值。也就是令curSum=a[i]，把前面的和序列舍弃掉;
假设curSum>=0,则能够直接把两个值相加来作为新的curSum;
然后再将curSum和max做比較。去更大值来更新max值。最后遍历完一遍，返回max值就是最大的值。
六、数值的整数次方pow:
解题思路：注意处理n<0的情况。n<0时。要把a转化成1/a;
还要注意处理底数为0，而指数却为负数的不合法情况；
七、推断是否为同位词：
即“ate””eat” “tae”为同位词；从一串字符串中找出同位词：
解题思路：使用HashMap。先对全部词进行字典序排序，然后比对。
八、字符串数组排序：
由于字符串实现了Comparable接口，能够比較两个字符串之间的大小。因此能够像实现int数组排序一样实现字符串数组的排序。
九、k个排序链表合并成一个排序链表（或者k个排序数组合并成一个排序数组）
解题思路：创建一个k阶的最小堆。创建堆的时间复杂度o(n*logn)。取最小值的事件复杂度为O(1)；删除最小值。加入一个新值，调整堆的时间复杂度为O(lgn);
每次取最小值，最为新链表（新数组）的下一个值。然后再从该数值相应数组中取出一个新值放在堆顶。然后调整堆。反复上述过程；
也能够使用败者树来实现。
思路：维护一个k阶最小堆，新值和堆顶元素进行比較，假设大于堆顶元素值。则替换堆顶元素，调整堆；
十、求两个整数的最大公约数；最小公倍数（辗转相除法）
十一、求格雷码：
格雷码是二进制转化成的编码。它的相邻两个数的格雷码仅仅有一个位是不同的。最大数和最小数也仅仅有一个位不同；所以适应了真正电气环境下数值不能连续变化多位的情况；
编码：二进制转化为格雷码： 第一位保持不变。然后从最右边一位開始，与左边一位进行异或，得到的异或值即为格雷码；
1001001010 ==> 1101101111
解码：格雷码转化为二进制： 解码从最左边開始，一个为解码值保持不前，然后从左边第二位開始，每一位和前一位的解码值进行异或。得到的值即为解码值。
十二、两个链表的公共交点：
解法：两个链表相交，则链表相交的第一个公共点之后的全部节点一定是相交的；即两个链表是呈Y型的；
1）两个链表无环时的解法：
（1）能够先遍历两条链表，得到两个链表的长度m,n；然后双指针，一个先走m-n步（假设m>n），然后两个指针同一时候出发，第一个相交的节点即为公共节点；若一直遍历结束也没有公共节点。则两个链表不相交；
（2）方法同一，但不须要遍历完两个链表来获得两个链表的长度；记两个链表为A、B，能够设置两个指针p、q，同一时候出发，当q到达链表尾（即为NULL时），此时从链表A头部出发一个指针a;当p到达链表尾时，此时从链表B头部出发一个指针b。则a,b转化为方法一中的问题。（两个方法的时间复杂度同样）
（3）假设两个链表相交，由于其公共节点之后的链表同样。此时将当中一个链表链接到还有一个链表之后，形成的新链表一定有环。则原问题转化为求一个有环链表的环的公共交点问题；
2）考虑链表有环
假设两个有环的链表相交，那么它们的环必定为公共环。假设交点不在环上。即在环前面的直链上，即转化为前面的连个无环链表求解公共点的问题。第一个公共点就是第一个交点。
可是假设交点在环上，即环的入口点不同，那么任一环的入口点都可为第一公共点。
十三、删除字符串中的指定字符：
题目：输入两个字符串，从第一字符串中删除第二个字符串中全部的字符。比如，输入”They are students.”和”aeiou”。则删除之后的第一个字符串变成”Thy r stdnts.”。
解题思路：基本思想是遍历字符串s1，推断字符串s1中的每一个字符在s2中是否存在，假设存在则删除；
这里就须要考虑两个细节：
1）删除字符问题
使用两个指针，pFast。pSlow；当有字符须要删除时，pSlow不变，pFast前移；当有字符不须要删除时，将pSlow和pFast指向的字符交换。最后取0-pSlow数组的字符组成的字符串就可以。基本思想是将后面不须要删除的字符替换到前面来。
2）推断字符是否须要删除：
推断字符是否须要删除。即该字符是否在s2字符串中；能够使用的方法如Hash，使用HashMap或则HashSet把s2中的字符存储进来，然后遍历s1每一个字符c在HashMap是否已经存在就可以。时间复杂度为O(1)；
同样的方法能够是使用一个boolean[256]数组。记录char(共256个)是否存在；原理相似Hash
十四、计算一个字符串中的最长无反复字符串：
问题描写叙述：计算给定一个字符串，如”abcabcbb” 则其最长无反复字符串为 “abc”；字符串”bbbbb”其最长无反复字符串为”b”；
解题思路：使用一个256的int数组indexs来记录每一个char在字符串中出现的位置；
假设indexs[i]为-1，表示当前測试字符串中没有出现过字节i，因此直接将indexs[i]赋值为i，即记录其出现位置。
假设indexs[i]不为-1。则表示已经出现过，这里要依据此算法分成两种情况讨论。这里使用一个start记录当前測试字符串的起始位置，即当前測试的字符串为start–i；假设indexs[i]小于start。表示该字节出如今測试字符串之前。因此能够当做-1情况对待。再者，假设已经存在。则当前字符串已经不是满足要求的唯一性字符串了，因此计算当前的非反复最大值，和系统当前记录的最大值作比較，记录更大值；然后測试下一个字符串，为满足非反复条件，则下一个測试字符串的起始位置须要从index[start]+1開始。
十五、求数组的最大值与最小值
1）主要的遍历法须要比較2N次；
2）採用双元素法，记录max和min；每次比較两个值，较小值和min做比較，较大值和max作比較。这样终于的比較次数为1.5*N次。
3）採用分治法；将数组分为两部分，分别得到两个子数组的最大值最小值，然后再合并在一起进行比較；
十六、找出数组中仅仅出现一次的数：
1）其它的数都出现了偶数次：直接使用全部异或就可以。
2）其它数出现的是奇数m次：则假设没有该特殊值，其它全部值二进制时二进制各个位相加之和肯定都能被m整数整除。再加上异常值，则全部位对于n进行取余，得到的值必定是该特殊值的二进制表示。
十七、数组中出现次数超过一半的数：
解题思路：
解法一：将原问题转化为求数组的中位数，採用高速排序的思想，每一次Partition取末位为哨兵，遍历将小于、大于哨兵的数分别移至哨兵左右，最后返回哨兵在处理后的数组中的位置。不断缩小要处理的数组的长度大小。终于确定返回值为数组长度一半的元素。即为中位数。
解法二：由于题设该数字出现的次数大于其它全部数字出现的次数，故用两个变量。一个表示数字num_data。一个表示次数。当下一个数字等于num_data时。则times加1。如若不等于，time减1。直至times等于0，则将num_data更换为下一个数字；由题知。最后得到的num_data的结果必为所要求得的值。
十八、旋转数组：
问题描写叙述：即给定一个数组如[1,2,3,4,5,6,7] ,及一个k=3。将后面k个数字旋转到前面来，则旋转之后的数组为[5,6,7,1,2,3,4].
解题思路：和旋转字符串问题比較相似。即先将数组分为两部分，后面k个数字为一组，前面n-k个为一组，将两组分别反转，然后再将整个数组反转就可以；反转能够採用双指针法。
十八、推断一个数是否是2的n次方：
解题思路：
一个数num是2的n次方则二进制表示为（000010000…），则num-1是(000001111111…)。其num与num-1二进制位必定没有一个相等；
因此推断num&(num - 1)是否等于0就可以。
十九、计算一个数的二进制中1的个数：
解题思路：
解法一：直接转换成二进制然后循环右移取出二进制中每一位推断是否为1就可以
解法二：使用n&（n-1）;二进制中有几个1，就循环几次n&(n-1)得到0
二十、2Sum,3Sum,4Sum问题：
《leetcode-1 Two Sum 找到数组中两数字和为指定和》
《Leetcode-15 3Sum》
《leetcode-18 4Sum》
《leetcode-16 3Sum Closest》
问题描写叙述：给定一个数组和一个target结果值，求2个/3个/4个数字的和为target的解法。
**解题思路：**2Sum问题典型的解决方案是使用双指针，从头部尾部同一时候往中间走进行推断。
然后从i=0,j=end開始和末位的两个数字開始，计算两个之和sum。若sum大于目标值target,则须要一个较小的因子。j–。反之。i++。直至找到终于的结果
二十一、排序算法
1、冒泡排序（交换排序）：
在循环遍历中。每一次遍历数组将最大的数字通过交换沉到最后一位
优化：
1）设置一个flag标示，当一次遍历有交换设置为true，没有交换时则表示前面数组已经有序。无需再做遍历
2）记录每一次遍历发生交换的最后位置。由于这个位置之后的数组肯定是有序的。最后交换位置为0时，循环结束
2、直接插入排序：
在循环遍历中。第j次遍历过程向已经排好序的数组a[1..j-1]插入a[j]
优化：查找插入排序。在插入的时候使用二分法
3、希尔排序（插入排序）：将数组分为非常多小序列，然后分别进行直接插入排序。待整个数组基本有序的时候，最后进行一次插入排序
实现，选取一个增量序列（递减到1）（比方x/2序列）
4、高速排序：
每一次循环选取一个中间值，将比这个值大的元素移动到中间的后面，比中间值小的移到中间值前面。这样分成了两个子序列，然后再对子序列进行高速排序。
时间复杂度：O(nlogn), 最好O(nlogn)，最坏（基本有序时退化成冒泡）O(n^2)。空间复杂度：O(1)+（递归栈的缓存空间最大O(n),最小O(logn)） 不稳定
实现：单指针法，双指针法
高速排序的改进：
1）中枢值的选取：传统方法中使用最左元素或者最右元素。这样在数组基本有序时的性能较差（会退化成冒泡算法）。
改进方法一：中枢值 pivot使用随机数来代替（可是产生随机数也会带来性能损耗）
方法三：median-of-three对小数组来说有非常大的概率选择到一个比較好的pivot，可是对于大数组来说就不足以保证能够选择出一个好的pivot，因此还有个办法是所谓median-of-nine，这个怎么做呢？它是先从数组中分三次取样，每次取三个数，三个样品各取出中数，然后从这三个中数当中再取出一个中数作为pivot。也就是median-of-medians。取样也不是乱来。各自是在左端点、中点和右端点取样。
什么时候採用median-of-nine去选择pivot。这里也有个数组大小的阀值，这个值也全然是经验值，设定在40，大小大于40的数组使用median-of-nine选择pivot，大小在7到40之间的数组使用median-of-three选择中数。大小等于7的数组直接选择中数，大小小于7的数组则直接使用插入排序
5、归并排序：
通过分治的思想。对数组序列进行分割，分割到最后每一个子序列中仅仅有一个元素的时候，然后再两两合并。最后每一次循环都是两个有序数组合并成一个有序数组的操作。 稳定
O(nlogn); O(nlogn); O(nlogn); 空间复杂度O(n);
6、简单选择排序：第i次遍历的时候。从i-n序列中找到最小值。与第i个元素进行交换。也就是每一趟遍历都选取一个最小元素作为第i元素值。
7、堆排序：
叶子节点的值都大于或等于根节点的值（最小堆）
建堆：从n/2+1開始剩下的都为叶子节点，因此从n/2到0递减顺序，分别以每一个节点为根节点建立最小堆。
堆的调整：比較左右子节点的值得到最小值，然后比較根节点与最小值，假设根节点的值要大，则不满足最小堆的概念，须要进行调整，将两者进行交换。然后再以交换后的位置为根节点，反复前面过程。
排序算法性能比較：
O(n^2)的有：直接插入排序，冒泡排序，简单选择排序
O(n^(1-2))： 希尔排序
O(nlogn):高速排序。归并排序。堆排序
O(n):线性：桶排序。基数排序
选择上：
基本有序时，选择直接插入排序。希尔排序；而高速排序会退化成冒泡排序；
平均性能上最优的是高速排序。在最坏情况下。性能上不如堆排序和归并排序，而n较大时。归并排序优于堆排序。可是其须要的存储空间要大。
直接插入排序在基本有序或者n较小时最佳。
稳定性：
即值同样的关键字在排序前后位置先后顺序不变
稳定的：冒泡、插入、归并、基数
不稳定：选择、希尔、高速、堆；
设待排序元素的个数为n.
堆排序 ： 假设内存空间同意且要求稳定性的。
归并排序：它有一定数量的数据移动，所以我们可能过与插入排序组合。先获得一定长度的序列，然后再合并，在效率上将有所提高。
2） 当n较大，内存空间同意。且要求稳定性 =》归并排序
3）当n较小，可採用直接插入或直接选择排序。
直接插入排序：当元素分布有序。直接插入排序将大大降低比較次数和移动记录的次数。
直接选择排序 ：元素分布有序。假设不要求稳定性，选择直接选择排序
5）一般不使用或不直接使用传统的冒泡排序。
6）基数排序
它是一种稳定的排序算法，但有一定的局限性：
1、关键字可分解。
2、记录的关键字位数较少，假设密集更好
3、假设是数字时，最好是无符号的，否则将添加相应的映射复杂度，可先将其正负分开排序。
二十二、外部排序：
1）依据内存能够缓存的大小，将全部数据进行分段，加入到内存。进行内部排序。
胜者树：锦标赛排序
败者树：使用节点来记录失败的元素；胜者往上一层进行比較，扩展一个节点来记录终于的冠军；
败者树重构仅仅须要新加入的元素和父节点进行比較（即败者进行比較）。而胜者树则是须要和右节点进行比較。
二十四、二分查找：
考虑有数值的同样情况
三、KMP：
本篇汇总了面试中最常见的算法题，后续会持续优化补充
该文解决的问题：存在两个列表中的数据（如ListA, ListB），如何找出他们中第一个不一样的值。如：给定两个列表ListA="6-c++,1-Java, 2-python, 3-javaScript,4-perl",ListB="1-Java,2-python,5-lua"，根据指定的索引数字（1,2,3,4,5,6等）找出他们中第一个不一样的值。第一，两个list不能全部为空第二，需要做的是
三子棋是大家学习完C语言数组知识后接触到的第一个小游戏设计，在初步设计的时候，他的智障ai总是感觉自己玩起来像一个智障，游戏体验感不是很好。那么，在结合了一些大佬的思想以后，我得出了一个逻辑简单，新手入门难度低的ai算法，虽然说代码不是很简洁，但只涉及到一些基本的编程思想和设计思路。废话不多说，让我们开始吧。（假设大家已经完成了基础框架的搭建，只是想提升一下电脑下棋部分的电脑智商，下面只介绍算法的
1，hadoop是什么Hadoop：一个分布式系统的基础架构，用户可以在不了解分布式底层细节的情况下，开发分布式程序，充分利用
在上微机实验课时，需要对汇编指令有一定的了解，但是由于初次接触，所以将在实验中存在的汇编指令和寄存器记录下来，方便后续查找使用。初步了解寄存器8086CPU一共有14个寄存器，每个寄存器器有一个名称。这些寄存器是: AX、BX、CX、DX、SI、 DI、SP、BP、IP、 CS、SS、DS、ES、PSW。寄存器名称解释数据寄存器AX累加器（Accumulator），使用时主要用于存放数据，如存放
pycharm基本用法+markdown语法+jupyter notebook的基本操作汇总 一.计算机基础 什么是编程，计算机组成 程序语言 二.变量 变量的概念 python的回收机制 三.数据类型基础 数据类型概述 数据类型概述补充 四.格式化输出+基本运算+流程控制 格式化输出+基本运算+流
1.插入排序算法直接插入排序：插入排序的基本思想是在遍历数组的过程中，假设在序号 i 之前的元素即 [0..i-1] 都已经排好序，本趟需要找到 i 对应的元素 x 的正确位置 k ，并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位，为元素 x “腾位置”，最后将 k 对应的元素值赋为 x ，一般情况下，插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1)。稳定void&
仅以此贴激励自己坚持刷题
排序算法无疑是学习数据结构中的重点内容，本文将给出排序算法的汇总。下面是具体的实现：#include<stdio.h>#include<stdlib.h>#include<time.h>#define N 1000000int Array[N];int Temp[N];//1、冒泡排序void BubbleSort(int a[],int n
对于「算法」的第一印象，我相信大部分人都是一样的，就是一个“难”字了得。 但说实话，效果不是很好，于是磊哥就琢磨有没有更简单的学习算
RAID5在 CACHE关闭与否的时候 性能影响很大。关闭写cache，RAID5的性能将差很多倍 RAID10对cache的依靠性没有RAID5那么明显。 决定IOPS的主要因素取决于阵列的算法，cache命中率，以及磁盘个数。 cache命中率对实际IOPS有决定性的影响，Cache命中率取决于数据的分布，cache size的大小，数据访问的规则，以及cache的算法，如果完整的讨
我们都知道，在业务系统中常常会有这样的业务需求：数据报表需要按实际纸张进行分页显示，在每页的最后对本页的数据进行汇总（例如，计数、求和）。下图显示的就是对每页的运货费进行求和小计：
给你一个按照非递减顺序排列的整数数组nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target，返回[-1, -1]。你必须设计并实现时间复杂度为O(log n)的算法解决此问题。
本文作者：得帆信息联合创始人兼CTO徐翔轩 EHS建设正在成为“必答题” 过去几年，随着国家监管要求趋严、审计频率增加、企业社会责任强化，内部安全管理要求不断细化，EHS系统在很多行业内的存在感明显提升。无论是制造业、化工、能源等传统行业，还是医药、电子等新兴领域，EHS系统已从最初的“合规性选择” ...
配置的前世今生：从逻辑中抽离，又与逻辑有限融合在软件开发中，我们总在追求一种优雅的平衡。配置管理的发展史，正是这种追求的完美体现。它走过了一条奇特的路径：从与代码的完全融合，到彻底分离，最终走向一种有限的、克制的融合。这并非简单的回归，而是一次螺旋式的上升。第一阶段：混沌之初——硬编码的“原罪”在最 ...
在Web开发中实现音频录制功能是许多应用场景的常见需求，本文详细解析如何利用现代浏览器API实现网页端的录音功能