哈希表算法（2）

date
tag , ,

# 202. 快乐数

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 <= 231 - 1

# 思路

这道题看上去貌似是一道数学问题，其实并不是！

题中说了会 无限循环，也就是说求和的过程中，sum 会反复出现。

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

所以这道题用哈希法来判断 sum 是否重复出现。如果重复了就 return false， 否则一直找到 sum 为止。

判断 sum 是否重复出现可以用 map[int][bool].

还有一个难点是求和的过程，要对 取数值各个位上的单数 很熟悉。

这道题还学到一点，return n == 1

这里的 n == 1 是个比较表达式，它的值是 bool，并不是把整数当作 bool 来用。等价于

if n == 0 {

	return true

} else {

	return false

}

详细代码：

func isHappy(n int) bool {
    hash := make(map[int]bool)
    for n != 1 && !hash[n] {
        hash[n] = true
        n = getsum(n)
    }
    // 这里是一个比较表达式，值是bool，而不是把整数当作 bool 值
    return n == 1
}

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

# 1. 两数之和

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]

提示：

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

力扣第一题却难度不低，属于哈希表的题。

# 暴力解法，2层 for 循环

噩梦开始的地方。。。

第一次写用了两层 for 循环。

func twoSum(nums []int, target int) []int {
    len := len(nums)
    for i, num := range nums {
        for j := i + 1; j < len; j++ {
            if tar := num + nums[j]; tar == target {
                return []int{i,j}
            }
        }
    }
    return nil
}

# 哈希表（最优解）

map key 存数组的值，value 存数组的下标，来记录出现过的元素。

func twoSum(nums []int, target int) []int {
    m := make(map[int]int) // 值 -> 下标
    for i, num := range nums {
        if j, ok := m[target-num]; ok {
            return []int{j, i}
        }
        m[num] = i
    }
    return nil
}

# 四数相加 II

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

提示：

  • n == nums1.length
  • n == nums2.length
  • n == nums3.length
  • n == nums4.length
  • 1 <= n <= 200
  • -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

# 思路–哈希表

先遍历数组 A 和数组 B，用 map 记录 a+b 出现的次数。

再遍历数组 C 和数组 D， 查询 map 中是否出现 0-(c+d)， 如果出现，counter += value。

相当于转化为了两数之和。

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
    hash := make(map[int]int)
    counter := 0
    for _, a := range nums1 {
        for _, b := range nums2 {
            hash[a+b]++
        }
    }

    for _, c := range nums3 {
        for _, d := range nums4 {
            if v, ok := hash[0 - (c + d)]; ok {
                counter += v
            }
        }
    }
    return counter
}

为什么遍历 A、B 再遍历 C、D？为什么不能先遍历 A 再遍历 B、C、D？

两两遍历，时间复杂度是 n^2 ；后者的时间复杂度是 n^3。

# 赎金信

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

提示：

  • 1 <= ransomNote.length, magazine.length <= 105
  • ransomNote 和 magazine 由小写英文字母组成

# 思路

这道题和 242.有效的字母异位词 很像。242 相当于求字符串a和字符串b是否可以相互组成，而这道题是求字符串a能否组成字符串b，而不用管字符串b能不能组成字符串a。

注意：

  • magazine 中的每个字符只能在 ransomNote 中使用一次。
  • 由小写英文字母组成

思路就是用哈希表来存每个字母出现的次数。

# 哈希法–map

func canConstruct(ransomNote string, magazine string) bool {
    hash := make(map[rune]int)
    for _, c := range magazine {
        hash[c]++
    }
    for _, c := range ransomNote {
        if hash[c] == 0 {
            return false
        }
        hash[c]--
    }
    return true
}

# 哈希法–数组

func canConstruct(ransomNote string, magazine string) bool {
    hash := [26]int{}
    for _, c := range magazine {
        index := c - 'a'
        hash[index]++
    }
    for _, c := range ransomNote {
        index := c - 'a'
        if hash[index] > 0 {
            hash[index]--
        } else if hash[index] == 0 {
            return false
        }
    }
    return true
}
归档 友链
arrow_up
theme