Learning Note of Go – Leetcode


Use of Channel

package main

import "golang.org/x/tour/tree"
import "fmt"
// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int){
	_Walk(t, ch)
	close(ch)
}
func _Walk(t *tree.Tree, ch chan int){
	if t.Left != nil{
	  _Walk(t.Left, ch)
	}
	ch <- t.Value
	if t.Right != nil{
	  _Walk(t.Right, ch)
	}
}

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool{
	c1 := make(chan int)
	c2 := make(chan int)
	go Walk(t1, c1)
	go Walk(t2, c2)
	for {
		a, ok1 := <- c1
		b, ok2 := <- c2
		if ok1 != ok2 || a != b{
		  return false
		// end of chan
		}else if(ok1 == ok2 && ok1 == false){
		  return true
		}
	}
    return true
}

func main() {
	
	b := Same(tree.New(2), tree.New(2))
	fmt.Println(b)
	fmt.Println("End of main")
}

 

Longest Palindrome

func longestPalindrome(s string) string {
    re := ""
    for center:= 0; center < len(s); center++{
        // check even length
        l := center
        r := center + 1
        for l >= 0 && r < len(s){
            if s[l] == s[r]{
                l--
                r++
            }else{
                break
            }
        }
        if (r - l - 1 > len(re)){
            re = s[l+1:r]
        }
        // check odd length
        l = center - 1
        r = center + 1
        for l >= 0 && r < len(s){
            if s[l] == s[r]{
                l--
                r++
            }else{
                break
            }
        }
        if (r - l - 1 > len(re)){
            re = s[l+1:r]
        }
    }
    return re
}

Longest Substring Without Repeating Characters

func lengthOfLongestSubstring(s string) int {
    isExist := make(map[byte]bool)
    head, tail := 0, 0
    length := 0
    
    for head < len(s){
        if _, ok := isExist[s[head]]; ok{
            // occured before
            delete(isExist, s[tail])
            tail++
        }else{
            isExist[s[head]] = true
            head++
        }
        if(head - tail > length){
            length = head - tail
        }
        
    }
    return length
}

 

Allocate space for slices. Use make.

Allocate space for pointer, use new

package main

import "golang.org/x/tour/pic"

func Pic(dx, dy int) [][]uint8 {
  var re [][]uint8
  re = make([][]uint8, dx)
  for i:=0; i < dx; i++{
    re[i] = make([]uint8, dy)
	for j := 0; j < dy; j++{
	  re[i][j] = uint8(i ^ j)
	}
  }
  return re
}

func main() {
	pic.Show(Pic)
}

Add two numbers

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    lenL1 := getLen(l1)
    lenL2 := getLen(l2)
    if lenL1 < lenL2{
        swap(&l1, &l2)
    }
    // lengthl1 >= l2
    carry := 0
    head := l1
    var prev *ListNode
    for l1 != nil{
        var v = 0
        if(l2 != nil){
            v = l2.Val
            l2 = l2.Next
        }
        l1.Val += carry + v
        carry = l1.Val / 10
        l1.Val %= 10
        prev = l1
        l1 = l1.Next
    }
    if carry != 0{
        prev.Next = new(ListNode)
        l1 = prev.Next
        l1.Val = carry
        l1.Next = nil
    }
    return head
}
func swap(l1, l2 **ListNode){
    temp := *l1
    *l1 = *l2
    *l2 = temp
}
func getLen(l *ListNode) int {
    var len = 0
    for l != nil{
        len++
        l = l.Next
    }
    return len
}

 

Hash Map

Note: using hash map

// Declare a hash map
mymap := make(map[int]int)

 

Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

 

func twoSum(nums []int, target int) []int {
    mymap := make(map[int]int)
    for i, v1 := range nums{
        j, ok := mymap[target - v1]
        if ok{
            return []int{j, i}
        }else{
            mymap[v1] = i
        }
    }
    return []int{-1,-1}
}

 

 

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.