代码随想录day6 | 242 有效字母异位词 349 两个数组交际 202 快乐数 1 两数之和

hash表

• 遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法

242 判断字母异位词

• 关于字符串的遍历问题

// 什么情况下遍历的是rune []int36类型， 什么情况下遍历的是 char 字节类型 ？ 

s := "Hello, 世界"
for i, r := range s {
	fmt.Printf("Index: %d, Rune: %c, Type: %T\n", i, r, r)
}

// 通过for range遍历得到的是rune类型，中文以及其他字节超过1的字符能够正确被打印
Index: 0, Rune: H, Type: int32
Index: 1, Rune: e, Type: int32
Index: 2, Rune: l, Type: int32
Index: 3, Rune: l, Type: int32
Index: 4, Rune: o, Type: int32
Index: 5, Rune: ,, Type: int32
Index: 6, Rune:  , Type: int32
Index: 7, Rune: 世, Type: int32
Index: 10, Rune: 界, Type: int32


 s := "Hello, 世界"
for i := 0; i < len(s); i++ {
	fmt.Printf("Index: %d, Byte: %x, Char: %c\n", i, s[i], s[i])
}
// 通过原始的for索引方式遍历，如果出现多字节的字符，那么还是按照一个字节打印，导致出现无意义的字符
Index: 0, Byte: 48, Char: H
Index: 1, Byte: 65, Char: e
Index: 2, Byte: 6c, Char: l
Index: 3, Byte: 6c, Char: l
Index: 4, Byte: 6f, Char: o
Index: 5, Byte: 2c, Char: ,
Index: 6, Byte: 20, Char:  
Index: 7, Byte: e4, Char: ä
Index: 8, Byte: b8, Char: ¸
Index: 9, Byte: 96, Char: -
Index: 10, Byte: e7, Char: ç
Index: 11, Byte: 95, Char: -
Index: 12, Byte: 8c, Char: Œ

func isAnagram(s string, t string) bool {
	// 思路，分别便利s， t ， 用map存储字符出现的此处，一个遍历++ 一个遍历--。 最终通过判断map val ==0来判断是否是异位
	var codeMap = make(map[rune]int)

	// 首次遍历，塞入元素并计数
	for _, val := range s {
		codeMap[val]++
	}

	// 二次遍历，根据元素删除计数
	for _, val := range t {
		codeMap[val]-- 
	}

	// 检查map是否有非空计数字符
	for _, v := range codeMap{
		if v != 0 {
			return false
		}
	}
	return true
}
时间 遍历m+n  空间 n

// 思考 ab  abc这种为什么也能通过测试呢？
因为codeMap[val]-- 这里如果元素没在第一个遍历中存入，也会在第二个遍历中放入，只不过map值 = -1 同样不满足val ！= 0 跳出条件

349 两个数组交集

func intersection(nums1 []int, nums2 []int) []int {
	// 思考，map存储键为元素值，此时不存储元素数量

	var codeMap = make(map[int]struct{})  // 实现类似set结构 key 为元素值， val为空结构体
	var res []int
	for _, val := range nums1{
		codeMap[val] = struct{}{}
	}

	for _, val := range nums2{
		if _, ok := codeMap[val]; ok {  // 判断元素是否存在
			res = append(res, val)
			delete(codeMap, val) // 删除键值对，防止一直塞入
		}
	}

	return res
}
时间复杂度 m+n  空间 n

350 两数交集 ||

// 首次尝试 ，但是解法错误
func intersect(nums1 []int, nums2 []int) []int {
	// 思路，双循环
	var res []int

	for _, v1 := range nums1{
		var flag bool
		for _, v2 := range nums2{
			if v1 == v2 {
				flag = true
				break
			}
		}
		if flag {
			res = append(res, v1)
		}
	}

	return res
}


// 这里尝试遍历a, 如果元素出现再b中，那么就加入res，但是这样的算法不能处理所有的描述情况

// 如果 a=[1,2,2,2,2,2,3] b=[2,2,3]  ==> 正确结果是[2,2,3], 但是我的结果却是[2，2，2，2，2，3]， 因为没考虑两个列表中元素出现次数最小的情况

func intersect(nums1 []int, nums2 []int) []int {
	// 思路，两个map存储出现次数最小
	var res []int
	var mapa, mapb = make(map[int]int), make(map[int]int)
	for _, val := range nums1 {
		mapa[val]++
	}
	for _, val := range nums2 {
		mapb[val]++
	}

	// 遍历mapa，如果key 相等，那么对比val决定插入到res中几次
	for k, v := range mapa{
		if v2, ok := mapb[k]; ok {
			minv := min(v, v2)
			for i := 0; i < minv; i++ {
				res = append(res, k)
			}
		}
	}
	return res
}

时间 m+n  空间 M+N

202 快乐数

// 此题目关键在于题设中的无限循环，循环两个字，题目看不懂，再牛逼也没用
func isHappy(n int) bool {
	// 思路，题目说可能无限循环，那么就用map存储每次计算和，如果后续计算出现了此次和，那么就不是快乐数
	var codeMap = make(map[int]struct{})
	for n != 1 {  // 循环终止条件，出现happy数（平方和为1），或者出现循环
		if _, ok := codeMap[n]; ok{  // 如果出现循环，不是happy num
			return false
		}
		codeMap[n] = struct{}{}
		n = sumHappy(n)
	}
	return true
}

func sumHappy(n int) int {
	var sum int
	for n > 0 {
		dig := n % 10
		sum += dig * dig
		n = n / 10
	}
	return sum
}
// 时间 各位平方和复杂度log10n ,  另一方面，快乐数的跳出条件， sum == 1 || sum出现循环，都是一个有限的常数次数c，所以 最终复杂度logn

// 空间 n

1 两数之和

func twoSum(nums []int, target int) []int {
	// 思考，双循环太简单不写了，在集合中查找某个元素优先考虑哈希表

	var codeMap = make(map[int]int)
	// codeMap 用来存储元素，以及差值

	for idx, num := range nums{
		codeMap[target - num] = idx	// 数组中元素不会重复，所以无需考虑值覆盖
	}

	for idx, num := range nums {
		if v, ok := codeMap[num]; ok && v != idx{
			return []int{idx, v}
		}
	}
	return []int{}
}
时间 n 空间 n