公众号merlinsea
- 括号生成
- 针对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] }
- 算法训练营永久vip学习班【目前主要采用的编程语言是go语言】
- golang算法训练营报名详情如下，快加入我们吧，永久授课和学习，我自己负责的课程会一直维护下去～
奔跑的小梁，公众号：梁霖编程工具库
算法训练营golang专题刷题来啦！！！
