目 录CONTENT

文章目录

算法学习-哈希表

Sakura
2023-09-18 / 0 评论 / 0 点赞 / 30 阅读 / 9140 字 / 正在检测是否收录...

242.有效字母的移位词

242. 有效的字母异位词 - 力扣(LeetCode)

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

注意:若 st 中每个字符出现的次数都相同,则称 st 互为字母异位词

# 示例 1:
输入: s = "anagram", t = "nagaram"
输出: true

# 示例 2:
输入: s = "rat", t = "car"
输出: false
type void struct{}
var Empty void

func isAnagram(s string, t string) bool {
	// 创建一个存放所有字母的数组
	Hash := [26]int{}

	// value是字母的ascII码值 - 'a' 就是每个字母的索引
	// a : 97 - 97 = 0 索引 再++,即为索引为0的的元素加一
	// b : 98 - 97 = 1 索引
	for _, value := range s {
		Hash[value-'a']++
	}
	for _, value := range t {
		Hash[value-'a']--
	}

	return Hash == [26]int{}
}

349.两个数组的交集

349. 两个数组的交集 - 力扣(LeetCode)

给定两个数组 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] 也是可通过的

由于 golang 没有 set , 可以用 map 传入空结构体

思路:

  1. 先将 nums1 存入 map 去重

  2. 再遍历 nums2 , 查找每个元素是否在 map 中

  3. 如果存在 , 存入一个新 map , 然后再将 map 遍历存入切片

func Intersection(nums1 []int, nums2 []int) []int {
	map1 := make(map[int]void)
	resultmap := make(map[int]void)
	//先把所有元素放到hash表中
	for i := 0; i < len(nums1); i++ {
		map1[nums1[i]] = Empty
	}
	for _, value := range nums2 {
		_, bool := map1[value]
		if bool {
			resultmap[value] = Empty
		}
	}
	resultslice := []int{}
	for key, _ := range resultmap {
		resultslice = append(resultslice, key)
	}

	fmt.Println(map1)
	fmt.Println(resultslice)
	return resultslice
}
  • 优化版

func Intersection(nums1 []int, nums2 []int) []int {
	set := make(map[int]struct{}, 0) // 用map模拟set
	res := make([]int, 0)
	// 将nums1里的所有元素存入set
	for _, v := range nums1 {
		set[v] = struct{}{}
	}
	// 遍历nums2,判断元素是否在set中
	for _, v := range nums2 {
		//如果存在于上一个数组中,则加入结果集,并清空该set值
		if _, ok := set[v]; ok {
			res = append(res, v)
			// 删除set里面的值,防止重复
			delete(set, v)
		}
	}
	return res
}

208.快乐数

202. 快乐数 - 力扣(LeetCode)

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

「快乐数」定义为:

  • 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。

  • 然后重复这个过程直到这个数变为1,也可能是无限循环但始终变不到 1

  • 如果这个过程结果为1,那么这个数就是快乐数。

如果 n 是快乐数就返回 true ; 不是,则返回 fase

# 示例 1:
输入:n = 19
输出:true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

# 示例 2:
输入:n = 2
输出:false
func IsHappy(n int) bool {
	m := make(map[int]bool)
	fmt.Println(m[n])
	for n != 1 && !m[n] {
		n, m[n] = getSum(n), true
	}

	return n == 1
}

func getSum(n int) int {
	sum := 0
	for n > 0 {
		sum += (n % 10) * (n % 10)
		n = n / 10
	}
	return sum
}

1.两数之和

1. 两数之和 - 力扣(LeetCode)

给定一个整数数组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]
func twoSum(nums []int, target int) []int {
	numsMap := make(map[int]int)
	resultSlice := make([]int, 0)
	// 将数组中每个元素存入map
	for key, value := range nums {
		// 算出需要相加等于target的值
		result := target - value
		//1.重点,先判断是否有值
		if _, bool := numsMap[result]; bool == true {
			resultSlice = append(resultSlice, numsMap[result], key)
			return resultSlice
		}
		// 2. 再将元素存入map
		numsMap[value] = key
	}
	return resultSlice
}

重点:

先判断 map 中是否有需要的值 , 再将元素存入map中

因为 nums = [ 3, 2, 4 ], target = 6 这个例子中 , 如果先把 3 存入map , 由于需要 3 才等于 6 , 那么查找的时候 , 索引为 1 的元素会重复 , 最后返回结果为[ 0, 0 ]

454.四数相加

454. 四数相加 II - 力扣(LeetCode)

给你四个整数数组nums1nums2nums3nums4 , 数组长度都是 n , 请你计算有多少个元组 ( i , j , k , 1 ) 能满足:

# 示例 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 是因为需要元素之和出现的次数

eg.

和为 3 出现了两次 [3] = 2

需要相加等于 0 的时候 , 如果出现了 -3 , 那么相当于有两个元组 , 返回值也应该是 2

func FourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
	m := make(map[int]int)
	count := 0

	// 遍历nums1和nums2数组,将元素之和出现的次数加入到map中
	for _, value1 := range nums1 {
		for _, value2 := range nums2 {
			// 相当于让key值存入之后让value++
			m[value1+value2]++
		}
	}
	// 遍历nums3和nums4数组
	// 找到如果 0-(c+d) 在map中出现过的话,就把map中key对应的value也就是出现次数统计出来
	for _, value3 := range nums3 {
		for _, value4 := range nums4 {
			// count加需要的数字出现的次数
			count += m[-value3-value4]
		}
	}

	return count
}

383.赎金信

383. 赎金信 - 力扣(LeetCode)

给你两个字符串:ransomNotemagazine , 判断ransomNote能不能由magazine里面的字符构成。

如果可以,返回true;否则返回false

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

本题使用 map 的空间消耗要比数组大一些的,因为map要维护红黑树或者哈希表,而且还要做哈希函数,是费时的!数据量大的话就能体现出来差别了。

所以数组更加简单直接有效 !

# 示例 1:
输入:ransomNote = "a", magazine = "b"
输出:false

# 示例 2:
输入:ransomNote = "aa", magazine = "ab"
输出:false

# 示例 3:
输入:ransomNote = "aa", magazine = "aab"
输出:true
func CanConstruct(ransomNote string, magazine string) bool {
	// 用长度为26的数组,记录字母
	record := [26]int{}

	// 如果ransomNode长度大于magazine,直接返回错误
	if len(ransomNote) > len(magazine) {
		return false
	}

	// 将magazine中所有字母存入arr
	for _, value := range magazine {
		record[value-'a']++
	}
	// 遍历ransomNote
	for _, value := range ransomNote {
		// 如果次数为0,那么直接返回false
		if record[value-'a'] == 0 {
			return false
		}
		record[value-'a']--
	}
	return true
}

15.三数之和

15. 三数之和 - 力扣(LeetCode)

# 示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。

# 示例 2:
输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 

# 示例 3:
输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 

18.四数之和

18. 四数之和 - 力扣(LeetCode)

0

评论区