Skip to content

Latest commit

 

History

History
408 lines (336 loc) · 8.97 KB

05.3.md

File metadata and controls

408 lines (336 loc) · 8.97 KB
Raw
title date category
5.3 哈希表应用
2023-09-11
algorithm

若哈希表的Key取值范围固定, 且范围不大, 那么可以使用数组来模拟哈希表.

5.3.1 问题32: 有效的变位词

给定两个字符串 s 和 t ，编写一个函数来判断它们是不是一组变位词（字母异位词）。

注意：若 *s* 和 *t* 中每个字符出现的次数都相同且字符顺序不完全相同，则称 *s* 和 *t* 互为变位词（字母异位词）。

示例 1:

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

示例 2:

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

示例 3:

输入: s = "a", t = "a"
输出: false

提示:

  • 1 <= s.length, t.length <= 5 * 104
  • s and t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

5.3.1.1 分析

仅包含小写字母

若只包含小写字母, 那么使用长度为26的数组来模拟哈希表即可:

  1. 创建哈希表 (字母, 出现次数)
  2. 录入字符串s1, 出现的字母次数加一
  3. 遍历字符串s2:
    1. 若字母次数直接为0, 表示出现不同字母或相同字母次数不同
    2. 当前字母次数减一(用于判断相同字母)

包含所有的Unicode

此时就需要使用真正哈希表来处理

5.3.1.2 题解

func isAnagramWithArray(s string, t string) bool {
	// 边界条件
	if len(s) != len(t) {
		return false
	}

	if s == t {
		return false
	}

	// 仅包含小写字母, 使用数组
	cnt := make([]int, 26)

	for _, c := range s {
		cnt[c-'a']++
	}

	for _, c := range t {
		if cnt[c-'a'] == 0 {
			return false
		}
		cnt[c-'a']--
	}

	return true
}

func isAnagramWithHashTable(s string, t string) bool {
	// 边界
	if len(s) != len(t) {
		return false
	}
	if s == t {
		return false
	}

	// 使用哈希表
	cnt := make(map[rune]int)

	for _, c := range s {
		cnt[c]++
	}
	for _, c := range t {
		if cnt[c] == 0 {
			return false
		}
		cnt[c]--
	}

	return true
}

5.3.2 问题33: 变位词分组

LCR 033. 字母异位词分组

给定一个字符串数组 strs ，将 变位词 组合在一起。 可以按任意顺序返回结果列表。

**注意：**若两个字符串中每个字符出现的次数都相同，则称它们互为变位词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

  • 1 <= strs.length <= 104
  • 0 <= strs[i].length <= 100
  • strs[i] 仅包含小写字母

5.3.2.1 分析&题解

若单词互为异位词, 那么将其按字母排序后的字符串一定相同.

  1. 构建哈希表 (排序后的单词, 单词组)
  2. 遍历数组, 对每个单词排序后进行分组
func groupAnagrams(strs []string) [][]string {
	// 哈希表
	m := make(map[string][]string, len(strs))

	result := make([][]string, 0)

	for _, s := range strs {
		// 字符串排序

		// using unsafe
		// bts := unsafe.Slice(unsafe.StringData(s), len(s)) // go 1.20
		// bts := *(*[]byte)(unsafe.Pointer(&s)) // before go 1.20
		// bs := make([]byte, len(bs))
		// copy(bs, bts)

		// not using unsafe
		bs := []byte(s)
		sort.Slice(bs, func(i, j int) bool {
			return bs[i] < bs[j]
		})
		// sortedStr := unsafe.String(unsafe.SliceData(bs), len(bs))
		sortedStr := *(*string)(unsafe.Pointer(&bs)) // before go 1.20
		// 记录至哈希表
		if _, ok := m[sortedStr]; !ok {
			m[sortedStr] = make([]string, 0)
		}
		m[sortedStr] = append(m[sortedStr], s)
	}

	for _, v := range m {
		result = append(result, v)
	}

	return result
}

​ 使用unsafe 进行字符串/字节数组的转换效率要高于直接的类型转换(How do I convert bytes to string in Go?)

  • go1.20 之前和之后的方式不同(1.20之后有更方便的函数)
  • 使用unsafe转换的字节数组不能直接进行排序(引发panic), 需要复制到另一数组

5.3.3 问题34: 外星语言是否排序

LCR 034. 验证外星语词典

某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。

给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

示例 1：

输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
输出：true
解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。

示例 2：

输入：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
输出：false
解释：在该语言的字母表中，'d' 位于 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。

示例 3：

输入：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
输出：false
解释：当前三个字符 "app" 匹配时，第二个字符串相对短一些，然后根据词典编纂规则 "apple" > "app"，因为 'l' > '∅'，其中 '∅' 是空白字符，定义为比任何其他字符都小（更多信息）。

提示：

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 20
  • order.length == 26
  • 在 words[i] 和 order 中的所有字符都是英文小写字母。

5.3.3.1 分析&题解

使用哈希表将字母表的字母及其顺序记录下来, 遍历数组进行比较.

func isAlienSorted(words []string, order string) bool {
    // 哈希表记录字母顺序
    orderArr := make([]int, len(order))
    for i, c := range order {
       orderArr[c-'a'] = i
    }
    
    // 比较单词 
    for i := 0; i < len(words) - 1; i++ {
       if !isSorted(words[i], words[i+1], orderArr) {
          return false
       }
    }
    
    return true
}

func isSorted(s1, s2 string, orderArr []int) bool{
    i := 0
    for ; i < len(s1) && i < len(s2); i++ {
       if s1[i] != s2[i] {
          return orderArr[s1[i]-'a'] < orderArr[s2[i]-'a']
       }
    }
    
    return i == len(s1)
}

5.3.4 问题35: 最小时间差

LCR 035. 最小时间差

给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

示例 1：

输入：timePoints = ["23:59","00:00"]
输出：1

示例 2：

输入：timePoints = ["00:00","23:59","00:00"]
输出：0

提示：

  • 2 <= timePoints <= 2 * 104
  • timePoints[i] 格式为 "HH:MM"

5.3.4.1 分析

暴力解法

将数组元素配对求时间差, $O(n^2)$

排序

将数组元素排序之后, 只需求相邻元素的时间差即可, $O(nlogn+n)$即 $O(nlogn)$

哈希表

由于一天内的时间是固定的, 而输入值只精确到分钟, 那么可以创建哈希表(时间, 是否出现)来表示所有的情况, 哈希表长度为$1440 = 24 \times 60$ .

比较时间差时, 要考虑两种情况:

  1. 当天的时间差 (当天零点和二十三点)
  2. 第二天之后的时间差(第二天零点和当天的二十三点)

计算时只需考虑两种情况之后, 再取较小的值即可.

此时遍历哈希表一次即可, 计算相邻的元素时间差.

边界条件

若输入的时间数组长度大于1440, 那么必定有相同的时间, 最小时间差必为0

5.3.4.2 题解

func findMinDifference(timePoints []string) int {
	totalMin := 24 * 60
	// 边界条件
	if len(timePoints) >= totalMin {
		return 0
	}

	// 创建哈希表
	minFlags := make([]int, totalMin)
	// 记录情况
	for _, t := range timePoints {
		hour, _ := strconv.Atoi(t[0:2])
		min, _ := strconv.Atoi(t[3:])
		mins := hour*60 + min
		// 出现重复的时间
		if minFlags[mins] == 1 {
			return 0
		}
		minFlags[mins] = 1
	}

	// 计算时间差
	prev := -1                   // 前一时间
	first := len(minFlags) - 1   // 最早
	last := -1                   // 最晚
	minDiff := len(minFlags) - 1 // 最小时间差
	for i := range minFlags {
		if minFlags[i] == 1 {
			if prev != -1 {
				minDiff = min(i-prev, minDiff)
			}
			prev = i
			first = min(i, first)
			last = max(i, last)
		}
	}
	// 最早最晚的时间差
	minDiff = min(first+len(minFlags)-last, minDiff)

	return minDiff
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Reference

  1. 剑指Offer（专项突破版）