用 javascript 分类刷 leetcode16.set&map(图文视频讲解)
集合与字典 :
集合常见的形式是 Set,字典常见的形式是 Map
Set 和 Map 主要的应用场景在于 数据重组 和 数据储存。
集合 与 字典 的区别:
共同点:集合、字典 可以储存不重复的值
不同点:集合类似于数组,元素的只有 key 没有 value,value 就是 key。字典是以 [key, value] 的形式储存,键的范围不限于字符串,各种类型的值(包括对象)都可以当作键
时间复杂度:
set 或 map 可以用哈希表或平衡二叉搜索树实现
哈希表实现的 map 或者 set 查找的时间复杂度是O(1)
,哈希表优点是查找非常快,哈希表的缺点是失去了数据的顺序性,平衡二叉搜索树实现的 map 或 set 查找时间复杂度是O(logn)
,它保证了数据顺序性
哈希函数
哈希函数是一个接受输入值的函数,由此输入计算出一个确定输出。
均匀分布:哈希函数计算出来的地址均匀分布
哈希碰撞:哈希函数计算出来的结果冲突
开放定址法
链地址法
242. 有效的字母异位词 (easy)
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"输出: true 示例 2:
输入: s = "rat", t = "car"输出: false
提示:
1 <= s.length, t.length <= 5 * 104s 和 t 仅包含小写字母
进阶: 如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?
方法 1.排序
思路:两个字符串转成数组,排序后转回字符串进行比较。
复杂度分析:时间复杂度
O(nlogn)
,排序采用快排,时间复杂度是 nlogn,比较两字符串是否相等时间复杂度为 n,O(n)+O(nlogn)=O(nlogn)
。空间复杂度为O(logn)
,排序需要O(logn)
的空间,java 和 js 字符串是不可变的,需要额外的O(n)
空间来拷贝字符串,我们忽略这个复杂度,这依赖不同语言实现的细节。
方法 2.哈希表:
思路:采用空间换时间的策略,准备一个数组,循环字符串 s,每个元素出现一次加 1,然后循环 t 元素,每次出现的字符减 1,如果 t 中出现一些不在 s 中的字符 则返回 false,所有循环结束 说明两个字符串中每个字符的数量相同
复杂度分析: 时间复杂度
O(n)
,n 是字符串的长度,空间复杂度O(s)
,s 为字符集大小
js:
454. 四数相加 II( medium)
给你四个整数数组 nums1、nums2、nums3 和 nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足:
0 <= i, j, k, l < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
示例 1:
输入:nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]输出:2 解释:两个元组如下:
(0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
(1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0 示例 2:
输入:nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]输出:1
提示:
n == nums1.lengthn == nums2.lengthn == nums3.lengthn == nums4.length1 <= n <= 200-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228
方法 1:哈希表
思路:在 A 和 B 中取出两个数的组合,将这两个数的和作为键,出现次数作为值加入哈希表中,循环 C、D,判断 C 和 D 中是否存在两个数的和 加 AB 中的俩元素的和正好是 0,统计组合数
复杂度:时间复杂度
O(n^2)
,两个嵌套循环。空间复杂度O(n^2)
,哈希表的空间,最差的情况下是n^2
js:
187. 重复的DNA序列 (medium)
DNA 序列 由一系列核苷酸组成,缩写为 'A', 'C', 'G' 和 'T'.。
例如,"ACGAATTCCG" 是一个 DNA 序列 。在研究 DNA 时,识别 DNA 中的重复序列非常有用。
给定一个表示 DNA 序列 的字符串 s ,返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。
示例 1:
输入:s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"输出:["AAAAACCCCC","CCCCCAAAAA"]示例 2:
输入:s = "AAAAAAAAAAAAA"输出:["AAAAAAAAAA"]
提示:
0 <= s.length <= 105s[i]=='A'、'C'、'G' or 'T'
思路:用 map 存储子串出现的次数,循环 dna 序列,每次截取长度为 10 的子串,加入 map 中 并更新出现的次数,次数超过 2,加入 ans
复杂度:时间复杂度
O(n)
,n 是字符串的长度。空间复杂度O(n)
js:
1. 两数之和 (easy)
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1:
输入:nums = [2,7,11,15], target = 9 输出:[0,1]解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。示例 2:
输入:nums = [3,2,4], target = 6 输出:[1,2]示例 3:
输入:nums = [3,3], target = 6 输出:[0,1]
提示:
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109 只会存在一个有效答案进阶:你可以想出一个时间复杂度小于 O(n2) 的算法吗?
方法 1.暴力枚举
思路:两层 for 循环,第一层
for i:0->n
-1, 枚举 nums 中的每一个数 x,第二层for j:i+1->n-1
,寻找是否存在两个数字的和是 target。复杂度分析:时间复杂度:
O(n^2)
, n 为数组的长度。空间复杂度O(1)
。
方法 2.哈希表:
思路:方法一第一层循环是必须的,关键是优化第二次循环,也就是寻找
targrt-x
的过程,这里关键采用空间换时间,也就是采用哈希表进行优化,让查找的过程变为O(1)
。首先还是遍历 nums 数组,然后在哈希表中寻找target-x
,如果不存在就把当前元素 x 和下标存入哈希表,如果存在就返回target-x
和当前元素的下标复杂度分析:时间复杂度
O(n)
, n 为数组的长度,空间复杂度O(n)
,n 为数组的长度,主要是哈希表的空间开销
js:
447. 回旋镖的数量 (medium)
给定平面上 n 对 互不相同 的点 points ,其中 points[i] = [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 ,其中 i 和 j 之间的距离和 i 和 k 之间的欧式距离相等(需要考虑元组的顺序)。
返回平面上所有回旋镖的数量。
示例 1:
输入:points = [[0,0],[1,0],[2,0]]输出:2 解释:两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]示例 2:
输入:points = [[1,1],[2,2],[3,3]]输出:2 示例 3:
输入:points = [[1,1]]输出:0
提示:
n == points.length1 <= n <= 500points[i].length == 2-104 <= xi, yi <= 104 所有点都 互不相同
思路:循环数组,找出与当前元素距离相同的点,记录频次加入 map 中,最后循环 map,从相同距离的数量中选取两个组合出来,加入结果中。从 m 个元素中选取两个的排列组合数 是
m*(m-1)
复杂度:时间复杂度
O(n^2)
,数组遍历两层,空间复杂度O(n)
,哈希表的空间
js:
49. 字母异位词分组 (medium)
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母通常恰好只用一次。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]输出: [["bat"],["nat","tan"],["ate","eat","tea"]]示例 2:
输入: strs = [""]输出: [[""]]示例 3:
输入: strs = ["a"]输出: [["a"]]
提示:
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i] 仅包含小写字母
方法 1.排序
思路:遍历字符串数组,对每个字符串中的字符排序,加入 map 对应的 key 的数组中。
复杂度:时间复杂度
O(n*klogk)
,n 是字符串的个数,k 是最长的字符串的长度,排序复杂度O(klogk)
,n 次排序,哈希表更新O(1)
。空间复杂度O(nk)
,排序空间复杂度O(nlogk)
,map 空间复杂度O(nk)
,取较大的O(nk)
js:
方法 2.计数
思路:题意是字符串的字符都是小写,可以对每个字符串统计其中字符的频次,将每个字符频次相同的字符串放在一组
复杂度:时间复杂度
O(n*k)
,n 是字符串个数,k 是最长字符串长度,循环字符串数组复杂度O(n)
,对每个字符串统计频次复杂度O(k)
。空间复杂度O(n*k)
,map 中存放了 n 个大小最长为 k 的字符串。
js:
视频讲解:传送门
评论