Lei Xia

Sr. Software Engineer | Solution Architect

抒写代码,尽享生活,筑就未来。

订阅 · 赞赏

avatar

洗牌算法

2023年1月3日 · 99 字 · 1 分钟

洗牌算法用来将给定的序列打乱,可以认为是排序的反操作。 正确性判断 对于包含$n$个元素的序列,其全排列有$n!$种。如果序列打乱的结果为$n!$种且每种序列出现的概率相同,则是正确的洗牌算法。 Fisher–Yates 洗牌算法 以下算法说明摘自: https://gaohaoyang.

原地哈希算法

2022年12月31日 · 214 字 · 2 分钟

原地哈希算法(Cyclic Sort)主要应用在值都在$[0,n]$的数组$nums$中,此时可以将$nums[i]$作为索引,放回原数组,当然,由于程序上索引是从0开始,因此可以将$nums[i]$放到$nums[nums[i]-1]$的位置上。 举例 Leetcode 268. 丢失的数字

厄拉多塞筛素数筛选算法

2022年12月31日 · 197 字 · 1 分钟

厄拉多塞筛算法(Eratosthenes Sieve)是一种求素数的方法,由古希腊数学家厄拉多塞提出。它的原理是,给定一个数 n,从 2 开始依次将 $\sqrt n$ 以内的素数的倍数标记为合数,标记完成后,剩余未被标记的数为素数(从 2 开始)。如此可省去检查每个数的步骤,使筛选素数的过程更加简单。

博耶-摩尔多数投票算法

2022年12月31日 · 263 字 · 2 分钟

来自维基百科的解释: 博耶-摩尔多数投票算法(英语:Boyer–Moore majority vote algorithm),中文常作多数投票算法、摩尔投票算法等,是一种用来寻找一组元素中占多数元素的常数空间级时间复杂度算法。这一算法由罗伯特·S·博耶(英语:Robert S.

基数排序算法

2022年12月30日 · 282 字 · 2 分钟

基数排序又叫桶排序,是一种时间复杂度为$O(n)$的排序算法,但是相比于其他排序算法有$O(n)$的空间复杂度。 思路 基数排序的核心思路如下: 准备0~9的10个桶,根据数字当前比较位的值来决定放入哪个桶。如当前比较个位,则数字13应该放入索引为3的桶中;当前比较百位,则123应该放入索引为1的桶中。 当所有数字全部放入桶之后,遍历0~9这10个桶,然后依次将数字保存到待排序数组,因为桶是有序的,所以本轮放回去的数字是有序的。 当前比较的位数左移,比如本轮比较个位,下一轮应该比较百位。 重复步骤1~3。 举例 现在我们来看一个实际例子。

算法篇-leetcode 131 分割回文串

2022年3月17日 · 630 字 · 3 分钟

题目 给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。

LeetCode109——有序链表转换二叉搜索树

2022年2月8日 · 292 字 · 2 分钟

题目 给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

LeetCode103——二叉树的锯齿形层序遍历

2022年2月6日 · 149 字 · 1 分钟

题目 给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。