Tourist with Data Structure Third Week

Jiawei_84a5 · · 198 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

探索哈希表

概念

哈希集合:哈希集合是集合数据结构的实现之一,用于存储非重复值。
哈希映射 :哈希映射是映射数据结构的实现之一,用于存储(key, value)键值对。

设计哈希集合

type MyHashSet struct {
    hash map[int]int
}


/** Initialize your data structure here. */
func Constructor() MyHashSet {
    temp := make(map[int]int)
    
    hash := MyHashSet{temp}
    
    return hash
}


func (this *MyHashSet) Add(key int)  {
    this.hash[key] = 1
}


func (this *MyHashSet) Remove(key int)  {
    delete(this.hash , key)
}


/** Returns true if this set contains the specified element */
func (this *MyHashSet) Contains(key int) bool {
    _, ok := this.hash[key] 
    
    return ok
}


/**
 * Your MyHashSet object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Add(key);
 * obj.Remove(key);
 * param_3 := obj.Contains(key);
 */

其实可以效仿C语言做如下操作。

type MyHashSet struct {
    set []bool
}


/** Initialize your data structure here. */
func Constructor() MyHashSet {
    temp := make([]bool , 1000001)
    
    hash := MyHashSet{temp}
    
    return hash
}


func (this *MyHashSet) Add(key int)  {
    this.set[key] = true
}


func (this *MyHashSet) Remove(key int)  {
    this.set[key] = false
}


/** Returns true if this set contains the specified element */
func (this *MyHashSet) Contains(key int) bool {
    return this.set[key]
}

设计哈希映射

type MyHashMap struct {
    table []int
}


/** Initialize your data structure here. */
func Constructor() MyHashMap {
    temp := make([]int , 1000001)
    for i := 0 ; i < len(temp)  ; i++ {
        temp[i] = -1
    }
    
    return MyHashMap{temp}
}


/** value will always be non-negative. */
func (this *MyHashMap) Put(key int, value int)  {
    this.table[key] = value
}


/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
func (this *MyHashMap) Get(key int) int {
    return this.table[key]
}


/** Removes the mapping of the specified value key if this map contains a mapping for the key */
func (this *MyHashMap) Remove(key int)  {
    this.table[key] = -1
}


/**
 * Your MyHashMap object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Put(key,value);
 * param_2 := obj.Get(key);
 * obj.Remove(key);
 */

存在重复值

func containsDuplicate(nums []int) bool {
    if len(nums) < 2 {
        return false
    }
    //default are all false
    table := make(map[int]bool)
    
    for _, v := range nums {
        //if ok == true , then the value alredy exist
        if _, ok := table[v]; ok {
            return true
        }
        
        table[v] = true
    }
    
    return false
}

只出现一次的数字

我的

func singleNumber(nums []int) int {
    if len(nums) < 2 {
        return nums[0]
    }
    
    table := make(map[int]int)
    
    for _, key := range nums {
        table[key]++
    }
    
    for key , value := range table {
        if value == 1 {
            return key
        }
    }
    
    return 0
}

smart guy 的

func singleNumber(nums []int) int {
    target := 0
    
    for _, value := range nums {
        target ^= value
    }
    
    return target
}

两个数组的交集

func intersection(nums1 []int, nums2 []int) []int {
    
    table := make(map[int]int)
    
    for _, val := range nums1 {
        if _, ok := table[val]; !ok {
            table[val] = 1
        }
    }
    
    res := []int{}
    
    for _, val := range nums2 {
        if key, ok := table[val] ; key > 0 && ok {
            res = append(res , val)
            table[val]--
        }
    }
    
    return res
}

快乐数

结题思路

func isHappy(n int) bool {
    return isOne(n)
}
func getSum(n int) int {
    if n/10 == 0 {
        return n * n
    }
    return (n%10)*(n%10) + getSum(n/10)
}
func isOne(n int) bool {
    a := getSum(n)
    if a == 1 {
        return true
    } else if a == 4 {
        return false
    } else {
        return isOne(a)
    }
}

两数之和

func twoSum(nums []int, target int) []int {
    table := make(map[int]int)
    //use hash table to store another number.
    for index , _ := range nums {
        
        if v, ok := table[nums[index]] ; ok {
            res := []int{v , index}
            return res
        } else {
            table[target - nums[index]] = index
        }
    }
    
    return []int{}
}

同构字符串

//the most understandable solution. But this is not a real hash map.
func isIsomorphic(s string, t string) bool {
    if len(s) < 2 {
        return true
    }
    
    mapS , mapT := make([]int , 256) , make([]int , 256)
    
    for i := 0 ;i < 256 ;i++ {
        mapS[i] = -1
        mapT[i] = -1
    }
    
    for i := 0 ;i < len(s) ; i++ {
        if mapS[s[i]] != mapT[t[i]] {
            return false
        }
        
        mapS[s[i]] = i
        mapT[t[i]] = i
    }
    
    
    return true
    
}
func isIsomorphic(s string, t string) bool {
    if len(s) < 2 {
        return true
    }
    
    table := make(map[rune]rune)
    runeS , runeT := []rune(s) , []rune(t)
    
    for i:= 0 ; i < len(runeS) ;i++ {
        if val ,ok := table[runeS[i]]; !ok {
            for _, temp := range table {
                //if temp == runeT[i] means there is no key in the map,
                //but there is a val == runeT[i],means key and val missmitch.
                //then return false
                if temp == runeT[i] {
                    return false
                }
            }
            table[runeS[i]] = runeT[i]
        } else {
            if val != runeT[i] {
                return false
            }
        }
    }
    
    return true
}

两个列表的最小索引总和

func findRestaurant(list1 []string, list2 []string) []string {
    table1 := make(map[string]int , len(list1))
    table2 := make(map[string]int , len(list2))
    
    for index, val := range list1 {
        table1[val] = index
    }
    
    for index, val := range list2 {
        table2[val] = index
    }
    min := 2001
    var ret []string
    for key , val1 := range table1 {
        if val2 , ok := table2[key]; ok&& val1 + val2 <= min {
            if val1+ val2 < min {
                ret = ret[:0]
                min = val1 + val2
            }
            
            ret = append(ret , key)
        }
    }
    
    return ret
}

字符串中的第一个唯一字符

func firstUniqChar(s string) int {
    table := make(map[rune]int)
    
    for _, val := range s {
        table[val]++
    }
    
    for index , val := range s{
        if 1 == table[val] {
            return index
        }
    }
    
    return -1
}
func firstUniqChar(s string) int {
    list := make([]int ,26)
    
    for _, val := range s {
        list[val - 'a']++
    }
    
    for index , val := range s{
        if 1 == list[val - 'a'] {
            return index
        }
    }
    
    return -1
}

两个数组的交集II

func intersect(nums1 []int, nums2 []int) []int {
    var ret []int

    table := make(map[int]int)

    if len(nums1) > len(nums2) {
        nums1 , nums2 = nums2 , nums1
    }

    for _ , val := range nums1 {
        if _, ok := table[val] ; ok{
            table[val]++
        } else {
            table[val] = 1
        }
    }

    for _, val := range nums2 {
        if _ , ok := table[val] ; num > 0 && ok {
            ret = append(ret , val)
            table[val]--
        }
    }

    return ret
}

存在重复元素

func abs(x int) int {
    if x < 0 {
        return -x
    }
    
    return x
}

func containsNearbyDuplicate(nums []int, k int) bool {
    if len(nums) < 2 {
        return false
    }
    
    table := make(map[int]int)
    
    for index , val := range nums {
        if v ,ok := table[val] ; ok {
            if abs(index - v ) <= k {
                return true
            }
        }
        
        table[val] = index
        
    }
    
    return false
}

字母异位词分组

我使用了golang自带的sort.Sort方法, 实现了接口,但是此种方式较为复杂。

type sortRunes []rune

func (s sortRunes) Less(i , j int) bool{
    return s[i] < s[j]
}

func (s sortRunes) Swap(i ,j int) {
    s[i], s[j] = s[j] ,s[i]
}

func (s sortRunes) Len() int {
    return len(s)
}

func SortString(s string) string {
    res := []rune(s)
    sort.Sort(sortRunes(res))

    return string(res)
}

func groupAnagrams(strs []string) [][]string {
    res := [][]string{}
    table := make(map[string]int, len(strs))
    index := 0

    for _, str := range strs {
        temp := SortString(str)
        fmt.Println(temp)
        if val , ok := table[temp]; ok {
            res[val] = append(res[val], str)
        } else {
            table[temp] = index
            res = append(res, []string{})
            res[index] = append(res[index] , str)
            index++
        }
    }

    return res
}

提交后发现有一位大神的方法很棒。使用了sort.Slice且少了很多判断, 也无需实现很多接口。

func groupAnagrams(strs []string) [][]string {
    category := make(map[string][]string)
    for _, v := range strs {
        b := []byte(v)
        sort.Slice(b, func(i, j int)bool {
            return b[i] < b[j]
        })
        idx := string(b)
        category[idx] = append(category[idx], v)
    }
    
    res := make([][]string, 0, len(category))
    for _, v := range category {
        res = append(res, v)
    } 
    
    return res
}

有效的数独

没有直接使用map.过后会想一个好的方式,使用map.

func isValidSudoku(board [][]byte) bool {
    rows := make([][10]bool, 10)
    cols := make([][10]bool, 10)
    block := make([][10]bool, 10)

    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[i]); j++ {
            if board[i][j] != '.' {
                num := int(board[i][j] - '0')
                if rows[i][num] || cols[j][num] || block[(i/3)*3+j/3][num] {
                    return false
                } else {
                    rows[i][num] = true
                    cols[j][num] = true
                    block[(i/3)*3+j/3][num] = true
                }
            }
        }
    }

    return true
}

宝石与石头

func numJewelsInStones(J string, S string) int {
    table := make(map[rune]bool)
    runeJ := []rune(J)
    runeS := []rune(S)
    count := 0
    for _, val := range runeJ {
        table[val] = true
    }
    
    for _, val := range runeS {
        if  _, ok := table[val] ;ok {
            count++
        }
    }
    
    return count
}

无重复字符的最长子串

func lengthOfLongestSubstring(s string) int {
    table := make(map[rune]int)

    start , max := -1 , 0

    for index , val := range s {
        if last , ok := table[val] ; ok && last > start {
            //if dupulicate then reset start .
            start = last
        }
        table[val] = index

        if index - start > max {
            max = index - start
        }
    }

    return max
    
}

四数相加

func fourSumCount(A []int, B []int, C []int, D []int) int {
    maps := make(map[int]int)
    res := 0
    length := len(A)
    for i := 0 ; i < length ; i++ {
        for j := 0 ; j < length ; j++ {
            maps[A[i] + B[j]]++
        }
    }

    for i := 0 ; i < length ; i++ {
        for j := 0 ; j < length ; j++ {
            res += maps[-1*(C[i] + D[j])]
        }
    }

    return res
}

前K个高频元素

func topKFrequent(nums []int, k int) []int {
    res := make([]int , 0 , k)
    
    table := make(map[int]int , len(nums))
    
    for _, val := range nums {
        table[val]++
    }
    
    counts := make([]int , 0 , len(table))
    
    for _, val := range table {
        counts = append(counts , val)
    }
    
    sort.Ints(counts)
    
    min := counts[len(counts) - k]
    
    for key , val := range table {
        if val >= min {
            res = append(res , key)
        }
    }
    
    return res
}

常数时间插入,删除和获取随机元素

type RandomizedSet struct {
    list []int
    index map[int]int
}


/** Initialize your data structure here. */
func Constructor() RandomizedSet {
    return RandomizedSet{
        list : []int{},
        index : make(map[int]int),
    }
}


/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
func (this *RandomizedSet) Insert(val int) bool {
    if _ , ok := this.index[val]; ok {
        return false
    }
    
    this.list = append(this.list , val)
    this.index[val] = len(this.list) -1
    return true
}


/** Removes a value from the set. Returns true if the set contained the specified element. */
func (this *RandomizedSet) Remove(val int) bool {
    if _, ok := this.index[val] ; !ok {
        return false
    }
    
    this.list[this.index[val]] = this.list[len(this.list) - 1]
    this.index[this.list[len(this.list) - 1]] = this.index[val]
    
    this.list = this.list[:len(this.list) -1]
    
    delete(this.index , val)
    
    return true
}


/** Get a random element from the set. */
func (this *RandomizedSet) GetRandom() int {
    return this.list[rand.Intn(len(this.list))]
}


/**
 * Your RandomizedSet object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */

设计键的总结


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:Jiawei_84a5

查看原文:Tourist with Data Structure Third Week

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:1006366459

198 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传