# Go Leetcode: Array & Hash Table
###### tags: `leetcode` `go`
## Contains Duplicate
### #1
```go=
func containsDuplicate(nums []int) bool {
// hash table
// key -> value
// if value > 1 return true
idmap := make(map[int]int)
// iterate through the given slice
for i:=0; i < len(nums); i++ {
idmap[nums[i]]++
if idmap[nums[i]] > 1 {return true}
}
return false
}
```
### #2 less memory
```go=
func containsDuplicate(nums []int) bool {
// struct comsumes less memory than integer and bool
idmap := make(map[int]struct{})
// iterate through the given slice
for _, v := range nums {
if _, ok := idmap[v]; ok {
return true
} else {
idmap[v] = struct{}{} // weird syntax
}
}
return false
}
```
### Note
- what is slice
- how to iterate through slice
- how to declare map
- how to assign empty struct
- consider what type to use
## Valid Anagram
### #1
```go=
func isAnagram(s string, t string) bool {
if len(s) != len(t) {return false}
hst := make(map[rune]int)
for _, r := range s {
hst[r]++ // init
}
for _, r := range t {
if _, ok := hst[r]; ok {
hst[r]--
if hst[r] < 0 {return false}
} else {
return false
}
}
return true
}
```
### Note
- what is rune
- how to iterate through string
## Two Sum
### #1
```go=
func twoSum(nums []int, target int) []int {
hst := make(map[int]int)
for i, v := range nums {
to_find := target - v
// find if the other piece in hash table
if j, ok := hst[to_find]; ok {
return []int{i, j}
} else {
// add self to hash table
hst[v] = i
}
}
return []int{0, 0}
}
```
## Group Anagrams
### #1
```go=
import (
"sort"
"fmt"
)
func groupAnagrams(strs []string) [][]string {
// hash each word
hst := make(map[string][]string)
for _, str := range strs {
bytes := []byte(str)
sort.SliceStable(bytes, func(i int, j int) bool{
return bytes[i] < bytes[j]
})
key := string(bytes)
hst[key] = append(hst[key], str)
}
res := make([][]string, 0, len(hst))
for _, v := range hst {
res = append(res, v)
}
return res
}
```
## Top K Frequent Elements
### #1
```go=
func topKFrequent(nums []int, k int) []int {
// hash table
// key: num
// value: counter
hst := make(map[int]int)
for _, n := range nums {
hst[n]++
}
// get the indexes of k max value
// get the index of maximum value k times
q := []int{}
for i:=0; i<k; i++ {
max_idx := 0
is_init := true
for key, val := range hst {
if is_init || hst[max_idx] < val {
max_idx = key
}
is_init = false
}
// append
q = append(q, max_idx)
// remove from hst
delete(hst, max_idx)
}
return q
}
```
### #2 custom map struct
faster but takes more mrmory
```go=
import "sort"
type Pair struct {
Key int
Value int
}
type PairList []Pair
func (p PairList) Len() int { return len(p) }
func (p PairList) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func (p PairList) Less(i, j int) bool { return p[i].Value > p[j].Value } // sort desc
func topKFrequent(nums []int, k int) []int {
// hash table
// key: num
// value: counter
hst := make(map[int]int)
for _, n := range nums {
hst[n]++
}
plist := make(PairList, len(hst))
i := 0
for k, v := range hst {
plist[i].Key = k
plist[i].Value = v
i++
}
sort.Sort(plist)
// get the indexes of k max value
// get the index of maximum value k times
q := []int{}
for i:=0; i<k; i++ {
// append
q = append(q, plist[i].Key)
}
return q
}
```
### #3 faster than #2
```go=
// ...
q := []int{}
for _, item := range plist[:k] {
// append
q = append(q, item.Key)
}
return q
```
### #4 cleaner way to sort
```go=
func topKFrequent(nums []int, k int) []int {
// key : value -> num : amount
hst := make(map[int]int)
for _, n := range nums {
hst[n]++
}
// collect keys
keys := []int{}
for num, _ := range hst {
keys = append(keys, num)
}
// sort keys by values in hash table
sort.Slice(keys, func(i, j int) bool {
return hst[keys[i]] > hst[keys[j]] // desc
})
return keys[:k]
}
```
### #5 use slice of slice as bucket
use slice of slice as bucket to collect nums
```go=
func topKFrequent(nums []int, k int) []int {
// special case
if len(nums) == k { return nums }
// frequency map
freqs := map[int]int{}
for _, num := range nums {
freqs[num]++
}
// frequency as index
// collect numbers with same frequency
nums_len := len(nums)
bucket := make([][]int, nums_len+1) // index: 0, 1 ... len(nums)
for num, freq := range freqs {
bucket[freq] = append(bucket[freq], num)
}
res := []int{}
for i:=nums_len; i>0; i-- {
if len(bucket[i]) > 0 {
res = append(res, bucket[i]...)
if len(res) >= k { return res }
}
}
return res
}
```
### #6 manual quick sort (most complicated)
```go=
func topKFrequent(nums []int, k int) []int {
// special case
if len(nums) == k { return nums }
// frequency map
freqs := map[int]int{}
for _, num := range nums {
freqs[num]++
}
keys := []int{}
for key, _ := range freqs {
keys = append(keys, key)
}
// quick sort
kQuickSort(keys, freqs, k)
return keys[len(keys)-k:]
}
func kQuickSort(slice []int, m map[int]int, k int) {
if len(slice) <= 1 { return }
kQuickSortRecr(slice, m , 0, len(slice)-1, k)
}
func kQuickSortRecr(slice []int, m map[int]int, start_i, end_i, k int) {
// end condition
if start_i >= end_i { return }
// main logic
piv_i := getPiv(start_i, end_i)
piv_final := sort(slice, m, start_i, end_i, piv_i)
// divide - DFS right first
kQuickSortRecr(slice, m, piv_final+1, end_i, k) // right
if len(slice) - 1 == piv_final + k { return }
kQuickSortRecr(slice, m, start_i, piv_final-1, k) // left
}
func getPiv(l, r int) int {
return l + (r - l) / 2
}
func sort(slice []int, m map[int]int, start_i, end_i, piv_i int) int {
swap(slice, piv_i, end_i)
curr_piv_i := end_i
for true {
for true {
if start_i == end_i { break }
if m[slice[start_i]] > m[slice[curr_piv_i]] {
break
}
start_i++
}
for true {
if start_i == end_i { break }
if m[slice[end_i]] < m[slice[curr_piv_i]] {
break
}
end_i--
}
if start_i == end_i { break }
swap(slice, end_i, start_i)
}
if m[slice[start_i]] >= m[slice[curr_piv_i]] {
swap(slice, start_i, curr_piv_i)
curr_piv_i = start_i
}
return curr_piv_i
}
func swap(slice []int, i, j int) {
slice[i], slice[j] = slice[j], slice[i]
}
```
### Note
- how to use `sort`
- sorting of map by key or value
## Product of Array Except Self
solution: https://www.cnblogs.com/grandyang/p/4650187.html
```go=
func productExceptSelf(nums []int) []int {
length := len(nums)
res := make([]int, length)
// forward
res[0] = 1
for i:=1; i < len(nums); i++ {
res[i] = res[i-1] * nums[i-1]
}
// backward
right := nums[length-1]
for i:=length-2; i >= 0; i-- {
res[i] *= right
right *= nums[i]
}
return res
}
```
## Encode & Decode Strings
solution: https://www.youtube.com/watch?v=B1k_sxOSgv8
```go=
package main
import (
"fmt"
"strconv"
)
const SEP string = ":"
func main() {
list := []string{"#set", "666", "rat"}
enco := encode(list)
fmt.Println(enco)
fmt.Println(decode(enco))
}
func encode(list []string) string {
str := ""
for _, w := range list {
str += fmt.Sprintf("%d%s%s", len(w), SEP, w)
}
return str
}
func decode(str string) []string {
list, i := []string{}, 0
for i < len(str) {
sep_i := i
// find seperator
for ; sep_i < len(str); sep_i++ {
if str[sep_i] == SEP[0] {
break
}
}
// get word length
length_str := str[i:sep_i]
length, err := strconv.Atoi(length_str)
if err != nil {
panic("err")
}
list = append(list, str[sep_i+1:sep_i+1+length])
i = sep_i + 1 + length
}
return list
}
```
### Note
- [efficient details of string append](https://shockerli.net/post/golang-concat-string/)
## Longest Consecutive
### find start and end of sequences
```go!
func longestConsecutive(nums []int) int {
set := make(map[int]struct{})
for _, n := range nums {
if _, ok := set[n]; !ok {
set[n] = struct{}{}
}
}
res := 0
for _, n := range nums {
// if not start number, continue
if _, ok := set[n-1]; ok {
continue
}
// else n is a start number
end := n
for {
// no next, means end
if _, ok := set[end+1]; !ok {
break
}
end++
}
res = max(res, end-n+1)
}
return res
}
func max(a, b int) int {
if a > b { return a }
return b
}
```
### Union Find
```go=
type UnionFind struct {
Roots map[int]int
Lengths map[int]int
}
func (this *UnionFind) Union (a, b int) {
root_a := this.FindRoot(a)
root_b := this.FindRoot(b)
if root_a != root_b {
this.Roots[root_a] = root_b
this.Lengths[root_b] += this.Lengths[root_a]
}
}
func (this *UnionFind) FindRoot (a int) int {
root := this.Roots[a]
if root == a { return a }
this.Roots[a] = this.FindRoot(root)
return this.Roots[a]
}
func createUnionFind(nums []int) *UnionFind {
roots, lengths := make(map[int]int), make(map[int]int)
for _, n := range nums {
roots[n] = n
lengths[n] = 1
}
return &UnionFind{roots, lengths}
}
func longestConsecutive(nums []int) int {
uf := createUnionFind(nums)
longest := 0
for _, n := range nums {
if _, ok := uf.Roots[n-1]; ok {
uf.Union(n, n-1)
}
if _, ok := uf.Roots[n+1]; ok {
uf.Union(n, n+1)
}
// length := uf.Lengths[uf.FindRoot(n)]
longest = max(longest, uf.Lengths[uf.FindRoot(n)])
}
return longest
}
func max(a, b int) int {
if a>b { return a }
return b
}
```
### Simliar to unionfind but faster!
```go!
func longestConsecutive(nums []int) int {
if len(nums) == 0 {
return 0
}
max := 0
bk := make(map[int]int)
for _, num := range nums {
if _, ok := bk[num]; ok {
continue
}
left, right := 0, 0
if val, ok := bk[num-1]; ok {
left = val
}
if val, ok := bk[num+1]; ok {
right = val
}
bk[num] = left + right + 1
if max < bk[num] {
max = bk[num]
}
bk[num-left] = bk[num]
bk[num+right] = bk[num]
}
return max
}
```
## Valid Sudoku
### #1
```go=
func isValidSudoku(board [][]byte) bool {
for i:=0; i<9; i++ {
// validate rows
if !validSlice(board[i]) {
return false
}
// validate cols
buk := make([]byte, 9)
for j:=0; j<9; j++ {
buk[j] = board[j][i]
}
if !validSlice(buk) {
return false
}
}
// validate square
r_i, c_i := 0, 0
for r_i < 9 {
buk := []byte{}
for _, row := range board[r_i:r_i+3] {
for _, num := range row[c_i:c_i+3] {
buk = append(buk, num)
}
}
if !validSlice(buk) { return false }
if c_i == 6 {
c_i = 0
r_i += 3
} else {
c_i += 3
}
}
return true
}
func validSlice(s []byte) bool {
hst := make(map[byte]struct{})
for _, num := range s {
if string(num) == "." { continue }
if _, ok := hst[num]; ok {
return false
} else {
hst[num] = struct{}{}
}
}
return true
}
```
Google Drive
Gist
Clipboard
Sign in via Facebook
Sign in via X(Twitter)
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
