探索哈希表
概念
哈希集合：哈希集合是集合数据结构的实现之一，用于存储非重复值。
哈希映射 ：哈希映射是映射数据结构的实现之一，用于存储（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();
*/
