leetcode242
leetcode383
这两道题一个类型

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-anagram

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


看了一下,感觉用hash表最方便

但还是推荐用数组,因为其实在本题的情况下,使用map的空间消耗要比数组大一些的,因为map要维护红黑树或者哈希表,而且还要做哈希函数,是费时的!数据量大的话就能体现出来差别了。 所以数组更加简单直接有效!

  • hash
// hash
func isAnagram(s string, t string) bool {
    // 先判断长度相等吗,不相等下一个
    if len(s)!=len(t){
        return false
    }
    // 定义hash map,用来存字符和次数
    m := map[byte]int{}
    // 遍历s,给map增加
    for i:=0;i<len(s);i++{
        m[s[i]]++
    }
    // 遍历t, 给map减少
    for i:=0;i<len(t);i++{
        tem := t[i]
        m[tem]--
        // 如果某个小于0,直接返回
        if m[tem]<0{
            return false
        }
    }
    // 专门检测
    return check(m)
}
func check(m map[byte]int)bool{
    // 判断每一个元素是否都等于0
    for _,v:=range m{
        if v!=0{
            return false
        }
    }
    return true
}
  • 数组
// 数组
func canConstruct(ransomNote string, magazine string) bool {
    // 定义26长度的数组
    record := make([]int, 26)
    for _, v := range magazine {
        fmt.Println(v-'a')
        // v-'a'用来记录每个字符的索引位置
        // 注意:很妙!!!!!!!
        record[v-'a']++
    }
    fmt.Println(record)
    for _, v := range ransomNote {
        record[v-'a']--
        if record[v-'a'] < 0 {
            return false
        }
    }
    return true
}


leetcode:383

func canConstruct(ransomNote string, magazine string) bool {
    // var tem int
    if len(ransomNote)>len(magazine){
        return false
    }
    m := make(map[byte]int)
    for i:=0;i<len(magazine);i++{
        m[magazine[i]]++
    }
    for i:=0;i<len(ransomNote);i++{
        m[ransomNote[i]]--
    }
    for _,v:= range m{
        if v<0{
            return false
        }
    }
    return true
}
分类: 算法

站点统计

  • 文章总数:309 篇
  • 分类总数:19 个
  • 标签总数:190 个
  • 运行天数:975 天
  • 访问总数:72955 人次

浙公网安备33011302000604

辽ICP备20003309号