数据结构与算法学习(十五)
1、大文件求词频 Top 10
1.1、题目描述
某一小时内,所有用户的搜索词汇,数量有 10 亿,单个词汇不超过 64 字节。存在一个文件中,作为实习生,你被分配了一台不太行的电脑,该电脑除了系统开销外,可使用硬盘 300 G ,内存 1 G ,请处理这个大文件,找出出现次数 Top 10 的词汇。
10 亿字节为 1 GB
1.2、哈希函数的特征
哈希函数的输入域无穷大,但输出域相对小
无随机成分,即一个同样的输入调用多少次哈希函数,得到的结果均相同
由于输入域远大于输出域,所以一定有某些输入的输出相同,抽屉效应,我们称这个现象为哈希碰撞
离散性,对于不同的输入,哪怕只有微小的差别都会导致输出差别极大
如果有非常多的不同输入去计算输出,输出的结果会呈现均匀性
1.3、解题思路
- 暴力法
使用一个 Map 来保存出现搜索词和出现次数,在最差的情况下(假设所有搜索词都不一样且每个搜索词都是 64 byte),那么需要建立十亿个键值对,占用的内存空间是 68 G(64 byte + 4 byte),很显然,这台计算机的内存是不够用的。
- 分治法
- 根据哈希函数将一样的搜索词放在一起
在最差的情况下,题目中给的计算机比较可以接受的数据条数是一千万条,即 680 M 的数据,我们根据哈希函数的性质(相同输入的输出必然相等),对每一条搜索值进行一次哈希运算,然后将结果通过 %100 得到一个 0 - 99 之间的整数 n ,然后将这个搜索词放到第 n 个小文件中。
比如说存在搜索词 “芜湖” ,它在经过哈希运算与取模运算后得到的结果是 2 ,那么它将被放在第 2 号小文件中,由于哈希函数输出的结果会呈现均匀性,所以最后分摊到这一百个小文件中的搜索词数目不会相差太多。
- 对第一步中获取到的小文件进行逐个筛选,选出各个文件的 top 10
对第 0 个文件进行统计,求出第 0 个文件中词频次数的 Top 10,然后释放内存,求第 1 号文件的 Top 10 … 由于每次我们只是将一个小文件加载到内存中,所以 1 G 的内存不会被撑满(在最差情况下,假设一个文件有 1 千万条数据,大概占 680 M )
- 选出全部数据的 top 10
对这 100 个小文件中的 Top 10 进行筛选,求出全部数据的 Top 10
2、一致性哈希
2.1、传统问题
- 在传统的数据存储服务中,我们可能会在后台部署 n 台机器,然后在每个请求进入时,使用请求中附带的某些值作为 hash key ,在进行哈希算法运算后,对结果进行取模运算,最终得到一个值在 0 到 n - 1 之间的值 x ,然后我们会将这条数据存入第 x 个数据库 / 发送到第 x 个服务器中
- 假设现在我们使用 n 台 MySQL 进行分库存储,然后用了以上的策略进行分库,那么在我们需要取出某条信息时,我们先根据上面的规则获取到这条数据是存储在哪个 MySQL 中,然后去那台 MySQL 取
- 有一种情况称之为会话粘黏,就是将一个用户的所有请求通过以上的策略永远分配到某台服务器上,比如说用户 id 为 100 的用户永远访问第一台 tomcat ,让 id 为 100 的用户会话一直放在第一台服务器上
这样做会带来一些问题:
- 如果是使用以上策略进行的分库分表,那么当数据库压力增大,我们需要水平扩充 MySQL 台数的时候,需要对之前的数据进行全量迁移
- 如果是使用以上策略进行请求分发,那么当某台 Tomcat 挂掉时,之前与这台 Tomcat 进行绑定的用户将无法登录(这个问题可以使用 Redis 进行解决)
2.2、哈希环
我们将哈希函数的有限输出域想象为一个环,以 MD5 算法的输出域返回 0 - 2 ^ 64 - 1 为例,哈希值在一个环上并排分布, 0 的前一个位置为 2 ^ 64 - 1 ,形成闭环,下面以网图为例(图里给的右区间是 2 ^ 32 - 1)
在上面提到的多台机器中,一定有某些数据可以用来区分本台机器与其它机器(可能是 MAC 地址、 IP 地址…这里以 IP 为例),那么我们先将计算这三台机器标识的 hash 值,然后将这三个值插入到哈希环中
现在应该如何为请求找到归属的机器?
- 根据请求的 Hash Key 与哈希函数获取到一个 hashCode
- 根据这个 hashCode 在环中的位置,顺时针找到离他最近的一台机器作为归属
比如说请求 1 的哈希值处于机器一与机器二之间,那么这个请求应该顺时针找到机器二作为它的归属
- 这样做有什么好处?
当我们动态增加 / 减少机器台数的时候,不用对数据做全量迁移,而只需要对部分数据进行迁移即可。
假设我们添加一台机器四,对这个机器的某些标识进行哈希后,得到的结果处于机器三与机器一之间
这个时候我们只需要将机器三与机器四之间的数据迁移到新的机器四中即可,其他数据可以不发生迁移。
2.3、落地实现
- 假设现在有三台机器,应该如何使用一致性哈希算法?
- 对三台机器的标识进行哈希,得到三个哈希值,分别为 a,c,b (假设 a > b > c),对三个哈希值进行排序
- 对进入的请求的标识进行哈希,得到哈希值 hashCode ,如果哈希值在 [a,c] 范围之间,那么将请求转发到大于 hashCode 的第一台的机器上
比如说当前请求的 hashCode 为 d ,b < d < c ,那么将其转给哈希值为 c 的机器,同理有一个请求的哈希值为 e (a < e < b)时,将其转给哈希值为 a 的机器。
- 如果请求得到的 hashCode 小于 a 或者大于 c ,那么将其转发到哈希值为 a 的机器上(哈希环)
这样会带来一些问题,即在机器台数少的时候,哈希算法得到的结果是不能保证均匀分布的,所以可能会出现三台机器的哈希值在圈上分布紧密的问题,那么这样就无法保证负载均衡
- 使用物理机的虚拟节点和哈希函数的均匀性来保证负载均衡
我们将实际接收请求的服务器称为物理机,并为其分配 n 个虚拟节点,当请求来到某个虚拟节点时,我们将这个请求转到对应的虚拟机中,物理机与虚拟节点是一对多的关系,这样我们得到了一张物理机与虚拟节点的映射表。
- 为三台物理机分配 n 个虚拟节点,将这 3 * n 个虚拟节点的某些属性进行哈希,再将得到的 3n 个值散落在哈希环中
- 当有请求来到时,对请求的标识进行哈希,然后根据上面的规则找到其对应的虚拟节点,再根据该虚拟节点来决定这个请求最终要去到的服务器
- 当我们需要增大 / 减少某些机器的负载时,我们只需要增加 / 减少这个服务器对应的虚拟节点的数目即可,此时再以虚拟节点为单位,按照上面的规则对某些数据完成迁移,就能恢复正常工作。
由于哈希算法具有均匀分布的特性,那么当我们为一台物理机分配的虚拟节点的数目足够多时,就可以让 3 n 个虚拟节点达到均匀分布,从而形成负载均衡。
3、分配整数
3.1、题目描述
给定两个数 a 和 b
- 第一轮,将 1 选择给 a 或者 b
- 第二轮,将 2 选择给 a 或者 b
- 第 i 轮,将 i 选择给 a 或者 b
想让 a b 值相等,那么请问至少要几轮
- 示例一
输入 a = 1,b = 1 ,那么输出 0
- 示例二
输入 a = 1,b = 2,那么需要两轮,即 第一轮将1给2,第二轮将2 给 1
- 示例三
输入 a = 5,b = 7,输出3,第一轮将 1 给 a,第二轮将 2 给 b,第三轮将 3 给 a
3.2、解题思路
- 当 a == b 时,直接返回 0
- 当 a != b 时,我们设此时大的数为 b ,小的数为 a,此时可以计算出它们两个的差值,记为 diff
- 从题意可知,每次给的数字是递增的等差数列,所以截至第 i 轮,我们给出的所有数字的和的值为 sum = (i + 1) * i / 2
- 设我们给 a 的数为 X (X > 0),给 b 的数为 Y (Y>=0),则有 X + Y = sum,X - Y = diff,则 X = (sum + diff) / 2,Y = (sum - diff) / 2
由于 Y 必须是一个大于等于 0 的整数,所以 sum - diff 必须是一个大于等于 0 的偶数,而 sum 由 i 决定,所以这道题只需要判断,当 i 等于几时, sum - diff 是一个大于等于 0 的偶数即可,第一个满足条件的 i 就是解
- 满足的条件是 sum >= diff,为了让 sum 快速接近 diff ,每次让 i 更新 2 倍,当 i = 1 不符合时,让 i = 2 * 1 = 2;在不符合时,更新 i 为 4 … 然后 8 ,16 ,直到 sum >= diff ,此时我们就找到了一个范围,在这范围的左边界,sum < diff ,右边界时 sum > diff ,此时结果就在这个边界中,我们使用二分快速查找这个值。
先定一个大概的范围,然后再进行二分查找
3、最大能被 3 整除的数
3.1、题目描述
给定一个arr,里面的数字都是0~9,你可以随意使用arr中的数字,哪怕打乱顺序也行,请拼出一个能被3整除的,最大的数字,用str形式返回
3.2、解题思路
- 对于一个多位数,如果这个数的每一位数 % 3 得到的值的和可以被 3 整除,那么证明这个数可以被 3 整除
比如说 321 ,3 % 3 = 0,2 % 3 = 2,1 % 3 = 1 ,由于 (1 + 2)可以被 3 整除,所以这个数可以被 3 整除
- 所以我们遍历数组,将数组中给的每个数都 % 3 ,然后将结果放入三个集合中,这三个集合分别存放 % 3 后值为 0,1,2 的数
- 对数组进行从大到小的排序,然后将结果加起来,得到最大数 sum
- 如果 sum % 3 == 0,那么 sum 就是所求值
- 如果 sum % 3 == 1,那么我们需要查找 % 3 后值为 1 的集合,然后从 sum 中剔除这个集合中最小的数即可
如果此时 % 3 后值为 1 的集合为空,那么我们就去掉 % 3 后值为 2 的集合中最小的两个数, (2 * 2) % 3 == 1
- 如果 sum % 3 == 2 ,那么我们只需要查找 % 3 后值为 2 的集合,然后从 sum 中剔除这个集合中最小的数即可
同理,如果集合中没有数,那么就剔除掉 % 3 后值为 1 的集合中的两个最小的数。
4、无重复字符的最长子串
4.1、题目描述
给定一个字符串
s
,请你找出其中不含有重复字符的 最长子串 的长度
- 示例一
输入 “abcabcbb” ,输出 3 ,无重复字符的子串为 abc ,长度为 3
- 示例二
输入 “pwwkew”,输出 3 ,无重复最长字符为 “wke” ,长度为 3
4.2、解题思路
- 子串是连续的,而子序列可以不连续
这道题可以考虑求出以某个位置结束,且符合条件的最长公共子串的长度,然后对这些长度取最大值,就可以得到我们需要的答案。
- 当我们处于第 i 个位置时,我们能向左推多长取决于什么因素?(假设第 i 个元素为字符 a)
上次 a 字符出现的位置
以第 i - 1 个元素结尾的元素向左推了多远
两个条件,哪个离 i 最近,哪个就作为限制条件,因为我们无重复最长子串需要满足两个条件,一是当前字符不能在之前的字符串中出现,二是以 i - 1 个元素作为结尾的子串也是不重复的。
- 用一个 Map 来存储当前字符及其上次出现的位置,在这道题中,我们使用一个数组来代替 Map
怎么知道某个字符上一次出现的位置?使用该字符的 ascii 码作为下标,该下标对应的值就是它上一次出现的位置。比如说 memo[97] 就是字符 ‘a’ 上次出现的位置,所以我们要初始化长度为 256 的数组。
- 由于处于 i 位置时,我们只需要查找 i - 1 的结果,所以只需要使用一个变量进行滚动更新即可
当 i 更新时,将该变量更新为 i - 1 位置的结果
4.3、解题代码
1 | public int lengthOfLongestSubstring(String s) { |
5、最长回文子串
5.1、题目描述
给你一个字符串
s
,找到s
中最长的回文子串。
5.2、解题思路
这里使用动态规划来解决这道问题,主要思想是:一旦在一个回文串的两端对称的添加相同的元素,那么新形成的字符串仍然是一个回文串。
- 先找出该字符串的所有子串
设立一个右边界,这个边界从第二个元素的后面开始,比如说现在存在一个字符串为 [a a b a d]
这种情况下,串 a 只有一个子串,即 a a ,我们将边界右移
这种情况,有两个子串,即 aab 和 ab
有三个子串,即 aaba 、 aba 和 ba
- 使用动态规划求解
创建一个二维数组,dp[ i ] [ j ] 表示从 i 到 j 的子串是否为回文子串,对于下标从 i 到 j 的子串
- 如果 i 位置的字符 == j 位置的字符,那么我们需要判断下标 [i + 1,j - 1] 的子串是否为回文子串
- 如果 i 位置的字符 != j 位置的字符,那么说明下标 [i,j] 的字符串不是回文子串
所以下标为 [i,j] 的字符串为回文串的条件是:arr[i] == arr[j] 且 [i+1,j-1] 的字符串是回文串
1 | public String longestPalindrome(String s) { |
6、将有序数组转换为二叉搜索树
6.1、题目描述
给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
6.2、解题思路
- 获取数组中的中间值,以这个值作为根节点构建树
- 递归向左向右构造子树
6.3、解题代码
1 | public TreeNode sortedArrayToBST(int[] nums) { |
7、验证二叉搜索树
7.1、题目描述
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树,一棵二叉搜索树必须满足以下条件:
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
7.2、解题思路
- 中序遍历法
中序遍历二叉搜索树,将结果放入一个数组中,然后判断这个数组是否为一个有序数组即可
- 使用递归 + 上下界的方法解决
在一棵二叉搜索树中,当前节点的值应该是其左子树节点值集合的上界,同时是其右子树节点值集合的下界
对于以 root 为根的树,我们要求其必须满足
下界 < root.val < 上界
,如果有节点的值不满足上面的条件,那么返回 false
在递归调用左子树时,将该节点的值作为上界传入;
在递归调用右子树时,将该节点的值作为下界传入;
上下界初始化为
Null
注意,在这道题中不能简单地觉得只需要满足
this.left.val < this.val < this.right.val
即可,比如下面的这棵树满足上面的条件,但是不是一棵 BST
我们以这棵树为例,来分析它的解题过程
- 初始化上下界为 Null
- 向左递归,此时将 5 作为上界传入,此时对于以 4 为根的子树而言,上下界分别为 5 , null ,对于 4 而言,4 < 5 满足条件
- 进一步向 4 的左子树递归,此时对于 1 而言,它的上下界分别为 4 和 null
- 向 4 的右子树递归,此时对于 7 而言,它的上界为 5 ,下界为 4 (4 将自己作为右子树的下界),此时由于 7 不在 (4,5) 内,所以这棵树不是一棵 BST
7.3、解题代码
- 中序遍历法
1 | List<Integer> list = new ArrayList<>(); |
- 递归法
1 | public boolean isValidBST(TreeNode root) { |
8、恢复二叉搜索树
8.1、题目描述
给你二叉搜索树的根节点
root
,该树中的两个节点被错误地交换。请在不改变其结构的情况下,恢复这棵树。
- 示例一
输入:root = [1,3,null,null,2]
输出:[3,1,null,null,2]
解释:3 不能是 1 左孩子,因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
8.2、解题思路
由于二叉搜索树的中序遍历结果是一个有序列表,所以我们通过判断遍历得到的列表之中的逆序对数量来决定接下来这一步应该怎么做
- 有一对逆序对
这种情况下,我们将这对逆序对的第一个元素记为 i ,将第二个元素记为 j ,然后交换这两个节点的值即可恢复二叉树。
比如,在这个列表 [1,3,2,4,5,6],由于只出现了一个逆序对,所以我们只需要将 3 和 2 交换位置即可
- 有两个逆序对
这种情况下,我们要找到这两个逆序对的位置,分别记为 i ,i + 1,j ,j + 1,然后交换 i 和 j + 1 元素的位置即可恢复二叉搜索树
比如,在这个列表 [1,6,3,4,5,2,7],由于出现了两个逆序对 [6,3] 和 [5,2] ,要想恢复原状,那么我们需要将 6(i) 和 2 (j + 1)的值交换
8.3、解题代码
1 | public void recoverTree(TreeNode root) { |
9、有序链表恢复为二叉搜索树
9.1、题目描述
给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
- 示例
1 | 给定的有序链表: [-10, -3, 0, 5, 9], |
9.2、解题思路
将链表转换为数组,根据数组进行构建
使用快慢指针
初始化两个指针,一个每次走两步,起始位置指向 head 的快指针,一个每次走一步,起始位置指向 head 的慢指针
同时定义一个指针,这个指针需要指向 slow 的前一个节点,我们不为初始化它,而是在 slow 指针运动过程中为它动态赋值(先让他指向 slow 指针指向的节点,然后 slow 后移)
- 快指针每次走两步,而剩下两个指针每次走一步,当快指针快走到链表尽头时,此时慢指针指向链表中间位置的节点
- 我们可以借鉴将有序数组转换为二叉搜索树的做法,将这个链表分为三部分,第一部分是 [head, preSlow] ,作为二叉搜索树的左子树, 第二部分是 slow ,作为二叉搜索树的 root ,第三部分是 [slow.next, null] ,作为二叉搜索树的右子树
9.3、解题代码
- 转换为有序数组
1 | public TreeNode sortedListToBST(ListNode head) { |
- 使用快慢指针
1 | public TreeNode sortedListToBST(ListNode head) { |