Tourist with Data Structure Third Week

해시 표 탐색
콘 셉 트
해시 집합: 해시 집합 은 집합 데이터 구조의 실현 중 하나 로 비 중복 값 을 저장 하 는 데 사용 된다.해시 맵: 해시 맵 은 맵 데이터 구조의 실현 중 하나 로 저장 (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
}

알파벳 이 위 단어 그룹
나 는 골 랑 이 자체 적 으로 가지 고 있 는 sort. ort 방법 을 사용 하여 인 터 페 이 스 를 실현 하 였 으 나 이런 방식 은 비교적 복잡 하 다.

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
}

유효한 게임
맵 을 직접 사용 하지 않 았 습 니 다. 나중에 좋 은 방법 을 생각해 서 맵 을 사용 하 겠 습 니 다.

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();
 */

디자인 키 의 총화