hash table reflections

·data-structure-and-algorithm
#hash-table

242. 有效的字母异位词

题目：https://leetcode.cn/problems/valid-anagram/description/

我的解答

这题主要还是要了解 go 底层对于字符串和字符的处理，思路见过之后下次能再写出来就行：

  • 声明一个含有 26 个元素的空数组/切片，索引是 0 - 25，刚好对应字母 a - z，这是我们自己定义的映射

  • 分别遍历给的两个字符串，利用 ch - 'a' 来得到对应的下标，从而实现对于数组的操作

    • 遍历第一个字符串时，每次循环，数组对应下标的元素加一

    • 遍历第二个字符串时，每次循环，数组对应下标的元素减一

  • 最后遍历数组，判断数组里元素是否都是 0 即可

这是哈希相关的方法，时间复杂度只有 O(n)，go 语言底层对于 'a' 是直接当作一个 rune 类型（相当于 32 位的整型）来处理的，它对应的码点（ASCII）是 97

而字符变量在 go 里也是 rune 类型的，所以我们可以通过这种方式得到数组对应的下标，比如 ch 在遍历字符串时被赋值为 c，那此时 ch - 'a' 就是 99 - 97，结果是 2，刚好就对应数组中我们映射的下标为 2 的元素 c

1002. 查找共用字符

题目：https://leetcode.cn/problems/find-common-characters/description/

我的解答

这道题主要也还是用到了上一题的哈希法映射方式，以此来实现对于字符串数组的遍历和对每个字符出现次数的统计，虽然是简单题，但逻辑还是有点绕的，具体思路如下：

  • 声明一个含有 26 个元素的空数组，还是对应字母 a - z，将这个空数组用已给数组的第一个字符串来初始化，记录初始的映射，也同样还是用 counts[ch - 'a']++ 来记录字符出现次数

  • 使用一个循环，循环内声明另一个 temp 来记录其他字符串中字符的出现次数

    • 再嵌套一个循环遍历这个字符串，记录次数

    • 再使用另一个循环，用来比较 counts 和 temp 中的所有元素，如果同一索引下 counts 的元素更大，就将 temp 赋给 counts

  • 最后再声明一个空数组来记录要返回的结果，也是循环里再嵌套一个循环，内层循环里直接用 append 来为这个空数组追加值

注意事项：

  • 这道题的时间复杂度是 O(n * m)，而不是 O(n ^ 2)，其中 n 是字符串数组的长度，m 是每个字符串的长度，这两个是有本质区别的

    • 并不是所有嵌套循环的时间复杂度都是 O(n ^ 2)，这里内层循环的次数 m 和 n 是无关的，代表的意义也不一样

  • temp 一定要在循环内声明，如果在循环外声明，在遇到下一个新的字符串时，temp 的所有元素并不都是 0

    • 会导致可能某个字母只在两个字符串里出现，但并没有在第三个字符串里出现，却还是返回成结果了

  • 最后记录返回结果时别忘了要用 string() 转成字符串类型的，否则 'a' + i 的底层还是 rune 类型的，直接 append 会报错

349. 两个数组的交集

题目：https://leetcode.cn/problems/intersection-of-two-arrays/description/

我的解答

这题主要是要对 go 语言中如何用 map 模拟集合的方法比较熟练，主要考察的还是对语言的掌控能力，本质并不难，具体思路如下：

  • 先比较两个数组的长度，保证是对更短的那个切片建哈希，节省空间

    • 递归一下，就是在 if 里重新调用这个函数，把两个数组的位置颠倒一下就行

  • 用 make(map[int]struct{}, len(nums1)) 来模拟集合，其中 int 表示键是整型，struct{} 表示值为空的结构体类型，这样通过遍历第一个数组来给键赋值即可，不用关心值，值的赋值方式直接用 struct{}{} 表示是一个空的结构体来为键占位就行

  • 再模拟另一个集合并遍历另一个数组，这次遍历是为了比较第二个数组中的值是否在第一个数组中出现过，判断条件是 if _, ok := set1[v]; ok {}，这里要对如何通过已知的键来获取值的方式比较熟悉（顺便校验键是否存在），ok 是一个布尔类型的变量，如果出现过就把同样的值赋给这个新的集合的键

    • 另一种获得键值对的方式是用 range

  • 最后创建一个切片，将第二个集合的键用 append 追加到这个切片中，返回即可

注意事项：

  • 对于如何用 map 模拟集合一定要熟悉，特别是如何赋空值，要能看懂

  • 对于如何获取键值，相关操作要熟悉

  • 最后的切片初始化时，长度要为 0，容量才是第二个集合的长度，否则在追加时切片中会额外多出来几个零（如果只指定长度为第二个集合的长度的话）

202. 快乐数

题目：https://leetcode.cn/problems/happy-number/description/

我的解答

这题同样要用到上一题的哈希法，利用 map 来模拟集合，从而实现对于已经出现数的检测，具体思路如下：

  • 首先初始化一个 visited 集合，方法是一样的，集合用来存放已经出现过的数字

  • 用一个循环实现快乐数的遍历过程，条件是 n != 1，因为是以 n 为条件，所以主要的逻辑都写在循环内部

    • 首先检测当前 n 是否已经在 visited 里出现过，这里也是用到上一题的判断方式，考察对于 map 的键值对的基本操作，通过 _, seen := visited[n]; seen 实现，seen 这里是布尔类型

    • 然后将键存入集合中，值也是一样用空结构体即可 {}{}

    • 声明两个新变量，sum 用来记录新数的和，将 n 赋给 t 用来操作当前的整数

    • 进入一个新循环，当 t > 0 时，拆分当前整数并累加

      • 对 t 取 10 的模能得到最后一位数字 t % 10，用另一个新变量 d 接收，平方后再赋给 sum

      • 对 t 除 10 能去除其最后一位数字 t /= 10

    • 最后将 sum 赋给 n 即可，循环外正常返回 true

注意事项：

  • 别忘了初始化集合，也别忘了给集合的键值赋值

  • 对于如何拆分整数的操作要熟悉

1. 两数之和

题目：https://leetcode.cn/problems/two-sum/description/

我的解答

这道题就是经典的两数之和了，其实还是哈希法，但能识别出哈希法的前提还是要能想到，先把已经遍历过的数存进一个 map 里，在遍历下一个数的时候再回 map 里索引有没有需要的数，具体思路如下：

  • 跟前面两题一样，还是使用 map 来模拟集合，我们叫它 seen

  • 进入一个循环，遍历给的数组，新声明一个变量 need = target - v，v 是当前正在遍历的数

  • 循环内判断一下 seen 里面有没有跟 need 相等的数，如果有的话，我们就找到了这两个数，返回两个索引即可

  • 循环最后将已经遍历的数赋给 seen

  • 默认返回 nil

注意事项：

  • 对于 map 的索引操作还是要熟练，一共就两种方式，要牢记

  • 我们将数组赋给 seen 的时候，是将数组的索引当作值，将数组内的数字当作键，来赋给它的，不要搞反了

    • 因为题目要求返回数组的索引，所以我们才这样操作的，也刚好方便我们的操作思路

454. 四数相加 II

题目：https://leetcode.cn/problems/4sum-ii/description/

我的解答

这道题要我们找四个数组中一共有几个能满足 nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 这样的四元组 i, j, k, l，其实还是用到哈希法，思路也是从这个等式出发的，因为如果想让那个等式成立，那 nums1[i] + nums2[j] == -(nums3[k] + nums4[l]) 也肯定会成立，所以我们可以将暴力法的四层循环拆成两个两层循环，从而找到所有符合条件的四元组，具体思路如下：

  • 还是用 map 来模拟集合，这个集合用来记录第一个数组和第二个数组所有元素和的可能的情况，方便我们后面查询

  • 用一个双层循环将前两个数组所有元素和可能的情况写入集合，和写入键，频率写入值，合起来就是 sum12[x + y]++

  • 声明一个 count 变量，用来记录可能的四元组

  • 再用另一个双重循环，声明 target 这个变量，并将第三四个数组元素和的负值赋给它，它就是我们要索引的键

    • 在循环内部，还是用 freq, ok := sum12[target]; ok 这种方式来操作集合，作为判断条件

    • 如果找到了符合的，就 count++，刚好我们的值是出现频率

本题是中等题，但掌握基本思路、对 go 中集合的操作有一定熟练度后并不难，下面是注意事项：

  • 思路是从题目给的等式出发的，也就是说这样操作等式，我们肯定能得到所有可能的四元组，不会漏

  • 要注意我们是将两个数组的元素和当作集合的键，将频率当作值，所以才会直接用 ++ 递增值

383. 赎金信

题目：https://leetcode.cn/problems/ransom-note/description/

我的解答

这道题要用到前面几题的映射法，从而实现对于已有字母的出现次数的统计，下面是具体思路：

  • 先比较，如果 magazine 比 ransomNote 的长度还小，就直接返回 false

  • 用一个数组来映射（具体方法见题目 242）26 个字母，使用一个循环，将 magazine 里有的字母存到数组中

  • 用另一个循环，先判断当前字母还有没有使用次数，如果是 0 次的话就可以直接返回 false

    • 再正常索引

  • 默认返回 true

注意事项：

  • 还是要将当前字母存成键，剩余的使用次数存成值

  • 如果要使用 map 的话，值也要存可使用次数，而不能什么都不存

15. 三数之和

题目：https://leetcode.cn/problems/3sum/description/

我的解答

这道题还是挺难的，用的其实也不是哈希法，而是双指针法，时间复杂度最佳也为 O(n^2)，并且有非常多小细节需要注意，下面是具体思路：

  • 首先利用 go 的 sort 包中的 Ints 函数对给的数组进行升序排序，方便我们后面双指针法的遍历

  • 声明一个二维数组 results 和长度变量 length（多次用到的数据可以记录，这里记录给的数组的长度），进入一个 for 循环

  • 外层循环通过 i 来实现第一个数的选取，进入循环后要先判断当前 i 索引到数组中的数是否跟上一个数相同，来实现去重，如果相同的话直接 continue 即可跳出当前循环

  • 声明 target、left 和 right 三个变量，target 是记录我们的目标值，后面两个是用来双指针法遍历数组的

  • 外层循环中开一个内层循环，进入条件是 left < right，一进入就声明一下 sum 变量（同理，用的多的值就声明一下），然后开始进入关键判断

    • 如果 sum < target，就 left++，左指针向右走

    • 如果 sum > target，就 right--，右指针向左走

    • 如果二者相等，就将当前的三个数存到二重数组 results 中

      • 存完之后要再开两个循环，来去重，分别是对左指针和右指针的，如果左指针跟它后一个数相等，就 left++，如果右指针跟它前一个数相等，就 right--

      • 进入这两个循环的条件一定要有 left < right，因为在赋完值之后，我们并不知道剩下没有遍历到的数是否有重复的、重复了几个，所以要用 for 而不是 if

      • 最后别忘了在两个循环后面也要对左右指针进行移动，因为我们赋值了已经，这样就保证了下一个左右指针对应的数一定是新的

注意事项：

  • go 中的排序函数要会用，二维数组的声明和赋值也要熟悉，赋值也是用 append，第一个参数传 results，第二个传一个数组进去 []int{}

  • 外层循环的进入条件为 i < length - 2 而不是 i < length，因为三数之和至少要保证有三个数参与，所以 i 到数组中倒数第三个数时就已经是最后一种情况了

  • 由于题目要求去重，所以我们主要是通过比较当前数和下一个或者前一个数是否重复来实现的

    • 选取第一个数时是跟前面的数比，选取第二个数时是跟后面的数比，选取第三个数时是跟前面的数比

    • 这样就能保证不会排除三个数中有重复的情况的同时实现去重

  • 在实现去重时，要把索引的加减或大小判断放在索引值的前面，这样才会先对索引的那个数进行判断，如果先判断索引值的话就会导致越界

18. 四数之和

题目：https://leetcode.cn/problems/4sum/description/

我的解答

这道题跟上一道题三数之和的思路是十分类似的，也是用双指针法，思路就不再赘述了，四数最外层就多套一个循环就可以了，无论是多少数之和，都是外面一直用 for 循环嵌套，固定到只剩下最后两个数没有选择时，就可以进入双指针法了，一些注意事项如下：

  • 双指针法外的多个 for 循环嵌套时，固定数的变量要跟上一层的有关，比如最外层是 i := 0 和 i > 0（去重时），那下一层就得是 j := i + 1 和 j > i + 1，这样才能保证每层每个数的顺序都是固定的 i < j < left < right

  • 双指针法外的多个 for 循环，每一层都需要去重，遇到五数、六数之和，无非就是多嵌套几层 for 循环而已

整体总结

这一块的题目其实并不难，见过了掌握常用的思路即可，主要考察熟练度