代码随想录算法训练营第六天| 242.有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和 。

242.有效的字母异位词

题目链接：力扣题目链接

文章讲解：代码随想录(programmercarl.com)

视频讲解：学透哈希表，数组使用有技巧！Leetcode：242.有效的字母异位词

状态：AC

思路

• 方法一：使用map即可。键是字母的ASCII码、值为频率。分别用两个串构建两个map，再比较两个map是否相同。

• 方法二：看了卡哥给的代码发现优化空间还是很大的，使用一个map即可，存放s的情况。异位词满足两个条件：

  • 两个串等长。
  • 两个串中字母出现的频率相同。这一点可以用s串的map的value自减。

代码

//麻烦的方法
func isAnagram(s string, t string) bool {
	words1 := map[byte]int{}
	words2 := map[byte]int{}
	for i := 0; i < len(s); i++ {
		_, ok := words1[s[i]]
		if ok {
			words1[s[i]] += 1
		} else {
			words1[s[i]] = 1
		}
	}
	for i := 0; i < len(t); i++ {
		_, ok := words2[t[i]]
		if ok {
			words2[t[i]] += 1
		} else {
			words2[t[i]] = 1
		}
	}

	return reflect.DeepEqual(words1, words2)
}

// 简单的代码
func isAnagram(s, t string) bool {
	if len(s) != len(t) {
		return false
	}
	cnt := map[rune]int{}
	for _, ch := range s {
		cnt[ch]++
	}
	for _, ch := range t {
		cnt[ch]--
		if cnt[ch] < 0 {
			return false
		}
	}
	return true
}

349. 两个数组的交集

题目链接：力扣题目链接

文章讲解：代码随想录(programmercarl.com)

视频讲解：学透哈希表，set使用有技巧！Leetcode：349. 两个数组的交集

状态：AC

思路

从求交集可以看出是要使用集合的结构，但是在Go语言中并没有集合，所以我使用了map（并不是用map模拟set）。map中，键为nums1的每个元素，值只有三种状态：第一次出现是0，多次出现是1，在nums2也出现过是2，最后遍历map，找到值为2的key。

利用const和iota模拟枚举类型。

代码

const (
	NEW = iota
	EXIST1
	EXIST2
)

func intersection(nums1 []int, nums2 []int) []int {
	set := map[int]int{}  //类集合操作
	for _, v := range nums1 {
		if _, ok := set[v]; !ok {
			set[v] = NEW  // 第一个出现
		} else {  // 多次出现
			set[v] = EXIST1
		}
	}
	for _, v := range nums2 {
		if _, ok := set[v]; ok {  // nums2也出现
			set[v] = EXIST2
		}
	}
	var result []int
	for k, v := range set {
		if v == EXIST2 {
			result = append(result, k)
		}
	}
	return result
}

202. 快乐数

题目链接：力扣题目链接

文章讲解：代码随想录(programmercarl.com)

状态：AC

思路

1. 构造一个集合，用于存放每一次拆数求平方和的结果
2. 拆数
3. 判断结果是否是1，如果是return true
4. 如果不是1，判断结果是否在集合中，如果存在则说明出现了循环，return false

代码

func isHappy(n int) bool {
	set := map[int]bool{}  // 模拟集合
	for {
		sum := 0
        //拆数求平方和
		for n > 0 {
			sum += (n % 10) * (n % 10)
			n /= 10
		}
        //得到正确答案
		if sum == 1 {
			return true
		}
        
        //结果不在集合中则放入集合
		if _, ok := set[sum]; !ok {
			set[sum] = true
		} else {// 否则退出循环 return false
			break
		}
		n = sum // 新一轮的数
	}
	return false
}

1.两数之和

题目链接：力扣题目链接

文章讲解：代码随想录(programmercarl.com)

视频讲解：梦开始的地方，Leetcode：1.两数之和

状态：AC

思路

1. 遍历nums将元素存为map的key，将元素的索引存放为map的value；
2. 再遍历nums，查看target - v是否在key中，并返回两个值：nums元素的索引和map[target-v]

遍历两次还是思路上走弯路了，一次即可。

代码

//遍历两次
func twoSum(nums []int, target int) []int {
    mapNums := map[int]int{}
    for i, v := range nums {
       mapNums[v] = i
    }
    var result []int
    for i, v := range nums {
       if _, ok := mapNums[target-v]; ok && mapNums[target-v] != i {
          result = append(result, i)
          result = append(result, mapNums[target-v])
          break
       }
    }
    return result
}

func twoSum(nums []int, target int) []int {
	mapNums := map[int]int{}
	for i, v := range nums {
		if value, ok := mapNums[target-v]; ok {
			return []int{i, value}
		} else {
			mapNums[v] = i
		}
	}
	return []int{}
}

小结

• 这次的题目不算很难，做起来就很快，算上写博客的时间不到两个小时

• 对Go语言的map有了新的理解：

  test = map[int]int{}
  if value, ok := test[key]; ok {
  	// key存在的情况
  } else {
  	// key不存在的情况
  }

  // 使用反射来判断两个map是否相等
  import reflect
  reflect.DeepEqual(map1, map2)

  test = map[int]int{}
  test[1]--  // 即使不存在1，默认新增键值对{1:0}，然后再自减

• 第一次使用Go模拟枚举

  const (
  	A iota
      B
      C
  )