用golang语言刷leetcode题目集锦

• 括号生成

• 针对slice切片类型，如果在函数内部使用append向切片中添加元素且希望函数内部对切片的操作可以影响到外部，传入切片的时候传递切片的地址，内部使用的时候用*list。
  

func generateParenthesis(n int) []string {
    list := make([]string,0)
    helper(n,n,"",&list)
    return list 
}


func helper(left int,right int,str string,list *[]string) {
    if right == 0 {
        // 通过*list添加可以影响到外部，相当于把generateParenthesis中的list指向改变了
        *list = append(*list,str)
        return
    }
    if left==right{
        str1 := str + "("
        helper(left-1,right,str1,list)
    }else{
        if left > 0{
            str1 := str + "("
            helper(left-1,right,str1,list)
        }
        str2 := str + ")"
        helper(left,right-1,str2,list)
    }
} 
/*
func helper(left int,right int,str string,list []string) {
    if right == 0 {
         不会影响到外部,append在底层会创建一个新的list来添加，添加以后再把新的list返回，但返回的结果不会影响到实参
        list = append(list,str)
        return
    }
    if left==right{
        str1 := str + "("
        helper(left-1,right,str1,list)
    }else{
        if left > 0{
            str1 := str + "("
            helper(left-1,right,str1,list)
        }
        str2 := str + ")"
        helper(left,right-1,str2,list)
    }
} 
*/

• 字母异位词分组

• 对string指向sort操作，可以先将string转byte切片，对切片排序操作以后再转回string
  

func groupAnagrams(strs []string) [][]string {
    var mp map[string][]string = make(map[string][]string)
    for _,str := range strs {
        slice := []byte(str) // string转切片
        sort.SliceStable(slice, func(i, j int) bool {
            return slice[i] < slice[j]
        })
        key := string(slice)


        _,ok := mp[key]
        if !ok {
            // 第一次遇见这个字符串，因此可以先构建空间
            mp[key] = make([]string,0)
            mp[key] = append(mp[key],str)
        }else{
           // list = append(list,str) 错误，不会影响到map本身，核心是append本身会创建一个新的空间返回
           mp[key] = append(mp[key],str)
        }
    }
    lists := make([][]string,0)
    for _,list := range mp{
        lists = append(lists,list)
    }
    return lists
}

• 最后一个单词的长度

func lengthOfLastWord(s string) int {
    s = strings.TrimSpace(s)
    // idx是下标-如果不存在返回-1
    idx := strings.LastIndex(s," ")
    if idx == -1 {
        //说明没有空格
        return len(s)
    }else{
        return len(s)-idx-1
    }
}

• 有效数字

func isNumber(s string) bool {
    return isInt(s) || isFloat(s) || isENum(s)
}


func isInt(s string) bool {
    // Atoi可以判断待前导0的整数也认为是整数
    _,err := strconv.Atoi(s)
    return err==nil
}


func isFloat(s string) bool {
    if strings.Index(s,".") == -1 {
        return false
    }
    // ParseFloat将字符串转为浮点型，只是整形也可以转
    _,err := strconv.ParseFloat(s,64)
    return err == nil
}


func isENum(s string) bool {
    idx := strings.Index(s,"e")
    if idx == -1 {
        idx = strings.Index(s,"E")
    }
    if idx == -1 {
        return false
    }
    str1 := s[0:idx] // 既可以是小数也可以是整数
    str2 := s[idx+1:len(s)] // 必须只能是整数
    return isInt(str2) && (isFloat(str1) || isInt(str1))
}

• K 个一组翻转链表

func reverseKGroup(head *ListNode, k int) *ListNode {
    var dummy = new(ListNode)
    dummy.Next = head
    var last = dummy
    for last!=nil {
        // 统计last后面有没有k个
        var i = 0
        var q = last
        for i<k && q.Next!=nil {
            i++
            q = q.Next
        }
        if i< k {
            break
        }
        // 逆序
        var flag = last.Next
        var p = last.Next
        last.Next = q.Next
        for p!=q {
            var temp = p.Next
            p.Next = last.Next
            last.Next = p
            p = temp
        }
        p.Next = last.Next
        last.Next = p


        last = flag
    }
    return dummy.Next
}

• 旋转链表

func rotateRight(head *ListNode, k int) *ListNode {
    if head == nil || head.Next==nil{
        return head
    }
    var len = 0
    var p = head
    var last *ListNode = nil
    for p!=nil {
        last = p
        len++
        p = p.Next
    }
    if k%len==0{
        return head
    }
    last.Next = head
    step := len - k%len
    p = head
    for i:=1 ; i<step;i++{
        p = p.Next
    }
    newHead := p.Next
    p.Next = nil
    return newHead
}

• 文本左右对齐

func fullJustify(words []string, maxWidth int) []string {
    res := make([]string,0)
    var i = 0
    for i< len(words){
        var lineWidth = 0
        var j = i
        for j<len(words){
            if j == i {
                lineWidth = len(words[j])
            }else{
                lineWidth += 1 + len(words[j])
            }
            if lineWidth > maxWidth {
                break
            }
            j++
        }
        var isLastLine = false
        if j==len(words){
            isLastLine = true
        }
        // 说明i~j-1要组成一行
        line := handle(words,i,j-1,maxWidth,isLastLine)
        res = append(res,line)
        i = j
    }
    return res
}


func handle(words []string,i int,j int,maxWidth int , isLastLine bool) string{
    var line string
    if i==j{
        //说明只有一个单词，因此所有的空格放在最后即可
        line = words[i]
        for len(line)<maxWidth{
            line = line + " "
        }
        return line
    }
    if isLastLine {
        for k:=i ; k<=j;k++{
            if k==i{
                line = words[k]
            }else{
                line = line + " " + words[k]
            }
        }
        for len(line)<maxWidth{
            line = line + " "
        }
    }else{
        sum := calSumLen(words,i,j)
        space := maxWidth - sum
        avgSpace := space  (j-i)
        spaceStr := ""
        for k:=0;k<avgSpace;k++{
            spaceStr += " "
        }
        modSpace := space % (j-i)
        for k:=i ; k<=j; k++ {
            if k==i {
                line = words[k]
            }else{
                line = line + spaceStr
                if k-i<=modSpace {
                    line = line+ " "
                }
                line = line + words[k]
            }
        }
    }     
    return line
}


func calSumLen(words []string,i int ,j int) int{
    var sum = 0
    for i<=j{
        sum += len(words[i])
        i++
    }
    return sum
}

• 最小覆盖子串

func minWindow(s string, t string) string {
    mp := make(map[byte]int)
    // for _,v := range t{   v在for-range遍历string类型的时候v是个rune类型，推荐使用for-i遍历字符串
    //     mp[v]++
    // }
    for i:=0;i<len(t);i++{
        mp[t[i]]++
    }
    var res string 
    // idxList代表从哪个字符开始
    var idxList = make([]int,0)
    var idx = 0
    curMap := make(map[byte]int)
    var cnt = 0
    for i:=0;i<len(s);i++ {
        v := s[i]
        _,ok := mp[v]
        if ok{
            curMap[v]++
            // 说明之前v是不满足大于等于t中v的字符个数到满足，因此cnt++
            if(curMap[v]==mp[v]){
                cnt++;
            }
            idxList = append(idxList,i)
            //头字符
            headChar := s[idxList[idx]]
            if curMap[headChar] > mp[headChar]{
                idx++
                curMap[headChar]--
            }
            // 校验
            if cnt == len(mp){
                if res == ""{
                    res = s[idxList[idx]:i+1]
                }else{
                    if len(res) > len(s[idxList[idx]:i+1]){
                        res = s[idxList[idx]:i+1]
                    }
                }
                for idx < len(idxList) {
                    headChar = s[idxList[idx]]
                    curMap[headChar]--
                    idx++
                    if curMap[headChar] < mp[headChar]{
                        break
                    }
                    if len(res) > len(s[idxList[idx]:i+1]){
                        res = s[idxList[idx]:i+1]
                    }
                }
                cnt--
            }
        }
    }
    return res


}

• 子集

func subsets(nums []int) [][]int {
    var res [][]int = make([][]int,0)
    res = append(res,make([]int,0))
    for _,v := range nums {
        length := len(res)
        for i:=0;i<length;i++{
            list := append(res[i],v)
            res = append(res,list)
        }
    }
    return res
}

• 克隆图

func cloneGraph(node *Node) *Node {
    if node==nil {
        return nil
    }
    var mp = make(map[*Node]*Node)
    bfsNode(node,mp)
    bfsEdge(node,mp)
    return mp[node]
}
// map本身是一个引用类型，map[key]是直接对其实际空间进行操作
// silce本身也是一个引用类型，slice[i]也是直接对其实际指向的空间进行操作，
// 但append()会创建一个新的空间返回，因此这个点需要注意
func bfsEdge(node *Node,mp map[*Node]*Node){
    slice := make([]*Node,0)
    slice = append(slice,node)
    var isVisitedMap = make(map[*Node]bool)
    for len(slice)!=0 {
        head := slice[0]
        isVisitedMap[head] = true
        newNode := mp[head]
        newNode.Neighbors = make([]*Node,0)
        // 左闭右开
        slice = slice[1:]
        for _,v := range head.Neighbors {
            newNode.Neighbors = append(newNode.Neighbors,mp[v])
            isVisited := isVisitedMap[v]
            if !isVisited {
                slice = append(slice,v)
            }
        }
    }
    return 
}


// golang中没有实现队列和栈，可以借助slice实现
// slice可以二次切片，二次切片的需要注意的是左闭右开
func bfsNode(node *Node,mp map[*Node]*Node){
    slice := make([]*Node,0)
    slice = append(slice,node)
    for len(slice)!=0 {
        head := slice[0]
        copyNode := new(Node)
        copyNode.Val = head.Val
        mp[head] = copyNode // 记录节点之间的关系
        // 左闭右开
        slice = slice[1:]
        for _,v := range head.Neighbors {
            _,ok := mp[v]
            if !ok {
                slice = append(slice,v)
            }
        }
    }
    return 
}

• 组合总和

说明，当一个函数要接收一个切片类型的变量的时候，最好传递切片的地址
func combinationSum(candidates []int, target int) [][]int {
    var lists [][]int = make([][]int,0)
    var list []int = make([]int,0)
    sort.Ints(candidates)
    dfs(candidates,0,target,&list,&lists)
    return lists
}


func dfs(candidates []int,i int,target int,listPtr *[]int,listsPtr *[][]int){
    if target == 0 {
        // cope(slice1,slice2) 将slice2的元素拷贝到slice1中，拷贝的数量是min(slice1.len,slice2.len)
        //var tmpList []int = make([]int,0) 错误
        var tmpList []int = make([]int,len(*listPtr))
        copy(tmpList,*listPtr)
        *listsPtr = append(*listsPtr,tmpList)
       // *listsPtr = append(*listsPtr,*listPtr)
        return
    }
    if i>=len(candidates) || target< candidates[i] {
        return
    }
    // 使用0次
    dfs(candidates,i+1,target,listPtr,listsPtr)


    var cnt = target  candidates[i]
    for k:=1;k<=cnt;k++ {
        *listPtr = append(*listPtr,candidates[i])
         dfs(candidates,i+1,target-k*candidates[i],listPtr,listsPtr)
    }
    // 回溯，把之前加入的元素进行清空 ，方便进入下一轮
    *listPtr = (*listPtr)[:len(*listPtr)-cnt]


}

• 组合总和 II

func combinationSum2(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    lists := make([][]int,0)
    list := make([]int,0)
    dfs(candidates,0,target,&list,&lists)
    return lists
}


func dfs(candidates []int,i int,target int,listPtr *[]int,listsPtr *[][]int){
    if target == 0 {
        var tempList = make([]int,len(*listPtr))
        copy(tempList,*listPtr)
        *listsPtr = append(*listsPtr,tempList)
        return
    }


    if i>=len(candidates) || candidates[i]>target {
        return
    }


    var j = i


    for j<len(candidates) && candidates[j]==candidates[i] {
        j++
    }


    var cnt = j-i
    // 添加0个
    dfs(candidates,j,target,listPtr,listsPtr)


    for k := 1 ;k<=cnt;k++{
        *listPtr = append(*listPtr,candidates[i])
        dfs(candidates,j,target-k*candidates[i],listPtr,listsPtr)
    }


    // 回溯,左闭右开
    // *listPtr[:len(*listPtr)-cnt]    注意这样写会报错，因为优先级不一样
    *listPtr = (*listPtr)[:len(*listPtr)-cnt]
}