package common // MinInt 找出两个整形中更小的值。 func MinInt(x, y int) int { if x > y { return y } return x } // IntArrayBinaryFind 数组中二分查找,返回目标值所在的索引,不存在则返回-1。 func IntArrayBinaryFind(list []int, target int) (index int) { var left, right = 0, len(list) - 1 for right >= left { index = (left + right) / 2 if target < list[index] { right = index - 1 } else if target > list[index] { left = index + 1 } else { return index } } return -1 }
package common import "fmt" type ListNode struct { Val int Next *ListNode } func IsEqualListChain(a, b *ListNode) bool { for a != nil && b != nil { if a.Val != b.Val { return false } a = a.Next b = b.Next } // 必须同时为nil if a != b { return false } return true } func CreateListChain(li []int) *ListNode { if li == nil || len(li) == 0 { return nil } var head = &ListNode{} var tail = head for _, val := range li { tail.Next = &ListNode{Val: val} tail = tail.Next } return head.Next } func PrintListChain(x *ListNode) { count := 0 for ; x != nil; x = x.Next { fmt.Printf("%d ", x.Val) count++ if count == 100 { fmt.Print("...") break } } fmt.Println() } // CreateListChainCycle 负责创建一个带环的链表。 // 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 // 如果 pos 是 -1,则在该链表中没有环。 func CreateListChainCycle(li []int, pos int) *ListNode { if pos >= len(li) { panic("错误的输入!pos应该小于li的长度!") } head := CreateListChain(li) if pos >= 0 { var insectNode *ListNode var currentNode = &ListNode{Next: head} for p := range li { currentNode = currentNode.Next if p == pos { insectNode = currentNode } } currentNode.Next = insectNode } return head }
package common // Factorial 负责计算n的阶乘 func Factorial(n int) int { if n < 1 { return 1 } var result int = 1 for ; n > 1; n-- { result *= n } return result } // Gcd 负责计算最大公约数 func Gcd(x, y int) int { tmp := x % y if tmp > 0 { return Gcd(y, tmp) } else { return y } }
// mySortInt 在这个包里练习常用的排序算法,附带测试用例。 package mySortInt func SelectSort(li []int) { for i := range li { minI := i for ii := i; ii < len(li); ii++ { if li[ii] < li[minI] { minI = ii } } li[minI], li[i] = li[i], li[minI] } } func QuickSort(li []int) { if len(li) < 6 { SelectSort(li) return } midValue := li[0] var left, right = 1, len(li) - 1 for left < right { for li[left] <= midValue && left < right { left++ // 最大值right, 不会越界 } for li[right] >= midValue && right > 0 { right-- // 最小值0,不会越界 } if left >= right { break } li[left], li[right] = li[right], li[left] } // 0号位置应该放小数,因此应该把right换过来 li[0], li[right] = li[right], li[0] QuickSort(li[:right]) QuickSort(li[right+1:]) } func BubbleSort(li []int) { for max := len(li); max > 1; max-- { for i := 1; i < max; i++ { if li[i-1] > li[i] { li[i-1], li[i] = li[i], li[i-1] } } } }
package common // 快速排序1:用栈实现的超复杂版本 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> func QuickSortInt(li []int) { if len(li) == 0 { return } quickSortInt(li, 0, len(li)-1) } func quickSortInt(li []int, lo, hi int) { stack := quickSortStackInt{} stack.Push(lo, hi) for stack.Len() > 0 { x, y, _ := stack.Pop() mid := quickSortIntPartition(li, x, y) if mid-x > 15 { stack.Push(x, mid-1) } else if mid-x > 1 { quickSortIntSelectSort(li, x, mid-1) } if y-mid > 15 { stack.Push(mid+1, y) } else if y-mid > 1 { quickSortIntSelectSort(li, mid+1, y) } } } func quickSortIntPartition(li []int, lo, hi int) (mid int) { l, r := lo, hi //li[lo], li[(lo+hi)/2] = li[(lo+hi)/2], li[lo] midValue := li[lo] for l < r { for l <= hi { // 找大的 if li[l] > midValue { break } l++ } for r >= lo { if li[r] <= midValue { break } r-- } if l < r { li[l], li[r] = li[r], li[l] } else { break } } li[lo], li[r] = li[r], li[lo] return r } func quickSortIntSelectSort(li []int, lo, hi int) { var min int for ; lo < hi; lo++ { min = lo for i := lo + 1; i <= hi; i++ { if li[i] < li[min] { min = i } } if lo != min { li[lo], li[min] = li[min], li[lo] } } } type quickSortStackInt struct { items []int } func (s *quickSortStackInt) Len() int { return len(s.items) } func (s *quickSortStackInt) Push(x, y int) { s.items = append(s.items, x, y) } func (s *quickSortStackInt) Pop() (int, int, error) { l := len(s.items) //if l < 2 { // return 0, 0, errors.New("没有元素可以取出") //} x, y := s.items[l-2], s.items[l-1] s.items = s.items[:l-2] return x, y, nil } // 快速排序1 结束 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< // 快速排序2:不要用栈,只加了选择排序的基础版快排(反转排序) >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> func QuickSortIntRev(li []int) { quickSortIntRev(li, 0, len(li)-1) } func quickSortIntRev(li []int, lo, hi int) { if hi-lo < 5 { quickSortIntSelectSortRev(li, lo, hi) return } mid := quickSortIntPartitionRev(li, lo, hi) quickSortIntRev(li, lo, mid-1) quickSortIntRev(li, mid+1, hi) } func quickSortIntPartitionRev(li []int, lo, hi int) (mid int) { l, r := lo, hi midValue := li[lo] // 比较处 for l < r { for l <= hi { if li[l] < midValue { // 比较处 break } l++ } for r >= lo { if li[r] >= midValue { // 比较处 break } r-- } if l < r { li[l], li[r] = li[r], li[l] } else { break } } li[lo], li[r] = li[r], li[lo] return r } func quickSortIntSelectSortRev(li []int, lo, hi int) { var min int for ; lo < hi; lo++ { min = lo for i := lo + 1; i <= hi; i++ { if li[i] > li[min] { // 比较处 min = i } } if lo != min { li[lo], li[min] = li[min], li[lo] } } } // 快速排序2 结束 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
package common import "fmt" type TreeNode struct { Val int Left *TreeNode Right *TreeNode } var printCache [][]string func PrintTreeNodes(root *TreeNode) { printCache = [][]string{} printTreeNodes(root, 0) for i := range printCache { fmt.Println(printCache[i]) } } func printTreeNodes(node *TreeNode, depth int) { if len(printCache) <= depth { printCache = append(printCache, []string{}) } if node == nil { printCache[depth] = append(printCache[depth], "null") return } printCache[depth] = append(printCache[depth], fmt.Sprint(node.Val)) printTreeNodes(node.Left, depth+1) printTreeNodes(node.Right, depth+1) }
package listnode type ListNode struct { Val int Next *ListNode } func NewList(values []int) *ListNode { var head = &ListNode{} var cur = head for _, value := range values { cur.Next = &ListNode{Val: value} cur = cur.Next } return head.Next } func Format(head *ListNode) []int { if head == nil { return nil } var res = []int{head.Val} var cur = head.Next for cur != nil && cur != head { // 防止循环链表导致死循环 res = append(res, cur.Val) cur = cur.Next } return res } func Concat(front, back *ListNode) *ListNode { if front == nil { return back } var tail = front for tail.Next != nil { tail = tail.Next } tail.Next = back return front } // NewListWithCycle 负责创建一个带环的链表。 // 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 // 如果 pos 是 -1,则在该链表中没有环。 func NewListWithCycle(li []int, pos int) *ListNode { if pos >= len(li) { panic("错误的输入!pos应该小于li的长度!") } head := NewList(li) if pos >= 0 { var insectNode *ListNode var currentNode = &ListNode{Next: head} for p := range li { currentNode = currentNode.Next if p == pos { insectNode = currentNode } } currentNode.Next = insectNode } return head } func Walk(head *ListNode, step int) *ListNode { if head == nil { return nil } for i := 0; i < step && head.Next != nil; i++ { head = head.Next } return head }
package treenode import ( "strconv" ) type TreeNode struct { Val int Left *TreeNode Right *TreeNode } func Format(t *TreeNode) []string { var res []string layer := []*TreeNode{t} next := true for next { next = false nextLayer := make([]*TreeNode, len(layer)*2) for i, parent := range layer { if parent == nil { res = append(res, "null") nextLayer[i*2], nextLayer[i*2+1] = nil, nil } else { res = append(res, strconv.Itoa(parent.Val)) nextLayer[i*2], nextLayer[i*2+1] = parent.Left, parent.Right if parent.Left != nil || parent.Right != nil { next = true } } } layer = nextLayer } { var cut int for cut = len(res); cut > 0 && res[cut-1] == "null"; cut-- { } if cut >= 0 { res = res[:cut] } } return res } func NewTree(words []string) (root *TreeNode) { if len(words) == 0 { return } { // 为了取得root,对第一层特殊处理一下 value, err := strconv.Atoi(words[0]) if err != nil { panic(err) } root = &TreeNode{Val: value} words = words[1:] } layer := []*TreeNode{root} for width := 2; ; width *= 2 { // 从第二层开始循环 if len(words) == 0 { return } var layerWords []string if len(words) < width { layerWords = words } else { layerWords = words[:width] } nextLayer := make([]*TreeNode, width) for i, word := range layerWords { if word != "null" { value, err := strconv.Atoi(word) if err != nil { panic(err) } nextLayer[i] = &TreeNode{Val: value} } } for i, parent := range layer { if parent != nil { parent.Left = nextLayer[i*2] parent.Right = nextLayer[i*2+1] } } layer = nextLayer if len(words) <= width { words = words[:0] } else { words = words[width:] } } }
/* 剑指 Offer 03. 数组中重复的数字 难度:简单 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。 数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 示例 1: 输入: [2, 3, 1, 0, 2, 5, 3] 输出:2 或 3 限制: 2 <= n <= 100000 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0003 /* 方案三: 考虑到一个特殊条件:nums里的数字都是符合下标条件的,所以可以利用下标来做。 用一个指针从左向右遍历。把每个数字都放到这个数字作为下标的位置上去,如果发现有两个数字放在一起了,说明重复了。 时间复杂度:N,空间复杂度:1,理论最优。 但是实际表现并没有明显优势,用时36ms,击败96% */ func findRepeatNumber(nums []int) int { for i := 0; i < len(nums); { num := nums[i] if i == num { // 因为置换过来的数字依然大概率不是符合位置的,因此可能需要在一个位置上循环判定。 i++ continue } if nums[num] == num { return num } nums[i], nums[num] = nums[num], nums[i] } return -1 }
package q0003 /* 方案一: 使用快排思路,用双指针去遍历。 时间复杂度 NlogN ,空间复杂度 1 。 暴力计算的门槛值设置为8或者10时,成绩最好,40ms,击败95% */ func findRepeatNumber2(nums []int) int { if len(nums) < 6 { return findRepeatNumberSmall(nums) } mid, left, right := len(nums)/2, 1, len(nums)-1 nums[0], nums[mid] = nums[mid], nums[0] bench := nums[0] for left < right { if nums[left] < bench { left++ continue } else if nums[left] == bench { return bench } if nums[right] > bench { right-- continue } else if nums[right] == bench { return bench } nums[left], nums[right] = nums[right], nums[left] left++ right-- } if nums[0] > nums[right] { nums[0], nums[right] = nums[right], nums[0] } if num := findRepeatNumber2(nums[:right]); num != -1 { return num } if num := findRepeatNumber2(nums[right:]); num != -1 { return num } return -1 } func findRepeatNumberSmall(nums []int) int { for i, v := range nums { for _, vv := range nums[i+1:] { if v == vv { return v } } } return -1 // 因为限制了数字最小是0 }
package q0003 /* 方案二: 把数组里的值全部丢进map里去检验。 时间复杂度 N,空间复杂度 N 。 时间排名40%,空间26%,很差。 */ func findRepeatNumber3(nums []int) int { book := make(map[int]struct{}) for _, num := range nums { if _, exist := book[num]; exist { return num } book[num] = struct{}{} } return -1 }
/* 剑指 Offer 04. 二维数组中的查找 难度:中等 在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。 请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 示例: 现有矩阵 matrix 如下: [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] 给定 target = 5,返回 true。 给定 target = 20,返回 false。 限制: 0 <= n <= 1000 0 <= m <= 1000 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0004 /* 日期:2021-02-15 感想:二维数组的解题思路的确没有了解过,没做出来。感觉比较取巧。 */ func findNumberIn2DArray(matrix [][]int, target int) bool { if len(matrix) == 0 || len(matrix[0]) == 0 { return false } var x, y = len(matrix[0]) - 1, 0 maxy := len(matrix) for { if matrix[y][x] == target { return true } else if target < matrix[y][x] { x-- if x < 0 { return false } } else if target > matrix[y][x] { y++ if y >= maxy { return false } } } }
/* 剑指 Offer 06. 从尾到头打印链表 难度:简单 输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。 示例 1: 输入:head = [1,3,2] 输出:[2,3,1] 限制: 0 <= 链表长度 <= 10000 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0006 func reversePrint(head *ListNode) []int { var res []int for head != nil { res = append(res, head.Val) head = head.Next } mid := len(res) / 2 max := len(res) - 1 for i := 0; i < mid; i++ { res[i], res[max-i] = res[max-i], res[i] } return res } type ListNode struct { Val int Next *ListNode }
/* 剑指 Offer 07. 重建二叉树 难度:中等 输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3 / \ 9 20 / \ 15 7 限制: 0 <= 节点个数 <= 5000 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0007 /* 执行用时:4 ms, 在所有 Go 提交中击败了95.89%的用户 内存消耗:4.2 MB, 在所有 Go 提交中击败了38.28%的用户 在定位 rootPos 的时候是用线性扫描,这种方式的时间复杂度较高(应该是 NlogN)。 一种解决方案是对inorder扫描一次,建立哈希表。这样用额外的 N 的空间复杂度,换取了较低的时间复杂度(N)。 */ func buildTree(preorder []int, inorder []int) *TreeNode { if len(preorder) == 0 { return nil } if len(preorder) == 1 { return &TreeNode{Val: preorder[0]} } var rootVal = preorder[0] var rootPos int for inorder[rootPos] != rootVal { rootPos++ } return &TreeNode{ Val: rootVal, Left: buildTree(preorder[1:rootPos+1], inorder[:rootPos]), Right: buildTree(preorder[rootPos+1:], inorder[rootPos+1:]), } } type TreeNode struct { Val int Left *TreeNode Right *TreeNode }
/* 剑指 Offer 10- I. 斐波那契数列 难度:简单 写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下: F(0) = 0, F(1)= 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。 答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。 示例 1: 输入:n = 2 输出:1 示例 2: 输入:n = 5 输出:5 提示: 0 <= n <= 100 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0010_1 func fib(n int) int { if n <= 1 { return n } var x, y, z = 0, 1, 1 for i := 2; i <= n; i++ { z = x + y if z >= 1000000007 { z -= 1000000007 } x, y = y, z } return z }
/* 剑指 Offer 10- II. 青蛙跳台阶问题 难度:简单 一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n级的台阶总共有多少种跳法。 答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。 示例 1: 输入:n = 2 输出:2 示例 2: 输入:n = 7 输出:21 示例 3: 输入:n = 0 输出:1 提示: 0 <= n <= 100 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0010_2 /* 评论: 直接用斐波那契的思路来做,就很容易。 如果没有斐波那契的铺垫,也能想到,不过需要脑内多推导一会儿,因为这种暴力线性推导的方式很容易被自我否定。 */ func numWays(n int) int { if n <= 1 { return 1 } var x, y, z = 1, 1, 2 for i := 2; i <= n; i++ { z = x + y if z >= 1000000007 { z -= 1000000007 } x, y = y, z } return z }
/* 剑指 Offer 11. 旋转数组的最小数字 难度:简单 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。 例如,数组[3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。 示例 1: 输入:[3,4,5,1,2] 输出:1 示例 2: 输入:[2,2,2,0,1] 输出:0 注意:本题与主站 154 题相同:https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/ 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0011 /* 评论: 跟官方题解略有不同。在 y==z 的情况下,官方题解的意思是忽略掉right位置,即right--然后继续循环。 而我的思路,在 y==z 的情况下,我把数组从mid位置切开,对两边分别递归然后返回更小的那个。 代码有可以精简的部分,但是影响不大,所以依然保留最易读的样子。 时间复杂度:最坏 (N),平均 (logN) 空间复杂度:最坏 (logN),因为要递归。正常 (1) 执行用时:4 ms, 在所有 Go 提交中击败了91.12%的用户 内存消耗:3.1 MB, 在所有 Go 提交中击败了59.08%的用户 */ func minArray(numbers []int) int { var left, right = 0, len(numbers) - 1 for right-left > 8 { mid := right/2 + left/2 var x, y, z = numbers[left], numbers[mid], numbers[right] if x < y { left = mid } else if x > y { right = mid } else { // x==y if y > z { left = mid } else { // x==y==z return minInt(minArray(numbers[1:mid]), minArray(numbers[mid+1:])) } } } return minArraySmall(numbers[left : right+1]) } func minArraySmall(numbers []int) int { if len(numbers) == 0 { return 1<<32 - 1 } var min = numbers[0] for _, num := range numbers { if num < min { min = num } } return min } func minInt(a, b int) int { if a > b { return b } return a }
/* 剑指 Offer 13. 机器人的运动范围 难度:中等 地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。 一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+7=18。但它不能进入方格 [35, 38],因为3+5+3+8=19。 请问该机器人能够到达多少个格子? 示例 1: 输入:m = 2, n = 3, k = 1 输出:3 示例 2: 输入:m = 3, n = 1, k = 0 输出:1 提示: 1 <= n,m <= 100 0 <= k<= 20 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0013 /* 评论: 一开始以为会有投机取巧的算法,想了半天,发现还是需要逐个格子遍历。 主要思路是先判断格子坐标是否合格,然后从(0,0)开始传播可达性。最后同时符合坐标合法和可达性的点就是符合的点,计数就可以了。 虽然对比官方题解稍微啰嗦了一点,但是复杂度是一样的。 官方题解最大的优化是,搜索方向只向下和向右。而我的是朝四个方向搜索(因为没有考虑到特性,实际上也是可以只向两个方向搜索的)。 空间复杂度:(mn) 时间复杂度:(mn) 执行用时:0 ms, 在所有 Go 提交中击败了100.00%的用户 内存消耗:2.5 MB, 在所有 Go 提交中击败了66.16%的用户 */ func movingCount(m int, n int, k int) int { // 1. 初始化格子 var board = make([][]int, m) for i := range board { board[i] = make([]int, n) } // 2. 判断合法 for x, row := range board { kk := k - x/10 - x%10 if kk < 0 { continue } for y := range row { if kk >= y/10+y%10 { board[x][y] = 1 } } } // 3. 判断可到达 propagate(board, 0, 0) // 4. 计数 count := 0 for _, row := range board { for _, num := range row { if num&0b11 == 0b11 { count++ } } } return count } func propagate(board [][]int, x, y int) { if x < 0 || x >= len(board) || y < 0 || y >= len(board[0]) { return } if board[x][y]&0b10 > 0 || board[x][y]&0b1 == 0 { return } board[x][y] |= 0b10 propagate(board, x+1, y) //propagate(board, x-1, y) propagate(board, x, y+1) //propagate(board, x, y-1) }
/* 剑指 Offer 14- I. 剪绳子 难度:中等 给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]...k[m-1] 。 请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少? 例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1 示例2: 输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 ×3 ×4 = 36 提示: 2 <= n <= 58 注意:本题与主站 343 题相同:https://leetcode-cn.com/problems/integer-break/ 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/jian-sheng-zi-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0014_1 /* 评论: 这其实是一道数学题。 由乘法分配律可知,和一定的两个数相乘时,两个数越接近,乘积越大。同理可推导:和一定的N个数相乘时,N个数越接近,乘积越大。 因此,我们尝试由2段、3段……推导到n/2段,每种情况令每一段长度尽可能相等,然后记下最大的乘积即可。 执行用时:0 ms, 在所有 Go 提交中击败了100.00%的用户 内存消耗:1.9 MB, 在所有 Go 提交中击败了77.44%的用户 */ func cuttingRope(n int) int { secMax := (n + 1) / 2 productMax := 1 for sec := 2; sec <= secMax; sec++ { // 2段、3段……n/2段的情况分别求解 secLength := n / sec secExtra := n % sec product := 1 // 让每段长度尽可能相等,即一部分长度是 secLength,另一部分长度是 secLength+1 for i := 0; i < secExtra; i++ { product *= secLength + 1 } for i := 0; i < (sec - secExtra); i++ { product *= secLength } // 记录最大值 if product > productMax { productMax = product } } return productMax }
/* 剑指 Offer 15. 二进制中1的个数 难度:简单 请实现一个函数,输入一个整数(以二进制串形式),输出该数二进制表示中 1 的个数。 例如,把 9表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。 示例 1: 输入:00000000000000000000000000001011 输出:3 解释:输入的二进制串 00000000000000000000000000001011中,共有三位为 '1'。 示例 2: 输入:00000000000000000000000010000000 输出:1 解释:输入的二进制串 00000000000000000000000010000000中,共有一位为 '1'。 示例 3: 输入:11111111111111111111111111111101 输出:31 解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。 提示: 输入必须是长度为 32 的 二进制串 。 注意:本题与主站 191 题相同:https://leetcode-cn.com/problems/number-of-1-bits/ 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0015 func hammingWeight(num uint32) int { var count = 0 for num > 0 { if num&1 == 1 { count++ } num = num >> 1 } return count }
/* 剑指 Offer 17. 打印从1到最大的n位数 难度:简单 输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。 示例 1: 输入: n = 1 输出: [1,2,3,4,5,6,7,8,9] 说明: 用返回一个整数列表来代替打印 n 为正整数 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0017 // 这个简单解法没有考虑大数越界int32问题,但是也通过单元测试了,因为越界时的数组内存已经吓死人了。 // 我在做的时候,直觉就认为不可能会有越界问题,所以如果用这题来考察越界问题是不合理的。 func printNumbers(n int) []int { if n == 0 { return nil } l := 1 for i := 0; i < n; i++ { l *= 10 } l -= 1 res := make([]int, l) for i := 0; i < l; i++ { res[i] = i + 1 } return res }
package q0046 import ( "strconv" ) /* 剑指 Offer 46. 把数字翻译成字符串 给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。 一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。 示例 1: 输入: 12258 输出: 5 解释: 12258有5种不同的翻译,分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi" 提示: 0 <= num < 231 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func translateNum(num int) int { numStr := strconv.Itoa(num) // x, y, z 分别代表 后2位、后1位、当前位的答案 var x, y, z = 0, 0, 1 for i := 0; i < len(numStr); i++ { // 滚动一次,当前位置在最坏情况下与上一位保持相同数量 x, y, z = y, z, z // 防御性代码,防止截取字符串截到-1位置 if i == 0 { continue } // 截取字符串并且判断条件 prv := numStr[i-1 : i+1] if prv <= "25" && prv >= "10" { z = y + x // 如果可以组合,则要加上后2位的答案 } else { z = y } } return z } func translateNum1(num int) int { if num < 0 { return 0 } if num < 10 { return 1 } var digs []int // len>=2 for ; num > 0; num /= 10 { digs = append(digs, num%10) } var results = make([]int, len(digs)) results[0] = 1 f1 := func(i int) { // i>=1 results[i] = results[i-1] } f2 := func(i int) { // i>=1 if i == 1 { results[i] = results[i-1] + 1 } else { results[i] = results[i-1] + results[i-2] } } for i := 1; i < len(digs); i++ { shi, ge := digs[i], digs[i-1] if shi > 2 { f1(i) } else if shi == 2 { if ge > 5 { f1(i) } else { f2(i) } } else if shi == 1 { f2(i) } else { // f==0 f1(i) } } return results[len(results)-1] }
/* 剑指 Offer 60. n个骰子的点数 把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。 你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。 示例 1: 输入: 1 输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667] 示例2: 输入: 2 输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778] 限制: 1 <= n <= 11 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0060 /* 执行用时:0 ms, 在所有 Go 提交中击败了100.00%的用户 内存消耗:1.9 MB, 在所有 Go 提交中击败了81.87%的用户 */ func dicesProbability(n int) []float64 { res := make([]float64, 1) res[0] = 1.0 for nn := 0; nn < n; nn++ { for i := range res { res[i] /= 6 } newRes := make([]float64, len(res)+5) for i := 0; i < 6; i++ { for ii := range res { newRes[ii+i] += res[ii] } } res = newRes } return res }
/* 剑指 Offer 63. 股票的最大利润 假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少? 示例 1: 输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 示例 2: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。 限制: 0 <= 数组长度 <= 10^5 注意:本题与主站 121 题相同:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/ 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0063 /* 执行用时:4 ms, 在所有 Go 提交中击败了94.38%的用户 内存消耗:3 MB, 在所有 Go 提交中击败了67.23%的用户 */ func maxProfit(prices []int) int { if len(prices) == 0 { return 0 } var minPrice, maxxProfit = prices[0], 0 for _, price := range prices { profit := price - minPrice if profit > maxxProfit { maxxProfit = profit } if price < minPrice { minPrice = price } } return maxxProfit }
/* 剑指 Offer 66. 构建乘积数组 给定一个数组 A[0,1,…,n-1],请构建一个数组 B[0,1,…,n-1],其中B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。 不能使用除法。 示例: 输入: [1,2,3,4,5] 输出: [120,60,40,30,24] 提示: 所有元素乘积之和不会溢出 32 位整数 a.length <= 100000 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0066 /* 执行结果:通过 执行用时:32 ms, 在所有 Go 提交中击败了42.70%的用户 内存消耗:9.3 MB, 在所有 Go 提交中击败了15.30%的用户 */ func constructArr(a []int) []int { if len(a) == 0 { return []int{} } b := make([]int, len(a)) for i := range b { b[i] = 1 } // 从左向右 var product int = 1 for i := 1; i < len(b); i++ { product *= a[i-1] b[i] = product } // 从右向左 product = 1 for i := len(b) - 2; i >= 0; i-- { product *= a[i+1] b[i] *= product } return b }
package p0 import "fmt" /* 给定一个按照升序排列的整数数组 nums,和一个目标值 target。 找出给定目标值在数组中的开始位置和结束位置。 你的算法时间复杂度必须是 O(log n) 级别。 如果数组中不存在目标值,返回 [-1, -1]。 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4] 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: [-1,-1] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func searchRange(nums []int, target int) []int { result := []int{-1, -1} if left := searchRangeLeft(nums, target); left != -1 { result[0] = left result[1] = searchRangeRight(nums[left:], target) + left } return result } func searchRangeLeft(nums []int, target int) int { if len(nums) == 0 { return -1 } var lo, hi, mid int for lo, hi = 0, len(nums); lo < hi; { mid = lo + (hi-lo)/2 if nums[mid] < target { lo = mid + 1 } else { hi = mid } } if hi == len(nums) { return -1 } if nums[hi] == target { return hi } return -1 } func searchRangeRight(nums []int, target int) int { if len(nums) == 0 { return -1 } var lo, hi, mid int for lo, hi = 0, len(nums); lo < hi; { mid = lo + (hi-lo)/2 if nums[mid] > target { hi = mid } else { lo = mid + 1 } } if hi == 0 { return -1 } if nums[hi-1] == target { return hi - 1 } return -1 } func searchRange1(nums []int, target int) []int { if len(nums) == 0 { return []int{-1, -1} } var lo, hi int for lo, hi = 0, len(nums)-1; lo <= hi; { mid := (lo + hi) / 2 switch { case nums[mid] < target: lo = mid + 1 case nums[mid] > target: hi = mid - 1 default: return []int{searchRangeLow(nums[lo:mid+1], target) + lo, searchRangeHigh(nums[mid:hi+1], target) + mid} } } return []int{-1, -1} } func searchRangeLow(nums []int, target int) int { fmt.Println(nums) if len(nums) == 0 { return 0 } var lo, hi int for lo, hi = 0, len(nums)-1; lo < hi; { mid := (lo + hi) / 2 if nums[mid] == target { hi = mid } else { lo = mid + 1 } } if nums[hi] == target { return hi } return -1 } func searchRangeHigh(nums []int, target int) int { fmt.Println(nums) if len(nums) == 0 { return 0 } var lo, hi int for lo, hi = 0, len(nums); lo < hi; { mid := (lo + hi) / 2 if nums[mid] != target { hi = mid } else { if lo == mid { break } lo = mid } } if nums[lo] == target { return lo } return -1 }
package p0 /* 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。 如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 你可以假设数组中无重复元素。 示例 1: 输入: [1,3,5,6], 5 输出: 2 示例 2: 输入: [1,3,5,6], 2 输出: 1 示例 3: 输入: [1,3,5,6], 7 输出: 4 示例 4: 输入: [1,3,5,6], 0 输出: 0 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/search-insert-position 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func searchInsert(nums []int, target int) int { var lo, hi, mid int for lo, hi = 0, len(nums)-1; lo <= hi; { mid = lo + (hi-lo)/2 switch { case nums[mid] > target: hi = mid - 1 case nums[mid] < target: lo = mid + 1 default: return mid } } return lo }
package p0 /* 判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 数独部分空格内已填入了数字,空白格用 '.' 表示。 示例 1: 输入: [ ["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] 输出: true 示例 2: 输入: [ ["8","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] 输出: false 解释: 除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。 说明: 一个有效的数独(部分已被填充)不一定是可解的。 只需要根据以上规则,验证已经填入的数字是否有效即可。 给定数独序列只包含数字 1-9 和字符 '.' 。 给定数独永远是 9x9 形式的。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/valid-sudoku 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func isValidSudoku(board [][]byte) bool { var checkRow, checkCol, checkBlk int var ch byte for i := 0; i < 9; i++ { checkRow, checkCol, checkBlk = 0, 0, 0 for j := 0; j < 9; j++ { // 检查第i行 ch = board[i][j] if ch != '.' { if checkRow&(1<<(ch-'0')) != 0 { return false } checkRow |= 1 << (ch - 48) } // 检查第i列 ch = board[j][i] if ch != '.' { if checkCol&(1<<(ch-'0')) != 0 { return false } checkCol |= 1 << (ch - 48) } // 第i块 坐标偏移量(i%3)*3, (i/3)*3 // 块内第j格 坐标偏移量j%3, j/3 ch = board[(i%3)*3+j%3][(i/3)*3+j/3] if ch != '.' { if checkBlk&(1<<(ch-'0')) != 0 { return false } checkBlk |= 1 << (ch - 48) } } } return true }
package p0 import "sort" /* 给定一个无重复元素的数组 candidates 和一个目标数 target , 找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 说明: 所有数字(包括 target)都是正整数。 解集不能包含重复的组合。 示例 1: 输入: candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ] 示例 2: 输入: candidates = [2,3,5], target = 8, 所求解集为: [ [2,2,2,2], [2,3,3], [3,5] ] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/combination-sum 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func combinationSum(candidates []int, target int) [][]int { if len(candidates) == 0 { return [][]int{} } g0039.cd = candidates g0039.len = len(g0039.cd) sort.Ints(g0039.cd) g0039.temp = make([]int, target/g0039.cd[0]+1) g0039.result = [][]int{} recurCombinationSum(0, 0, target) return g0039.result } var g0039 = struct { cd []int len int temp []int result [][]int }{} func recurCombinationSum(cdPos, tempPos int, target int) { for ; cdPos < g0039.len; cdPos++ { if g0039.cd[cdPos] > target { return } g0039.temp[tempPos] = g0039.cd[cdPos] if g0039.cd[cdPos] == target { newSolution := make([]int, tempPos+1) copy(newSolution, g0039.temp) g0039.result = append(g0039.result, newSolution) return } else { recurCombinationSum(cdPos, tempPos+1, target-g0039.cd[cdPos]) } } }
package p0 import "sort" /* 给定一个数组 candidates 和一个目标数 target , 找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。 说明: 所有数字(包括目标数)都是正整数。 解集不能包含重复的组合。 示例 1: 输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] 示例 2: 输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/combination-sum-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func combinationSum2(candidates []int, target int) [][]int { if len(candidates) == 0 { return [][]int{} } g0040.temp = make([]int, len(candidates)) // 对原数组计数 g0040.counter = map[int]int{} for _, num := range candidates { g0040.counter[num]++ } // 得到一个无重复元素的数组,并排序 count := 0 for key := range g0040.counter { candidates[count] = key count++ } g0040.len = count g0040.cd = candidates[:count] sort.Ints(g0040.cd) // 初始化剩下的全局变量 g0040.result = [][]int{} recurCombinationSum2(0, 0, target) return g0040.result } var g0040 = struct { cd []int len int temp []int result [][]int counter map[int]int }{} func recurCombinationSum2(cdPos, tempPos int, target int) { // 在无重复元素的数组上前进,跳过的值就是相当于是0个的 for ; cdPos < g0040.len; cdPos++ { num := g0040.cd[cdPos] tg := target // 根据个数,分别求1个,2个,3个……的情况,并递归 for dupl := 0; dupl < g0040.counter[num]; dupl++ { g0040.temp[tempPos+dupl] = num tg -= num if tg == 0 { newSolution := make([]int, tempPos+dupl+1) copy(newSolution, g0040.temp) g0040.result = append(g0040.result, newSolution) } else if tg > 0 { recurCombinationSum2(cdPos+1, tempPos+dupl+1, tg) } else { break } } } }
package p0 import ( "unsafe" ) /* 给定两个以字符串形式表示的非负整数 num1 和 num2, 返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。 示例 1: 输入: num1 = "2", num2 = "3" 输出: "6" 示例 2: 输入: num1 = "123", num2 = "456" 输出: "56088" 说明: num1 和 num2 的长度小于110。 num1 和 num2 只包含数字 0-9。 num1 和 num2 均不以零开头,除非是数字 0 本身。 不能使用任何标准库的大数类型(比如 BigInteger)或直接将输入转换为整数来处理。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/multiply-strings 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func multiply(num1 string, num2 string) string { if num1[0] == '0' || num2[0] == '0' { return "0" } // 初始化 var result = make([]int32, len(num1)+len(num2)) var n1 = make([]int32, len(num1)) var n2 = make([]int32, len(num2)) { for i, le := 0, len(num1)-1; i <= le; i++ { n1[le-i] = int32(num1[i] - '0') } for i, le := 0, len(num2)-1; i <= le; i++ { n2[le-i] = int32(num2[i] - '0') } } // 逐位计算 var incre int32 = 0 for i1, dig1 := range n1 { for i2, dig2 := range n2 { incre += dig1*dig2 + result[i1+i2] result[i1+i2] = incre % 10 incre /= 10 } result[i1+len(num2)] = incre incre = 0 } // 返回结果 var resultS = make([]byte, len(num1)+len(num2)) for i, le := 0, len(result)-1; i <= le; i++ { resultS[le-i] = byte(result[i]) + '0' } for i, b := range resultS { if b != '0' { resultS = resultS[i:] break } } return *(*string)(unsafe.Pointer(&resultS)) }
package p0 import ( "github.com/Saodd/leetcode-algo/leetcode/p0/q0031" "sort" ) /* 46. 全排列 给定一个没有重复数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/permutations 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func permute(nums []int) [][]int { if len(nums) == 0 { return [][]int{} } var le = len(nums) var total = 1 for i := 2; i <= le; i++ { total *= i } var result = make([][]int, total) for i := 0; i < total; i++ { result[i] = make([]int, le) } sort.Ints(nums) copy(result[0], nums) for i := 1; i < total; i++ { q0031.NextPermutation(nums) copy(result[i], nums) } return result }
package p0 import "sort" /* 47. 全排列 II 给定一个可包含重复数字的序列,返回所有不重复的全排列。 示例: 输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/permutations-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func permuteUnique(nums []int) [][]int { if len(nums) == 0 { return [][]int{} } sort.Ints(nums) g0047.len = len(nums) g0047.nums = nums g0047.temp = make([]int, len(nums)) g0047.used = make([]bool, len(nums)) g0047.result = make([][]int, 0, 6) recurPermuteUnique(0) return g0047.result } var g0047 = struct { nums []int temp []int len int result [][]int used []bool }{} func recurPermuteUnique(pos int) { if pos == g0047.len { newSolution := make([]int, len(g0047.temp)) copy(newSolution, g0047.temp) g0047.result = append(g0047.result, newSolution) return } for i := 0; i < g0047.len; i++ { if !g0047.used[i] { if i > 0 && !g0047.used[i-1] && g0047.nums[i] == g0047.nums[i-1] { continue } g0047.temp[pos] = g0047.nums[i] g0047.used[i] = true recurPermuteUnique(pos + 1) g0047.used[i] = false } } } // // --------------------------------------- //func permuteUnique(nums []int) [][]int { // if len(nums)==0{ // return [][]int{} // } // // len = len(nums) - 1 // temp = nums // sort.Ints(temp) // // result = make([][]int, 0, 5) // // recurPermuteUnique(0) // return result //} // //var temp []int //var len int //var result [][]int // //func recurPermuteUnique(pos int) { // if pos == len { // newSolution := make([]int, len(temp)) // copy(newSolution, temp) // result = append(result, newSolution) // return // } // // recurPermuteUnique(pos + 1) // for i := pos + 1; i <= len; i++ { // for j:=pos; j<i; j++{ // if temp[j]==temp[i]{ // goto NEXTI // } // } // temp[pos], temp[i] = temp[i], temp[pos] // recurPermuteUnique(pos + 1) // temp[pos], temp[i] = temp[i], temp[pos] // NEXTI: // } //}
package p0 /* 48. 旋转图像 给定一个 n × n 的二维矩阵表示一个图像。 将图像顺时针旋转 90 度。 说明: 你必须在原地旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。 示例 1: 给定 matrix = [ [1,2,3], [4,5,6], [7,8,9] ], 原地旋转输入矩阵,使其变为: [ [7,4,1], [8,5,2], [9,6,3] ] 示例 2: 给定 matrix = [ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16] ], 原地旋转输入矩阵,使其变为: [ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11] ] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/rotate-image 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func rotate(matrix [][]int) { if len(matrix) < 2 { return } var width = len(matrix[0]) var maxDepth = width / 2 for d := 0; d < maxDepth; d++ { w := width - 2*d - 1 for i := 0; i < w; i++ { //左上 matrix[d][d+i] //右上 matrix[d+i][width-1-d] //右下 matrix[width-1-d][width-1-d-i] //左下 matrix[width-1-d-i][d] matrix[d][d+i], matrix[d+i][width-1-d], matrix[width-1-d][width-1-d-i], matrix[width-1-d-i][d] = matrix[width-1-d-i][d], matrix[d][d+i], matrix[d+i][width-1-d], matrix[width-1-d][width-1-d-i] } } }
package p0 import ( "unsafe" ) /* 49. 字母异位词分组 给定一个字符串数组,将字母异位词组合在一起。 字母异位词指字母相同,但排列不同的字符串。 示例: 输入: ["eat", "tea", "tan", "ate", "nat", "bat"], 输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] 说明: 所有输入均为小写字母。 不考虑答案输出的顺序。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/group-anagrams 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func groupAnagrams(strs []string) [][]string { var dictionary = map[string][]string{} var temp string for i := range strs { temp = countAlpha(strs[i]) if value, ok := dictionary[temp]; ok { dictionary[temp] = append(value, strs[i]) } else { dictionary[temp] = []string{strs[i]} } } var result [][]string for _, v := range dictionary { result = append(result, v) } return result } var counter = make([]byte, 26) func countAlpha(s string) (count string) { for i := 0; i < 26; i++ { counter[i] = 0 } for _, i := range s { counter[i-'a']++ } return string(counter) } // 方案1 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> func groupAnagrams1(strs []string) [][]string { var dictionary = map[string][]string{} var p []byte var temp string for i := range strs { p = []byte(strs[i]) QuickSortByte(p) temp = *(*string)(unsafe.Pointer(&p)) if value, ok := dictionary[temp]; ok { dictionary[temp] = append(value, strs[i]) } else { dictionary[temp] = []string{strs[i]} } } var result [][]string for _, v := range dictionary { result = append(result, v) } return result } // 辅助 >>>>>>>>>>>>>>>>>>>>>>>>>>>>> func QuickSortByte(li []byte) { if len(li) == 0 { return } quickSortByte(li, 0, len(li)-1) } func quickSortByte(li []byte, lo, hi int) { stack := quickSortStack{} stack.Push(lo, hi) for stack.Len() > 0 { x, y, _ := stack.Pop() mid := quickSortBytePartition(li, x, y) if mid-x > 15 { stack.Push(x, mid-1) } else if mid-x > 1 { quickSortByteSelectSort(li, x, mid-1) } if y-mid > 15 { stack.Push(mid+1, y) } else if y-mid > 1 { quickSortByteSelectSort(li, mid+1, y) } } } func quickSortBytePartition(li []byte, lo, hi int) (mid int) { l, r := lo, hi //li[lo], li[(lo+hi)/2] = li[(lo+hi)/2], li[lo] midValue := li[lo] for l < r { for l <= hi { // 找大的 if li[l] > midValue { break } l++ } for r >= lo { if li[r] <= midValue { break } r-- } if l < r { li[l], li[r] = li[r], li[l] } else { break } } li[lo], li[r] = li[r], li[lo] return r } func quickSortByteSelectSort(li []byte, lo, hi int) { var min int for ; lo < hi; lo++ { min = lo for i := lo + 1; i <= hi; i++ { if li[i] < li[min] { min = i } } if lo != min { li[lo], li[min] = li[min], li[lo] } } } type quickSortStack struct { items []int } func (s *quickSortStack) Len() int { return len(s.items) } func (s *quickSortStack) Push(x, y int) { s.items = append(s.items, x, y) } func (s *quickSortStack) Pop() (int, int, error) { l := len(s.items) //if l < 2 { // return 0, 0, errors.New("没有元素可以取出") //} x, y := s.items[l-2], s.items[l-1] s.items = s.items[:l-2] return x, y, nil }
package p0 /* 50. Pow(x, n) 实现 pow(x, n) ,即计算 x 的 n 次幂函数。 示例 1: 输入: 2.00000, 10 输出: 1024.00000 示例 2: 输入: 2.10000, 3 输出: 9.26100 示例 3: 输入: 2.00000, -2 输出: 0.25000 解释: 2-2 = 1/22 = 1/4 = 0.25 说明: -100.0 < x < 100.0 n 是 32 位有符号整数,其数值范围是 [−231, 231 − 1] 。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/powx-n 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func myPow(x float64, n int) float64 { if n < 0 { if n == -1<<31 { return myPow(x, n+1) / x } x = 1 / x n *= -1 } var result float64 = 1 var currentProduct = x for n > 0 { if n&1 == 1 { result *= currentProduct } currentProduct *= currentProduct n = n >> 1 } return result }
package p0 /* 51. N皇后 n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。 给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。 每一种解法包含一个明确的 n 皇后问题的棋子放置方案, 该方案中 'Q' 和 '.' 分别代表了皇后和空位。 示例: 输入: 4 输出: [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ] 解释: 4 皇后问题存在两个不同的解法。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/n-queens 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func solveNQueens(n int) [][]string { // 初始化各项全局变量 g0051.len = n g0051.temp = make([]int, n) g0051.pattern = make([]byte, n) for i := range g0051.temp { g0051.temp[i] = i g0051.pattern[i] = '.' } g0051.result = [][]string{} // 开始递归 recSolveNQueens(0) return g0051.result } var g0051 = struct { len int // 皇后的数量 temp []int // 当前棋盘的摆放情况 result [][]string // 最后返回的结果 pattern []byte // 帮助生成字符串 }{} func recSolveNQueens(n int) { var num int // 递归到最后一位,如果满足斜线条件就记录这个答案 if n == g0051.len-1 { num = g0051.temp[n] for j := 0; j < n; j++ { if g0051.temp[j]+n-j == num || g0051.temp[j]-n+j == num { return } } recordNQueens() return } // 不是最后一位,就回溯+递归 for i := n; i < g0051.len; i++ { if i == n { num = g0051.temp[n] for j := 0; j < n; j++ { if g0051.temp[j]+n-j == num || g0051.temp[j]-n+j == num { goto NEXTNUM } } recSolveNQueens(n + 1) } else { g0051.temp[n], g0051.temp[i] = g0051.temp[i], g0051.temp[n] num = g0051.temp[n] for j := 0; j < n; j++ { if g0051.temp[j]+n-j == num || g0051.temp[j]-n+j == num { g0051.temp[n], g0051.temp[i] = g0051.temp[i], g0051.temp[n] goto NEXTNUM } } recSolveNQueens(n + 1) g0051.temp[n], g0051.temp[i] = g0051.temp[i], g0051.temp[n] } NEXTNUM: } } func recordNQueens() { // 记录当前的答案 solution := make([]string, g0051.len) for i, n := range g0051.temp { g0051.pattern[i] = 'Q' solution[n] = string(g0051.pattern) g0051.pattern[i] = '.' } g0051.result = append(g0051.result, solution) }
package p0 /* 53. 最大子序和 给定一个整数数组 nums ,找到一个具有最大和的连续子数组 (子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 进阶: 如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-subarray 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func maxSubArray(nums []int) int { if len(nums) == 0 { return 0 } var sumMax = nums[0] var group int for i := range nums { group += nums[i] if group > sumMax { sumMax = group } if group < 0 { group = 0 } } return sumMax }
package p0 /* 54. 螺旋矩阵 给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。 示例 1: 输入: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] 输出: [1,2,3,6,9,8,7,4,5] 示例 2: 输入: [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ] 输出: [1,2,3,4,8,12,11,10,9,5,6,7] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/spiral-matrix 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func spiralOrder(matrix [][]int) []int { if len(matrix) == 0 || len(matrix[0]) == 0 { return []int{} } var result = make([]int, len(matrix[0])*len(matrix)) // 四个边界 var right, down, left, up = len(matrix[0]) - 1, len(matrix) - 1, 0, 1 // 当前指针的位置x,y var x, y = 0, 0 // 循环填满结果数组 for direct, p := 0, 0; p < len(result); p++ { result[p] = matrix[y][x] // 决定这次的前进方向 switch direct { case 0: // 向右碰到边界 if x == right { direct = 1 right-- } case 1: // 向下碰到边界 if y == down { direct = 2 down-- } case 2: // 向左碰到边界 if x == left { direct = 3 left++ } case 3: // 向上碰到边界 if y == up { direct = 0 up++ } } // 前进一步 switch direct { case 0: x++ case 1: y++ case 2: x-- case 3: y-- } } return result }
package p0 /* 55. 跳跃游戏 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例 1: 输入: [2,3,1,1,4] 输出: true 解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。 示例 2: 输入: [3,2,1,0,4] 输出: false 解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/jump-game 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func canJump(nums []int) bool { if len(nums) < 2 { return true } var endPoint = len(nums) var touchPoint = nums[0] for pos := 0; pos < touchPoint; pos++ { // 当前点能够触及的最远点 newPoint := nums[pos] + pos + 1 // 如果是比记录中更远的点,那就记录下来 if newPoint > touchPoint { // 如果达到终点,就返回 if newPoint >= endPoint { return true } touchPoint = newPoint } } return false }
package p0 /* 56. 合并区间 给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2: 输入: [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/merge-intervals 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func merge(intervals [][]int) [][]int { if len(intervals) < 2 { return intervals } QuickSortInterval(intervals) var merges = make([][]int, 0) var merge = []int{intervals[0][0], intervals[0][1]} for i := range intervals { left, right := intervals[i][0], intervals[i][1] if left <= merge[1] { if right > merge[1] { merge[1] = right } } else { merges = append(merges, merge) merge = []int{left, right} } } merges = append(merges, merge) return merges } // 快速排序 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> func QuickSortInterval(li [][]int) { if len(li) == 0 { return } quickSortInterval(li, 0, len(li)-1) } func quickSortInterval(li [][]int, lo, hi int) { stack := quickSortStackInterval{} stack.Push(lo, hi) for stack.Len() > 0 { x, y, _ := stack.Pop() mid := quickSortIntervalPartition(li, x, y) if mid-x > 15 { stack.Push(x, mid-1) } else if mid-x > 1 { quickSortIntervalSelectSort(li, x, mid-1) } if y-mid > 15 { stack.Push(mid+1, y) } else if y-mid > 1 { quickSortIntervalSelectSort(li, mid+1, y) } } } func quickSortIntervalPartition(li [][]int, lo, hi int) (mid int) { l, r := lo, hi //li[lo], li[(lo+hi)/2] = li[(lo+hi)/2], li[lo] midValue := li[lo][0] for l < r { for l <= hi { // 找大的 if li[l][0] > midValue { break } l++ } for r >= lo { if li[r][0] <= midValue { break } r-- } if l < r { li[l], li[r] = li[r], li[l] } else { break } } li[lo], li[r] = li[r], li[lo] return r } func quickSortIntervalSelectSort(li [][]int, lo, hi int) { var min int for ; lo < hi; lo++ { min = lo for i := lo + 1; i <= hi; i++ { if li[i][0] < li[min][0] { min = i } } if lo != min { li[lo], li[min] = li[min], li[lo] } } } type quickSortStackInterval struct { items []int } func (s *quickSortStackInterval) Len() int { return len(s.items) } func (s *quickSortStackInterval) Push(x, y int) { s.items = append(s.items, x, y) } func (s *quickSortStackInterval) Pop() (int, int, error) { l := len(s.items) //if l < 2 { // return 0, 0, errors.New("没有元素可以取出") //} x, y := s.items[l-2], s.items[l-1] s.items = s.items[:l-2] return x, y, nil } // 快速排序 结束 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
package p0 /* 58. 最后一个单词的长度 给定一个仅包含大小写字母和空格 ' ' 的字符串,返回其最后一个单词的长度。 如果不存在最后一个单词,请返回 0 。 说明:一个单词是指由字母组成,但不包含任何空格的字符串。 示例: 输入: "Hello World" 输出: 5 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/length-of-last-word 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func lengthOfLastWord(s string) int { var lastChar = len(s) - 1 for lastChar >= 0 && s[lastChar] == ' ' { lastChar-- } if lastChar == -1 { return 0 } var lastSp = lastChar - 1 for lastSp >= 0 && s[lastSp] != ' ' { lastSp-- } return lastChar - lastSp }
package p0 import ( "github.com/Saodd/leetcode-algo/common" ) /* 60. 第k个排列 给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下: "123" "132" "213" "231" "312" "321" 给定 n 和 k,返回第 k 个排列。 说明: 给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例 1: 输入: n = 3, k = 3 输出: "213" 示例 2: 输入: n = 4, k = 9 输出: "2314" 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/permutation-sequence 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func getPermutation(n int, k int) string { // 先把所有元素生成 var nums = make([]byte, n) for i := byte(0); i < byte(n); i++ { nums[i] = i + '1' } // 计算阶乘,为后面做准备 var fac = common.Factorial(n - 1) // 因为n, k 都是从1开始计算,因此把他们都减掉1 n-- k-- // 逐位做除法,找出k落在哪一段 for i := 0; i < n && k != 0; i++ { upInsertBytes(i, i+k/fac, nums) k %= fac fac /= (n - i) } return string(nums) } // upInsertBytes 把ori位置的元素前移到tar位置,中间的元素相应后移一位。 func upInsertBytes(tar, ori int, bs []byte) { temp := bs[ori] for i := ori; i > tar; i-- { bs[i] = bs[i-1] } bs[tar] = temp }
package p0 import ( "github.com/Saodd/leetcode-algo/common" ) /* 62. 不同路径 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。 问总共有多少条不同的路径? 说明:m 和 n 的值均不超过 100。 示例 1: 输入: m = 3, n = 2 输出: 3 解释: 从左上角开始,总共有 3 条路径可以到达右下角。 1. 向右 -> 向右 -> 向下 2. 向右 -> 向下 -> 向右 3. 向下 -> 向右 -> 向右 示例 2: 输入: m = 7, n = 3 输出: 28 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/unique-paths 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func uniquePaths(m int, n int) int { m-- n-- // 保证n更小 if n > m { n, m = m, n } // 准备分子和分母 var numo, deno = make([]int, n), make([]int, n) for i := 0; i < n; i++ { numo[i] = m + i + 1 deno[i] = i + 1 } // 分子分母对消。最后答案一定是整数,分母一定能全部被分子消除掉。 for _, d := range deno { // 把分子的元素集中一下,减少循环次数 for numo[0] < 1<<25 && len(numo) > 1 { numo[0] = numo[0] * numo[1] numo[1], numo[len(numo)-1] = numo[len(numo)-1], numo[1] numo = numo[:len(numo)-1] } for i := range numo { // 分母元素能被分子整除就最好了,不能整除就去掉最大公约数 if numo[i]%d == 0 { numo[i] /= d break } else { g := common.Gcd(numo[i], d) numo[i] /= g d /= g } } } // 把分子剩下的元素乘起来 var paths int = 1 for _, n := range numo { paths *= n } return paths } // 另一种实现:对象式 ------------------------ func uniquePaths2(m int, n int) int { b := newUniquePathsBoard(m, n) return b.Paths(m-1, n-1) } type uniquePathsBoard [][]int func newUniquePathsBoard(m, n int) uniquePathsBoard { var cache = make([][]int, m) for i := 0; i < m; i++ { cache[i] = make([]int, n) } return cache } func (b uniquePathsBoard) Paths(m, n int) int { if m == 0 || n == 0 { return 1 } if b[m][n] == 0 { b[m][n] = b.Paths(m-1, n) + b.Paths(m, n-1) } return b[m][n] } // 另一种实现:函数式 ------------------------ func uniquePaths1(m int, n int) int { // 创建一个二维数组 var cache = make([][]int, m) for i := 0; i < m; i++ { cache[i] = make([]int, n) } // 递归求解 return uniquePathsRec(m-1, n-1, cache) } func uniquePathsRec(m, n int, cache [][]int) int { // 递归终止条件 if m == 0 || n == 0 { return 1 } // 查看之前是否计算过 if cache[m][n] == 0 { cache[m][n] = uniquePathsRec(m-1, n, cache) + uniquePathsRec(m, n-1, cache) } return cache[m][n] }
package p0 /* 63. 不同路径 II 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径? 网格中的障碍物和空位置分别用 1 和 0 来表示。 说明:m 和 n 的值均不超过 100。 示例 1: 输入: [ [0,0,0], [0,1,0], [0,0,0] ] 输出: 2 解释: 3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径: 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/unique-paths-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func uniquePathsWithObstacles(obstacleGrid [][]int) int { if len(obstacleGrid) == 0 || len(obstacleGrid[0]) == 0 { return 0 } b := newUniquePathsWithObstaclesBoard(obstacleGrid) return b.Paths(len(obstacleGrid)-1, len(obstacleGrid[0])-1) } type uniquePathsWithObstaclesBoard struct { paths [][]int obstacle [][]int } func newUniquePathsWithObstaclesBoard(ob [][]int) uniquePathsWithObstaclesBoard { m, n := len(ob), len(ob[0]) var paths = make([][]int, m) for i := 0; i < m; i++ { temp := make([]int, n) for ii := 0; ii < n; ii++ { temp[ii] = -1 } paths[i] = temp } return uniquePathsWithObstaclesBoard{paths, ob} } func (b uniquePathsWithObstaclesBoard) Paths(m, n int) int { if b.obstacle[m][n] == 1 { return 0 } if m == 0 && n == 0 { return 1 } if b.paths[m][n] == -1 { temp := 0 if m > 0 { temp += b.Paths(m-1, n) } if n > 0 { temp += b.Paths(m, n-1) } b.paths[m][n] = temp } return b.paths[m][n] }
package p0 import "github.com/Saodd/leetcode-algo/common" /* 64. 最小路径和 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。 示例: 输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/minimum-path-sum 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func minPathSum(grid [][]int) int { m, n := len(grid), len(grid[0]) for x := 0; x < m; x++ { for y := 0; y < n; y++ { grid[x][y] += minPathSumValue(x, y, grid) } } return grid[m-1][n-1] } func minPathSumValue(x, y int, grid [][]int) int { if x == 0 && y == 0 { return 0 } if x == 0 { return grid[0][y-1] } if y == 0 { return grid[x-1][0] } return common.MinInt(grid[x-1][y], grid[x][y-1]) } // 第二次提交:在第一次的基础上稍作优化 ---------------------------------------- func minPathSum2(grid [][]int) int { maxX, maxY := len(grid), len(grid[0]) { for i := 1; i < maxY; i++ { grid[0][i] += grid[0][i-1] } for i := 1; i < maxX; i++ { grid[i][0] += grid[i-1][0] } } var minLevel int = maxX if maxX > maxY { minLevel = maxY } for level := 1; level < minLevel; level++ { for i := level; i < maxY; i++ { if grid[level][i-1] > grid[level-1][i] { grid[level][i] += grid[level-1][i] } else { grid[level][i] += grid[level][i-1] } } for i := level + 1; i < maxX; i++ { if grid[i][level-1] > grid[i-1][level] { grid[i][level] += grid[i-1][level] } else { grid[i][level] += grid[i][level-1] } } } return grid[maxX-1][maxY-1] /* 执行用时 :8 ms, 在所有 golang 提交中击败了91.42%的用户 内存消耗 :3.9 MB, 在所有 golang 提交中击败了92.42%的用户 */ } // 第一次提交:建立一个空的二维数组,分别对行、列计算最小路径 -------------------------------------- func minPathSum1(grid [][]int) int { maxX, maxY := len(grid), len(grid[0]) paths := make([][]int, maxX) for i := 0; i < maxX; i++ { paths[i] = make([]int, maxY) } paths[0][0] = grid[0][0] x, y := 0, 0 for x < maxX && y < maxY { if x == 0 { for i := y + 1; i < maxY; i++ { paths[x][i] = paths[x][i-1] + grid[x][i] } for i := x + 1; i < maxX; i++ { paths[i][y] = paths[i-1][y] + grid[i][y] } } else { for i := y; i < maxY; i++ { if paths[x][i-1] > paths[x-1][i] { paths[x][i] = paths[x-1][i] + grid[x][i] } else { paths[x][i] = paths[x][i-1] + grid[x][i] } } for i := x; i < maxX; i++ { if paths[i][y-1] > paths[i-1][y] { paths[i][y] = paths[i-1][y] + grid[i][y] } else { paths[i][y] = paths[i][y-1] + grid[i][y] } } } x++ y++ } return paths[maxX-1][maxY-1] }
package p0 /* 66. 加一 给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。 最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外,这个整数不会以零开头。 示例 1: 输入: [1,2,3] 输出: [1,2,4] 解释: 输入数组表示数字 123。 示例 2: 输入: [4,3,2,1] 输出: [4,3,2,2] 解释: 输入数组表示数字 4321。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/plus-one 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func plusOne(digits []int) []int { // 先加一 var pos = len(digits) - 1 digits[pos] += 1 // 进位 for ; pos > 0; pos-- { if digits[pos] == 10 { digits[pos] = 0 digits[pos-1] += 1 } } // 最高位进位 if digits[0] == 10 { temp := make([]int, len(digits)+1) copy(temp[2:], digits[1:]) temp[1] = 0 temp[0] = 1 digits = temp } return digits }
package p0 /* 给定两个二进制字符串,返回他们的和(用二进制表示)。 输入为非空字符串且只包含数字 1 和 0。 示例 1: 输入: a = "11", b = "1" 输出: "100" 示例 2: 输入: a = "1010", b = "1011" 输出: "10101" 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/add-binary 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 提交成绩: 执行用时 :0 ms, 在所有 Go 提交中击败了100.00%的用户 内存消耗 :2.2 MB, 在所有 Go 提交中击败了82.95%的用户 */ func addBinary(a string, b string) string { // 令a的长度大于等于b if len(a) < len(b) { return addBinary(b, a) } // 准备变量 var temp []byte = make([]byte, len(a)+1) copy(temp[1:], a) ex := false x, y := len(temp)-1, len(b)-1 // 把b加入temp中 for y >= 0 { if ex { temp[x] += (b[y] - '0' + 1) } else { temp[x] += (b[y] - '0') } if temp[x] > '1' { temp[x] -= 2 ex = true } else { ex = false } x-- y-- } // temp剩下的部分要继续处理进位 if ex { for ; x > 0; x-- { if temp[x] == '0' { temp[x] = '1' ex = false break } else { temp[x] = '0' } } } // 整理最后结果返回 if ex { temp[0] = '1' return string(temp) } return string(temp[1:]) }
package p0 /* 实现 int sqrt(int x) 函数。 计算并返回 x 的平方根,其中 x 是非负整数。 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例 1: 输入: 4 输出: 2 示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/sqrtx 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func mySqrt(x int) int { if x < 2 { return x } var lo, hi int = 1, x var prod int for mid := (lo + hi) / 2; mid > lo; mid = (lo + hi) / 2 { prod = mid * mid if prod < x { lo = mid } else if prod == x { return mid } else { hi = mid } } return lo /* 提交成绩: 执行用时 : 4 ms , 在所有 Go 提交中击败了 56.13% 的用户 内存消耗 : 2.2 MB , 在所有 Go 提交中击败了 62.12% 的用户 其他思路:牛顿法 */ }
package p0 /* 70. 爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 示例 1: 输入: 2 输出: 2 解释: 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶 示例 2: 输入: 3 输出: 3 解释: 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/climbing-stairs 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func climbStairs(n int) int { if n <= 3 { return n } a, b := 2, 3 for i := 3; i < n; i++ { b, a = b+a, b } return b /* 第三次: 执行用时 : 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗 : 1.9 MB , 在所有 Go 提交中击败了 87.35% 的用户 注: 题解中还给出了利用矩阵乘法的算法,复杂度是log(n)。 由于矩阵乘法是纯粹的数学(线性代数),已经不是编程算法思想了,所以暂时不考虑。(主要还是我忘记矩阵乘法怎么做了……) */ } func climbStairs2(n int) int { if n <= 3 { return n } dyn := make([]int, n) dyn[0], dyn[1], dyn[2] = 1, 2, 3 for i := 3; i < n; i++ { dyn[i] = dyn[i-1] + dyn[i-2] } return dyn[n-1] /* 第二次 执行用时 : 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗 : 1.9 MB , 在所有 Go 提交中击败了 42.24% 的用户 */ } func climbStairs1(n int) int { if n <= 3 { return n } dyn := make([]int, n) dyn[0], dyn[1], dyn[2] = 1, 2, 3 return climbStairs1Dyn(n-1, dyn) /* 第一次: 执行用时 : 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗 : 2.1 MB , 在所有 Go 提交中击败了 5.89% 的用户 */ } func climbStairs1Dyn(n int, dyn []int) int { t := dyn[n] if t == 0 { t = climbStairs1Dyn(n-1, dyn) + climbStairs1Dyn(n-2, dyn) dyn[n] = t } return t }
package p0 import ( "strings" ) /* 71. 简化路径 以 Unix 风格给出一个文件的绝对路径,你需要简化它。或者换句话说,将其转换为规范路径。 在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..) 表示将目录切换到上一级(指向父目录); 两者都可以是复杂相对路径的组成部分。更多信息请参阅:Linux / Unix中的绝对路径 vs 相对路径 请注意,返回的规范路径必须始终以斜杠 / 开头,并且两个目录名之间必须只有一个斜杠 /。 最后一个目录名(如果存在)不能以 / 结尾。此外,规范路径必须是表示绝对路径的最短字符串。 示例 1: 输入:"/home/" 输出:"/home" 解释:注意,最后一个目录名后面没有斜杠。 示例 2: 输入:"/../" 输出:"/" 解释:从根目录向上一级是不可行的,因为根是你可以到达的最高级。 示例 3: 输入:"/home//foo/" 输出:"/home/foo" 解释:在规范路径中,多个连续斜杠需要用一个斜杠替换。 示例 4: 输入:"/a/./b/../../c/" 输出:"/c" 示例 5: 输入:"/a/../../b/../c//.//" 输出:"/c" 示例 6: 输入:"/a//b////c/d//././/.." 输出:"/a/b/c" 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/simplify-path 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func simplifyPath(path string) string { // 注:这里使用strings.Split严格来说是偷懒了。因为它(以及后面的strings.Join)会引入大量的字符串操作,性能相对较低。 // 正确解答参考标准库path.Clean() var originWords = strings.Split(path, "/") var words []string for _, w := range originWords { switch w { case "", ".": case "..": if len(words) > 0 { words = words[:len(words)-1] } default: words = append(words, w) } } return "/" + strings.Join(words, "/") }
package p0 /* 73. 矩阵置零 给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。 示例 1: 输入: [ [1,1,1], [1,0,1], [1,1,1]] 输出: [ [1,0,1], [0,0,0], [1,0,1]] 示例 2: 输入: [ [0,1,2,0], [3,4,5,2], [1,3,1,5]] 输出: [ [0,0,0,0], [0,4,5,0], [0,3,1,0]] 进阶: 一个直接的解决方案是使用 O(mn) 的额外空间,但这并不是一个好的解决方案。 一个简单的改进方案是使用 O(m + n) 的额外空间,但这仍然不是最好的解决方案。 你能想出一个常数空间的解决方案吗? 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/set-matrix-zeroes 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func setZeroes(matrix [][]int) { /* 执行用时 : 16 ms , 在所有 Go 提交中击败了 82.06% 的用户 内存消耗 : 6 MB , 在所有 Go 提交中击败了 100.00% 的用户 */ if len(matrix) == 0 || len(matrix[0]) == 0 { return } var xl, yl = len(matrix[0]), len(matrix) // 因为后面要用第一行和第一列做标记,所以提前判断一下 var xClear, yClear bool for x := 0; x < xl; x++ { if matrix[0][x] == 0 { xClear = true break } } if xClear { defer func() { for x := 0; x < xl; x++ { matrix[0][x] = 0 } }() } for y := 0; y < yl; y++ { if matrix[y][0] == 0 { yClear = true break } } if yClear { defer func() { for y := 0; y < yl; y++ { matrix[y][0] = 0 } }() } // 在第一行和第一列打上标记 for y := 1; y < yl; y++ { for x := 1; x < xl; x++ { if matrix[y][x] == 0 { matrix[y][0] = 0 matrix[0][x] = 0 } } } // 执行标记 for x := 1; x < xl; x++ { // 这里根据第一行的0标记来清除整列 if matrix[0][x] == 0 { for y := 1; y < yl; y++ { matrix[y][x] = 0 } } } for y := 1; y < yl; y++ { // 这里根据第一列的0标记来清除整行 if matrix[y][0] == 0 { for x := 1; x < xl; x++ { matrix[y][x] = 0 } } } }
package p0 import "github.com/Saodd/leetcode-algo/common" /* 74. 搜索二维矩阵 编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性: 每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。 示例 1: 输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 输出: true 示例 2: 输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 13 输出: false 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/search-a-2d-matrix 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func searchMatrix2(matrix [][]int, target int) bool { /* 大致思路 : (官方题解思路)二维坐标转换为一维坐标。 执行用时 : 4 ms , 在所有 Go 提交中击败了 98.17% 的用户 内存消耗 : 3.8 MB , 在所有 Go 提交中击败了 100.00% 的用户 */ if len(matrix) == 0 || len(matrix[0]) == 0 { return false } var y, x = len(matrix), len(matrix[0]) var left, right = 0, x*y - 1 for right >= left { mid := (left + right) / 2 midValue := matrix[mid/x][mid%x] if target < midValue { right = mid - 1 } else if target > midValue { left = mid + 1 } else { return true } } return false } func searchMatrix(matrix [][]int, target int) bool { /* 大致思路 : 先在纵向做二分,然后到横向做二分。 执行用时 : 8 ms , 在所有 Go 提交中击败了 79.58% 的用户 内存消耗 : 3.8 MB , 在所有 Go 提交中击败了 100.00% 的用户 */ if len(matrix) == 0 || len(matrix[0]) == 0 { return false } var xm, ym = len(matrix[0]) - 1, len(matrix) - 1 if target < matrix[0][0] || target > matrix[ym][xm] { return false } // 先在纵向确定 target 在哪一行 var up, row, down = 0, ym / 2, ym for { if target < matrix[row][0] { down = row } else if target > matrix[row][0] { if up == row { // 此时 down == up + 1, target 可能处在 down数组 上。 // 无法像数组二分查找中那样直接+1,所以打个补丁额外判断一下。 if target >= matrix[down][0] { row = down } break } up = row } else { return true } row = (up + down) / 2 } // 再在一行中进行二分查找 return common.IntArrayBinaryFind(matrix[row], target) >= 0 }
package p0 /* 75. 颜色分类 给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 注意: 不能使用代码库中的排序函数来解决这道题。 示例: 输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2] 进阶: 一个直观的解决方案是使用计数排序的两趟扫描算法。 首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗? 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/sort-colors 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func sortColors(nums []int) { /* 大致思路: 从左向右扫描,遇到0就丢到左边,遇到2就丢到右边。一共标记三个指针(左、中、右)。 执行用时 : 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗 : 2 MB , 在所有 Go 提交中击败了 100.00% 的用户 */ if len(nums) <= 1 { return } // left 是 下一个放置0的位置。right是下一个2的位置。 var left, right = 0, len(nums) - 1 for left <= right && nums[left] == 0 { left++ } for left <= right && nums[right] == 2 { right-- } // 用now作为当前索引,遍历一次 for now := left; now <= right; { switch nums[now] { case 0: if now != left { nums[now], nums[left] = nums[left], nums[now] } left++ // left 指向的是非0索引,理论上可能是1或2。但此时由于是从左向右遍历,因此左边不可能剩下2。 // 因此left只会指向1,因此 now 可以放心前进一步。 now++ case 1: now++ case 2: nums[now], nums[right] = nums[right], nums[now] right-- // right 指向的是非2索引,理论上可能是1或0。 // 因此 now 不能前进,等下一个循环再判断一次。 } } }
package p0 /* 77. 组合 给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。 示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/combinations 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func combine(n int, k int) [][]int { /* 大致思路: (回朔法)小数放前面,大数放后面。用迭代的思路,下一层迭代只能使用比上一层更大的数字。 执行用时 : 12 ms , 在所有 Go 提交中击败了 76.79% 的用户 内存消耗 : 6.3 MB , 在所有 Go 提交中击败了 100.00% 的用户 其他思路: 动态规划法。用公式表达 combine(n,k) = combine(n,k-1)+combine(n-1,k-1)。缺点是空间复杂度爆炸。 官方题解: 字典序 (二进制排序) 组合 */ var mod = make([]int, k) var result [][]int return combineRecur(result, mod, 0, 1, n) } func combineRecur(result [][]int, mod []int, pos, left, right int) [][]int { if pos == len(mod)-1 { for i := left; i <= right; i++ { mod[pos] = i var newMod = make([]int, len(mod)) copy(newMod, mod) result = append(result, newMod) } } else { for i := left; i <= right; i++ { mod[pos] = i result = combineRecur(result, mod, pos+1, i+1, right) } } return result }
package p0 import . "github.com/Saodd/leetcode-algo/common" /* 86. 分隔链表 给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/partition-list 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func partition(head *ListNode, x int) *ListNode { var smallHead, bigHead = &ListNode{}, &ListNode{} var smallTail, bigTail = smallHead, bigHead for p := head; p != nil; p = p.Next { if p.Val < x { smallTail.Next = p smallTail = p } else { bigTail.Next = p bigTail = p } } bigTail.Next = nil smallTail.Next = bigHead.Next return smallHead.Next }
package p0 import . "github.com/Saodd/leetcode-algo/common" /* 92. 反转链表 II 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。 说明: 1 ≤ m ≤ n ≤ 链表长度。 示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/reverse-linked-list-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func reverseBetween(head *ListNode, m int, n int) *ListNode { if m == n { return head } var dumHead = &ListNode{Next: head} var start = dumHead for i := 1; i < m; i++ { start = start.Next } var a, b, c *ListNode a = start // start, a, b, c 都不会是nil,因为m<n<=链表长度 b = a.Next c = b.Next for i := m; i < n; i++ { a, b, c = b, c, c.Next b.Next = a } start.Next, start.Next.Next = b, c return dumHead.Next }
package q0021 /* 2021-03-23 执行用时:4 ms, 在所有 Go 提交中击败了67.60%的用户 内存消耗:2.5 MB, 在所有 Go 提交中击败了97.82%的用户 */ func mergeTwoLists2(l1 *ListNode, l2 *ListNode) *ListNode { var head = &ListNode{} var cur = head for l1 != nil && l2 != nil { if l1.Val < l2.Val { cur.Next = l1 l1 = l1.Next } else { cur.Next = l2 l2 = l2.Next } cur = cur.Next } if l1 != nil { cur.Next = l1 } if l2 != nil { cur.Next = l2 } return head.Next }
/* 将两个有序链表合并为一个新的有序链表并返回。 新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/merge-two-sorted-lists 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0021 import "github.com/Saodd/leetcode-algo/common" type ListNode = common.ListNode type Solution func(*ListNode, *ListNode) *ListNode func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { if l2 == nil { return l1 } if l1 == nil { return l2 } var head *ListNode = &ListNode{} var tail *ListNode = head for { if l1.Val < l2.Val { tail.Next = l1 tail = tail.Next l1 = l1.Next if l1 == nil { tail.Next = l2 break } } else { tail.Next = l2 tail = tail.Next l2 = l2.Next if l2 == nil { tail.Next = l1 break } } } return head.Next }
package q0031 func nextPermutation2(nums []int) { // 二分查找 indexOfMinGreater := func(nums []int, target int) int { var gt, lt int for gt, lt = 0, len(nums); lt-gt > 1; { mid := (gt + lt) / 2 if nums[mid] > target { gt = mid } else { lt = mid } } return gt } // 交换排序 swapSortInt := func(nums []int) { for i, j := 0, len(nums)-1; i < j; { nums[i], nums[j] = nums[j], nums[i] i++ j-- } } if len(nums) < 2 { return } var top int for top = len(nums) - 1; top > 0; top-- { if nums[top-1] < nums[top] { break } } if top == 0 { swapSortInt(nums) return } exchId := indexOfMinGreater(nums[top:], nums[top-1]) + top nums[top-1], nums[exchId] = nums[exchId], nums[top-1] swapSortInt(nums[top:]) return } var NextPermutation = nextPermutation2
package q0031 import ( "sort" ) /* 2021-03-23 执行用时:4 ms, 在所有 Go 提交中击败了74.04%的用户 内存消耗:2.5 MB, 在所有 Go 提交中击败了97.03%的用户 */ func nextPermutation3(nums []int) { // 两个数的平均值,避免整形溢出 half := func(left, right int) int { return (right-left)/2 + left } // 传入一个递减排序的数组 findMinGreatPos := func(nums []int, compare int) int { var left, right = 0, len(nums) var mid int for mid = half(left, right); left < right-1; mid = half(left, right) { if nums[mid] <= compare { right = mid } else { left = mid } } return left } // 降序数组排序,直接用交换排序 swapSort := func(nums []int) { maxI := len(nums) / 2 for i := 0; i < maxI; i++ { j := len(nums) - 1 - i nums[i], nums[j] = nums[j], nums[i] } } // 1. 找到需要进位的位置(即从右向左数,第一个升序排列的位置) var downPos int for downPos = len(nums) - 2; downPos >= 0; downPos-- { if nums[downPos] < nums[downPos+1] { break } } if downPos < 0 { sort.Ints(nums) return } // 2. 从后面降序排列数组中,找到下一个值(即最小的比前面那个数字大的数字) descendingList := nums[downPos+1:] minGreatPos := findMinGreatPos(descendingList, nums[downPos]) // 3. 交换数字并排序 nums[downPos], descendingList[minGreatPos] = descendingList[minGreatPos], nums[downPos] swapSort(descendingList) }
/* 实现获取下一个排列的函数,算法需要将给定数字序列 重新排列成字典序中下一个更大的排列。 如果不存在下一个更大的排列, 则将数字重新排列成最小的排列(即升序排列)。 必须原地修改,只允许使用额外常数空间。 以下是一些例子,输入位于左侧列,其相应输出位于右侧列。 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/next-permutation 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0031 import ( "github.com/Saodd/leetcode-algo/common" ) func nextPermutation1(nums []int) { if len(nums) < 2 { return } var top int // 找到顶点,即降序排列的头部 for top = len(nums) - 1; top > 0; top-- { if nums[top-1] < nums[top] { break } } if top == 0 { common.QuickSortInt(nums) // 快速排序函数 return } // 在右边数组中找到一个值去跟左边交换 var targetNum, updateIndex = nums[top-1], top for i := len(nums) - 1; i > top; i-- { if nums[i] > targetNum && nums[i] < nums[updateIndex] { updateIndex = i } } nums[top-1], nums[updateIndex] = nums[updateIndex], nums[top-1] common.QuickSortInt(nums[top:]) // 快速排序函数 return }
package q0033 /* 2021-03-23 太难了,重点做 执行用时:0 ms, 在所有 Go 提交中击败了100.00%的用户 内存消耗:2.5 MB, 在所有 Go 提交中击败了57.98%的用户 */ func search2(nums []int, target int) int { if len(nums) < 2 { for i, n := range nums { if n == target { return i } } return -1 } var half = func(a, b int) int { return (b-a)/2 + a } var max = len(nums) - 1 var left, right = 0, len(nums) - 1 for left <= right { mid := half(left, right) if target == nums[mid] { return mid } if nums[0] <= nums[mid] { if nums[0] <= target && target < nums[mid] { right = mid - 1 } else { left = mid + 1 } } else { if nums[mid] < target && target <= nums[max] { left = mid + 1 } else { right = mid - 1 } } } return -1 }
/* 33. 搜索旋转排序数组 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2])。 搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回-1。 你可以假设数组中不存在重复的元素。 你的算法时间复杂度必须是O(logn) 级别。 示例 1: 输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4 示例2: 输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0033 func search(nums []int, target int) int { switch len(nums) { case 0: return -1 case 1: if target == nums[0] { return 0 } return -1 } var minId = indexOfMin(nums) var maxId int if minId == 0 { maxId = len(nums) - 1 } else { maxId = minId - 1 } //fmt.Println(maxId) switch { case target > nums[maxId] || target < nums[minId]: return -1 case target >= nums[0]: return binarySearch(nums[:maxId+1], target) default: if got := binarySearch(nums[minId:], target); got == -1 { return -1 } else { return got + minId } } } func indexOfMin(nums []int) int { // 假设1:nums长度大于1 // 假设2:nums没有重复元素 var firstElem = nums[0] for left, right := 0, len(nums); ; { mid := (left + right) / 2 if mid == left { if left == len(nums)-1 { return 0 } return left + 1 } if nums[mid] > firstElem { left = mid } else { right = mid } } } func binarySearch(nums []int, target int) int { // 假设1:nums已经升序排列 // 假设2:nums没有重复元素 if len(nums) == 0 || nums[0] > target || nums[len(nums)-1] < target { return -1 } for left, right := 0, len(nums); ; { mid := (left + right) / 2 switch { case nums[mid] < target: if left == mid { return -1 } left = mid case nums[mid] > target: right = mid default: return mid } } }
/* 61. 旋转链表 难度:中等(简单) 给定一个链表,旋转链表,将链表每个节点向右移动k个位置,其中k是非负数。 示例1: 输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL 示例2: 输入: 0->1->2->NULL, k = 4 输出: 2->0->1->NULL 解释: 向右旋转 1 步: 2->0->1->NULL 向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步:0->1->2->NULL 向右旋转 4 步:2->0->1->NULL 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/rotate-list 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0061 import ( "github.com/Saodd/leetcode-algo/helper/listnode" ) type ListNode = listnode.ListNode /* 2021-03-27 执行用时:4 ms, 在所有 Go 提交中击败了68.15%的用户 内存消耗:2.6 MB, 在所有 Go 提交中击败了94.81%的用户 */ func rotateRight(head *ListNode, k int) *ListNode { if head == nil { return head } var tail = head var count = 1 for tail.Next != nil { count++ tail = tail.Next } tail.Next = head var move = count - k%count for i := 0; i < move; i++ { tail = tail.Next } head = tail.Next tail.Next = nil return head }
package q0078 /* 78. 子集 给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1: 输入:nums = [1,2,3] 输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 示例 2: 输入:nums = [0] 输出:[[],[0]] 提示: 1 <= nums.length <= 10 -10 <= nums[i] <= 10 nums 中的所有元素 互不相同 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/subsets 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func subsets(nums []int) [][]int { var res = make([][]int, 0, 1<<len(nums)) for bits := int64(0); bits < 1<<len(nums); bits++ { res = append(res, copyByBits(nums, bits)) } return res } func copyByBits(nums []int, bits int64) (copy []int) { for i, v := range nums { if bits&(1<<i) > 0 { copy = append(copy, v) } } return }
package q0079 /* 79. 单词搜索 给定一个二维网格和一个单词,找出该单词是否存在于网格中。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示例: board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] 给定 word = "ABCCED", 返回 true 给定 word = "SEE", 返回 true 给定 word = "ABCB", 返回 false 提示: board 和 word 中只包含大写和小写英文字母。 1 <= board.length <= 200 1 <= board[i].length <= 200 1 <= word.length <= 10^3 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/word-search 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func exist(board [][]byte, word string) bool { Word = []byte(word) Board = board Depth = len(word) Path = make([][]bool, 0, len(board)) for range board { Path = append(Path, make([]bool, len(board[0]))) } first := Word[0] for x, row := range board { for y, b := range row { if b == first { Path[x][y] = true if Next(x, y, 1) { return true } Path[x][y] = false } } } return false } var ( Board [][]byte Word []byte Depth int Path [][]bool ) func Next(x, y int, depth int) bool { if depth == Depth { return true } first := Word[depth] xmax, ymax := len(Board), len(Board[0]) if x := x + 1; x < xmax && Board[x][y] == first { if !Path[x][y] { Path[x][y] = true if Next(x, y, depth+1) { return true } Path[x][y] = false } } if y := y + 1; y < ymax && Board[x][y] == first { if !Path[x][y] { Path[x][y] = true if Next(x, y, depth+1) { return true } Path[x][y] = false } } if x := x - 1; x >= 0 && Board[x][y] == first { if !Path[x][y] { Path[x][y] = true if Next(x, y, depth+1) { return true } Path[x][y] = false } } if y := y - 1; y >= 0 && Board[x][y] == first { if !Path[x][y] { Path[x][y] = true if Next(x, y, depth+1) { return true } Path[x][y] = false } } return false } /* 日期:2021-02-13 时间:实现+优化 约1小时 感想: 其实优化点在于如何记录已经搜索过的路径。 第一次用list存+map检验,超过时间限制了; 第二次用map存,时间排名16%; 最后才想到用board相同大小的bool二维数组来实现,时间排名95%,达到最优解。 */
/* 82. 删除排序链表中的重复元素 II 给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中没有重复出现的数字。 示例1: 输入: 1->2->3->3->4->4->5 输出: 1->2->5 示例2: 输入: 1->1->1->2->3 输出: 2->3 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0082 import "github.com/Saodd/leetcode-algo/helper/listnode" type ListNode = listnode.ListNode /* 2021-03-25 执行用时:4 ms, 在所有 Go 提交中击败了84.89%的用户 内存消耗:3 MB, 在所有 Go 提交中击败了100.00%的用户 */ func deleteDuplicates3(head *ListNode) *ListNode { if head == nil { return nil } head = &ListNode{Val: head.Val, Next: head} var cur = head for cur.Next != nil { if cur.Next.Next == nil { break } if cur.Next.Val != cur.Next.Next.Val { cur = cur.Next continue } var next = cur.Next.Next.Next for next != nil && next.Val == cur.Next.Val { next = next.Next } cur.Next = next } return head.Next } func deleteDuplicates2(head *ListNode) *ListNode { left := &ListNode{} newHead := left for right := head; right != nil; right = right.Next { dupFlag := false for right.Next != nil && right.Val == right.Next.Val { dupFlag = true right = right.Next } if !dupFlag { left.Next = right left = right } } left.Next = nil return newHead.Next } func deleteDuplicates1(head *ListNode) *ListNode { var dupMap = map[int]bool{} // 用map记录重复值 for p := head; p != nil; p = p.Next { _, ok := dupMap[p.Val] if ok { dupMap[p.Val] = true } else { dupMap[p.Val] = false } } // 删除重复节点 left := &ListNode{} newHead := left for right := head; right != nil; right = right.Next { if !dupMap[right.Val] { left.Next = right left = right } } left.Next = nil return newHead.Next }
/* 93. 复原IP地址 难度:中等 给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。 有效的 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 '.' 分隔。 例如:"0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址,但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效的 IP 地址。 示例 1: 输入:s = "25525511135" 输出:["255.255.11.135","255.255.111.35"] 示例 2: 输入:s = "0000" 输出:["0.0.0.0"] 示例 3: 输入:s = "1111" 输出:["1.1.1.1"] 示例 4: 输入:s = "010010" 输出:["0.10.0.10","0.100.1.0"] 示例 5: 输入:s = "101023" 输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"] 提示: 0 <= s.length <= 3000 (Lewin注:这个条件应该是错的) s 仅由数字组成 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/restore-ip-addresses 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0093 import ( "strings" ) func restoreIpAddresses(s string) []string { ctx := MyContext{ originS: s, Res: nil, temp: make([]string, 4), } ctx.Run(s, 0) return ctx.Res } type MyContext struct { originS string Res []string temp []string } func (c *MyContext) Run(s string, depth int) { if depth == 4 { newRes := strings.Join(c.temp, ".") if len(newRes) == len(c.originS)+3 { c.Res = append(c.Res, newRes) } return } for i := 0; i < 3 && i < len(s); i++ { sub := s[:i+1] if !isValid(sub) { return } c.temp[depth] = sub c.Run(s[i+1:], depth+1) } } func isValid(s string) bool { switch a := s[0]; a { case '0': return len(s) == 1 case '1': return true case '2': if len(s) == 3 { return s[1:] <= "55" } return true default: return len(s) < 3 } }
/* 94. 二叉树的中序遍历 难度:中等 给定一个二叉树的根节点 root ,返回它的 中序 遍历。 提示: 树中节点数目在范围 [0, 100] 内 -100 <= Node.val <= 100 进阶: 递归算法很简单,你可以通过迭代算法完成吗? */ package q0094 func inorderTraversal(root *TreeNode) []int { var res []int inorderTraversalRun(root, &res) return res } func inorderTraversalRun(root *TreeNode, res *[]int) { if root == nil { return } inorderTraversalRun(root.Left, res) *res = append(*res, root.Val) inorderTraversalRun(root.Right, res) } type TreeNode struct { Val int Left *TreeNode Right *TreeNode } /* 感想:这也忒简单了……3分钟写完一次通过。中等界的耻辱。 看了下其他人的解答,还有基于栈的实现,的确是一种思路。我之前好像做过(看到栈就想起来了),所以不再重复了。 */
/* 95. 不同的二叉搜索树 II 难度:中等 给定一个整数 n,生成所有由 1 ... n 为节点所组成的 二叉搜索树 。 示例: 输入:3 输出: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ] 解释: 以上的输出对应以下 5 种不同结构的二叉搜索树: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/unique-binary-search-trees-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0095 import ( "github.com/Saodd/leetcode-algo/helper/treenode" ) type TreeNode = treenode.TreeNode func generateTrees(n int) []*TreeNode { nums := make([]int, n) for i := range nums { nums[i] = i + 1 } nodes := Run(nums) return nodes } func Run(nums []int) (nodes []*TreeNode) { if len(nums) == 0 { return []*TreeNode{nil} } if len(nums) == 1 { return []*TreeNode{{Val: nums[0]}} } for i, num := range nums { left, right := nums[:i], nums[i+1:] leftNodes, rightNodes := Run(left), Run(right) for _, l := range leftNodes { for _, r := range rightNodes { nodes = append(nodes, &TreeNode{ Val: num, Left: l, Right: r, }) } } } return }
package p1 /* 121. 买卖股票的最佳时机 给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。 注意你不能在买入股票前卖出股票。 示例 1: 输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 示例 2: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func maxProfit(prices []int) int { var maxP = 0 var low = 1 << 30 for _, price := range prices { if price < low { low = price } if price-low > maxP { maxP = price - low } } return maxP }
/* 109. 有序链表转换二叉搜索树 难度:中等 给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。 示例: 给定的有序链表: [-10, -3, 0, 5, 9], 一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树: 0 / \ -3 9 / / -10 5 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0109 import ( "github.com/Saodd/leetcode-algo/helper/listnode" "github.com/Saodd/leetcode-algo/helper/treenode" ) type TreeNode = treenode.TreeNode type ListNode = listnode.ListNode /* 2021-03-27(难度中等偏下) 执行用时:8 ms, 在所有 Go 提交中击败了69.40%的用户 内存消耗:5.8 MB, 在所有 Go 提交中击败了100.00%的用户 */ func sortedListToBST2(head *ListNode) *TreeNode { if head == nil { return nil } if head.Next == nil { return &TreeNode{Val: head.Val} } var start = &ListNode{Next: head} var slow, fast = start, start for fast.Next != nil && fast.Next.Next != nil { slow = slow.Next fast = fast.Next.Next } var value = slow.Next.Val fast = slow.Next.Next slow.Next = nil return &TreeNode{ Val: value, Left: sortedListToBST2(head), Right: sortedListToBST2(fast), } } func sortedListToBST1(head *ListNode) *TreeNode { if head == nil { return nil } // 用快慢指针找到中点,并在中点前后将链表切分成两部分 var before, slow, fast *ListNode = nil, head, head.Next for fast != nil && fast.Next != nil { before = slow slow = slow.Next fast = fast.Next.Next } // 递归 if before != nil { before.Next = nil return &TreeNode{Val: slow.Val, Left: sortedListToBST1(head), Right: sortedListToBST1(slow.Next)} } else { return &TreeNode{Val: slow.Val, Right: sortedListToBST1(slow.Next)} } }
/* 118. 杨辉三角 难度:简单 给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。 在杨辉三角中,每个数是它左上方和右上方的数的和。 示例: 输入: 5 输出: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/pascals-triangle 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0118 func generate(numRows int) [][]int { if numRows == 0 { return nil } var rows = [][]int{{1}} for num := 2; num <= numRows; num++ { lastRow := rows[num-2] row := make([]int, num) row[0], row[num-1] = 1, 1 for i := 1; i < num-1; i++ { row[i] = lastRow[i-1] + lastRow[i] } rows = append(rows, row) } return rows }
/* 141. 环形链表 难度:简单 给定一个链表,判断链表中是否有环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。 示例 1: 输入:head = [3,2,0,-4], pos = 1 输出:true 解释:链表中有一个环,其尾部连接到第二个节点。 示例2: 输入:head = [1,2], pos = 0 输出:true 解释:链表中有一个环,其尾部连接到第一个节点。 示例 3: 输入:head = [1], pos = -1 输出:false 解释:链表中没有环。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/linked-list-cycle 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0141 import ( "github.com/Saodd/leetcode-algo/helper/listnode" ) type ListNode = listnode.ListNode /* 2021-03-27(难度:简单) 执行用时:8 ms, 在所有 Go 提交中击败了82.99%的用户 内存消耗:4.3 MB, 在所有 Go 提交中击败了24.45%的用户 */ func hasCycle(head *ListNode) bool { if head == nil { return false } var slow, fast = head, head.Next for fast != nil && fast.Next != nil { if slow == fast { return true } slow = slow.Next fast = fast.Next.Next } return false }
/* 142. 环形链表 II 给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回null。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。 说明:不允许修改给定的链表。 示例 1: 输入:head = [3,2,0,-4], pos = 1 输出:tail connects to node index 1 解释:链表中有一个环,其尾部连接到第二个节点。 示例2: 输入:head = [1,2], pos = 0 输出:tail connects to node index 0 解释:链表中有一个环,其尾部连接到第一个节点。 示例 3: 输入:head = [1], pos = -1 输出:no cycle 解释:链表中没有环。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/linked-list-cycle-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0142 import ( "github.com/Saodd/leetcode-algo/helper/listnode" ) type ListNode = listnode.ListNode func detectCycle(head *ListNode) *ListNode { if head == nil || head.Next == nil { return nil } var slow, fast = head, head.Next for slow != fast { if fast == nil || fast.Next == nil { return nil } slow = slow.Next fast = fast.Next.Next } fast = fast.Next slow = head for slow != fast { slow = slow.Next fast = fast.Next } return slow } var DetectCycle = detectCycle
/* 148. 排序链表 难度:中等 在O(nlogn) 时间复杂度和常数级空间复杂度下,对链表进行排序。 示例 1: 输入: 4->2->1->3 输出: 1->2->3->4 示例 2: 输入: -1->5->3->4->0 输出: -1->0->3->4->5 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/sort-list 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0148 import ( "github.com/Saodd/leetcode-algo/helper/listnode" ) type ListNode = listnode.ListNode /* 2021-03-27(难度:中等偏上) 执行用时:1480 ms, 在所有 Go 提交中击败了5.08%的用户 内存消耗:8.2 MB, 在所有 Go 提交中击败了18.35%的用户 分析:用的快排思路,看来并不适合链表,链表的特性适合使用归并排序(合并有序链表)。 */ func sortList2(head *ListNode) *ListNode { if head == nil { return nil } { var slow, fast = head, head.Next for fast != nil && fast.Next != nil { slow = slow.Next fast = fast.Next.Next } if slow.Next != nil { temp := head head = slow.Next slow.Next = slow.Next.Next head.Next = temp } } var value = head.Val var small, big, smallHead, bigHead *ListNode var cur = head.Next for cur != nil { if cur.Val <= value { if small == nil { small = cur smallHead = small } else { small.Next = cur small = small.Next } } else { if big == nil { big = cur bigHead = big } else { big.Next = cur big = big.Next } } cur = cur.Next } if small != nil { small.Next = nil } if big != nil { big.Next = nil } head.Next = nil smallHead = sortList2(smallHead) bigHead = sortList2(bigHead) head.Next = bigHead if smallHead == nil { return head } cur = smallHead for cur.Next != nil { cur = cur.Next } cur.Next = head return smallHead } func sortList1(head *ListNode) *ListNode { // 划分终点 if head == nil || head.Next == nil { return head } // 把链表对半划分 var slow, fast = head, head for fast.Next != nil && fast.Next.Next != nil { slow = slow.Next fast = fast.Next.Next } // 递归,分别对两半链表排序 head2 := sortList1(slow.Next) slow.Next = nil head = sortList1(head) // 合并两个有序链表 if head2 == nil { return head } var newHead *ListNode if head.Val <= head2.Val { newHead = head head = head.Next if head == nil { newHead.Next = head2 return newHead } } else { newHead = head2 head2 = head2.Next if head2 == nil { newHead.Next = head return newHead } } var p = newHead for { if head.Val <= head2.Val { p.Next = head p = head head = head.Next if head == nil { p.Next = head2 break } } else { p.Next = head2 p = head2 head2 = head2.Next if head2 == nil { p.Next = head break } } } return newHead }
/* 160. 相交链表 难度:简单(中等) 编写一个程序,找到两个单链表相交的起始节点。 注意: 如果两个链表没有交点,返回 null. 在返回结果后,两个链表仍须保持原有的结构。 可假定整个链表结构中没有循环。 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/intersection-of-two-linked-lists 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q0160 import ( "github.com/Saodd/leetcode-algo/helper/listnode" "github.com/Saodd/leetcode-algo/leetcode/p1/q0142" ) type ListNode = listnode.ListNode func getIntersectionNode2(headA, headB *ListNode) *ListNode { if headA == nil || headB == nil { return nil } var a, b = headA, headB var goA, goB = true, true for goA || goB { if a.Next == nil { a = headB goA = false } else { a = a.Next } if b.Next == nil { b = headA goB = false } else { b = b.Next } } for a != nil { if a == b { return a } a = a.Next b = b.Next } return nil } func getIntersectionNode1(headA, headB *ListNode) *ListNode { if headA == nil || headB == nil { return nil } // 找到A链表的尾部 var tailA = headA for ; tailA.Next != nil; tailA = tailA.Next { } // 把A链表收尾相连做成环,最后要恢复原样 tailA.Next = headA defer func() { tailA.Next = nil }() // 142题算法 return q0142.DetectCycle(headB) }
/* 1701. 平均等待时间 难度:中等(简单) 有一个餐厅,只有一位厨师。你有一个顾客数组customers,其中customers[i] = [arrivali, timei]: arrivali是第i位顾客到达的时间,到达时间按 非递减 顺序排列。 timei是给第 i位顾客做菜需要的时间。 当一位顾客到达时,他将他的订单给厨师,厨师一旦空闲的时候就开始做这位顾客的菜。每位顾客会一直等待到厨师完成他的订单。厨师同时只能做一个人的订单。厨师会严格按照 订单给他的顺序做菜。 请你返回所有顾客需要等待的 平均时间。与标准答案误差在10-5范围以内,都视为正确结果。 示例 1: 输入:customers = [[1,2],[2,5],[4,3]] 输出:5.00000 解释: 1) 第一位顾客在时刻 1 到达,厨师拿到他的订单并在时刻 1 立马开始做菜,并在时刻 3 完成,第一位顾客等待时间为 3 - 1 = 2 。 2) 第二位顾客在时刻 2 到达,厨师在时刻 3 开始为他做菜,并在时刻 8 完成,第二位顾客等待时间为 8 - 2 = 6 。 3) 第三位顾客在时刻 4 到达,厨师在时刻 8 开始为他做菜,并在时刻 11 完成,第三位顾客等待时间为 11 - 4 = 7 。 平均等待时间为 (2 + 6 + 7) / 3 = 5 。 示例 2: 输入:customers = [[5,2],[5,4],[10,3],[20,1]] 输出:3.25000 解释: 1) 第一位顾客在时刻 5 到达,厨师拿到他的订单并在时刻 5 立马开始做菜,并在时刻 7 完成,第一位顾客等待时间为 7 - 5 = 2 。 2) 第二位顾客在时刻 5 到达,厨师在时刻 7 开始为他做菜,并在时刻 11 完成,第二位顾客等待时间为 11 - 5 = 6 。 3) 第三位顾客在时刻 10 到达,厨师在时刻 11 开始为他做菜,并在时刻 14 完成,第三位顾客等待时间为 14 - 10 = 4 。 4) 第四位顾客在时刻 20 到达,厨师拿到他的订单并在时刻 20 立马开始做菜,并在时刻 21 完成,第四位顾客等待时间为 21 - 20 = 1 。 平均等待时间为 (2 + 6 + 4 + 1) / 4 = 3.25 。 提示: 1 <= customers.length <= 105 1 <= arrivali, timei <= 104 arrivali<= arrivali+1 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/average-waiting-time 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q1701 /* 2021-03-25 执行用时:168 ms, 在所有 Go 提交中击败了87.50%的用户 内存消耗:15.6 MB, 在所有 Go 提交中击败了97.50%的用户 */ func averageWaitingTime(customers [][]int) float64 { var queueFinish = 0 var total = 0 for _, customer := range customers { arrival, cost := customer[0], customer[1] // 无需等待,立即开始 if arrival >= queueFinish { total += cost queueFinish = arrival + cost continue } // 需要等待 queueFinish += cost total += queueFinish - arrival } return float64(total) / float64(len(customers)) }
/* 面试题 04.02. 最小高度树 难度:简单 给定一个有序整数数组,元素各不相同且按升序排列,编写一个算法,创建一棵高度最小的二叉搜索树。 示例: 给定有序数组: [-10,-3,0,5,9], 一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树: 0 / \ -3 9 / / -10 5 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/minimum-height-tree-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q1929 import "github.com/Saodd/leetcode-algo/helper/treenode" type TreeNode = treenode.TreeNode /* 2021-03-25 执行用时:4 ms, 在所有 Go 提交中击败了82.50%的用户 内存消耗:4.2 MB, 在所有 Go 提交中击败了100.00%的用户 */ func sortedArrayToBST(nums []int) *TreeNode { switch len(nums) { case 0: return nil case 1: return &TreeNode{Val: nums[0]} default: mid := len(nums) / 2 return &TreeNode{ Val: nums[mid], Left: sortedArrayToBST(nums[:mid]), Right: sortedArrayToBST(nums[mid+1:]), } } }
/* 面试题 04.05. 合法二叉搜索树 实现一个函数,检查一棵二叉树是否为二叉搜索树。 示例1: 输入: 2 / \ 1 3 输出: true 示例2: 输入: 5 / \ 1 4 / \ 3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ,但是其右子节点值为 4 。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/legal-binary-search-tree-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ package q1932 import ( "github.com/Saodd/leetcode-algo/helper/treenode" ) type TreeNode = treenode.TreeNode /* 2021-03-25 执行用时:4 ms, 在所有 Go 提交中击败了97.97%的用户 内存消耗:5.1 MB, 在所有 Go 提交中击败了88.51%的用户 注意:子树也要保持父节点的大小要求 */ func isValidBST(root *TreeNode) bool { if root == nil { return true } return isValidBSTRecur(root, false, false, 0, 0) } func isValidBSTRecur(root *TreeNode, f1, f2 bool, v1, v2 int) bool { // 要求 root!=nil if f1 && root.Val <= v1 { return false } if f2 && root.Val >= v2 { return false } if root.Left != nil { if ok := isValidBSTRecur(root.Left, f1, true, v1, root.Val); !ok { return false } } if root.Right != nil { if ok := isValidBSTRecur(root.Right, true, f2, root.Val, v2); !ok { return false } } return true }
package q0232 import "sync" /* 232. 用栈实现队列 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空,返回 true ;否则,返回 false 说明: 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。 进阶: 你能否实现每个操作均摊时间复杂度为 O(1) 的队列?换句话说,执行 n 个操作的总时间复杂度为 O(n) ,即使其中一个操作可能花费较长时间。 提示: 1 <= x <= 9 最多调用 100 次 push、pop、peek 和 empty 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作) Your MyQueue object will be instantiated and called as such: obj := Constructor(); obj.Push(x); param_2 := obj.Pop(); param_3 := obj.Peek(); param_4 := obj.Empty(); 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/implement-queue-using-stacks 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ type MyQueue struct { list []int lock sync.Mutex } /** Initialize your data structure here. */ func NewMyQueue() MyQueue { return MyQueue{lock: sync.Mutex{}} } /** Push element x to the back of queue. */ func (q *MyQueue) Push(x int) { q.lock.Lock() q.list = append(q.list, x) q.lock.Unlock() } /** Removes the element from in front of queue and returns that element. */ func (q *MyQueue) Pop() int { q.lock.Lock() x := q.list[0] // 对空数组取值时自动panic q.list = q.list[1:] q.lock.Unlock() return x } /** Get the front element. */ func (q *MyQueue) Peek() int { return q.list[0] // 对空数组取值时自动panic } /** Returns whether the queue is empty. */ func (q *MyQueue) Empty() bool { return len(q.list) == 0 } /* 日期:2021-02-13 用时:约10分钟 难度:容易 感受:非常容易 */
package p3 import . "github.com/Saodd/leetcode-algo/common" /* 328. 奇偶链表 给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。 请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。 示例 1: 输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL 示例 2: 输入: 2->1->3->5->6->4->7->NULL 输出: 2->3->6->7->1->5->4->NULL 说明: 应当保持奇数节点和偶数节点的相对顺序。 链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/odd-even-linked-list 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 */ func oddEvenList(head *ListNode) *ListNode { var oddHead, evenHead = &ListNode{}, &ListNode{} var odd, even = oddHead, evenHead var isOdd = true for p := head; p != nil; p = p.Next { if isOdd { odd.Next = p odd = p } else { even.Next = p even = p } isOdd = !isOdd } odd.Next = evenHead.Next even.Next = nil return oddHead.Next // 手写完成时间:5'20" }