Ltd的算法大抄·哈希表

这是算法记录的第五天，主要是哈希表的使用

对应leetcode题目为242.349.202.1.454.383

哈希表

242.有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意： 若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

s 和 t 仅包含小写字母

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

思路

记录s的字母出现次数，再与t的进行比较，若所有字母出现次数相等那么就满足条件。

因为只有小写字母，且字母个数是有限个并为26个，所有这里可以直接用数组来存放26个字母，并使用这26个字母的ascii与基准值'a'的差值（这样的话正好是从0到25个值）来作为哈希表的索引下标。

这样遍历s，会得到s所有字母对应的个数（无须保存字符具体是啥，有个相对位置就行了）。再遍历t，若有相同的字母就减1，这样最终结果不为全0的话说明两个字符串不一样，否则就说明所包含的字母及其个数一样，满足互为字母异位词。

代码

func isAnagram(s string, t string) bool {
	record := [26]int{}
	//遍历s，记录下每个字母个数
	for _, i := range s {
		record[i-'a']++
	}
	//遍历t，对每个存在的
	for _, i := range t {
		record[i-'a']--
	}
	//int数组默认全零
	return record == [26]int{}
}

349.两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

思路

使用哈希中的set结构，存放第一个数组所有元素（自动去重），再遍历第二个数组，若有相同的就保存在新数组中，最后返回新数组就可以了

代码

//使用map模拟set，因为set的k是去重的，所以先把第一个数组的值作为k放到set中，然后再去遍历第二个数组，若存在就先删除
func intersection(nums1 []int, nums2 []int) (res []int) {
	set := map[int]struct{}{}
	for _, v := range nums1 {
		//只关心前半部分就行了
		set[v] = struct{}{}
	}
	for _, v := range nums2 {
		if _, exit := set[v]; exit {
			res = append(res, v)
			//删除这个元素，避免nums2中有多个相同值
			delete(set, v)
		}
	}
	return res
}

注意

由于在 Go 中没有原生的 set 数据类型，因此通常使用 map 实现 set。

因为 map 中的键必须是唯一的，因此将一个值添加到 map 中，实际上就是将该值作为键添加到 map 中，并将其对应的值设置为一个任意的非零值，这里使用的是空结构体。

1. 节省内存：空结构体不需要任何额外的内存分配，因此使用空结构体作为 map 的值类型可以最大程度地减少内存占用。
2. 可读性：使用空结构体作为 map 的值类型可以更清晰地表达这个 map 只是用于存储键的集合，而不需要关心值的具体内容。
3. 避免误用：由于空结构体没有任何字段或方法，因此无法通过 map 中的值进行操作。这有助于避免在集合使用期间对值进行误用，从而提高代码的可靠性。

202.快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

输入：n = 2
输出：false

思路

首先看到这题，感觉会包含三种情况：

1. n变成1，满足条件
2. n不为1，产生循环了
3. n越来越大，无限不循环下去

前两种是肯定会产生的，关键在于第三种情况是否会出现，下面进行一下分析：

下面为了方便，把每一位的平方之和均简称为平方和

可以看到，一旦n是任意三位数，最大平方和只会小于等于243，所以一定会在243里面循环，而不会出现越算越大的情况；而即使是大于三位数，在进行一两次（有限次）循环后就会快速变为3位数（81×13=1053），所以第三种情况一定不会出现，这样就可以只考虑前两种了。

第三种情况不存在，对于n来说不会无限不循环下去，for循环就是有限次，所以还是可以使用hash，用map来记录每个n，并标记为true，用来判断这个值是否重复出现，然后计算出平方和赋值给n，判断这个新的n是否为1或是否出现过，若是跳出循环，否则继续循环。

代码

func isHappy(n int) bool {
	m := map[int]bool{}
	//当n不为1且没有循环的时候
	for n != 1 && !m[n] {
		sum := 0
		//进入循环就表示这是新出现的n，需要记录一下
		m[n] = true
		//求n的各位数的平方和
		for n > 0 {
			sum += (n % 10) * (n % 10)
			n = n / 10
		}
		//将n赋值为sum
		n = sum
	}
	return n == 1
}

实际编写的时候要注意赋值的位置，一步步理清思路就好。而不要像leetcode那样写一行第一眼看着就迷糊的代码

for ; n != 1 && !m[n]; n, m[n] = step(n), true { }

1.两数之和

给定一个整数数组 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]

思路

哈希，使用Map记录下每次遍历的值和位置，同时寻找能够与其匹配的值。

Map的k存放值，可以用来判断是否存在，v存放下标用于返回结果。

即，假设最后的结果是a、b两个数，a开始在map中找不到匹配的，但会存进去；当后面遍历到b的时候，就会找到a，这样两个节点都知道了，返回下标就行

代码

func twoSum(nums []int, target int) []int {
	m := map[int]int{}
	for i, v := range nums {
		//判断v需要的值是否存在，j就是下标值
		j, exit := m[target-v]
		if exit {
			//存在就返回下标
			return []int{i, j}
		} else {
			//不存在就把v放进去
			m[v] = i
		}
	}
	//找不到返回空切片
	return []int{}
}

454.四数相加II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (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

思路

由于是四个独立的数组，所以可以两两分组，先求出前两个数组所有和的结果作为map的k，该和出现的次数作为map的v，再对剩下两个数组进行遍历：若存在m[-c-d]即说明前两个数组中有和这c、d相加为0的元素，满足条件，就加上map对应的v值，否则继续遍历

代码

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
	m := map[int]int{}
	//两层for循环，计算出所有nums1、nums2包含的和，并保存到map中
	for _, a := range nums1 {
		for _, b := range nums2 {
			m[a+b]++
		}
	}
	sum := 0
	for _, c := range nums3 {
		for _, d := range nums4 {
            //出现了多少次就说明可以组合多少次
			sum += m[-c-d]
		}
	}
	return sum
}

383.赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

ransomNote 和 magazine 由小写英文字母组成

思路

这个和之前的242.非常像，就是一个变形。

都是小写字母，将数量定在了26个以内，所以仍然可以使用数组，字母与'a'的差值作为索引下标（0-25）

基本思路就是把其中一个字符串放进数组中，统计个数，然后和另一个字符串比较。实际操作的话有两种入手的，一个是先把ransomNote放进去，另一个是先把magazine放进去，再与剩下的进行比较，下面是先把randsomNote放进去的方式。

先把randsomNote放进num数组，对每一个字母++，获得包含索引与个数；然后遍历magazine，对每一个存在的字母–；最后再遍历数组，若存在一个值大于0的话就返回false，此时说明randsomNote的字母没有被匹配完

也可以先统计magazine有的，再对ransomNote一一读取，这样就可以在第二次循环中直接判断是否存在小于0的，省去了第三次遍历。

代码

func canConstruct(ransomNote string, magazine string) bool {
	num := [26]int{}
	for _, v := range ransomNote {
		fmt.Println(v - 'a')
		num[v-'a']++
	}
	for _, v := range magazine {
		fmt.Println(v - 'a')
		num[v-'a']--
	}
	for _, v := range num {
		if v > 0 {
			return false
		}
	}
	return true
}

• ← Previous Post
• Next Post →