2024-06-01-代码随想录-Day5-哈希表

other

Posted by berlinfog on June 1, 2024

链表

今日任务

242.有效的字母异位词

力扣题目链接

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

示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true

示例 2: 输入: s = “rat”, t = “car” 输出: false

说明: 你可以假设字符串只包含小写字母

//定义一个数组叫做record用来上记录字符串s里字符出现的次数。

//需要把字符映射到数组也就是哈希表的索引下标上,因为字符a到字符z的ASCII是26个连续的数值,所以字符a映射为下标0,相应的字符z映射为下标25。

//再遍历 字符串s的时候,只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可,并不需要记住字符a的ASCII,只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数,统计出来了。


func isAnagram(s string, t string) bool {
    record := [26]int{}
    for _,v := range s {
        record[v - 'a'] ++
    }
    for _,v := range t {
        record[v - 'a'] --
    }
    return record == [26]int{}
}
func isAnagram(s string, t string) bool {
    if len(s) != len(t) {
		return false
	}
	records := [26]int{}
	for index := 0; index < len(s); index++ {
		if s[index] == t[index] {
			continue
		}
		sCharIndex := s[index] - 'a'
		records[sCharIndex]++
		tCharIndex := t[index] - 'a'
		records[tCharIndex]--
	}
    
    return records == [26]int{}
}

349. 两个数组的交集

力扣题目链接

题意:给定两个数组,编写一个函数来计算它们的交集。

示例 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] 也是可通过的

提示:

1 <= nums1.length, nums2.length <= 1000 0 <= nums1[i], nums2[i] <= 1000

func intersection(nums1 []int, nums2 []int) []int {
    set := make(map[int]struct{},0)
    res := make([]int,0)

    for _,v := range nums1{
        if _,sv := set[v];!sv{
            set[v] = struct{}{}
        }
    }

    for _,v := range nums2{
        if _,sv := set[v];sv{
            res = append(res,v)
            delete(set,v)
        }
    }
    return res
}

第202题. 快乐数

力扣题目链接(opens new window)

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

「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果 可以变为 1,那么这个数就是快乐数。

如果 n 是快乐数就返回 True ;不是,则返回 False 。

示例:

输入:19 输出:true 解释: 1^2 + 9^2 = 82 8^2 + 2^2 = 68 6^2 + 8^2 = 100 1^2 + 0^2 + 0^2 = 1

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

func isHappy(n int) bool {
    m := make(map[int]bool)
    for n != 1 && !m[n]{
        n,m[n] = getSum(n),true
    }
    return n == 1 
}

//2 4 16 37 58 89 145 42 20 4

1. 两数之和

力扣题目链接

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

这里知识点主要是 a,b := map[key] a接收的是v b接受的是存在不,是一个bool
func twoSum(nums []int, target int) []int {
    mapv := make(map[int]int)
    for i,v := range nums{
        if val,isexist := mapv[target - v]; isexist{
            return []int{val,i}
        }
        mapv[v] = i
    }
    return []int{}
}

第454题.四数相加II

力扣题目链接

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化,所有的 A, B, C, D 具有相同的长度 N,且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间,最终结果不会超过 2^31 - 1 。

例如:

输入:

A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2] 输出:

2

解释:

两个元组如下:

(0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0 (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
        res := 0
        map12 := make(map[int]int)
        for _,i := range nums1{
            for _,j := range nums2{
                map12[i+j]++
            } 
        }

        for _,k := range nums3{
            for _,l := range nums4{
                if v,isexist := map12[-k-l];isexist{
                    res+= v
                }
            }
        }
        return res
}

383. 赎金信

力扣题目链接

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串,判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成,返回 true ;否则返回 false。

(题目说明:为了不暴露赎金信字迹,要从杂志上搜索各个需要的字母,组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

注意:

你可以假设两个字符串均只含有小写字母。

canConstruct(“a”, “b”) -> false canConstruct(“aa”, “ab”) -> false canConstruct(“aa”, “aab”) -> true

func canConstruct(ransomNote string, magazine string) bool {
    cnt := [26]int{}
    for _,ch := range magazine{
        cnt[ch - 'a'] ++
    }
    for _,ch := range ransomNote{
        cnt[ch - 'a'] --
        if cnt[ch - 'a'] < 0{
            return false
        }
    }
    return true
}

第15题. 三数之和

力扣题目链接(opens new window)

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。

注意: 答案中不可以包含重复的三元组。

示例:

给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]

func quicksort(nums []int,l int,r int) []int{
    left := l
    right := r
    pvt := nums[left]
    for left < right{
        for left < right && nums[right] > pvt{
            right --
        }
        if left < right{
            nums[left] = nums [right]
        }
        for left < right && nums[left] < pvt {
            left ++
        }
        if left < right {
            nums[right] = nums[left]
        }
    }
    nums[left] = pvt
    quicksort(nums,l,left-1)
    quicksort(nums,left+1,r)
    return nums
}
//双指针
func threeSum(nums []int) [][]int {
    res := [][]int{}
    sort.Ints(nums)
    for i := 0; i < len(nums); i++{
        n1 := nums[i]
        if n1 > 0 {
            break
        }
        if i > 0 && nums[i] == nums[i-1]{
            continue
        }
        l,r := i+1 ,len(nums)-1
        for l < r{
            n2,n3 := nums[l],nums[r]
            if n1+n2+n3 == 0 {
                res = append(res,[]int{n1,n2,n3})
                for l < r && n2 == nums[l]{
                    l++
                }
                for l < r && n3 == nums[r]{
                    r--
                }
            }else if n1+n2+n3 < 0{
                l++
            }else{
                r--
            }
        }
    }
    return res
}


第18题. 四数之和

力扣题目链接(opens new window)

题意:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。

注意:

答案中不可以包含重复的四元组。

示例: 给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。 满足要求的四元组集合为: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

func fourSum(nums []int, target int) (quadruplets [][]int) {
    sort.Ints(nums)
    n := len(nums)
    for i := 0; i < n-3 && nums[i]+nums[i+1]+nums[i+2]+nums[i+3] <= target; i++ {
        if i > 0 && nums[i] == nums[i-1] || nums[i]+nums[n-3]+nums[n-2]+nums[n-1] < target {
            continue
        }
        for j := i + 1; j < n-2 && nums[i]+nums[j]+nums[j+1]+nums[j+2] <= target; j++ {
            if j > i+1 && nums[j] == nums[j-1] || nums[i]+nums[j]+nums[n-2]+nums[n-1] < target {
                continue
            }
            for left, right := j+1, n-1; left < right; {
                if sum := nums[i] + nums[j] + nums[left] + nums[right]; sum == target {
                    quadruplets = append(quadruplets, []int{nums[i], nums[j], nums[left], nums[right]})
                    for left++; left < right && nums[left] == nums[left-1]; left++ {
                    }
                    for right--; left < right && nums[right] == nums[right+1]; right-- {
                    }
                } else if sum < target {
                    left++
                } else {
                    right--
                }
            }
        }
    }
    return
}

作者:力扣官方题解
链接:https://leetcode.cn/problems/4sum/solutions/436368/si-shu-zhi-he-by-leetcode-solution/

总结

https://draveness.me/golang/docs/part2-foundation/ch03-datastructure/golang-hashmap/