力扣刷题（二）

title: golang力扣刷题（二）
date: 2021-11-04 10:06:27
categories:

go
tags:
基础

力扣刷题（二）

力扣刷题全部题目模块（30～60）

简单

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2

func searchInsert(nums []int, target int) int {i := 0j := len(nums) - 1c := -1for t := (i + j) / 2; i <= j; t = (i + j) / 2 {//二分法查找if nums[t] == target {    //相等输出c = tbreak}if nums[t] < target {     //缩小范围i = t + 1}if nums[t] > target {j = t - 1}}if j < 0 {               //排除最左端c = 0} else if i > len(nums)-1 {    //排除最右端c = len(nums)} else if nums[i] > target && target > nums[j] {   //中间端c = i}return c
}
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：3 MB, 在所有 Go 提交中击败了28.29%的用户

最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。

单词是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例 1：
输入：s = "Hello World"
输出：5
解释：最后一个单词是“World”，长度为5。

func lengthOfLastWord(s string) int {n := 0         //记录长度a := 0         //计数器for _, m := range s {     //遍历字符串if m == 32 {         //如果为空  a清0a = 0} else {           //不为空 a++a++}if a != 0 {          //如果a不是空，则n跟着a增加n = a}}return n
}
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2 MB, 在所有 Go 提交中击败了89.55%的用户

最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：
输入：nums = [1]
输出：1

func maxSubArray(nums []int) int {max := nums[0]    //max 计数for i := 1; i < len(nums); i++ {if nums[i]+nums[i-1] > nums[i] {nums[i] = nums[i] + nums[i-1]  //更新i  记录最大值}if nums[i] > max {    //更新最大值max = nums[i]}}return max
}
执行用时：72 ms, 在所有 Go 提交中击败了99.93%的用户
内存消耗：9.3 MB, 在所有 Go 提交中击败了37.27%的用户

回文链表

给定一个链表的 头节点 head **，**请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

输入: head = [1,2,3,3,2,1]
输出: true

func reverselist(head *ListNode) (l *ListNode, r *ListNode) {var p, q, m *ListNode //翻转函数，输入123，返回321 的头尾指针p = headq = head.Nextm = q.Nextif m == nil {q.Next = pp.Next = nilreturn q, p}for q != nil {q.Next = pp = qq = mif m.Next != nil {m = m.Next} else {q.Next = pbreak}}head.Next = nilreturn q, head
}
func isPalindrome(head *ListNode) bool {n := 1head1 := headhead2 := headfor head1.Next != nil {  //算出链表长度n++head1 = head1.Next}print(n)for i := 0; i < n/2; i++ {  //找到后面链表的开头head2 = head2.Nextprint(i)}if n > 1 && n%2 == 0 && n < 6 { //n=2,4  //排除前五个if n == 2 {if head.Val != head.Next.Val {return false}}if n == 4 {if head.Next.Val != head2.Val {return false}if head.Val != head2.Next.Val {return false}}}if n > 1 && n%2 == 1 && n < 6 { //n=3,5if n == 3 {if head.Val != head.Next.Next.Val {return false}}if n == 5 {head2 = head2.Nextif head.Next.Val != head2.Val {return false}if head.Val != head2.Next.Val {return false}}}if n > 5 && n%2 == 0 { //偶数  大于6的时候 head3, _ := reverselist(head2)   //翻转后面链表，逐个对比print(head3.Val)for head3 != nil {if head.Val == head3.Val {head = head.Nexthead3 = head3.Next} else {return false}}}if n>5&&n%2==1 { //奇数 大于6的时候head2 = head2.Nexthead3, _ := reverselist(head2)//翻转后面链表，逐个对比  for head3 != nil {if head.Val == head3.Val {head = head.Nexthead3 = head3.Next} else {return false}}}return true
}//这个太笨了 史上最lou代码
执行用时: 224 ms
内存消耗: 9.4 MB

func isPalindrome(head *ListNode) bool {head1 := headhead2 := headvar p, q *ListNodefor head1 != nil && head1.Next != nil { //翻转前部分head1 = head1.Next.Nextq = head2.Nexthead2.Next = pp = head2head2 = q}if head1 != nil {  //看他是不是奇数head2 = head2.Next}for p != nil {     //逐个对比if p.Val != head2.Val {return false}p = p.Nexthead2 = head2.Next}return true
}
执行用时：128 ms, 在所有 Go 提交中击败了90.49%的用户
内存消耗：10.9 MB, 在所有 Go 提交中击败了21.61%的用户

func isPalindrome(head *ListNode) bool {//递归var spalin func(*ListNode) boolspalin = func(head1 *ListNode) bool {if head1 != nil {if spalin(head1.Next) == false {return false}if head.Val != head1.Val {return false}head = head.Next}return true}return spalin(head)
}
执行用时: 164 ms
内存消耗: 17.6 MB

中等

下一个排列

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]

func nextPermutation(nums []int) []int {b := 0for i := len(nums) - 1; i > 0; i-- {     //从后往前遍历if nums[i] > nums[i-1] {               //如果比前一个大a := 0 num := nums[i:]                    //截取切片sort.Ints(num)                     //升序排列for n := 0; n < len(num); n++ {    //遍历这个排列找到比它大的最小值if num[n] > nums[i-1] {a = nums[i-1]                  //交换位置nums[i-1] = num[n]num[n] = abreak}}sort.Ints(num)                     //后面的再进行升序for j := 0; j < len(num); j++ {    //插入原来的数组nums[i] = num[j]i++}break                              //返回} else {                               //如果不大于前一个数 计数b++ }}if b == len(nums)-1 {                    //计数等于数组长度 则全是降序nums = sort.Ints(nums)                   //将它生序}return nums
}执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.5 MB, 在所有 Go 提交中击败了15.16%的用户

func isPalindrome(head *ListNode) bool {//递归var spalin func(*ListNode) boolspalin = func(head1 *ListNode) bool {if head1 != nil {if spalin(head1.Next) == false {return false}if head.Val != head1.Val {return false}head = head.Next}return true}return spalin(head)
}
执行用时：164 ms, 在所有 Go 提交中击败了14.99%的用户
内存消耗：17.6 MB, 在所有 Go 提交中击败了5.19%的用户

搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标从 0 开始计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你旋转后的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

func search(nums []int, target int) int {if len(nums) >= 2 {  //>=2的时候l := 0r := len(nums) - 1      //分别指向首尾for l <= r {i := (l + r) / 2if nums[i] == target {    //找到返回return i}if nums[0] <= nums[i] {      //前半部分部分if nums[0] <= target && target < nums[i] {r = i - 1} else {l = i + 1}} else {if nums[i] < target && target <= nums[len(nums)-1] {l = i + 1} else {r = i - 1}}}} else { //如果只有一个或0个的时候if len(nums) == 1 && nums[0] == target {return 0} else {return -1}}return -1
}
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.5 MB, 在所有 Go 提交中击败了100.00%的用户

在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

func searchRange(nums []int, target int) []int {l := sort.SearchInts(nums, target)    //找出这个数并返回下标if l == len(nums) || nums[l] != target {return []int{-1, -1}}r := sort.SearchInts(nums, target + 1) - 1 //找出比他大的数返回下标 减1return []int{l, r}
}
执行用时：8 ms, 在所有 Go 提交中击败了40.01%的用户
内存消耗：3.9 MB, 在所有 Go 提交中击败了59.36%的用户

有效的数独

请你判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。

func isValidSudoku(board [][]byte) bool {for i := 0; i < 9; i++ { //检查每行每列for j := 0; j < 8; j++ {a := board[i][j]b := board[j][i]for k := j + 1; k < 9; k++ {if a == board[i][k] && a != 46 { //行return false}if b == board[k][i] && b != 46 { //列return false}}}for j := 0; j < 9; j++ {            //检查每个小方块for k := i + 1; k%3 != 0; k++ {   //直接从下一行检查  for h := j / 3 * 3; h < j/3*3+3; h++ {if board[i][j] == board[k][h] && board[i][j] != 46 {return false}}}}}return true
}
执行用时：4 ms, 在所有 Go 提交中击败了60.38%的用户
内存消耗：2.6 MB, 在所有 Go 提交中击败了71.78%的用户

外观数列

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

countAndSay(1) = “1”
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221

第一项是数字 1
描述前一项，这个数是 1 即 “ 一个 1 ”，记作 “11”
描述前一项，这个数是 11 即 “ 二个 1 ” ，记作 “21”
描述前一项，这个数是 21 即 “ 一个 2 + 一个 1 ” ，记作 “1211”
描述前一项，这个数是 1211 即 “ 一个 1 + 一个 2 + 二个 1 ” ，记作 “111221”
要描述一个数字字符串，首先要将字符串分割为最小数量的组，每个组都由连续的最多相同字符组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

func countAndSay(n int) string {s := make([]rune, 0)c := '1's = append(s, c)for i := 1; i < n; i++ {   //n==1直接输出，大于1循环d := s[0]                 //d==第一个字节s2 := make([]rune, 0)for a, b := range s {      //遍历sif a == 0 {              //去掉第一个重复的continue}if d != b {               //遇到不一样的s2 = append(s2, c, d)   //将之前的加入d = b                   //d改成现在的bc = '1'                 //		计数改为1} else {                  //遇到一样的 C++c++}}s2 = append(s2, c, d)        //将最后的结果加入s = s2c = '1'                      //c计数改为1}return string(s)
}
执行用时：216 ms, 在所有 Go 提交中击败了14.13%的用户
内存消耗：7.2 MB, 在所有 Go 提交中击败了46.46%的用户

组合总和

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。

对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

示例 1：
输入: candidates = [2,3,6,7], target = 7
输出: [[7],[2,2,3]]

func combinationSum(candidates []int, target int) [][]int {sum := 0start := 0var s = make([][]int, 0)var s1 = make([]int, 0)var combination func(candidates []int, target int, sum int, start int)   //定义内置函数  将两个函数分开会出错，不是函数本身错误 它系统有问题过不去combination = func(candidates []int, target int, sum int, start int) {if sum == target {  //如果和与target相等 t := make([]int, len(s1)) //切片只是一个指向基础数组的指针，必须复制copy(t, s1)       //如果不希望影响其他切片，需要创建切片副本s = append(s, t)   //插入正确答案return}for i := start; i < len(candidates); i++ {if sum > target {  //剪枝，大于 终止循环break}s1 = append(s1, candidates[i])  //插入数组sum = sum + candidates[i]       //求和combination(candidates, target, sum, i)    //回溯sum = sum - candidates[i]       //撤销操作s1 = s1[:len(s1)-1]}}combination(candidates, target, sum, start)return s
}
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.7 MB, 在所有 Go 提交中击败了98.66%的用户

组合总和II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

func combinationSum2(candidates []int, target int) [][]int {sort.Ints(candidates) //排序var s = make([][]int, 0)     //最终输出数组var s1 = make([]int, 0)     //单个记录答案数组vis := make([]bool, len(candidates))   //一个标记数组，去重sum := 0             //和star := 0           //candidates开始下标var combin func(candidates []int, target int, sum int, star int)combin = func(candidates []int, target int, sum int, star int) {//根据上个题的经验 将回溯函数建立在函数内部if sum == target {      //如何和相等t := make([]int, len(s1))       //新建答案数组 复制插入，切片是指针copy(t, s1)s = append(s, t)return}for i := star; i < len(candidates); i++ {  //从开始下标遍历if sum > target {               //大于  剪枝，后面不用遍历break}// vis[i - 1] == true，说明同一树支candidates[i - 1]使用过// vis[i - 1] == false，说明同一树层candidates[i - 1]使用过// 要对同一树层使用过的元素进行跳过if i > 0 && candidates[i] == candidates[i-1] && !vis[i-1] {continue   //去重}vis[i] = truesum = sum + candidates[i]s1 = append(s1, candidates[i])combin(candidates, target, sum, i+1)   //回溯sum = sum - candidates[i]s1 = s1[:len(s1)-1]vis[i] = false}}combin(candidates, target, sum, star)return s
}
执行用时：4 ms, 在所有 Go 提交中击败了45.08%的用户
内存消耗：2.5 MB, 在所有 Go 提交中击败了88.90%的用户

字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

func multiply(num1 string, num2 string) string {if num1 == "0" || num2 == "0" {return "0"}ans := "0"m, n := len(num1), len(num2)for i := n - 1; i >= 0; i-- {curr := ""add := 0for j := n - 1; j > i; j-- {//字符串移位加0curr += "0"}y := int(num2[i] - '0')for j := m - 1; j >= 0; j-- {x := int(num1[j] - '0')product := x * y + addcurr = strconv.Itoa(product % 10) + curradd = product / 10}for ; add != 0; add /= 10 {curr = strconv.Itoa(add % 10) + curr}ans = addStrings(ans, curr)}return ans
}func addStrings(num1, num2 string) string {i, j := len(num1) - 1, len(num2) - 1add := 0ans := ""for ; i >= 0 || j >= 0 || add != 0; i, j = i - 1, j - 1 {x, y := 0, 0if i >= 0 {x = int(num1[i] - '0')}if j >= 0 {y = int(num2[j] - '0')}result := x + y + addans = strconv.Itoa(result % 10) + ansadd = result / 10}return ans
}
执行用时：44 ms, 在所有 Go 提交中击败了9.51%的用户
内存消耗：6.7 MB, 在所有 Go 提交中击败了21.60%的用户

跳跃游戏2

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2

func jump(nums []int) int { //创建一个切片记录m := len(nums)n1:=0a:=0num:=make([]int,m)for i:=0;i<m;i++{n2:=i+nums[i]    //本次能挑到的最远值if n2>n1{   //如果比n1大 则换值n1=n2a=num[i]+1  //a++  为了确保不出错 从num[i]上加}for i:=1;i<=n1&&i<m;i++{ //更新这个切片  防止越界 加上i<mif num[i]==0{  //如果里面没有值 则加上anum[i]=a}}}return num[m-1]   //最后输出最后记录值
}
执行用时：236 ms, 在所有 Go 提交中击败了5.04%的用户
内存消耗：6.1 MB, 在所有 Go 提交中击败了27.96%的用户

func jump(nums []int) int {m := len(nums)n1 := 0a := 0    //记录跳跃次数max := 0   //记录边界for i := 0; i < m-1; i++ {   //i<m-1可防止只有一个值时 程序执行for循环n2 := i + nums[i]   //最远值if n2 > n1 {       //找到跳的最大值n1 = n2 }if i == max {     //到达边界max = n1       //边界等于最大值a++            //步数+1}}return a
}
执行用时：20 ms, 在所有 Go 提交中击败了35.90%的用户
内存消耗：5.8 MB, 在所有 Go 提交中击败了53.87%的用户

全排列

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]

func permute(nums []int) [][]int {n := len(nums)num := make([][]int, 0)var backtrace func(path int)  //内置循环函数backtrace = func(path int) {if path == n {              //深度等于n 输出nu := make([]int, n)copy(nu, nums)             //不然会全部改变num = append(num, nu)return}for i := path; i < n; i++ {nums[path], nums[i] = nums[i], nums[path]   //交换位置backtrace(path + 1)                           //递归nums[path], nums[i] = nums[i], nums[path]     //撤销交换}}backtrace(0)return num
}
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.4 MB, 在所有 Go 提交中击败了99.60%的用户

func permute(nums []int) [][]int {if len(nums) == 0 {return nil}//思路是在已有的排列数组中，从头到尾见缝插针，组成新的全排列//比如有 1,2 的情况下，插入3，就是在头插入 3,1,2;中间插入1,3,2;尾巴插入1,2,3temp := make([][]int,0)temp = append(temp,[]int{nums[0]})for i:=1;i<len(nums);i++{temp2 := temptemp = make([][]int,0)for j:=0;j<=i;j++{for k:=0;k<len(temp2);k++ {temp3 := make([]int, 0)temp3 = append(temp3, temp2[k][0:j]...)temp3 = append(temp3, nums[i])temp3 = append(temp3, temp2[k][j:]...)temp = append(temp, temp3)}}}return temp
}

全排列2

给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。

示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],[1,2,1],[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]】

func rotate(matrix [][]int) {  //有点绕 背答案吧n := len(matrix)for i := 0; i < n/2; i++ {for j := 0; j < (n+1)/2; j++ {matrix[i][j], matrix[n-j-1][i], matrix[n-i-1][n-j-1], matrix[j][n-i-1] =matrix[n-j-1][i], matrix[n-i-1][n-j-1], matrix[j][n-i-1], matrix[i][j]}}
}执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.1 MB, 在所有 Go 提交中击败了100.00%的用户

字母异位词分组

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]

func SortString(s string) string { //排序函数ss := make([]rune, 0)for _, n := range s {ss = append(ss, n)}for i := 0; i < len(ss); i++ {for j := i + 1; j < len(ss); j++ {if ss[i] > ss[j] {a := ss[i]ss[i] = ss[j]ss[j] = a}}}return string(ss)
}
func groupAnagrams(strs []string) [][]string {mp := map[string][]string{} //建立一个字典for _, str := range strs {  //遍历字符串数组ss := SortString(str)      //排序mp[ss] = append(mp[ss], str)   //加入字典 }ans := make([][]string, 0, len(mp))  for _, v := range mp {  //将字典中的数据加入二维数组ans = append(ans, v)}return ans
}
执行用时：24 ms, 在所有 Go 提交中击败了54.24%的用户
内存消耗：7.9 MB, 在所有 Go 提交中击败了71.81%的用户

Pow(x,n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn ）。

示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100

func Pow(x float64, n int) float64 {  //精髓在这里 2^0 2^1 2^2 2^4 2^8if n == 0 {                         //不然会超时return 1}y := Pow(x, n/2)if n%2 == 0 {return y * y}return y * y * x
}
func myPow(x float64, n int) float64 {if n > 0 {if x < 0 {if n%2 == 1 {x = -Pow(-x, n)} else {x = Pow(-x, n)}} else {x = Pow(x, n)}} else if n == 0 {return 1.0} else { //n<0if x < 0 {if (-n)%2 == 1 {x = -Pow(-x, -n)} else {x = Pow(-x, -n)}} else {x = (1 / Pow(x, -n))}}return x
}func myPow(x float64, n int) float64 {  //最后结果跟x正负没有关系if n > 0 {x = Pow(x, n)} else if n == 0 {return 1.0} else { //n<0x = (1 / Pow(x, -n))}return x
}
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：1.9 MB, 在所有 Go 提交中击败了86.38%的用户

螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

func spiralOrder(matrix [][]int) []int {m := len(matrix)n := len(matrix[0])s := make([]int, 0)if m == 1 {  //处理只有一行for i := 0; i < n; i++ {s = append(s, matrix[0][i])}} else if n == 1 {//处理只有一列for i := 0; i < m; i++ {s = append(s, matrix[i][0])}} else {matrix2 := make([][]bool, m)for i := 0; i < m; i++ { //创建记录数组，默认为falsematrix2[i] = make([]bool, n)}for i, j := 0, 0; i < m && j < n; {  //循环for j < n && matrix2[i][j] == false {  //遍历到尾部，向下s = append(s, matrix[i][j])matrix2[i][j] = truej++}if j == n || matrix2[i][j] == true { //到尾部，改i,jj--i++}for i < m && matrix2[i][j] == false { //向下遍历s = append(s, matrix[i][j])matrix2[i][j] = truei++}if i == m || matrix2[i][j] == true {//到底部，改i,ji--j--}for j > -1 && matrix2[i][j] == false {//向左遍历s = append(s, matrix[i][j])matrix2[i][j] = truej--}if j == -1 || matrix2[i][j] == true { //到左边，改i,jj++i--}for i > -1 && matrix2[i][j] == false {//向上遍历s = append(s, matrix[i][j])matrix2[i][j] = truei--}if i == 0 || matrix2[i][j] == true {//到顶部，改i,ji++j++if matrix2[i][j] == true {    //设置结束条件break}}}}return s
}
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：1.9 MB, 在所有 Go 提交中击败了77.39%的用户

跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的第一个下标。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

func canJump(nums []int) bool {n:=len(nums)boundary:=0  //设置边界for i:=0;i<n;i++{if (i+nums[i])>boundary{  boundary=i+nums[i]   //更新边界}if nums[i]==0&&n>1&&i>=boundary{  //去除[0][0,1][3,0,4]return false}if boundary>=n-1{  //边界超出 truereturn true}}return false
}
执行用时：52 ms, 在所有 Go 提交中击败了74.87%的用户
内存消耗：6.7 MB, 在所有 Go 提交中击败了75.06%的用户

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

func merge(intervals [][]int) [][]int {for i := 0; i < len(intervals); i++ {   //先从第一个值开始排序  不排序搞不了，试过了for j := i + 1; j < len(intervals); j++ {if intervals[i][0] > intervals[j][0] {a := intervals[i][0]b := intervals[i][1]intervals[i][0] = intervals[j][0]intervals[i][1] = intervals[j][1]intervals[j][0] = aintervals[j][1] = b}}}for i := 0; i < len(intervals);  {if i+1 < len(intervals)&& intervals[i][1] <= intervals[i+1][1]&&intervals[i][1]>=intervals[i+1][0] {//[a,b][c,d] d>=b>=c 时intervals[i][1] = intervals[i+1][1] //b=dintervals = append(intervals[:i+1], intervals[i+2:]...)  //去掉后面的i=0} else{if i+1 < len(intervals)&& intervals[i][1] > intervals[i+1][1] {//b>d时intervals = append(intervals[:i+1], intervals[i+2:]...) //去掉后面的i=0}else{i++  //i++}}}return intervals
}

插入区间

给你一个无重叠的，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1：
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]

示例 2：
输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

//最笨方法
func merge(intervals [][]int) [][]int {for i := 0; i < len(intervals); i++ { //先从第一个值开始排序  不排序搞不了，试过了for j := i + 1; j < len(intervals); j++ {if intervals[i][0] > intervals[j][0] {a := intervals[i][0]b := intervals[i][1]intervals[i][0] = intervals[j][0]intervals[i][1] = intervals[j][1]intervals[j][0] = aintervals[j][1] = b}}}for i := 0; i < len(intervals); {if i+1 < len(intervals) && intervals[i][1] <= intervals[i+1][1] && intervals[i][1] >= intervals[i+1][0] { //[a,b][c,d] d>=b>=c 时intervals[i][1] = intervals[i+1][1]                     //b=dintervals = append(intervals[:i+1], intervals[i+2:]...) //去掉后面的i = 0} else {if i+1 < len(intervals) && intervals[i][1] > intervals[i+1][1] { //b>d时intervals = append(intervals[:i+1], intervals[i+2:]...) //去掉后面的i = 0} else {i++ //i++}}}return intervals
}
func insert(intervals [][]int, newInterval []int) [][]int {if len(intervals) == 0 { //如果长度为零，直接加入输出intervals = append(intervals, newInterval)} else {  //直接插入 然后用上面函数重新排序 合并  最笨方法intervals = append(intervals, newInterval)intervals = merge(intervals)}return intervals
}
执行用时：92 ms, 在所有 Go 提交中击败了5.41%的用户
内存消耗：4.5 MB, 在所有 Go 提交中击败了95.68%的用户

func insert(intervals [][]int, newInterval []int) [][]int {ans := make([][]int, 0)acc := false //哨兵 插入变truefor _, terval := range intervals {if newInterval[1] < terval[0] { //在左边 无交集if acc != true {ans = append(ans, newInterval) //先把newInterval插入 并做好标记acc = true}ans = append(ans, terval) //继续插入其他元素} else if newInterval[0] > terval[1] { //在右边 无交集ans = append(ans, terval) // 先插入 interval newInterval先放着} else { //有交集的情况  更改 newInterval值newInterval[0] = min(newInterval[0], terval[0])newInterval[1] = max(newInterval[1], terval[1])}}if acc != true { //如果遍历完还没插入  则加后面ans = append(ans, newInterval)}return ans
}
func min(a, b int) int {if a < b {return a}return b
}
func max(a, b int) int {if a > b {return a}return b
}
执行用时：8 ms, 在所有 Go 提交中击败了75.14%的用户
内存消耗：4.5 MB, 在所有 Go 提交中击败了83.78%的用户

螺旋矩阵2

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]

func generateMatrix(n int) [][]int {made := make([][]int, 0)mm := make([]int, 0)for i := 0; i < n; i++ {  //创建数组mm = append(mm, 0)}for i := 0; i < n; i++ {   //创建二维数组 cc := make([]int, len(mm))  //这里要copy 不然会一起改变数字copy(cc, mm)made = append(made, cc)}if n == 1 {   //排除n==1的情况made[0][0] = 1return made}m := 1for i, j := 0, 0; m < n*n+1; {   //给出循环限定条件  让他一直转if made[i][j] != 0 {         //改变方向条件i++j++}for j < n-1 && made[i][j] == 0 {    //从左往右made[i][j] = mm++j++}if made[i][j] != 0 {        //改变方向j--i++}for i < n-1 && made[i][j] == 0 {    //从上往下made[i][j] = mm++i++}if made[i][j] != 0 {        //改变方向i--j--}for j > 0 && made[i][j] == 0 {    //从右往左made[i][j] = mm++j--}if made[i][j] != 0 {      //改变方向i--j++}for i > 0 && made[i][j] == 0 {     //从下往上made[i][j] = mm++i--}}return made
}

困难

最长有效括号

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

type Stack struct {        //栈结构size inttop  intdata []int
}
func max(x, y int) int {    //输出最大值函数if x > y {return x}return y
}
func longestValidParentheses(s string) int {s1 := Stack{            //初始化栈size: len(s),top:  -1,data: make([]int, len(s)+1),}length := 0maxlength := 0s1.top = 0s1.data[s1.top] = -1       //里面输入-1for m, a := range s {      //遍历Sif string(a) == "(" {        //（  入栈s1.top++s1.data[s1.top] = m} else {                 //） 先出栈s1.top--if s1.top == -1 {            //如果栈为空  把 m放进去 新的开始s1.top++s1.data[s1.top] = m} else {                     //栈不为空 得到length  上面输入-1的原因length = m - s1.data[s1.top]maxlength = max(length, maxlength)     //得到最大值}}}return maxlength
}
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.8 MB, 在所有 Go 提交中击败了83.89%的用户

解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需遵循如下规则：

func isvalid(row int, col int, k byte, borad [][]byte) bool {for i := 0; i < 9; i++ { //判断行是否重复if borad[row][i] == k {return false}}for j := 0; j < 9; j++ { //判断列是否重复if borad[j][col] == k {return false}}Row := (row / 3) * 3Col := (col / 3) * 3for i := Row; i < Row+3; i++ { //判断这个小方块是否重复for j := Col; j < Col+3; j++ {if borad[i][j] == k {return false}}}return true //都没有重复 返回true
}
func solve(board [][]byte) bool {for i := 0; i < 9; i++ {for j := 0; j < 9; j++ {if board[i][j] != '.' { //如果为数字 继续continue}for k := '1'; k <= '9'; k++ { //需要判断这行 这列 这小块有没有这个数  有的话++if isvalid(i, j, byte(k), board) { //都没有重复board[i][j] = byte(k) //把K 填入if solve(board) {     //找到则返回return true} else {board[i][j] = '.' //没找到回溯}}}return false}}return true
}
func solveSudoku(board [][]byte) {solve(board)
}
执行用时：4 ms, 在所有 Go 提交中击败了50.56%的用户
内存消耗：2 MB, 在所有 Go 提交中击败了95.10%的用户

缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：
输入：nums = [1,2,0]
输出：3

func firstMissingPositive(nums []int) int {n := len(nums)for i := 0; i < n; i++ {for nums[i] > 0 && nums[i] < n && nums[nums[i]-1] != nums[i] {nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]}//置换， 注意这里不是if  for加了限制条件 可以把某位置的数直接放到原位置，如果是if的话 只换一次 换回来的数不一定在原位置}for i := 0; i < n; i++ {if nums[i] != i+1 {return i + 1}}return n + 1
}

func firstMissingPositive(nums []int) int {  //这他妈好狗n := len(nums)for i := 0; i < n; i++ {//将所有负数变为n+1if nums[i] <= 0 {nums[i] = n + 1}}for i := 0; i < n; i++ {//将对应位置变为负数num := abs(nums[i])if num <= n {fmt.Println(num-1)nums[num - 1] = -abs(nums[num - 1])}}for i := 0; i < n; i++ { //找正数下标加一  没变负数 证明这个没出现过if nums[i] > 0 {return i + 1}}return n + 1
}
func abs(x int) int {if x < 0 {return -x}return x
}

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

func trap(height []int) int {c := 0p := 1a := 0b := len(height) - 1for i := 0; a < b; { //从头往后遍历for height[i] < p { //一个一个往上增  找到定位i++a++if i == b {  //越界就返回break}}for height[b] < p {  //找定位b--if b == 0 {break}}for j := a; j < b; j++ {//遍历定位中的值if height[j] < p {c++}}p++   //p++}return c
}

执行用时：1444 ms, 在所有 Go 提交中击败了5.43%的用户
内存消耗：4.4 MB, 在所有 Go 提交中击败了13.87%的用户

通配符匹配

给定一个字符串 (s) 和一个字符模式 § ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

func isMatch(s string, p string) bool {if len(p) == 0 { //len(p)=0 len(s)=0 true         len(p)=0 len(s)!=0  falseif len(s) == 0 {return true}return false}if len(s) == 0 { //len(s)=0  len(p)!=0时  排除*for i := 0; i < len(p); {if p[i] == '*' {i++} else {return false}}return true}ss, pp := s[0], p[0]if ss == pp || pp == '?' {return isMatch(s[1:], p[1:])} else {if pp == '*' {if isMatch(s, p[1:]) == true {return true} else {if isMatch(s[1:], p) == true {return true} else {return false}}} else {return false}}return true
}
用递归做的 自认为没问题 但是超时了  很烦

func isMatch(s string, p string) bool {m, n := len(s), len(p)pp := make([][]bool, m+1) // 制作一个二维bool数组 表示字符串s的前i个字符和p中的前j个字符是否能匹配for i := 0; i <= m; i++ {pp[i] = make([]bool, n+1) //?防止数组越界  默认都为false}pp[0][0] = true //两个空字符串匹配for i:=1;i<=n;i++{if p[i-1]=='*'{pp[0][i]=true  //*匹配所有字符}else {break //跳出for循环 从第一个开始都为* 则为true 一直到不一样}}for i:=1;i<=m;i++{  //s选一 p从一选到最后 看是否匹配for j:=1;j<=n;j++{if p[j-1]=='*'{  //p为*号；pp[i][j]=pp[i][j-1]||pp[i-1][j]}else if p[j-1]=='?'|| s[i-1]==p[j-1]{ //p为？ 或者这两个相等，看它前面的匹配 他就匹配pp[i][j]=pp[i-1][j-1]}}}return pp[m][n]
}
执行用时：20 ms, 在所有 Go 提交中击败了26.35%的用户
内存消耗：6.3 MB, 在所有 Go 提交中击败了63.81%的用户

N皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

N皇后2

n 皇后问题研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题不同的解决方案的数量。

输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。

排序序列

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123"
"132"
"213"
"231"
"312"
"321"

给定 n 和 k，返回第 k 个排列。

示例 1：
输入：n = 3, k = 3
输出："213"
示例 2：
输入：n = 4, k = 9
输出："2314"