参考代码： https://github.com/njZhuMin/algorithm-practice 异或运算 异或运算：相同为 0，不同为 1 同或运算：相同为 1，不同为 0 异或运算可以简记成无进位相加。 异或运算的性质 0 ^ N = N; N ^ N = 0 异或运算满足交换律与结合律。 异或奇偶性应用 交换两个数 利用异或运算交换律与结合律的性质，我们可以不借助额外变量来交换两个数。 void swap(int a, int b) { // 假设 a = x; b = y a = a ^ b; //…

前缀树 前缀树是一种可以完成前缀相关查询的树状结构。其构建过程如下： 单个字符串中，字符从前到后的加到一棵多叉树上； 字符放在路上，节点上有专属的数据项（常见的是 pass 和 end 值）； 所有样本都这样添加，如果没有路就新建，如有路就复用； 沿途节点的 pass 值增加 1，每个字符串结束时来到的节点 end 值增加 1 。 代码实现不是很复杂，主要注意删除一个字符串时，需要先判断是否存在。当最后一个字符删除后，其 pass 值为 0，要依次删除（释放）后续的子节点（路径已经没用了）。 class Node …

堆结构 堆与二叉树 堆结构是用数组实现的完全二叉树结构。 完全二叉树，通俗的解释就是，一颗二叉树要么每一层都是满的，要么不满的那一层也是正在从左向右填满的。 大根堆：完全二叉树中每棵子树的最大值都在顶部； 小根堆：完全二叉树中每棵子树的最小值都在顶部。 将数组表示为完全二叉树，其下标与二叉树节点有如下关系： 0 / \ 1 2 / \ / \ 3 4 5 6 节点左子节点：2 * i + 1 节点右子节点：2 * i + 2 父节点：(i - 1) / 2 有些实现会屏蔽掉数组的第 0 个下标，从下标 1 开始使用…

桶排序 桶排序的思想如下： 桶排序思想下的排序都是不基于比较的排序； 时间复杂度为 O(N)，额外空间复杂度为 O(M)； 应用范围有限，需要样本的数据状况满足桶的划分。 这里的桶可以由数组、队列、栈等等来实现，这是一种基于统计的排序算法。 常见的桶排序算法有计数排序和基数排序。 计数排序 计数排序的适用场景要求数据范围不大，且有规律。例如对员工按年龄排序。 通常可以假设员工的年龄是正整数，分布在 [0 ... 100]，我们就建立 100 个桶（Bucket）来统计这些数据。那么在一次 O(N)的遍历中，我们就可…

归并排序 传统的数组排序算法时间复杂度是 O(N^2)，因为每一次扫描数组，只能将 1 个数字移动到目标位置。每一个数的排序过程之间是互不关联的，也就浪费了一些有用的信息。 递归实现 我们用递归的思想来考虑排序问题，如果一个数组分为左右两部分，且两部分别都是有序的，那么我们只需要做一次 O(N)的操作，就可以将整个数组排序。这个操作就是归并排序核心的算法。 然后，为了合并整个大数组，我们先要将这个数组一分为二个部分，然后再继续分为两部分，直到达到最小子问题：当数组中只有一个元素时，他天然就是有序的。 public …

递归 通俗地讲，递归就是自己调用自己。递归函数的意义，是将一个大问题，分解为若干个同等算法，但规模更小的子问题。通过解决一系列小范围的子问题，总而在大范围上解决整个问题。 求数组的最大值 举个例子，求一个数组中的最大值。常规的做法是扫描整个数据，用一个变量记录下最大值，时间复杂度为 O(N)。 而递归的思想是，要求一个数组中的最大值，假设有 10 个数，那么我只要找出左边 5 个数的最大值，和右边 5 个数的最大值，一比较，就可以得到整个数组的最大值。 因此这个问题被分解为了，求两个长度为 5 的数组中的最大值，这…

链表 链表是一种非连续的数据结构，常见的实现有单链表和双向链表。 class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } class DoubleNode { public int value; public DoubleNode last; …

算法系列参考代码： https://github.com/njZhuMin/algorithm-practice 算法复杂度 评估算法优劣的核心指标一般有以下三个方面： 时间复杂度（流程决定） 额外空间复杂度（流程决定） 常数项时间（实现细节决定） 常数时间操作 我们先来说常数时间操作。如果一个操作的执行时间不以具体样本量为转移，每次执行时间都是固定时间，这样的操作为常数时间的操作。 常见的常数吋囘的操作有： 常见的算术运算（+、-、*、/、%）等 常见的位运算（>> 、>>> 、&l…