今日算法小题总结

前言

今天开始我的刷题记录筑一下地基，回忆一下哈希算法：

散列表（Hash table，也叫哈希表），是依据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。哈希表是一种典型的以空间换时间的做法。

常用的构造散列函数的方法有：直接寻址法，数字分析法，平方取中法，折叠法，随机数法，除留余数法。

1.字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

1
2
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

1
2
输入: strs = [""]
输出: [[""]]

分析

简单理解是对于第一个单词，查找和它相同的都是由这些字母组成的其他单词，并push在一个数组内，最后将整体的数组输出

思路：对每个单词进行排序，排序后得到的字符串一定相同，判断是否相同

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
    const map = new Map()
    for (let str of strs) {
        // Array.from() 静态方法从可迭代或类数组对象创建一个新的浅拷贝的数组实例。
        // console.log(Array.from('foo'));Expected output: Array ["f", "o", "o"]
        let array = Array.from(str)
        array.sort()//['a','t','e']
        let key = array.toString()//a,t,e
        // map.get()返回指定键所映射的值，找不到返回undefined
        let list = map.get(key)?map.get(key):new Array()
        //判断是否有和第一个ate相等的，比如把eatpush进去
        list.push(str)
        map.set(key,list)
    }
    return Array.from(map.values())
};