剑指offer memo

数组中重复数字

题目：https://leetcode.com/problems/find-the-duplicate-number/submissions/1114957310/

解法：

1. hashmap，最容易想到的解法，但是空间复杂度O(n)

2. 能改变nums数组的背景下将值对应index的值变为-，重复遇到时值为负，但是会改变数组值

   func findDuplicate(nums []int) int {
       for _,num := range nums {
           key := int(math.Abs(float64(num)))
           if nums[key] < 0 {
               return key
           }
           nums[key] = -nums[key]
       }
       return 0
   }

3. 二分法：在n个 1-n的数字中有重复，这个问题可以理解为，在数字 1到n/2 和 n/2到n两个范围中，重复数字落下的区间所拥有的数组数字量一定比一半要更多，用这个方式可以对 1-n的数字二分最后找到答案，时间复杂度O(nlogn)

   func findDuplicate(nums []int) int {
       left := 1
       right := len(nums)
       for {
           if(left >= right) {
               return left
           }
           mid := (left+right) / 2
           var leftNum,rightNum int
           for _,num := range nums {
               if num > mid && num <= right {
                   rightNum++
               } else if num >= left && num <= mid {
                   leftNum++
               }
           }
   
           if leftNum <= mid - left + 1 {
               left = mid + 1
           } else {
               right = mid
           }
       }
       return 0
   }

4. 环形链表：数字和对应下标值可以组成一个链表（当然是在数字本身是1-n的背景下），比如数组 [1,3,2,2] 组成的链表就是 1->3->2->2…，最后的2就会变成一个环形链表，可以用快慢指针找环形链表的方案求解，时间复杂度O(n)，空间复杂度O(1) 完美

   func findDuplicate(nums []int) int {
       var fast,slow,start int
       for {
           
           slow = nums[slow]
           fast = nums[nums[fast]]
           if fast == slow {
               break
           }
       }
       for {
           if start == slow {
               break
           }
           slow = nums[slow]
           start = nums[start]
       }
       return start
   }

二维数组中的查找

题目：https://leetcode.com/problems/search-a-2d-matrix-ii/submissions/1116268925/

没啥老朋友+1，就是从左到右从上到下递增的二维数组怎么找数字

从右上和左下开始的思路是一样的，以从右上开始打个比方，就是

• 如果matrix[a][b] > target，那么对所有x,y, x > a && y > b，都比target要大，也就是整个右下角，所以可以跳过右下角的遍历
• 如果matrix[a][b] < target，那么对所有x,y, x < a && y < b，都比target要小，所以不需要关心左上角
• 从右上开始的逻辑就是，右上角已经走过了，之后只需要对左下角接着遍历就ok了

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 {
        return false
    }
    m := len(matrix)
    x := 0
    y := len(matrix[0])-1
    for {
        if x == m || y < 0 {
            break
        }
        if matrix[x][y] == target {
            return true
        }
        
        if matrix[x][y] > target {
            y --
        } else {
            x ++
        }
    }
    return false
}

重建二叉树

题目：https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

老朋友加一，同时知道前序遍历（或后序遍历）和中序遍历就能够唯一确定一颗二叉树，而前序和后序则不能

func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }
    cur := &TreeNode{
        Val: preorder[0],
    }
    var inIndex int
    for i,in := range inorder {
        if in == preorder[0] {
            inIndex = i
        }
    }
    cur.Left = buildTree(preorder[1:inIndex+1], inorder[0:inIndex])
    cur.Right = buildTree(preorder[inIndex+1:], inorder[inIndex+1:])
    return cur
}

用两个栈实现堆

题目：https://leetcode.com/problems/implement-queue-using-stacks/submissions/1116341974/

没什么好讲的+1，写着玩

type MyQueue struct {
    In []int
    Out []int
}


func Constructor() MyQueue {
    return MyQueue{}
}


func (this *MyQueue) Push(x int)  {
    this.In = append(this.In, x)
}


func (this *MyQueue) Pop() int {
    var ret int
    if len(this.Out) == 0 {
        this.Out = append(this.Out, this.In...)
        this.In = []int{}
    }
    ret = this.Out[0]
    this.Out = this.Out[1:]
    return ret
}


func (this *MyQueue) Peek() int {
    if len(this.Out) == 0 {
        this.Out = append(this.Out, this.In...)
        this.In = []int{}
    }
    return this.Out[0]
}


func (this *MyQueue) Empty() bool {
    return len(this.Out) == 0 && len(this.In) == 0
}


/**
 * 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();
 */

斐波那契数列

题目：

• https://leetcode.com/problems/fibonacci-number/
• https://leetcode.com/problems/climbing-stairs/description/

func fib(n int) int {
    if n == 0 || n == 1 {
        return n
    }
    return fib(n-1) + fib(n-2)
}

多写两步就是爬楼梯，爬楼梯的本质方法其实就是下面：

func climbStairs(n int) int {
    if n == 1 || n == 2 {
        return n
    }
    return climbStairs(n-1) + climbStairs(n-2)
}

但是显而易见这是个递归，时间复杂度O(2^n)，这么简单的问题用递归太消耗时间了（虽然确实很简单），climbStairs(n-1) 和 climbStairs(n-2) 一定遇见过很多次重复计算，如果我们把爬到每层楼梯的计算结果都存下来呢？

下面就是用空间换时间之后的结果：

func climbStairs(n int) int {
    steps := make([]int, n)
    steps[0] = 1
    steps[1] = 2
    for i := 2; i<n; i++ {
        steps[i] = steps[i-2] + steps[i - 1]
    }
    return steps[n-1]
}

瞬间就变成了时间O(n)，空间O(n)的东西了

最后我们发现其实每次只关心step[n-1]和step[n-2]，所以就可以简化空间：

func climbStairs(n int) int {
    one := 1
    res := 1
    for i := 1; i<n; i++ {
        two := res
        res += one
        one = two
    }
    return res
}

时间复杂度O(n)，空间复杂度O(1)

最后总结一下，dp本质上就是用空间换时间，主要的流程分为以下三步：

1. 写出递归公式 f(n) = f(n-k)+f(n-w) （简单打个比方）
2. 用空间换时间方法写出dp解法
3. 优化空间

旋转数组的最小数字

题目：https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

解法就是显而易见的二分法，写二分法的时候我为了看起来舒服所以个人习惯喜欢写递归，这次把迭代递归两种都写一下：
递归：

func findMin(nums []int) int {
  if len(nums) == 1 {
      return nums[0]
  }   
  mid := (0 + len(nums) - 1 ) / 2
  if nums[len(nums) - 1] < nums[mid] {
      return findMin(nums[mid+1:])
  } else {
      return findMin(nums[0:mid+1])
  }
}

迭代：

func findMin(nums []int) int {
    left := 0
    right := len(nums) - 1
    for {
        if left >= right {
            return nums[left]
        }
        mid := (left + right) / 2
        if nums[right] < nums[mid] {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return 0
}

矩阵中的路径

题目：https://leetcode.com/problems/word-search/solutions/2498848/simple-backtracking-with-go/

典型回溯法求解，一开始天真地写了个外部函数：

func exist(board [][]byte, word string) bool {
    for i,row := range board {
        for j,_ := range row {
            res := find(board,word,0,i,j)
            if res == true {
                return res
            }
        
        }
    }
    return false
}

func find(board [][]byte, word string, wordIndex,x,y int) bool{
        m := len(board)
    n := len(board[0]) 
    if x < 0 || x >= m || y < 0 || y >= n {
        return false
    }
    if board[x][y] != []byte(word)[wordIndex] {
        return false
    }
    if wordIndex == len(word) - 1 {
        return true
    }

    
    tmp := board[x][y]
    board[x][y] = byte(0)

    wordIndex++
    res := false
        res = find(board,word,wordIndex,x,y + 1) || find(board,word,wordIndex,x,y - 1) || find(board,word,wordIndex,x-1,y) || find(board,word,wordIndex,x+1,y)
        
    board[x][y] = tmp
    return res
}

然后发现go可以搞闭包：

func exist(board [][]byte, word string) bool {
    m := len(board)
    n := len(board[0]) 
    var backtrack func(x,y,wordIndex int) bool
    backtrack = func(x,y,wordIndex int) bool{
        if x < 0 || x >= m || y < 0 || y >= n {
            return false
        }
        if board[x][y] != []byte(word)[wordIndex] {
            return false
        }
        if wordIndex == len(word) - 1 {
            return true
        }

        
        tmp := board[x][y]
        board[x][y] = byte(0)

        wordIndex++
        res := false
        res = backtrack(x,y + 1, wordIndex) || backtrack(x,y - 1, wordIndex) || backtrack(x-1,y, wordIndex) || backtrack(x+1,y,wordIndex)
            
        board[x][y] = tmp
        return res
    }
    for i,row := range board {
        for j,_ := range row {
            if backtrack(i,j,0) {
                return true
            }
        
        }
    }
    return false
}

二进制中1的个数

题目： https://leetcode.com/problems/number-of-1-bits/solutions/4340903/o-log-n-c-python-java-explained/

解法：
简单遍历取余，时间复杂度 O(logn)

func hammingWeight(num uint32) int {
    var time int
    for {
        if num == 0 {
            break
        }
        if num %2 == 1 {
            time++
        }
        num /= 2
    }
    return time
}

可以写成位运算的形式（从计算效率来说位运算肯定比除法好很多）（为什么？）：

func hammingWeight(num uint32) int {
    var time int
    for {
        if num == 0 {
            break
        }
        time+= int(num%2)
        num >>= 1
    }
    return time
}

数值的整数次方

题目：https://leetcode.com/problems/powx-n/

解法：

1. 顺着乘起来，时间复杂度是O(n)
2. 假设二进制 n = 1001， $a^n$ = $a^8*a$，可以把时间复杂度降低到 $log_2n$

func myPow(x float64, n int) float64 {
    var powVal float64
    powVal = 1
    newN := int(math.Abs(float64(n)))
    for {
        if newN==0 {
            break
        }
        if newN & 1 != 0 {
            powVal *= x
        }
        x *= x
        newN = newN >> 1
    }
    if n >= 0 {
        return powVal
    } else {
        return 1/powVal
    }
}

在O(1)时间内删除链表节点

题目：https://leetcode.com/problems/delete-node-in-a-linked-list/submissions/1117061591/

简单来说考验的就是对链表的熟悉程度

1. 一开始想到的方案是把链表整个往左移，所以写了个循环

func deleteNode(node *ListNode) {
    for {
        fmt.Printf("node:%v",node.Next)
        if node.Next != nil {
            node.Val = node.Next.Val
            if node.Next.Next == nil {
                node.Next = nil
                break        
            }
            node = node.Next
            
        } else {
            node = nil
            break
        }
        
    }
}

2. 后来发现自己就是个弱智，直接把下一个节点跳过不就行了？题目还强调了那么多次保证不会给末端节点，不审题唉

   func deleteNode(node *ListNode) {
       node.Val = node.Next.Val
       node.Next = node.Next.Next
   }

删除链表中重复的节点

题目：https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

自己写的时候多绕了一层，判断是否重复，然后再挨个判断

func deleteDuplicates(head *ListNode) *ListNode {
    newHead := &ListNode{
        Val: -101,
        Next : head,
    }
    cur := newHead
    before := -101
    for {
        if cur == nil {
            break
        }
        if cur.Next == nil {
            break
        }
        if cur.Next.Val == before {
            cur.Next = cur.Next.Next
        } else if cur.Next.Next != nil && cur.Next.Val == cur.Next.Next.Val {
            before = cur.Next.Val
            cur.Next = cur.Next.Next.Next
            
        } else {
            cur = cur.Next
        }
    }
    return newHead.Next
}

也可以把每个节点内加个判断重复的循环就行了，性能差不多但是代码可读性和理解会更简单一点

func deleteDuplicates(head *ListNode) *ListNode {
    newHead := &ListNode{
        Val: -101,
        Next : head,
    }
    cur := head
    before := newHead
    for {
        if cur == nil {
            break
        }

        var count int 
        
        for {
            if cur.Next == nil ||cur.Next.Val != cur.Val {
                break
            }
            cur = cur.Next
            count++
        }
        if count == 0 {
            before.Next = cur
            before = cur
        }
        cur = cur.Next
    }
    before.Next = nil
    return newHead.Next
}

正则表达式

题目：https://leetcode.com/problems/regular-expression-matching/

经典dp题，做了好一阵子

首先写出dp公式，一开始的时候写出来是这样的：

• 假设 i:字符串index,j:正则index
• 当p[j] 不等于 ‘*’ 时，dp[i][j] = dp[i-1][j-1] && (s[i] = p[j] || p[j] = ‘.’)
• 当p[j] 等于 ‘*’ 时，dp[i][j] = (s[i] = p[j-1] || p[j-1] = ‘.’) && (dp[i-1][j-1] || dp[i-1][j])

美滋滋写完发现报错了，忽略了一种场景：input= “aab”, regx = “c*a*b”，也就是”c*“不是”c+”，没有字符也是ok的

所以在这个的基础上针对输入加了第0位，也就是空字符串的正则表达匹配，最后的公式等于：

• 假设 i:字符串index,j:正则index
• 当p[j] 不等于 ‘*’ 时，dp[i][j] = dp[i-1][j-1] && (s[i] = p[j] || p[j] = ‘.’)
• 当p[j] 等于 ‘*’ 时，dp[i][j] = (s[i] = p[j-1] || p[j-1] = ‘.’) && (dp[i-1][j-1] || dp[i-1][j]) || dp[i][j-2]

func isMatch(s string, p string) bool {
    var dps [][]bool
    m := len(s)
    n := len(p)
    dps = make([][]bool, m+1)
    for d:= 0; d< m+1; d++ {
        dps[d] = make([]bool, n+1)
    }

    dps[0][0] = true
    for  i:=0; i<=m; i++ {
        for j := 1;j<=n; j++ {
            if p[j-1] != '*' {
                dps[i][j] = i > 0 && dps[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1]  == '.')
            } else {
                dps[i][j] = (i > 0 && (s[i-1] == p[j-2] || p[j-2]  == '.') && (dps[i-1][j] || dps[i-1][j-1])) || dps[i][j-2]
            }
        }
    }
    return dps[m][n]
}

合法数值字符串

题目：https://leetcode.com/problems/valid-number/

解法：

1. 本能用了有限状态自动机来做：

   • 状态0:字符串开始和结束
   • 状态1:符号
   • 状态2:数字
   • 状态3:e和E
   • 状态4:前面没有出现过数字的.
   • 状态5:前面出现过数字的.
     然后构建了一个状态转移矩阵，不过因为其实需要处理的特殊场景比较多（比如E和.只能出现一次），所以还是出现了不少if else判断，其实也可以把这些if else都转成其他状态，但是懒了这样也挺好

     func isNumber(s string) bool {
         trans :=[6][6]int{
             {0,1,1,0,1,0},
             {0,0,1,0,1,0},
             {1,0,1,1,1,1},
             {0,1,1,0,0,0},
             {0,0,1,0,0,0},
             {1,0,1,1,0,0},
         }
         var hasE,hasPoint,hasVal bool
         var preStatus int
         for _,val := range s{
             var status = 0
             if val == '-'|| val == '+'{
                 status = 1
             } else if val >= '0' && val <= '9' {
                 status = 2
                 hasVal = true
             } else if val == '.' {
                 if hasPoint {
                     return false
                 }
                 if hasVal {
                     status = 5
                 } else {
                     status = 4
                 }
                 hasPoint = true
                 
             } else if val == 'E' || val == 'e' {
                 status = 3
                 if hasE {
                     return false
                 }
                 hasE = true
                 hasPoint = true
             } else {
                 return false
             }
             if trans[preStatus][status] == 0 {
                 return false
             }
             preStatus = status
         }
         status := 0
         return trans[preStatus][status] == 1
     }

2. 正则，当然是个很不错的解法 const regex Solution::pattern("[+-]?(?:\\d+\\.?\\d*|\\.\\d+)(?:[Ee][+-]?\\d+)?") 但是y1s1对正则真的不是特别熟练。。。

按奇偶排序数组

题目：https://leetcode.com/problems/sort-array-by-parity/

非常典型的双指针题，遍历都是一遍过没有问题
解法：

1. 分配一个新的数组存，空间复杂度会变成O(n)

   func sortArrayByParity(nums []int) []int {
       start := 0
       end := len(nums) - 1
       res := make([]int, end+1)
       for _,num:= range nums {
           if num%2 == 0 {
               res[start] = num
               start++
           } else {
               res[end] = num
               end--
           }
       }
       return res
   }

2. 原地交换，空间复杂度O(1)

   func sortArrayByParity(nums []int) []int {
       start := 0
       end := len(nums) - 1
       for {
           
           for {
               if nums[start]%2 ==  && start < end{
                   start++
               } else {
                   break
               }
           }
           for {
               if nums[end]%2 == 1 && end > start{
                   end--
               } else {
                   break
               }
           }
           if start >= end {
               break
           } else {
               tmp := nums[start]
               nums[start] = nums[end]
               nums[end] = tmp
               start++
               end--
           }
       }
       return nums
   }

链表中倒数第n个节点

题目：https://leetcode.com/problems/remove-nth-node-from-end-of-list/

没啥，前后指针

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    newHead := &ListNode{
        Next: head,
    }
    start := newHead
    end := newHead
    for i:=0; i<n; i++ {
        start = start.Next
    }
    for {
        if start == nil {
            break
        }
        if start.Next != nil {
            start = start.Next
            end = end.Next
        } else {
            break
        }
    }
    end.Next = end.Next.Next
    return newHead.Next
}

链表环入口

题目：https://leetcode.com/problems/linked-list-cycle-ii/
解法见第一题

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    fast := head
    slow := head
    var step int
    for {
        if fast == nil || slow == nil || fast.Next == nil || slow == nil || fast.Next.Next == nil {
            return nil
        }
        if step == 0 || fast != slow {
            fast = fast.Next.Next
            slow = slow.Next
            step++
        } else {
            break
        }
    }
    // 肯定有环，找入口就行
    start := head
    for {
        if start != slow {
            start = start.Next
            slow = slow.Next
        } else {
            break
        }
    }
    return start
}

反转链表

题目：https://leetcode.com/problems/reverse-linked-list/solutions/3211778/using-2-methods-iterative-recursive-beats-97-91/

老朋友了+1，没什么好说的，写了两种解法：

1. 循环迭代，时间复杂度O(n)，空间复杂度 O(1)

   func reverseList(head *ListNode) *ListNode {
       newHead := &ListNode{
           Next:nil,
       }
       for {
           if head != nil {
               old := newHead.Next
               newHead.Next = head
               head = head.Next
               newHead.Next.Next = old
           } else {
               break
           }
       }
       return newHead.Next
   }

2. 递归：时间复杂度O(n)，空间复杂度 O(n)（函数调用空间）

   func reverseList(head *ListNode) *ListNode {
       if head == nil || head.Next == nil {
           return head
       }
       newHead := reverseList(head.Next)
       head.Next.Next = head
       head.Next = nil
       return newHead
   }

合并两个排序链表

题目：https://leetcode.com/problems/merge-two-sorted-lists/

不优雅但好理解，好理解最重要～

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    newHead := &ListNode{
    }
    head := newHead
    for {
        if list1 == nil && list2 == nil {
            break
        }
        if list1.Val < list2.Val {
            head.Next = list1
            list1 = list1.Next
        } else {
            head.Next = list2
            list2 = list2.Next
        }
        head = head.Next
    }
    var left *ListNode 
    if list1 != nil {
        left = list1
    } else {
        left = list2
    }
    for {
        if left != nil {
            head.Next = left
            head = head.Next
            left = left.Next
        } else {
            break
        }
    }
    return newHead.Next
}

判断是否子树

题目：https://leetcode.com/problems/subtree-of-another-tree/

题解：

我自己写的时候思路是把判断是子树往下走的逻辑和找子树的逻辑混在一块写了，用isSub来判断是在判断子树部分是否一致还是在找子树，这样不是很好看懂还有一堆判断逻辑

func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    
    return findSub(root,subRoot,false)
}

func findSub (root *TreeNode, subRoot *TreeNode, isSub bool) bool {
    if root == nil && subRoot == nil {
        return true
    }
    if root == nil || subRoot == nil {
        return false
    }
    var res bool
    if root.Val == subRoot.Val {
        res = findSub(root.Left,subRoot.Left, true) && findSub(root.Right,subRoot.Right, true)
    } else if isSub {
        return false
        
    }
    if !isSub {
        res = res || findSub(root.Left,subRoot, false) || findSub(root.Right,subRoot, false)
    }
    return res
}

把判断是否一致的逻辑单独拆出来：

func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    if root == nil || subRoot == nil {
        return root == subRoot
    }
    return isIdentical(root,subRoot) || isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
}

func isIdentical (root *TreeNode, subRoot *TreeNode) bool {
    if root == nil || subRoot == nil {
        return root == subRoot
    }
    var res bool
    if root.Val == subRoot.Val {
        res = isIdentical(root.Left,subRoot.Left) && isIdentical(root.Right,subRoot.Right)
    } else {
        return false
    }
    return res
}

翻转二叉树

题目：https://leetcode.com/problems/invert-binary-tree/description/

解法：

1. dfs递归，说实话递归没啥好写的，就是个普通的递归就结束了（所以说人类爱写递归不是没有原因的，太好写也太好懂了虽然占地方）

   func invertTree(root *TreeNode) *TreeNode {
       if root == nil {
           return nil
       }
       var right,left *TreeNode
       right = invertTree(root.Left)
       left = invertTree(root.Right)
       root.Left = left
       root.Right = right
       return root
   }

2. bfs，用队列来遍历二叉树，以后经常会这么做，习惯就好

   func invertTree(root *TreeNode) *TreeNode {
       if root == nil {
           return nil
       }
       var stack []*TreeNode
       stack = append(stack, root)
       for {
           l := len(stack)
           if l == 0 {
               break
           }
           head := stack[l - 1]
           stack = stack[:l-1]
           tmp := head.Right
           head.Right = head.Left
           head.Left = tmp
           if head.Right != nil {
               stack = append(stack, head.Right)
           }
           if head.Left != nil {
               stack = append(stack, head.Left)
           }
       }
       return root
   }

对称的二叉树

题目：https://leetcode.com/problems/symmetric-tree/

当然肯定有用堆来做的解法，一样一样的，偷懒不想写了

func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return symmetric(root.Left, root.Right)
}

func symmetric(left *TreeNode, right *TreeNode) bool {
    if left == nil || right == nil {
        return left == right
    }
    if left.Val == right.Val {
        return symmetric(left.Left, right.Right) &&  symmetric(left.Right, right.Left)
    } else {
        return false
    }
}

顺时针打印矩阵

题目：https://leetcode.com/problems/spiral-matrix/

题解：设置上下左右边界，按照边界进行遍历就行，时间复杂度O(mn)，空间复杂度O(1)，因为只需要记录四个边界

func spiralOrder(matrix [][]int) []int {
    if len(matrix) == 0 {
        return []int{}
    }
    var left,right,up,down int
    var res []int
    right = len(matrix[0]) - 1
    down = len(matrix) - 1
    for {
        if left > right || up > down {
            break
        }

        for i:= left; i <= right; i++ {
            res = append(res, matrix[up][i])
        }
        up++
        for i:= up; i<= down; i++ {
            res = append(res, matrix[i][right])
            
        }
        right--
        if up <= down {
            for i:= right; i >= left; i-- {
                res = append(res, matrix[down][i])
                
            }
            down--
        }
        if left <= right {
            for i:= down; i>= up; i-- {
                res = append(res, matrix[i][left])
                
            }
            left++
        }
    }
    return res
}

min stack

题目：https://leetcode.com/problems/min-stack/submissions/1117973116/

解法：

1. 辅助栈。时间复杂度O(1)，空间复杂度O(n)，简单来说就是搞个辅助栈minStack，利用栈先进后出的特性保存当前栈的最小值（一开始把栈和堆搞反了怎么也做不出来）

   type MinStack struct {
       stack []int
       minStack []int
   }
   
   
   func Constructor() MinStack {
       return MinStack{}
   }
   
   
   func (this *MinStack) Push(val int)  {
       this.stack = append(this.stack,val)
       
       if len(this.minStack) > 0 &&  this.minStack[len(this.minStack) - 1] < val {
           this.minStack = append(this.minStack, this.minStack[len(this.minStack) - 1])
       } else {
           this.minStack = append(this.minStack, val)
       }
   }
   
   
   func (this *MinStack) Pop()  {
       this.stack = this.stack[:len(this.stack)-1]
       this.minStack = this.minStack[0:len(this.minStack)-1]
   }
   
   
   func (this *MinStack) Top() int {
       return this.stack[len(this.stack)-1]
   }
   
   
   func (this *MinStack) GetMin() int {
       return this.minStack[len(this.minStack)-1]
   }

2. 空间复杂度为O(1)的辅助栈：受到了一点题解的启发，用和最小值的差值而不是当前值来保存，不过说实话这么难以阅读的逻辑不要也罢

   type MinStack struct {
       stack []int
       min int
   }
   
   
   func Constructor() MinStack {
       return MinStack{
           min:-1,
       }
   }
   
   
   func (this *MinStack) Push(val int)  {
       if len(this.stack) == 0 {
           this.min = val
       }
       diff := val - this.min
       this.stack = append(this.stack,diff)
       
       if diff < 0{
           this.min = val
       }
   }
   
   
   func (this *MinStack) Pop()  {
       val := this.stack[len(this.stack)-1]
       this.stack = this.stack[:len(this.stack)-1]
       if val < 0 {
           this.min -= val
       }
       
   }
   
   
   func (this *MinStack) Top() int {
       val := this.stack[len(this.stack)-1]
       if val <= 0 {
           return this.min
       } else {
           return val + this.min
       }
   }
   
   
   func (this *MinStack) GetMin() int {
       return this.min
   }

判断栈压入弹出序列合法

题目：https://leetcode.com/problems/validate-stack-sequences/

题解：其实就是模拟栈来处理

1. 空间复杂度O(1)但是修改原数组，因为不是很清楚go的删除节点是不是要O(n)一下，所以非常不建议

func validateStackSequences(pushed []int, popped []int) bool {
    var i,j int
    for {
        
        if i >= len(pushed) {
            return i == 0
        }
        if i == -1 || pushed[i] != popped[j] {
            i++
        } else {
            tmp := pushed[i+1:]
            pushed = append(pushed[:i], tmp...)
            j++
            i--
        }
    }
    return true
}

2. 使用辅助数组来模拟栈的操作

   func validateStackSequences(pushed []int, popped []int) bool {
       var help []int
       var i int
       for _,val := range pushed {
           help = append(help, val)
           for {
               if len(help) > 0 && popped[i] == help[len(help) - 1] {
                   help = help[:len(help) - 1]
                   i++
               } else {
                   break
               }
           }
       }
       return len(help) == 0
   }

分行从上到下打印二叉树

题目：https://leetcode.com/problems/binary-tree-level-order-traversal/submissions/1118009830/

题解：用堆就结束了，时间和空间复杂度都是O(n)，除了go不提供堆这种数据结构之外没有什么难点

func levelOrder(root *TreeNode) [][]int {
    var heap []*TreeNode
    var res [][]int
    if root == nil {
        return res
        }
    heap = append(heap, root)
    for {
        if len(heap) == 0 {
            break
        }
        tmp := heap
        heap = []*TreeNode{}
        var resTmp []int
        for _,node := range tmp {
            resTmp = append(resTmp, node.Val)
            if node.Left != nil {
                heap = append(heap, node.Left)
            }
            if node.Right != nil {
                heap = append(heap, node.Right)
            }
        }
        res = append(res, resTmp)
    }
    return res
}

分行之字打印二叉树

题目：https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

和上题差不多就是个欢乐堆bfs

func zigzagLevelOrder(root *TreeNode) [][]int {
    var res [][]int
    var heap []*TreeNode
    if root == nil {
        return res
    }
    heap = append(heap, root)
    inOrder := true
    for {
        if len(heap) == 0 {
            break
        }
        tmp := heap
        heap = []*TreeNode{}
        var tmpRes []int
        for i:= len(tmp) -1; i>=0; i-- {
            node := tmp[i]
            tmpRes = append(tmpRes, node.Val)
            if inOrder {
                if node.Left != nil {
                    heap = append(heap, node.Left)
                }
                if node.Right != nil {
                    heap = append(heap, node.Right)
                }
            } else {
                if node.Right != nil {
                    heap = append(heap, node.Right)
                }
                if node.Left != nil {
                    heap = append(heap, node.Left)
                }
            }
        }
        inOrder = !inOrder
            res = append(res, tmpRes)

    }
    return res
}

判断二叉搜索树后续遍历合法

（leetcode要钱所以去了牛客）题目：https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?tpId=13&tqId=11176&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

二叉搜索树：根节点内所有左子树值\<root，所有右子树值> root

解法递归本身没什么问题

func VerifySquenceOfBST( sequence []int ) bool {
    if len(sequence) == 0 {
        return false
    }
    // write code here
    var checkRight func(left int, right int) bool
    checkRight = func(left int, right int) bool {
        if left >= right {
            return true
        }
        rootVal := sequence[right]
        var i = right - 1
        for ; i>= left; i-- {
            if sequence[i] < rootVal {
                break
            }
        }
        for j:=left;j<=i;j++ {
            if sequence[j] >= rootVal {
                return false
            }
        }
        return checkRight(left, i) && checkRight(i+1,right-1)
    }
    return checkRight(0,len(sequence) - 1)
}

二叉树中和为某一值的路径

题目：https://leetcode.com/problems/path-sum-ii/

题解：

1. 简单dfs

   func pathSum(root *TreeNode, targetSum int) [][]int {
       var res [][]int
       if root == nil {
           return res
       }
       
       var checkVal func(root *TreeNode, targetSum int, before []int) 
       checkVal = func(root *TreeNode, nowSum int, before []int) {
           nowSum += root.Val 
           before = append(before, root.Val)
           if root.Left == nil && root.Right == nil {
               if nowSum == targetSum {
                   res = append(res, append([]int{}, before...))
               }
               return
           }
           if root.Left != nil {
           checkVal(root.Left, nowSum, before)
           }
           if root.Right != nil {
           checkVal(root.Right, nowSum, before)
           }
       return
       }
       checkVal(root,0,[]int{})
       return res
   }

2. 利用回溯法优化路径存储，只要有一个path就行不需要传参

   func pathSum(root *TreeNode, targetSum int) [][]int {
       var res [][]int
       if root == nil {
           return res
       }
       var path []int
       var checkVal func(root *TreeNode, targetSum int) 
       checkVal = func(root *TreeNode, nowSum int) {
           nowSum += root.Val 
           path = append(path, root.Val)
           if root.Left == nil && root.Right == nil {
               if nowSum == targetSum {
                   res = append(res, append([]int{}, path...))
               }
           } else {
               if root.Left != nil {
                   checkVal(root.Left, nowSum)
               }
               if root.Right != nil {
                   checkVal(root.Right, nowSum)
               }
           }
           path = path[:len(path) - 1]
           return
       }
       checkVal(root,0)
       return res
   }

随机链表的复制

题目：https://leetcode.com/problems/copy-list-with-random-pointer/submissions/1118858301/

解法：

1. 用hash保存已经创建的链表（面试答不出来就用这个方法），空间复杂度是O(n)，时间复杂度O(n)

   func copyRandomList(head *Node) *Node {
       if head == nil {
           return nil
           }
       nodeMap := map[*Node]*Node{}
       cur := &Node{
           Val: head.Val,
       }
       newNode := &Node {
           Next: cur,
       }
       nodeMap[head] = cur
       nodeMap[nil] = nil
       for {
           if head == nil {
               break
           }
   
           if next,ok := nodeMap[head.Next]; ok {
               cur.Next = next
           } else {
               next :=&Node{
                   Val: head.Next.Val,
               }
               nodeMap[head.Next] = next
               cur.Next = next
           }
   
           if rand,ok := nodeMap[head.Random]; ok {
               cur.Random = rand
           } else {
               rad :=&Node{
                   Val: head.Random.Val,
               }
               nodeMap[head.Random] = rad
               cur.Random = rad
           }
   
           cur = cur.Next
           head = head.Next
       }
       return newNode.Next
   }

2. 原地复制链表，从1->2->3 变成 1->1->2->2->3->3*，再去进行random赋值和链表拆分，所以一共有三个循环

   1. 原地复制当前节点，组成复制后链表
   2. 复制后节点的random指向
   3. 拆开两个链表

最后的时间复杂度:O(n)，空间复杂度O(1)

func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }
    newNode := &Node{
        Next:head,
    }
    for {
        if head == nil {
            break
        }
        next := &Node{
            Val:head.Val,
            Next:head.Next,
        }
        head.Next = next
        head = next.Next
    }
    
    head = newNode.Next
    for {
        if head == nil {
            break
        }
        if head.Random != nil {
            head.Next.Random = head.Random.Next
        }
        head = head.Next.Next
    }
    head = newNode.Next  
    newHead := head.Next
    newH := newHead
    for {
        
        head.Next = newHead.Next
        head = head.Next
        if head == nil  {
            break
        }
        newHead.Next = head.Next
        newHead = newHead.Next
    }

    return newH
}

双向链表转二叉搜索树

题目：https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=11179&tPage=2&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking

题解：

1. 用数组存中序遍历的结果，然后再重新组装（空间复杂度O(n)）（不想写了

2. 原地处理数组，我写的方法好像比较复杂一点，不过性能一样

   func Convert( pRootOfTree *TreeNode ) *TreeNode {
       // write code here
       if pRootOfTree == nil {
           return nil
       }
       left := pRootOfTree
       if pRootOfTree.Left != nil {
           left = convLeft(pRootOfTree.Left, pRootOfTree)
       }
       if pRootOfTree.Right != nil {
           convRight(pRootOfTree.Right, pRootOfTree)
       }
       return left
   }
   
   func convLeft( pRootOfTree *TreeNode , before *TreeNode) *TreeNode {
       left := pRootOfTree
       if pRootOfTree.Left != nil {
           left = convLeft(pRootOfTree.Left,pRootOfTree)
       }
       if pRootOfTree.Right != nil {
           right := convRight(pRootOfTree.Right,pRootOfTree)
           before.Left = right
           right.Right = before
       } else {
           before.Left = pRootOfTree
           pRootOfTree.Right = before
       }
       return left
   }
   
   func convRight( pRootOfTree *TreeNode, before *TreeNode ) *TreeNode {
       right := pRootOfTree
       if pRootOfTree.Left != nil {
           left := convLeft(pRootOfTree.Left,pRootOfTree)
           before.Right = left
           left.Left = before
       } else {
           before.Right = pRootOfTree
           pRootOfTree.Left = before
       }
   
       if pRootOfTree.Right != nil {
           right = convRight(pRootOfTree.Right,pRootOfTree)
       }
       return right
   
   }

3. 可以先找到最左的开始节点，再中序遍历就行了，符合中序遍历的核心思想

   func Convert( pRootOfTree *TreeNode ) *TreeNode {
       // write code here
       if pRootOfTree == nil {
           return nil
       }
       var left = pRootOfTree
       for {
           if left.Left == nil {
               break
           } else {
               left = left.Left
           }
       }
       var preNode *TreeNode
       var inOrder func(root *TreeNode)
       inOrder = func(root *TreeNode) {
           if root == nil {
               return
           }
           inOrder(root.Left)
           root.Left = preNode
           if preNode != nil {
               preNode.Right = root
           }
           preNode = root
           inOrder(root.Right)
       }
       inOrder(pRootOfTree)
       return left
   }

序列化二叉树

题目：https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

解法：

1. bfs用堆，按行遍历，只要不是叶子结点并且有null 子项就输出null，反正主打一个不在乎时间空间优化，hard嘛写出来就算胜利

   type Codec struct {
   }
   
   func Constructor() Codec {
       return Codec{}
   }
   
   // Serializes a tree to a single string.
   func (this *Codec) serialize(root *TreeNode) string {
       var resStr string
       isLeaf := this.isLeaf(root)
       var    pops []*TreeNode
   
       pops = append(pops, root)
       for {
           if len(pops) > 0 {
               tmp := pops 
               pops = []*TreeNode{}
               newLeaf := true
               for _,node := range tmp {
                   resStr += ","
                   if node == nil {
                       resStr +=  "nil"
                   } else {
                       resStr +=strconv.Itoa(node.Val)
                       if !isLeaf {
                           pops = append(pops, node.Left)
                           pops = append(pops, node.Right)
                           newLeaf = newLeaf && this.isLeaf(node.Left) && this.isLeaf(node.Right)
                       }
                   }
               }
               isLeaf = newLeaf
           } else {
               break
           }
       }
       return resStr[1:]
   }
   
   func (this *Codec) isLeaf(root *TreeNode) bool {
       return  root == nil || (root.Left == nil && root.Right == nil )
   }
   
   // Deserializes your encoded data to tree.
   func (this *Codec) deserialize(data string) *TreeNode {    
       list := strings.Split(data, ",")
       var    pops []*TreeNode
       var root *TreeNode
       if len(list) == 1 && list[0] == "nil" {
           return root
       }
       val,_ := strconv.Atoi(list[0])
       root = &TreeNode{Val:val}
       pops = append(pops,root)
       i := 1
       l := len(list)
       for {
           if len(pops) > 0 {
               tmp := pops 
               pops = []*TreeNode{}
               for _,node := range tmp {
                   if i < l - 1 {
                       left := list[i]
                       right := list[i+1]
                       i += 2
                       if left != "nil" {
                           leftVal,_ := strconv.Atoi(left)
                           ll := &TreeNode{
                               Val:leftVal,
                           }
                           node.Left = ll
                           pops = append(pops, ll)
                       }
                       if right != "nil" {
                           rightVal,_ := strconv.Atoi(right)
                           rr := &TreeNode{
                               Val:rightVal,
                           }
                           node.Right = rr
                           pops = append(pops, rr)
                       }
                   }
               }
           } else {
               break
           }
       }
       return root
   }

2. 去参观一下题解，感觉核心思路大差不差放弃治疗就这样吧hard嘛，能写出来就不错了

字符串全排列

题目：https://leetcode.com/problems/permutations/description/

解法：

1. 回溯没有什么好说的，但是我写的时候偷懒，是用了设置成11的方式来处理已经使用过的数字，这样的问题是时间复杂度会变成：O(n^n)

   func permute(nums []int) [][]int {
       var res [][]int
       var path []int
       l := len(nums)
       var per func()
       per = func() {
           if len(path) == l {
               res = append(res ,append([]int{}, path...))
           }
           for i,num := range nums {
               if num == 11 {
                   continue
               }
               nums[i] = 11
               path = append(path, num)
               per()
               nums[i] = num
               path = path[:len(path) - 1]
           }
       }
       per()
       return res
   }

2. 如果我每次都把已经处理过的交换到前面，没处理的交换到后面，那时间复杂度就会变成O(n*n!)

   func permute(nums []int) [][]int {
       var res [][]int
       var path []int
       l := len(nums)
       var per func(start int)
       per = func(start int) {
           if len(path) == l {
               res = append(res ,append([]int{}, path...))
           }
           for i:= start; i<l; i++ {
               path = append(path, nums[i])
               nums[i], nums[start] = nums[start],nums[i]
               per(start+1)
               nums[i], nums[start] = nums[start],nums[i]
               path = path[:len(path) - 1]
           }
       }
       per(0)
       return res
   }

3. 直接递归能做么，当然可以有什么不可以的，但是每次都要把新的nums数组作为参数传进去，刚学过call的堆栈调用想想就很可怕

全排列2（有重复元素）

题目：https://leetcode.com/problems/permutations-ii/

有重复元素场景的全排列，如果没记错的话当初我应该是搞了个map嗯

func permuteUnique(nums []int) [][]int {
    var res [][]int
    var path []int
    var per func(start int) 
    l := len(nums)
    per = func(start int) {
        valMap := map[int]bool{}
        if len(path) == l {
            res = append(res, append([]int{}, path...))
        }
        for i:= start; i<l; i++ {
            num := nums[i]
            if _,ok := valMap[num]; ok {
                continue
            }
            valMap[num] = true
            path = append(path, num)
            nums[i], nums[start] = nums[start], nums[i]
            per(start + 1)
            nums[i], nums[start] = nums[start], nums[i]
            path = path[:len(path) - 1]
        }
    }
    per(0)
    return res
}

组合

题目：https://leetcode.com/problems/combinations/description/

顺手就用剪枝+回溯给做了

func combine(n int, k int) [][]int {
    var res [][]int
    var path []int
    var list func(start int)
    list = func(start int) {
        for i:= start; i<=n ; i++ {
            path = append(path, i)
            if len(path) == k {
                res = append(res, append([]int{}, path...))
            } else {
                list(i+1)
            }
            path = path[:len(path) - 1]
        }
    }
    list(1)
    return res
}

数组中出现次数超过一半的数字

题目：https://leetcode.com/problems/majority-element/submissions/1119582289/

解法：

1. 排序，不想写也不是什么最优解，时间复杂度O(nlogn)，空间复杂度O(1)
2. 搞个map计算出现次数，时间复杂度O(n)，空间复杂度O(n)

   func majorityElement(nums []int) int {
       n := len(nums)/2
       numsMap := map[int]int{}
       for _,num := range nums {
           if _,ok := numsMap[num]; !ok {
               numsMap[num] = 0
           }
           numsMap[num]++
           if numsMap[num] > n {
               return num
           }
       }
       return 0
   }

3.摩尔计数法，很有意思的东西，简单来说就是两个王国之间打架，一换一，人数多的那里赢。现在因为有一个数字是过半的，所以不一样的数字就一换一抵消，最后剩下的一定是过半的数字,时间复杂度O(n)，空间复杂度O(1)

func majorityElement(nums []int) int {
    maj := nums[0]
    count := 0
    for _,num := range nums {
        if maj == num {
            count++
        } else if count == 0 {
            maj = num
            count++
        } else {
            count--
        }
    }
    return maj
}

4.分治，把一堆数字分成两部分，则所求的数字一定是这两部分的众数之一，再合并求这堆的众数，时间复杂度O(nlogn)，空间复杂度O(1)

func majorityElement(nums []int) int {
    var  maxCnt =  func(lo int, up int, val int) (count int){
        for i:= lo; i<= up; i++ {
            if nums[i] == val {
                count++
            }
        }
        return
    } 
    var maj func(lo int, up int) int
    maj =  func(lo int, up int) int {
        if lo == up {
            return nums[lo]
        }
        mid := (lo + up) / 2
        left := maj(lo,mid)
        right := maj(mid+1,up)
        if left == right {
            return left
        }
        return map[bool]int{true:left, false:right}[maxCnt(lo,up, left) > maxCnt(lo,up, right)]
    }
    return maj(0,len(nums) - 1)
}

最大的k个数

题目：https://leetcode.com/problems/kth-largest-element-in-an-array/submissions/1119616730/

解法：

1. 最小堆嘛，老朋友了

func findKthLargest(nums []int, k int) int {
    var heap []int
    for _, num := range nums {
        if len(heap) < k {
            heap = append(heap, num)
            construct(&heap, len(heap))
        } else {
            if num < heap[0] {
                continue
            } else {
                heap[0] = num
                update(&heap,1)
            }
        }
    }
    return heap[0]

}

func construct(heap *[]int, n int) {
    if n == 1 {
        return
    }
    val := (*heap)[n-1]
    if n%2 == 1 {
        father := (*heap)[(n-1)/2 - 1]
        if val < father {
             (*heap)[n-1], (*heap)[(n-1)/2 - 1] = (*heap)[(n-1)/2 - 1], (*heap)[n-1]
             n = (n-1)/2
             construct(heap, n)
        }
    } else {
        father := (*heap)[n/2 - 1]
        if val < father {
             (*heap)[n-1], (*heap)[n/2 - 1] = (*heap)[n/2 - 1], (*heap)[n-1]
             n = n/2
             construct(heap, n)
        }
    }
}

func update(heap *[]int, n int) {
    if n*2 > len(*heap) {
        return
    }
    val := (*heap)[n-1]
    leftPos := n*2
    left := (*heap)[n*2 - 1]
    if n*2 < len(*heap) {
        right := (*heap)[n*2]
        if right < left {
            left = right
            leftPos =  n*2 + 1
        }
    }
    if left < val {
        (*heap)[leftPos - 1],(*heap)[n-1] = (*heap)[n-1],(*heap)[leftPos - 1]
        update(heap, leftPos)
    }
    return
}

2. 分治，其实就是快排，只是说如果某次快排的基准点刚好是k，就不用再排下去了，平均时间复杂度O(n)，最坏情况O(n^n)，空间复杂度O(1)（因为用的是快排原地交换的逻辑）

   func findKthLargest(nums []int, k int) int {
       var quickSort func(left,right int)int
       quickSort = func(left,right int) int{
           if left == right {
               return nums[left]
           }
           base := nums[left]
           basePost := left + 1
           for i:= left+1; i<= right; i++ {
               if nums[i] > base {
                   nums[i],nums[basePost] = nums[basePost], nums[i]
                   basePost++
               }
           }
           nums[left],nums[basePost-1] = nums[basePost-1], nums[left]
           if basePost == k {
               return base
           } else if basePost < k {
               return quickSort(basePost, right)
           } else {
               return quickSort(left, basePost-2)
           }
       }
       return quickSort(0,len(nums) - 1)
   }

数据流的中位数

题目：https://leetcode.com/problems/find-median-from-data-stream/

解法：

1. 错误解法：二分法，能做但是时间复杂度太高

type MedianFinder struct {
    val []int
}


func Constructor() MedianFinder {
    return MedianFinder{}
}


func (this *MedianFinder) AddNum(num int)  {
    if len(this.val) == 0 {
        this.val = append(this.val, num)
        return
    }
    left := 0 
    right := len(this.val) - 1
    var pos int
    for {
        if left >= right {
            if this.val[left] >=num {
                pos = left
            } else {
                pos = left+1
            }
            break
        }
        mid := (left + right )/2
        if this.val[mid] <= num {
            left = mid + 1
        } else {
            right = mid
        }
        
    }
    rightNums := append([]int{},this.val[pos:]...)
    this.val = append(this.val[:pos],num)
    this.val = append(this.val, rightNums...)
}


func (this *MedianFinder) FindMedian() float64 {
    ll := len(this.val)
    if ll % 2 == 1 {
        return float64(this.val[ll/2])
    } else {
        return (float64(this.val[ll/2 - 1]) + float64(this.val[ll/2])) / 2
    }
}

2. 用一个最大堆和一个最小堆来维护中位数。很可以理解的解法但是用go得再手写一遍最大堆和最小堆好累啊（以后有心情再说）（前面已经写过一次最小堆了嗯）
3. 用红黑树，嗯红黑树。。。

最大子数组和

题目：https://leetcode.com/problems/maximum-subarray/submissions/1120161253/、

解法：

1. 双指针

   func maxSubArray(nums []int) int {
       var left,right int
       var max,now int
       ll := len(nums)
       now = nums[0]
       max = nums[0]
       right = 1
       for{
           if right < ll {
               if now < 0{
                   for ;left<right; left++ {
                       now -= nums[left]
                   }
               }
               now += nums[right]
               if now > max {
                   max = now
               }
               right++
           } else {
               break
           }
       }
       return max
   }

2. dp，不过我偷懒写了个没有优化空间的方案，其实空间复杂度可以到O(1)
   $$
   sum(i) = max(f(i),sum(i-1)+f(i))
   $$
   $$
   dp(i) = max(dp(i-1), sum(i))
   $$

   func maxSubArray(nums []int) int {
       ll := len(nums)
       merge := make([]int,ll)
       dp := make([]int,ll)
       merge[0] = nums[0]
       dp[0] = nums[0]
       for i:=1;i<ll;i++ {
           merge[i]=merge[i-1] + nums[i]
           if merge[i]<nums[i] {
               merge[i] = nums[i]
           }
           
           dp[i] = dp[i-1]
           
           if merge[i] > dp[i] {
               dp[i] = merge[i]
           }
       }
       return dp[ll-1]
   }

3. 贪心，其实和双指针很相似但是更直接一点（也有效），只要当前和是小于0的就丢弃

   func maxSubArray(nums []int) int {
       curSum := nums[0]
       maxVal := nums[0]
       for i:=1;i<len(nums);i++{
           if curSum < 0 {
               curSum = 0
           }
           curSum += nums[i]
           if curSum > maxVal {
               maxVal = curSum
           }
       }
       return maxVal
   }

1到n整数中1出现的次数

题目：https://leetcode.com/problems/number-of-digit-one/

一开始没有思路后来看了一眼题解，计算每一位出现的次数，豁然开朗

func countDigitOne(n int) int {
    cnt := 0
    cur := 1
    raw := n
    for {
        if n == 0 {
            break
        }
        last := n%10
        n = n/10
        cnt += n * cur
        if last > 1 {
            cnt += cur
        } else if last == 1 {
            cnt += (raw%cur) + 1
        } 
        cur *= 10
    }
    return cnt
}

把数组排成最大的数

题目：https://leetcode.com/problems/largest-number/

题解：

1. 一开始想的是遍历两次，按照int(a+b)>int(b+a)的顺序排起来

   func largestNumber(nums []int) string {
       var res []string
       for k,num := range nums {
           cur := strconv.Itoa(num)
           for i,val := range res {
               if compare(cur,val) {
                   last := append([]string{}, res[i:]...)
                   res = append(res[:i], cur)
                   res = append(res, last...)
                   break
               }
           }
           if len(res) == k {
               res = append(res,cur)
           }
       }
       if res[0] == "0" {
           return "0"
       }
       return strings.Join(res,"")
   }
   
   func compare(a,b string) bool {
       left,_ := strconv.Atoi(a+b)
       right,_:= strconv.Atoi(b+a)
       return left > right
   }

然后发现自己只是写了个很拙劣的插入排序，其实核心是compare函数，这题本质是个排序，对所有算法都适用的

2. 用go提供的slice排序来处理，好像是个快排，待排序数组为s:

   sort.Slice(s,func(i,j int)bool {
       return s[i] < s[j]
   })

在这题的逻辑就是：

sort.Slice(s,func(i,j int)bool {
    left,_ := strconv.Atoi(s[i]+s[j])
    right,_:= strconv.Atoi(s[j]+s[i])
    return left > right
})

简化一点其实可以直接用字典排序：

sort.Slice(s,func(i,j int)bool {
    if s[i][0] == s[j][0] {
        return s[i] + s[j] > s[j] + s[i]
    } else {
        return s[i] > s[j]
    }
})

最后：

func largestNumber(nums []int) string {
    var res []string
    for _,num := range nums {
        res = append(res, strconv.Itoa(num))
    }
    sort.Slice(res, func(i,j int) bool {
        if res[i][0] == res[j][0] {
            return res[i] + res[j] > res[j] + res[i]
        } else {
            return res[i] > res[j]
        }
    })
    if res[0] == "0" {
        return "0"
    }
    return strings.Join(res,"")
}

把数字翻译成字符串个数

题目：https://leetcode.com/problems/decode-ways/submissions/1122667338/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china

怎么看都是一道dp题，不过关于0和>27的场景有很多判断条件，一定要理清楚再写

func numDecodings(s string) int {
    if s[0] == '0' {
        return 0
    }
    start := 0
    before := 1
    now := 1
    ll := len(s)
    
    for i:= 1; i<ll; i++ {
        tmp := start
        start = before
        before = now
        if s[i] == '0' {
            if s[i-1]  == '0' || s[i-1:i+1] > "27"{
                return 0
            } else {
                now = start
            }
            continue
        } else if s[i-1] == '0' {
            now = tmp

        } else if s[i-1:i+1] < "27" {
            now += start
        } else {
            now = before
        }
    } 
    return now
}

最短路径和

题目：https://leetcode.com/problems/minimum-path-sum/submissions/

熟悉的dp again，应该说是最经典的dp之一
我这里偷了判断的懒，加了个初始化，其实用 if i == 0 j == 0也没啥问题

func minPathSum(grid [][]int) int {
    xlen := len(grid)
    ylen := len(grid[0])
    beforeRow := make([]int, ylen+1)
    for j,row := range grid[0] {
        beforeRow[j+1] = beforeRow[j]+row
    }
    beforeRow[0] = beforeRow[ylen]

    for i:=1; i<xlen; i++ {
        for j,val := range grid[i] {
            beforeRow[j+1] = min(beforeRow[j], beforeRow[j+1]) + val 
        }
        beforeRow[0] = beforeRow[ylen]
    }
    return beforeRow[ylen]
}

无重复字符最短字串

题目：https://leetcode.com/problems/longest-substring-without-repeating-characters/

滑动窗口嘛，常用办法是双指针，右指针代表当前字母，左指针代表子字符串开头，两个循环

这里用空间换了点时间，用map存当前字符串的最近一个位置

func lengthOfLongestSubstring(s string) int {
    posMap := make(map[rune]int, 26)
    var max,preLen int
    for i,d := range s {
        if pos,ok := posMap[d]; ok && i-preLen <= pos{
            preLen = i - pos
        } else {
            preLen++
            if max < preLen {
                max = preLen
            }
        }
        posMap[d] = i
    }
    return max
}

丑数

题目：https://leetcode.com/problems/ugly-number-ii/

方案

1. 不想写，但是可以堆排+hash去重

2. 当 2≤i≤n2 \le i \le n2≤i≤n 时，令dp[i]=min⁡(dp[p2]×2,dp[p3]×3,dp[p5]×5)\textit{dp}[i]=\min(\textit{dp}[p_2] \times 2, \textit{dp}[p_3] \times 3, \textit{dp}[p_5] \times 5)dp[i]=min(dp[p2]×2,dp[p3]×3,dp[p5]×5)，然后分别比较 dp[i]\textit{dp}[i]dp[i] 和 dp[p2]×2,dp[p3]×3,dp[p5]×5\textit{dp}[p_2] \times 2,\textit{dp}[p_3] \times 3,\textit{dp}[p_5] \times 5dp[p2]×2,dp[p3]×3,dp[p5]×5 是否相等，如果相等则将对应的指针加 111。

   func nthUglyNumber(n int) int {
       var p2,p3,p5 int
       uglyList := make([]int, n)
       uglyList[0] = 1
       for i:=1; i<n; i++ {
           var p *int
           var val int
           for {
               v2 := uglyList[p2] * 2
               v3 := uglyList[p3] * 3
               v5 := uglyList[p5] * 5
               if v2 < v3 {
                   p = &p2
                   val = v2
               } else {
                   p = &p3
                   val = v3
               }
               if val > v5 {
                   p = &p5
                   val = v5
               }
               *p += 1
               if val != uglyList[i-1] {
                   break
               }
           }
           uglyList[i] = val
       }
       return uglyList[n-1]
   }

字符串中第一个只出现一次的字符

题目：https://leetcode.com/problems/first-unique-character-in-a-string/description/

解法：

1. 可以用hash保存次数，再遍历一次返回次数大于一的
2. 用hash改成用26字母数组，保存是否为单数/是单数的位置，空间复杂度O(1)，时间复杂度O(n)

func firstUniqChar(s string) int {
    count := make([]int, 26)
    ll := len(s)+1
    for i,val := range s {
        if count[val-'a'] > 0 {
            count[val-'a'] = ll
        } else {
            count[val-'a'] = i+1
        }
        
    }
    min := ll
    for _,val := range count {
        if val != ll && val != 0 {
            if min > val {
                min = val
            }
        }
    }
    if min == ll {
        return -1
    } else {
        return min-1
    }
}

字符流中第一个不重复的字符

题目：https://www.nowcoder.com/practice/00de97733b8e4f97a3fb5c680ee10720?tpId=13&&tqId=11207&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

解法：

1. 干了一件很神奇的事情，搞了两个数组，一模一样大，第一个存第一次出现的byte，第二个存第二次出现的byte，虽然性能肯定不是最好的但是还挺好玩

   var pops []byte
   var pops2 []byte
   
   func Insert(ch byte) {
       ll := len(pops)
       var flag bool
   	for i:=0; i<ll; i++ {
           val := pops[i]
           if val == ch{ 
               flag = true
               pops2[i] = ch 
               break
           }
       }
       if !flag {
           pops = append(pops, ch)
           pops2 = append(pops2, byte(0))
       }
   }
   
   func FirstAppearingOnce() byte {
       ll := len(pops)
   	for i:=0; i<ll; i++ {
           if pops[i] != pops2[i] {
               return pops[i]
           }
       }
       return '#'
   }

2. 第一个优化是用map保存地址，在插入的时候就不需要遍历，节约时间。第二个是获取的时候遍历数组而不是map

   var pops []byte
   var posMap = map[byte]int{}
   
   func Insert(ch byte) {
   	if _,ok := posMap[ch]; !ok {
           posMap[ch] = len(pops)
           pops = append(pops, ch)
       } else {
           posMap[ch] = -1
       }
   }
   
   func FirstAppearingOnce() byte {
   	for _,b := range pops {
           if posMap[b] != -1 {
               return b
           }
       }
       return '#'   
   }

逆序对

题目：https://leetcode.com/problems/reverse-pairs/
理论上也是老朋友了但是不影响写起来好陌生
用的是分治的思路，先算出每个子数组里面的逆序对数，同时排序，因为归并的求逆序对数和排序需要两次O(n)，最后的时间复杂度就是O(nlogn)

func reversePairs(nums []int) int {
    var num int
    var  mergeSort func(nums []int) []int
    mergeSort = func(nums []int) []int {
        ll := len(nums)
        if ll == 1 {
            return nums
        }
        mid := ll/2
        rightl := ll - mid
        left := mergeSort(nums[:mid])
        right := mergeSort(nums[mid:])
        res := make([]int, ll)
        var righti,lefti int
        for  {
            if lefti >= mid || righti >= rightl {
                break
            }
            if left[lefti] > right[righti] * 2 {
                num += mid - lefti
                righti++
            } else {
                lefti++
            }
        }
        lefti = 0
        righti = 0
        i := 0
        for {
            if lefti >= mid || righti >= rightl {
                break
            }
            if left[lefti] > right[righti] {
                res[i] = right[righti]
                righti++
            } else {
                res[i] = left[lefti]
                lefti++
            }
            i++
        }
        if lefti < mid {
            for ; lefti <mid; lefti++ {
                res[i] = left[lefti]
                i++
            }
        } else if righti < rightl {
            for ; righti <rightl; righti++ {
                res[i] = right[righti]
                i++
            }
        }
        return res
    }
    mergeSort(nums)
    return num
    
}

相交链表

题目：https://leetcode.com/problems/intersection-of-two-linked-lists/
解法1: 用哈希记录已经访问节点

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    seenHash := map[*ListNode]bool{}
    aHead := headA
    for {
        if aHead != nil {
            seenHash[aHead] = true
            aHead = aHead.Next
        }else {
            break
        }
    }
    for {
        if headB == nil {
            return nil
        }
        if _,ok := seenHash[headB]; ok {
            return headB
        } else {
            headB = headB.Next
        }
    }
    return nil
}

解法2: 核心思路是消除长度差，不过我的脑回路比较简单，就是先算出两个链表的长度差，再抹平，再遍历

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    aHead := headA
    bHead := headB
    var aTimes,bTimes int
    for {
        aTimes++
        if aHead.Next == nil {
            break
        }
        aHead = aHead.Next
        
    }
    for {
        bTimes++
        if bHead.Next == nil {
            break
        }
        bHead = bHead.Next
        
    }
    if aHead != bHead {
        return nil
    }
    var left int
    if aTimes > bTimes {
        t := aTimes - bTimes
        left = bTimes
        for i:=0;i<t;i++ {
            headA = headA.Next
        }
    } else {
        t := bTimes - aTimes
        left = bTimes
        for i:=0;i<t;i++ {
            headB = headB.Next
        }
    }

    for i:=0; i<left; i++{
        if headA == headB {
            return headA
        }
        headA = headA.Next
        headB = headB.Next
    }
    return nil
}

解法3:本质还是抹平长度差，但是解法讨巧很多，当A结尾后指向B，当B结尾后指向A，相当于两个链表各循环了一次，天然抹平了长度差

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    aHead := headA
    bHead := headB
    for {
        if aHead == bHead {
            return aHead
        }

        if aHead == nil {
            aHead = headB
        } else {
            aHead = aHead.Next
        }
        if bHead == nil {
            bHead = headA
        } else {
            bHead = bHead.Next
        }
        
    }
    return nil
}

排序数组中数字的开始和结束节点

题目：https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

核心肯定是二分法

解法1:二分法，分别查找上界和下界，两次查找O(logn)，可以关注一下找上界和下界的边界处理方式

func searchRange(nums []int, target int) []int {
    res := make([]int,2)
    ll := len(nums) - 1
    start := 0 
    end := ll
    for {
        if start > end {
            break
        }
        mid := start + (end - start)/2
        if nums[mid] >= target {
            end = mid - 1
        } else {
            start = mid + 1
        }
    }

    if start > ll || nums[start] != target {
        return []int{-1,-1}
    }
    res[0] = start
    end = ll
    for {
        if start > end {
            break
        }
        mid := start + (end - start)/2
        if nums[mid] <= target {
            start = mid + 1
        } else {
            end = mid - 1
        }
    }
    res[1] = end
    return res
}

解法2: 只用一个上界/下界的函数，比如找上界，那就是分别找target和target - 1的上界，主要的好处是只用了一个函数

func searchRange(nums []int, target int) []int {
    ll := len(nums) - 1
    low := upper(nums, target - 1)
    if low >= ll || nums[low+1] != target {
        return []int{-1,-1}
    }
    high := upper(nums, target)
    return []int{low+1, high}
}

func upper(nums []int, target int) int{
    start := 0
    end := len(nums) - 1
    for {
        if start > end {
            break
        }
        mid := start + (end - start) / 2
        if nums[mid] <= target {
            start = mid + 1
        } else {
            end = mid - 1
        }
    }
    return end
}

求缺失数字

题目：https://leetcode.com/problems/missing-number/

求从0开始的一个数组中缺少的那个数字，用异或做就行

func missingNumber(nums []int) int {
    ll := len(nums)
    res := ll
    for i:=0; i<ll; i++ {
        res ^= i 
        res ^= nums[i]
    }
    return res
}

二叉搜索树第k大的值

题目：https://leetcode.com/problems/kth-smallest-element-in-a-bst/

很显然也很典型的中序遍历：

func kthSmallest(root *TreeNode, k int) int {
    var res int
    var midTraversal func(root *TreeNode) 
    midTraversal = func(root *TreeNode){
        if root == nil {
            return
        }
        midTraversal(root.Left)
        k -= 1
        if k == 0 {
            res = root.Val
            return
        }
        midTraversal(root.Right)
    }
    midTraversal(root)
    return res
}

看到了一种很骚的利用go管道的做法

func kthSmallest(root *TreeNode, k int) int {
    c := make(chan int)
    go midTraversal(root,c)
    for i:=0;i<k-1;i++ {
        <-c
    }
    return <-c
}
func midTraversal (root *TreeNode, c chan int){
    if root == nil {
        return
    }
    midTraversal(root.Left,c)
    c <- root.Val
    midTraversal(root.Right,c)
}

也就是每次遍历写了值就会直接被取出，直到写入第k个的时候函数返回。

会不会出现内存泄漏？

我理解应该是会的，因为通道的存活时长和程序是一样的，也就是只有在main函数执行结束程序退出才会销毁，所以oj还比较简单，毕竟只有这么点自测用力，如果是个后台服务就原地表演一个g了

二叉树深度

题目：https://leetcode.com/problems/maximum-depth-of-binary-tree/solutions/2817503/golang-solution/

一个dfs或者bfs，好像也翻不出什么花来，写个dfs的

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := maxDepth(root.Left)
    right := maxDepth(root.Right)
    if left > right {
        return left + 1
    }else {
        return right + 1
    }
}

bfs本来是不想写的，但是看到了一个list包，是一个go的链表的包，也可以用来当成队列处理，这样以后写队列会顺手很多，不用把数组复制来复制去的

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    queue := list.New()
    var level int
    queue.PushBack(root)
    for queue.Len() > 0{
        ll := queue.Len()
        for i:=0; i<ll; i++ {
            e := queue.Front()
            queue.Remove(e)
            node := e.Value.(*TreeNode)
            if node.Left != nil {
                queue.PushBack(node.Left)
            }
            if node.Right != nil {
                queue.PushBack(node.Right)
            }
        }
        level++
    }
    return level
}

判断平衡树

题目：https://leetcode.com/problems/balanced-binary-tree/

题解：好像也没啥好说的就是个dfs

func isBalanced(root *TreeNode) bool {
    isB := true
    var checkHeight func(root *TreeNode) int
    checkHeight = func(root *TreeNode) int {
        if root == nil {
            return 0
        }
        ll := checkHeight(root.Left)
        rr := checkHeight(root.Right)
        if ll - rr > 1 || ll - rr < -1 {
            isB = false
        }
        if ll < rr {
            return rr + 1
        } else {
            return ll + 1
        }
    }
    checkHeight(root)
    return isB
}

数组中只出现一次的两个数字

题目：https://leetcode.com/problems/single-number-iii/

题解：

这题题解还挺有意思的，这题和136唯一不同就是此题有两个出现了一次的数, 所以我们按照136题类似的遍历一遍数组然后得到所有数字异或结果是待求两个数(设为res1和res2)的异或结果res1^res2, 所以我们不能直接这样做. 既然同时存在两个只出现过一次的数, 那么如果我们将数组分成两部分且这两部分数组分别包含了res1和res2, 然后再采用136完全一样的思路不就解决了吗。

所以问题转换成如何将数组分成两个部分且这两部分分别包含res1和res2. 还是利用位操作, 我们可以根据res1和res2不同的某一位来划分数组, 例如若二者第3位分别为0和1, 那么我们就根据”第三位为0还是为1”来划分数组. 我们不妨取二者不同位的最低(即最右)的那位, 即二者异或结果res1^res2最低位的1. 设res=res1^res2, 那么res&(-res)即res最低位的1。

func singleNumber(nums []int) []int {
    var res int
    for _,val := range nums {
        res ^= val
    }
    bitNum := res & (-res)
    var res1,res2 int
    for _,val := range nums {
        if val & bitNum > 0 {
            res1 ^= val
        } else {
            res2 ^= val
        }
    }
    return []int{res1,res2}
}

数组中唯一只出现一次的数字

题目：https://leetcode.com/problems/single-number-ii/

这题最简单粗暴的方式就是搞一个map，存每个数字出现的次数，出现次数为1的就是返回值

func singleNumber(nums []int) int {
    mapNum := map[int]int{}
    for _,num := range nums {
        mapNum[num]++
    }
    for k,v := range mapNum{
        if v > 1 {
            continue
        } else {
            return k
        }
    }
    return 0
}

但是这样要占用的空间确实也很大,所以按照前面的不重复数字解法来看，这题用到的应该也是位运算。一个数一共32位，计算每位1出现的次数，最后总数mod3，余下的就是唯一的单数个数字在这位的位数了。思路很简单～但是写的时候要看一下得用int32

func singleNumber(nums []int) int {
    var res int32
    for i:=0;i<32;i++ {
        var val int
        for _,num := range nums {
            val += (num>>i) & 1
        }
        cnt := val%3
        res |= int32(cnt<<i)
    }
    return int(res)
}

还有一种数电思路，但是说实话数电那个时候都拿来学法语课了。。。

和为s的两个数字

题目：https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/solutions/3267180/c-go-two-approaches/

解法：标准的双指针

func twoSum(numbers []int, target int) []int {
    rr := len(numbers) - 1
    ll := 0
    for ll < rr {
        sum := numbers[ll] + numbers[rr]
        if sum == target {
            return []int{ll+1,rr+1}
        } else if sum > target {
            rr--
        } else {
            ll++
        }
    }
    return []int{-1,-1}
}

和为s的连续正整数序列

题目：https://leetcode.com/problems/consecutive-numbers-sum/solutions/4416081/golang-solution-clean-code-easy-to-understand/

这题本质是个数学题，写个等差数列求和公式放在这里：
$$
\sum^y_{i=x,n=k} x= k(x+y)/2
$$

func consecutiveNumbersSum(n int) int {
    cnt := 1
    i := 2
    for isConsecutive(i,n){
        mid := n/i
        if i%2 == 1 && i*mid == n  {
            fmt.Printf("i:%d,mid:%d",i,mid)
            cnt++
        } else if i%2 == 0 && i*(mid*2+1) == 2 * n {
            fmt.Printf("i:%d,mid:%d",i,mid)
            cnt++
        }
        i++
    }
    return cnt
}

func isConsecutive(i,k int) bool {
    if i * (i+1) <= 2*k {
        return true
    } else {
        return false
    }
}

翻转单词顺序

题目：https://leetcode.com/problems/reverse-words-in-a-string/

一开始用了暴力求解，遍历扫一遍字符串，把每个单词放进栈里，最后再出栈。这个思路是没有问题的，但是首先要多余的空间复杂度，其次要多次遍历

func reverseWords(s string) string {
    var stack [][]byte
    var res string
    i:=0
    ll:=len(s)
    var tmpStr []byte
    for i<ll{
        if s[i] == ' ' {
            if len(tmpStr) > 0{
                stack = append(stack, tmpStr)
                tmpStr = []byte{}
            }
        } else {
            tmpStr = append(tmpStr,s[i])
        }
        i++
    }
    if len(tmpStr) > 0{
        stack = append(stack, tmpStr)
    }
    for j:= len(stack) - 1; j>=0;j-- {
        res += string(stack[j])
        res += " "
    }
    return strings.TrimRight(res, " ")
}

后面改成了双指针，从后往前

func reverseWords(s string) string {
    rr := len(s) - 1
    ll := rr
    var res []byte
    for rr >=0 {
        for rr >= 0 && s[rr] == ' ' {
            rr--
            ll--
        }
        
        for ll>=0 && s[ll] != ' ' {
            ll--
        }
        res = append(res, s[ll+1:rr+1]...)
        res = append(res, ' ')
        rr = ll
        ll = rr
    }
    return strings.TrimRight(string(res), " ")
}