转自专栏 快速幂（Exponentiation by squaring，平方求幂）是一种简单而有效的小算法，它可以以O(log(n))的时间复杂度计算乘方。快速幂不仅本身非常常见，而且后续很多算法也都会用到快速幂。 让我们先来思考一个问题：7的10次方，怎样算比较快？ 方法1：最朴素的想法，77=49，497=343，… 一步一步算，共进行了9次乘法。 这样算无疑太慢了，尤其对计算机的CPU而言，每次运算只乘上一个个位数，无疑太屈才了。这时我们想到，也许可以拆分问题。 方法2：先算7的5次方，即77777，再算它的平方，共进行了5次乘法。 但这并不是最优解，因为对于“7的5次方”，我们仍然可以拆分问题。 方法3：先算77得49，则7的5次方为4949*7，再算它的平方，共进行了4次乘法。 模仿这样的过程，我们得到一个在 O(log(n)) 时间内计算出幂的算法，也就是快速幂。 递归快速幂 刚刚我们用到的，无非是一个二分的思路。我们很自然地可以得到一个递归方程 计算a的n次方，如果n是偶数（不为0），那么就先计算a的n/2次方，然后平方；如果n是奇数，那么就先计算a的n-1次方，再乘上a；递归出口是a的0次方为1。 递归快速幂的思路非常自然，代码也很简单（直接把递归方程翻译成代码即可）： 注意，这个temp变量是必要的，因为如果不把计算结果记录下来，直接写成qpow(a, n /2)*qpow(a, n /2)，那会计算两次，整个算法就退化为了O(n)。 在实际问题中，题目常常会要求对一个大素数取模，这是因为计算结果可能会非常巨大，但是在这里考察高精度又没有必要。这时我们的快速幂也应当进行取模，此时应当注意，原则是步步取模，如果MOD较大，还应当开long long。 大家知道，递归虽然简洁，但会产生额外的空间开销。我们可以把递归改写为循环，来避免对栈空间的大量占用，也就是非递归快速幂。 非递归快速幂 我们换一个角度来引入非递归的快速幂。还是7的10次方，但这次，我们把10写成二进制的形式，也就是。 我们先看代码，再来仔细推敲这个过程： 最初ans为1，然后我们一位一位算： 1010的最后一位是0，所以a^1这一位不要。然后1010变为101，a变为a^2。 101的最后一位是1，所以a^2这一位是需要的，乘入ans。101变为10，a再自乘。 10的最后一位是0，跳过，右移，自乘。 然后1的最后一位是1，ans再乘上a^8。循环结束，返回结果。 这里的位运算符，>>是右移，表示把二进制数往右移一位，相当于/2；&是按位与，&1可以理解为取出二进制数的最后一位，相当于%2==1。这么一等价，是不是看出了递归和非递归的快速幂的关系了？虽然非递归快速幂因为牵扯到二进制理解起来稍微复杂一点，但基本思路其实和递归快速幂没有太大的出入。 快速幂的拓展 上面所述的都是整数的快速幂，但其实，在算a的n次方时，只要a的数据类型支持乘法且满足结合律，快速幂的算法都是有效的。矩阵、高精度整数，都可以照搬这个思路。下面给出一个模板： 注意，较复杂类型的快速幂的时间复杂度不再是简单的 O(log(n)) ，它与底数的乘法的时间复杂度有关。
KMP是一种线性时间都字符串匹配算法。 参考： 算法导论-32.4-588页 KMP算法详解-使用dp来解答 深入理解 KMP详解 KMP详解 一篇英文博客
回溯法的一个流程便是 设置 递归 回溯，循环 背景介绍：回溯法是一种穷举类型的算法，与其说它是一种算法，倒不如说它是一种试法。回溯法并没有什么高深的算法思想，虽然名字起的很高规格，但其实它的算法性连二分查找都比不上。这里说的算法性其实就是指技巧性，对问题特性了解越深入，越能创造出很巧妙的算法，在时间复杂度的级别上提高算法效率。这体现了算法效率与适用性之间的矛盾，二分查找效率很高，但适用性比较低，类似的还有著名的KMP算法。而穷举法效率最低，但几乎适用于所有问题。 好像有点儿扯远了，我们还是接着说回溯法。回溯法是一种试探性算法，从这一点上看，它很像穷举法。但它终究不是穷举法，回溯法是有组织的进行穷举，在试探过程中不断通过题设要求减少搜索空间，而这种减少不是一个一个解的减少，而是对搜索空间进行大规模剪枝，从而使得实际搜索空间远远小于问题的解空间，所以回溯法的实际运行效率还是比较高的。 应用场景：回溯法的应用背景说大很大，说小很小。算法大都在“不得不”的情况 下才会使用，如果有别的算法，那它很有可能比回溯法高效，别忘了，回溯法是基于穷举的。回溯法适用于解排列组合类问题，也就是说目标解是从一个候选空间中选择出来的。从数量级上考虑，设候选空间的大小为n，如果选择是可重复的，那生成的搜索树为完全n叉树，搜索空间为n^n（如0-1背包问题，生成的解空间为高度为n完全二叉树，其中n为物体个数）。如果选择不能重复，那生成的解空间为n!(如TSP问题生成的解空间为n!,其中n为城市个数)。也就是说，当我们通过分析发现问题的解空间为n^n或者n!时，那很可能要用到我们的回溯法了。 搜索策略：要用回溯法解决问题，那首先要确定问题的状态空间树。这个并不是很难，就看每一步选择有多少个可选值就可以了，第一步有8个可选值，那树第一层就有8个节点，第二步有5个可选值，那第一层每个节点都有5个分支，则第二层有8×5=40个节点，以此类推……到第n层一共有m1×m2×……×mn个节点，其中mi为第i步的可选值的个数。 确定了状态空间树，那下一步就是搜索了。这时候就体现出回溯法的优势了，前面不是说了嘛，回溯法的特点就是有规律、有组织的进行搜索，那下面就来看一下回溯法是如何进行搜索的：（PS：这部分内容大都取自清华大学郑宗汉的《算法设计与分析》一书，当然也有自己的一些理解）在开始搜索之前，我们先来说一下我们要做的事情，我们要得到一个解向量solution，每个分量对应每一步选择的结果，显然这个解向量的长度应该为n（我们采用C语言的标准，下标范围为0到n-1）。好了，现在我们有了一个状态空间树（逻辑上的，并不用实现）和一个解向量（物理上的，要用来装数据的）。现在可以开始搜索了，先设定一个下标r，这个r就是解向量的下标，也用于标识状态树的第r行。先做第一步，令r=0，选solution[0]，也就是从树的第0行选择一个值放入solution[0]，显然刚开始我们应该选择第一个，即前面提到的8个里面的第一个。然后看这个半成品解向量是否是可行的，也就是说看看刚才选择的那个值是否满足要求，加入那个值不满足要求，那应该选择第二个，以此类推直到选择一个可行的值，放入solution[0]。然后r++进行第二步，选择solution[1]，同样的，我们应该从树的第二行中选择第一个看构成的解是否可行（此时解向量中包含两个元素），这样的步骤一直进行下去，直到出现这样的情况 （1）r=n-1了，也就是说我们得到了问题的一个可行解，这时候就要看题设要求了，如果只要求找到一个可行解，那此时算法就可以停止了。 （2）某一层的候选值选完了，我们知道，每一层的候选值都有一定个数，如上面提到的例子中第二层只有5个候选值，如果这五个候选值都试探完了还是没有可行解那该怎么办呢？这里体现的思想就是我们回溯法名字的由来，回溯。也就是令r–退回去，从新选择上面的解。比如上面的例子先选择8个中的第一个作为解的一部分，然后发现后面的5个和前面这个都不能组成可行解，那这就说明前面那个选择是不可行的，和后面是不搭配的。所以应该返回去选择8个中的第二个，然后再对5个进行选择，看哪个与这个第二个想匹配。 （3）最后一种情况，因为我们这个过程中有回溯过程，即r–的过程，那可能最后r小于0了，这说明整个树都搜索完了，也就是问题没有可行解。 代码实现： 用回溯法解题一般思想为： 在解空间树中，从根节点出发，采用深度优先搜索的思想来遍历解空间树。每一次遍历节点时都判断当前 节点是否为合法解，如果为合法解，那么继续遍历其自子树，如果不是合法节点，那么访问其下一个兄弟节点，如果没有下一个兄就退回到父节点（回溯），访问父节点下一个兄弟节点。 回溯法结束的条件是回溯到根节点而且所有子树均已遍历到。 回溯法归根结底是一种带有节点判断条件的深度优先搜索算法。 回溯法解题一般步骤： （1）针对所给问题，确定问题的解空间： 首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。 （2）确定结点的扩展搜索规则 （3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 回溯法一般有两种代码实现方案，递归方法和非递归方法。相比之下，递归设计方法比较简单，用前面提到的r作为递归变量即可，如果满足搜索条件，则递归调用r+1对应函数，如果不满足，则递归调用r-1对应的函数。基础步为当r＜0或r=n-1分别对应无解和得到可行解，这个就不多说了。非递归方法，也就是循环方法设计细节比较多，但只要掌握了其特点，对不同问题的适用性很强（即代码只通过很少的修改就可以应用到不同问题），加之其效率高于递归算法（循环的优势），所以这里我们着重讲一下回溯的非递归代码实现。 算法框架： （1）问题框架 设问题的解是一个n维向量(a1,a2,………,an),约束条件是ai(i=1,2,3,…..,n)之间满足某种条件，记为f(ai)。 （2）非递归回溯框架 （3）递归的算法框架 回溯法是对解空间的深度优先搜索，在一般情况下使用递归函数来实现回溯法比较简单，其中i为搜索的深度，框架如下： 回溯法有“通用解题法”之称。用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索 算法。 在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一 结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的 解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解 时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。 应用举例：纸上谈兵已经做完了，该来点儿实践了。这里举三个小例子以示回溯法的基本应用，更高深的留待大家自己去研究。 第一个例子是八皇后问题，是回溯法应用中很典型的一个。还有一个是图的着色问题，也是很明显的回溯问题。最后一个是全排列问题，也可以用回溯法来解。 直接上代码吧： 八皇后问题： 在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 思路是按行来规定皇后，第一行放第一个皇后，第二行放第二个，然后通过遍历所有列，来判断下一个皇后能否放在该列。直到所有皇后都放完，或者放哪都不行。第一个皇后先放第一行第一列，然后第二个皇后放在第二行第一列、然后判断是否OK，然后第二列、第三列、依次把所有列都放完，找到一个合适继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解。然后回头继续第一个皇后放第二列，后面继续循环…… 下面再看着色问题的代码。 全排列代码： 全排列问题，输入一个字符串，输出字符串全部排列组合，可能有重复字符固定第一个字符，递归取得首位后面的各种字符串组合；再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合； 递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。 假如有重复值呢？ 由于全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。例如abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。但是对bab，第二个数和第三个数不 同，则需要交换，得到bba。 * 由于这里的bba和开始第一个数与第三个数交换的结果相同了，因此这个方法不行。 […]
已知问题规模为n的前提A，求解一个未知解B。（我们用An表示“问题规模为n的已知条件”） 此时，如果把问题规模降到0，即已知A0，可以得到A0->B. 如果从A0添加一个元素，得到A1的变化过程。即A0->A1; 进而有A1->A2; A2->A3; …… ; Ai->Ai+1. 这就是严格的归纳推理，也就是我们经常使用的数学归纳法； 对于Ai+1，只需要它的上一个状态Ai即可完成整个推理过程（而不需要更前序的状态）。我们将这一模型称为马尔科夫模型。对应的推理过程叫做“贪心法”。 然而，Ai与Ai+1往往不是互为充要条件，随着i的增加，有价值的前提信息越来越少，我们无法仅仅通过上一个状态得到下一个状态，因此可以采用如下方案： {A1->A2}; {A1, A2->A3}; {A1,A2,A3->A4};……; {A1,A2,…,Ai}->Ai+1. 这种方式就是第二数学归纳法。 对于Ai+1需要前面的所有前序状态才能完成推理过程。我们将这一模型称为高阶马尔科夫模型。对应的推理过程叫做“动态规划法”。 上述两种状态转移图如下图所示： 能用动规解决的问题的特点 能采用动态规划求解的问题的一般要具有3个性质： (1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。 (2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。 （3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势） 动规解题的一般思路 动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。 初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态 图1 动态规划决策过程示意图 (1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。 (2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。 (3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。 (4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。 一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。 实际应用中可以按以下几个简化的步骤进行设计： （1）分析最优解的性质，并刻画其结构特征。 （2）递归的定义最优解。 （3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值 （4）根据计算最优值时得到的信息，构造问题的最优解 算法实现的说明 动态规划的主要难点在于理论上的设计，也就是上面4个步骤的确定，一旦设计完成，实现部分就会非常简单。 使用动态规划求解问题，最重要的就是确定动态规划三要素： （1）问题的阶段 （2）每个阶段的状态 （3）从前一个阶段转化到后一个阶段之间的递推关系。 递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。 确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。 f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)} **算法实现的步骤** […]
转自某故事会。 最近在看数据结构中图的相关知识，之前看的很混乱，现在总算是理清了，在此记录一下。 目录： 图的基本知识 广度优先搜索（BFS） 深度优先搜索（DFS） 总结 代码实现 一、图的基本知识 日常有很多地方都用到了图，比如地铁线路图，计算机网络连线图等。 图就就是下面这种由节点和连接每对节点的边所构成的图形。 这是最简单的图，我们可以根据图的一些特性将其进行分类： 1、如果给边加上一个值表示权重，这种图就是加权图，没有权重的图就是非加权图，没有权重的边只能表示两个节点的连接状态，而有权重的边就可以表示节点之间的“连接程度”。 2、如果给边加上表示方向的箭头，即表示节点之间的传递方向，这种图就是有向图，而边上没有箭头的图就是无向图。 3、如果图中任意两个节点都能找到路径可以将它们进行连接，则称该图为连通图，上面这个图就是连通图，反之则为非连通图。 下面两个图分别为加权图和有向图： 非连通图如下所示： 知道了什么是图，和图相关的算法主要有两类： 图的搜索算法：图的搜索指的就是从图的某一节点开始，通过边到达不同的节点，最终找到目标节点的过程。根据搜索的顺序不同，图的搜索算法可分为“广度优先搜索”和“深度优先搜索”两种。 图的最短路径问题：最短路径问题就是要在两个节点的所有路径中，找到一条所经过的边的权重总和最小的路径。相关算法有“贝尔曼-福特算法”，“狄克斯特拉算法”和“A* 算法”三种。 二、广度优先搜索 广度优先搜索和深度优先搜索一样，都是对图进行搜索的算法，都是从起点开始顺着边搜索，此时并不知道图的整体结构，直到找到指定节点(即终点)。在此过程中每走到一个节点，就会判断一次它是否为终点。 广度优先搜索会根据离起点的距离，按照从近到远的顺序对各节点进行搜索。而深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条路径。 在广度优先搜索中，有一个保存候补节点的队列，队列的性质就是先进先出，即先进入该队列的候补节点就先进行搜索。 下图中红色表示当前所在的节点（节点A），终点设为节点G，将与节点A直连的三个节点B, C, D放入存放候补节点的队列中（与节点A直连的三个节点放入时可以没有顺序，这里的放入顺序为B, C, D），用绿色表示。 此时队列中有B, C, D三个节点，我们来看看广度优先搜索是如何对各节点进行搜索的。 1、上面左图：此时从队列中选出一个节点，优先选择最早放入队列的那个节点，这里选择最左边的节点B。将已经搜索过的节点变为橙色（节点A），搜索到节点B时，将与节点B直连的两个节点E和F放入队列中，此时队列为 [C, D, E, F]。 2、上面中图：对节点B搜索完毕，节点B不是要找的终点，再搜索节点C，将与节点C直连的节点H放入队列中，此时队列为 [D, E, F, H]。 3、然后对节点D进行同样的操作，此时队列为 [E, F, H, I, J]。 4、上面右图：对与节点A直连的节点搜索完毕，再对与节点B直连的节点进行搜索（因为剩下的点中它们最先放入队列），这里选择节点E，将与节点E直连的节点K放入队列中，此时队列为 [F, H, I, J, K]。 […]
JavaGuide Yesterday The following article is from yes的练级攻略 Author 是Yes呀 大家好，我是 Guide哥。今天这篇文章所聊的话题，非常重要！不论是你想在面试中脱颖而出，还是你想要搞懂 Netty、Kafka、Zookeeper 等等中间件的原理，你都务必要把这篇文章仔细阅读完！一遍看不懂就多看几遍，相信我，你一定会有收获！总之，搞懂时间轮算法真的非常有必要！！！ 另外，我建议你在搞懂了时间轮算法的原理之后，可以参考一些开源项目对时间轮算法的实现，自己也手写一个。 下面是正文！ 最近看 Kafka 看到了时间轮算法，记得以前看 Netty 也看到过这玩意，没太过关注。今天就来看看时间轮到底是什么东西。 为什么要用时间轮算法来实现延迟操作? 延时操作 Java 不是提供了 Timer 么？ 还有 DelayQueue 配合线程池或者 ScheduledThreadPool 不香吗？ 我们先来简单看看 Timer、DelayQueue 和 ScheduledThreadPool 的相关实现，看看它们是如何实现延时任务的，源码之下无秘密。再来剖析下为何 Netty 和 Kafka 特意实现了时间轮来处理延迟任务。 如果在手机上阅读其实纯看字也行，不用看代码，我都会先用文字描述清楚。不过电脑上看效果更佳。 Timer Timer 可以实现延时任务，也可以实现周期性任务。我们先来看看 Timer 核心属性和构造器。 核心就是一个优先队列和封装的执行任务的线程，从这我们也可以看到一个 Timer 只有一个线程执行任务。 再来看看如何实现延时和周期性任务的。我先简单的概括一下，首先维持一个小顶堆，即最快需要执行的任务排在优先队列的第一个，根据堆的特性我们知道插入和删除的时间复杂度都是 O(logn)。 然后 TimerThread 不断地拿排着的第一个任务的执行时间和当前时间做对比。如果时间到了先看看这个任务是不是周期性执行的任务，如果是则修改当前任务时间为下次执行的时间，如果不是周期性任务则将任务从优先队列中移除。最后执行任务。如果时间还未到则调用 […]
1. 两数相加 题目描述 Leetcode:给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。 你可以假设除了数字 0 之外，这两个数字都不会以零开头。 示例： 问题分析 Leetcode官方详细解答地址： https://leetcode-cn.com/problems/add-two-numbers/solution/ 要对头结点进行操作时，考虑创建哑节点dummy，使用dummy->next表示真正的头节点。这样可以避免处理头节点为空的边界问题。 我们使用变量来跟踪进位，并从包含最低有效位的表头开始模拟逐 位相加的过程。 Solution 我们首先从最低有效位也就是列表 l1和 l2 的表头开始相加。注意需要考虑到进位的情况！ 2. 翻转链表 题目描述 剑指 offer:输入一个链表，反转链表后，输出链表的所有元素。 问题分析 这道算法题，说直白点就是：如何让后一个节点指向前一个节点！在下面的代码中定义了一个 next 节点，该节点主要是保存要反转到头的那个节点，防止链表 “断裂”。 Solution 测试方法： 输出： 3. 链表中倒数第k个节点 题目描述 剑指offer: 输入一个链表，输出该链表中倒数第k个结点。 问题分析 链表中倒数第k个节点也就是正数第(L-K+1)个节点，知道了只一点，这一题基本就没问题！ 首先两个节点/指针，一个节点 node1 先开始跑，指针 node1 跑到 k-1 个节点后，另一个节点 node2 开始跑，当 node1 跑到最后时，node2 所指的节点就是倒数第k个节点。 Solution 4. 删除链表的倒数第N个节点 Leetcode:给定一个链表，删除链表的倒数第 […]
位算法的效率有多快我就不说，不信你可以去用 10 亿个数据模拟一下，今天给大家讲一讲位运算的一些经典例子。不过，最重要的不是看懂了这些例子就好，而是要在以后多去运用位运算这些技巧。我会从最简单的讲起，一道比一道难度递增，不过居然是讲技巧，那么也不会太难，相信你分分钟看懂。 判断奇偶数 判断一个数是基于还是偶数，相信很多人都做过，一般的做法的代码如下 如果把 n 以二进制的形式展示的话，其实我们只需要判断最后一个二进制位是 1 还是 0 就行了，如果是 1 的话，代表是奇数，如果是 0 则代表是偶数，所以采用位运算的方式的话，代码如下： 有人可能会说，我们写成 n % 2 的形式，编译器也会自动帮我们优化成位运算啊，这个确实，有些编译器确实会自动帮我们优化。但是，我们自己能够采用位运算的形式写出来，当然更好了。别人看到你的代码，我靠，牛逼啊。无形中还能装下逼，是不是。当然，时间效率也快很多，不信你去测试测试。 2、交换两个数 交换两个数相信很多人天天写过，我也相信你每次都会使用一个额外来变量来辅助交换，例如，我们要交换 x 与 y 值，传统代码如下： 这样写有问题吗？没问题，通俗易懂，万一哪天有人要为难你，不允许你使用额外的辅助变量来完成交换呢？你还别说，有人面试确实被问过，这个时候，位运算大法就来了。代码如下： 我靠，牛逼！三个都是 x ^ y，就莫名交换成功了。在此我解释下吧，我们知道，两个相同的数异或之后结果会等于 0，即 n ^ n = 0。并且任何数与 0 异或等于它本身，即 n ^ 0 = n。所以，解释如下： 把（1）中的 x 带入 （2）中的 x，有 y = x^y = (x^y)^y […]
0、排序算法说明 0.1 排序的定义 对一序列对象根据某个关键字进行排序。 0.2 术语说明 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面； 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面； 内排序：所有排序操作都在内存中完成； 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行； 时间复杂度： 一个算法执行所耗费的时间。 空间复杂度：运行完一个程序所需内存的大小。 0.3 算法总结 图片名词解释： n: 数据规模 k: “桶”的个数 In-place: 占用常数内存，不占用额外内存 Out-place: 占用额外内存 0.5 算法分类 0.6 比较和非比较的区别 常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。 计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置。非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。 todo： 考虑用compare替换数值间的比较 1、冒泡排序（Bubble Sort） 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 1.1 算法描述 比较相邻的元素。如果第一个比第二个大，就交换它们两个； 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数； 针对所有的元素重复以上的步骤，除了最后一个； 重复步骤1~3，直到排序完成。 1.2 动图演示 1.3 代码实现 1.4 算法分析 最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = […]