# Tourist with Data Structure Third Week

Jiawei_84a5 · · 399 次点击 · · 开始浏览

# 探索哈希表

## 概念

#### 设计哈希集合

``````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.Remove(key);
* param_3 := obj.Contains(key);
*/
``````

``````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
}
``````

#### 字母异位词分组

``````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
}
``````

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

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

# 探索哈希表

## 概念

#### 设计哈希集合

``````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.Remove(key);
* param_3 := obj.Contains(key);
*/
``````

``````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
}
``````

#### 字母异位词分组

``````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
}
``````

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