2023年1月19日 · 128 字 · 1 分钟
滑动窗口算法是查找连续区间常用的算法之一。 本文分享滑动窗口算法的通用框架。 算法 定义$left$和$right$双指针，代表窗口的左边界和右边界 当$right$小于给定区间大小时，我们可以进行操作。 在扩大窗口时，需要加当前新加入的数据进行处理 当当前窗口内数据不满足条件时，右移$left$指针缩小窗口 计算$[left,right]$之间的数据，和最佳答案比较并更新最佳答案 右移$right$ 下面是滑动窗口通用框架的java语言实现。
2023年1月5日 · 63 字 · 1 分钟
本文分享一种检测一个字符串是否为另一个字符串子序列的算法。 子序列的定义： 若字符串$s1$可以由字符串$s2$删除某些字符得到，则$s1$是$s2$的子序列。换句话说，若$s1$的所有字符都在$s2$中且顺序一致，则$s1$是$s2$的子序列。 例如： a是aaa的子序列，adf是abcdef的子序列，但是cba不是abc的子序列（因为字符顺序变了）。
2023年1月5日 · 48 字 · 1 分钟
本文分享一种计算给定数字二进制表示中有多少个1的算法。 位运算对于非硬件相关的开发者来说可能用的比较少，朴素做法是将数字转换为二进制字符串，然后遍历该字符串得到1的个数。 算法 通过右移我们可以访问到数字的指定比特 将该比特与1进行按位与&，结果为1则证明当前比特位是1，计数器+1 根据给定数字的数据类型可以确定需要位移的次数，对于int来说，4个字节，因此需要右移32次，而对于long来说，8个字节，需要右移64次。
2023年1月3日 · 108 字 · 1 分钟
本文分享一种如何在字符串中解析数字的算法。 思路 解析字符串中的数字需要判断当前是否是数字字符，以及如何处理连续的数字字符。 本文使用while循环来解析数字，之所以不使用for循环，是笔者认为while循环操控力比for循环要好。 while循环解析方法如下：
2023年1月3日 · 206 字 · 1 分钟
在给定的序列中查找第N大的数，朴素做法是对序列排序，然后根据索引直接查询，时间复杂度为$O(nlogn)$。 本文介绍一种在$O(n)$的时间复杂度查询第N大的数的算法。 算法 算法思路就是定义标志变量，然后遍历数组，根据标志变量和当前数组变量的大小更新标志变量，最后根据情况返回标志变量。 示例：查找第2大的数 定义$first$和$second$分别存储最大和次大，然后遍历数组时更新即可。
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。 举例 现在我们来看一个实际例子。
