参考代码: 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; //…

2020-05-24 0条评论 2194点热度 0人点赞 SilverLining 阅读全文

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

2021-03-04 0条评论 943点热度 0人点赞 SilverLining 阅读全文

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

2021-02-25 0条评论 1029点热度 0人点赞 SilverLining 阅读全文

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

2021-02-21 0条评论 1209点热度 0人点赞 SilverLining 阅读全文

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

2021-02-15 0条评论 1256点热度 0人点赞 SilverLining 阅读全文

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

2021-02-14 0条评论 1257点热度 0人点赞 SilverLining 阅读全文

链表 链表是一种非连续的数据结构,常见的实现有单链表和双向链表。 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; …

2021-02-13 0条评论 1742点热度 0人点赞 SilverLining 阅读全文

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

2020-05-24 0条评论 1901点热度 0人点赞 SilverLining 阅读全文