数组

T14. 除自身以外数组的乘积

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

如果是遍历每个数，令每个数在每个位置上相乘，则时间复杂度为 $O(n^2)$，不满足题意

使用 lmul 和 rmul 记录：当前这个数左侧所有数的乘积与当前这个数右侧所有数的乘积，就能使用 lmul[i]*rmul[i] 得到对应位置的乘积

func productExceptSelf(nums []int) []int {
    n := len(nums)
    lmul, rmul := make([]int, n), make([]int, n)
    lmul[0], rmul[n-1] = 1, 1
    for i := 1; i < n; i++ {
       lmul[i] = lmul[i-1] * nums[i-1]
    }
    for i := n - 2; i >= 0; i-- {
       rmul[i] = rmul[i+1] * nums[i+1]
    }
    ret := make([]int, n)
    for i := 0; i < n; i++ {
       ret[i] = lmul[i] * rmul[i]
    }
    return ret
}

T16. 乘积最大子数组

Given an integer array nums, find a subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

  • f[i]
    • 表示以第 $i$ 个元素为结尾，得到的子数组的所有组合
    • 乘积 max
  • 计算：选取前一段加上自己，或者以自己为新的子数组
    • 如果当前位置是负数，希望以它前一个位置为结尾的某段子数组的积，也能为负数，且绝对值尽可能得大（即数值尽可能小）
    • 如果当前位置为正数，则希望以它前一个位置为结尾的某段子数组的积，也能为正数，且尽可能得大
    • 所以维护两个数组 fmax 和 fmin（但是只需要上一个位置的数据，可以优化为只使用一个变量记录）
func maxProduct(nums []int) int {
    ret := nums[0]
    // 维护positive最大，negative最小
    positive, negative := max(0, nums[0]), min(0, nums[0])
    for i := 1; i < len(nums); i++ {
       cur := nums[i]
       if cur < 0 {
          // 交换正负
          positive, negative = max(cur, cur*negative), min(cur, cur*positive)
       } else {
          // 不用交换，直接选取最优
          positive, negative = max(cur, cur*positive), min(cur, cur*negative)
       }
       ret = max(ret, positive)
    }
    return ret
}

T23. 回文子串

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

中心扩展：选取中心点，使用两个指针向两侧扩展，判断是否仍然为回文串

需要考虑中心长度为 1 或长度为 2，对应奇数长度的回文串和偶数长度的回文串

func countSubstrings(s string) int {
    n, ret := len(s), 0

    // 判断奇数长度
    for i := 0; i < n; i++ {
       for l, r := i, i; l >= 0 && r < n; l, r = l-1, r+1 {
          if s[l] == s[r] {
             ret++
          } else {
             break
          }
       }
    }

    // 判断偶数长度
    for i := 0; i < n-1; i++ {
       for l, r := i, i+1; l >= 0 && r < n; l, r = l-1, r+1 {
          if s[l] == s[r] {
             ret++
          } else {
             break
          }
       }
    }
    return ret
}

T29. 找到所有数组中消失的数字

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

do it without extra space and in O(n) runtime

  1. 哈希表映射，但是需要 $O(n)$ 的空间复杂度
  2. 鸽笼原理：当数 $x$ 出现时，对 nums[x-1] 进行标记

标记方式有 2 种：

  1. +n，这样子可以通过取模 %n 来恢复数字，但是要注意溢出问题
  2. 转为负数，可以不改变数组信息，通过正负号来判断元素是否出现过，要注意出现大于 2 次的情况，应该是要取绝对值的负数：nums[x-1] = -abs(nums[abs(x)-1])
func abs(x int) int {
    if x >= 0 {
       return x
    }
    return -x
}

func findDisappearedNumbers(nums []int) []int {
    n := len(nums)
    for _, x := range nums {
       t := abs(x) - 1
       if nums[t] < 0 {
          continue
       }
       nums[t] = -nums[t]
    }

    ret := make([]int, 0)
    for i := 0; i < n; i++ {
       if nums[i] > 0 {
          ret = append(ret, i+1)
       }
    }
    return ret
}

T30. 找到字符串中所有字符的异位词

Given two strings s and p, return an array of all the start indices of p‘s anagrams in s. You may return the answer in any order.

滑动窗口。比较统计数组是否一致即可

func findAnagrams(s string, p string) []int {
    ret := make([]int, 0)
    n, m := len(s), len(p)
    if n < m {
       return ret
    }

    var ms, mp [26]int
    for i := 0; i < m; i++ {
       ms[s[i]-'a']++
       mp[p[i]-'a']++
    }
    if ms == mp {
       ret = append(ret, 0)
    }

    for i := m; i < n; i++ {
       ms[s[i]-'a']++
       ms[s[i-m]-'a']--
       if ms == mp {
          ret = append(ret, i-m+1)
       }
    }
    return ret
}

T33. 根据身高重建队列

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

因为身高低的人无论怎么移动，都不会影响高的人的 k，所以先按照身高从小到大排序，再从身高高的开始调整，每次就只会影响一个变量，相当于降维处理

链表

T1. 相交链表

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

只有当链表 headA 和 headB 都不为空时，两个链表才可能相交。因此首先判断链表 headA 和 headB 是否为空，如果其中至少有一个链表为空，则两个链表一定不相交，返回 null。

当链表 headA 和 headB 都不为空时，创建两个指针 pA 和 pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下：

  • 每步操作需要同时更新指针 pA 和 pB。
  • 如果指针 pA 不为空，则将指针 pA 移到下一个节点；如果指针 pB 不为空，则将指针 pB 移到下一个节点。
  • 如果指针 pA 为空，则将指针 pA 移到链表 headB 的头节点；如果指针 pB 为空，则将指针 pB 移到链表 headA 的头节点。
  • 当指针 pA 和 pB 指向同一个节点或者都为空时，返回它们指向的节点或者 null。
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    p1, p2 := headA, headB
    for p1 != p2 {
        if p1 == nil {
            p1 = headB
        } else {
            p1 = p1.Next
        }
        if p2 == nil {
            p2 = headA
        } else {
            p2 = p2.Next
        }
    }
    return p1
}

T3. 回文链表

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

  1. 直接遍历链表，将元素提取到数组中再判断回文
  2. 快慢指针，慢指针遍历到中间结点，快指针遍历到末尾结点，反转一半链表，然后遍历两条链表判断是否相同 3. 从工程角度来说要恢复这个链表，但从做题角度直接返回结果就好
func isPalindrome(head *ListNode) bool {
    slow, fast := head, head.Next
    // 快指针走到 nil 时停止: 奇数个节点
    // 快指针走到最后一个节点停止: 偶数个节点
    for fast != nil && fast.Next != nil {
        // 慢指针一次走一步
        slow = slow.Next
        // 快指针一次走两步
        fast = fast.Next.Next
    }
    // 将链表以 slow 为分界线，将 slow 之后的进行反转
    l1 := head
    l2 := reverseList(slow.Next)
    // l2 长度小于等于 l1，但是最多只会少 1 个中间字符，不影响结果
    for l2 != nil {
        if l1.Val != l2.Val {
            return false
        }
        l1 = l1.Next
        l2 = l2.Next
    }
    return true
}

// 反转链表
func reverseList(head *ListNode) *ListNode {
    var prev *ListNode = nil
    cur := head
    for cur != nil {
        next := cur.Next
        cur.Next = prev
        prev = cur
        cur = next
    }
    // 如果 head == nil，返回的也是 nil
    return prev
}

T10. 反转链表

Given the head of a singly linked list, reverse the list, and return the reversed list.

顺序反转

  1. 设 3 个结点：prev / cur / next，整体向后移动
  2. next = cur.Next
  3. cur.Next = prev
  4. prev = cur
  5. cur = next
func reverseList(head *ListNode) *ListNode {
    var prev, cur, next *ListNode = nil, head, nil
    for cur != nil {
        next = cur.Next
        cur.Next = prev
        prev = cur
        cur = next
    }
    return prev
}

递归反转

假设链表为：

$$
n_{1} \rightarrow \dots \rightarrow n_{k} \rightarrow n_{k+1} \rightarrow \dots \rightarrow n_{m}
$$

若从结点 $n_{k+1}$ 到 $n_{m}$ 已经被反转，当前处于 $n_{k}$

$$
n_{1} \rightarrow \dots \rightarrow n_{k} \rightarrow n_{k+1} \leftarrow \dots \leftarrow n_{m}
$$

希望 $n_{k+1}$ 的下一个节点指向 $n_{k}$

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
}

T18. LRU 缓存

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:

  • LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
  • int get(int key) Return the value of the key if the key exists, otherwise return -1.
  • void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

哈希表+双向链表

  • 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的
    • 用一个伪头部（dummy head）和伪尾部（dummy tail）标记界限
  • 哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置

对于 get 操作，首先判断 key 是否存在：

  • 如果 key 不存在，则返回 −1；
  • 如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。
    对于 put 操作，首先判断 key 是否存在：
  • 如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；
  • 如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。
type Node struct {
    key, val   int
    prev, next *Node
}

type LRUCache struct {
    set            map[int]*Node
    head, tail     *Node
    capacity, size int
}

func initNode(key, val int) *Node {
    return &Node{key, val, nil, nil}
}

func Constructor(capacity int) LRUCache {
    // 注意只是双向链表，不是环
    head, tail := initNode(0, 0), initNode(0, 0)
    head.next, tail.prev = tail, head
    return LRUCache{
       set:      make(map[int]*Node, capacity),
       head:     head,
       tail:     tail,
       capacity: capacity,
    }
}

func (t *LRUCache) addToHead(node *Node) {
    node.next = t.head.next
    node.prev = t.head
    t.head.next.prev = node
    t.head.next = node
}

func (t *LRUCache) removeNode(node *Node) {
    node.next.prev = node.prev
    node.prev.next = node.next
}

func (t *LRUCache) moveToHead(node *Node) {
    // 摘除
    t.removeNode(node)
    // 塞入
    t.addToHead(node)
}

func (t *LRUCache) removeFromTail() (key int) {
    rmv := t.tail.prev
    t.removeNode(rmv)
    return rmv.key
}

func (t *LRUCache) Get(key int) int {
    if node, ok := t.set[key]; ok {
       // 元素存在，移动到链表头部
       t.moveToHead(node)
       return node.val
    }
    return -1
}

func (t *LRUCache) Put(key int, value int) {
    if node, ok := t.set[key]; ok {
       // update
       node.val = value
       t.moveToHead(node)
       return
    }

    // insert
    ist := initNode(key, value)
    t.addToHead(ist)
    t.set[key] = ist
    t.size++
    if t.size > t.capacity {
       rmv := t.removeFromTail()
       delete(t.set, rmv)
       t.size--
    }
}

T19. 环形链表 II

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle.

Note that pos is not passed as a parameter.

Do not modify the linked list.

  1. 哈希表，存储遍历过的指针即可
  2. 快慢指针

判断是否有环

  1. 使用双指针，快指针以快的速度移动（两个结点），慢指针以慢的速度移动（一个结点），如果快慢指针相遇，则存在环（因为快指针陷入环里了）
  2. 有环则一定相遇证明：两个指针都进入环中时，相当于快指针以一个结点每步的速度追逐慢指针，两者距离是逐个结点递减的，所以必定会相遇

寻找入口

  1. 假设在环中两个指针相遇了，设头结点到入口结点距离为 x ​，入口结点到相遇结点距离为 y ​，相遇结点沿着环再回到入口结点距离为 z ​
  2. 根据快指针每次走 2 步，慢指针每次走 1 步，可以得到：
    • ​ slow = x + y ​ 慢指针一定在第一圈就会被快指针追上
    • fast = x + y + n * (y + z) ​ n 为快指针转的圈数
    • 2 * slow = fast ​

=> x = n * (y + z) - y ​ (n >= 1) 因为是快指针追逐慢指针的过程，所以快指针一定在环中转至少一圈

=> x = (n - 1) * (y + z) + z ​

即头结点到入口的距离，就是 (n - 1) 个环的长度 + 相遇结点回到入口结点的距离：从相遇点出发，沿环走 z 步，再绕 n-1 圈，能到达环入口；同时取一个新节点从 head 出发，也走同样的步数，也恰好能到达环入口（和另一节点重合）

所以两个节点同时减去绕环走的部分，即只需要第一次相遇，就是环的入口！

func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
       slow = slow.Next
       fast = fast.Next.Next
       // 相遇
       if slow == fast {
          // 一个节点从head开始
          // 另一个节点从相遇点开始
          x, z := head, slow
          // 两者相交处即为环入口
          for x != z {
             x = x.Next
             z = z.Next
          }
          return x
       }
    }
    return nil
}

T20. 环形链表

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

上一题的子问题，双指针判断即可

func hasCycle(head *ListNode) bool {
    if head == nil {
        return false
    }
    slow, fast := head, head
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}

哈希表

T24. 最长连续序列

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

  1. 排序
  2. 哈希表：想办法不重复遍历：遍历元素时，判断 num-1 是否存在，如果存在，则说明当前元素为“中间元素”，需要遍历的只有“开始元素”，即每一段连续序列的最小值。
func longestConsecutive(nums []int) int {
    if len(nums) <= 1 {
       return len(nums)
    }
    // set
    set := make(map[int]struct{})
    for _, num := range nums {
       set[num] = struct{}{}
    }

    maxLen := 1
    for num, _ := range set {
       // 如果num-1存在，说明不是起点，跳过
       if _, ok := set[num-1]; ok {
          continue
       }
       curNum, curLen := num+1, 1
       for _, ok := set[curNum]; ok; _, ok = set[curNum] {
          curLen++
          curNum++
       }
       maxLen = max(maxLen, curLen)

    }
    return maxLen
}

栈

T4. 每日温度

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

  1. 维护一个单调递减栈，从后往前遍历 temperatures，对比 top 和 temperatures[i]
type Pair struct {
    Val int
    Idx int
}

// StackPair 栈
type StackPair struct {
    arr  []*Pair
    size int
}

func NewStackPair() *StackPair {
    return &StackPair{
       arr:  []*Pair{},
       size: 0,
    }
}

func (ms *StackPair) Push(v *Pair) {
    ms.arr = append(ms.arr, v)
    ms.size++
}

func (ms *StackPair) Pop() *Pair {
    if ms.size == 0 {
       return nil
    }
    ret := ms.arr[ms.size-1]
    ms.arr = ms.arr[:ms.size-1]
    ms.size--
    return ret
}

func (ms *StackPair) Size() int {
    return ms.size
}

func (ms *StackPair) Top() *Pair {
    if ms.size == 0 {
       return nil
    }
    return ms.arr[ms.size-1]
}

func dailyTemperatures(temperatures []int) []int {
    // 维护栈单调递减
    stack := NewStackPair()
    ret := make([]int, len(temperatures))
    for i := len(temperatures) - 1; i >= 0; i-- {
       for top := stack.Top(); top != nil; top = stack.Top() {
          if top.Val > temperatures[i] {
             ret[i] = top.Idx - i
             break
          } else {
             stack.Pop()
          }
       }
       if stack.Size() == 0 {
          ret[i] = 0
       }
       stack.Push(&Pair{
          Val: temperatures[i],
          Idx: i,
       })
    }
    return ret
}
  1. 上一种方法是从后往前遍历，将确定的元素放入栈。此方法是从前往后遍历，将未确定的元素（索引）放入单调栈，当遍历数组到比栈顶元素大（通过索引查询）的元素时，取出栈顶元素，直到栈空或栈顶元素大于等于当前元素。同时将栈压缩为数组实现
func dailyTemperatures(temperatures []int) []int {
    n := len(temperatures)
    ret := make([]int, n)
    st := []int{}
    for i := 0; i < n; i++ {
       for len(st) > 0 && temperatures[st[len(st)-1]] < temperatures[i] {
          // 栈顶元素对应结果
          tmp := st[len(st)-1]
          ret[tmp] = i - tmp
          // 出栈
          st = st[:len(st)-1]
       }
       st = append(st, i)
    }
    return ret
}

T15. 最小栈

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

  • MinStack() initializes the stack object.
  • void push(int val) pushes the element val onto the stack.
  • void pop() removes the element on the top of the stack.
  • int top() gets the top element of the stack.
  • int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

某一时刻的栈的最小值，一定与最近入栈的元素有关，即元素入栈时，最小值要么不变，要么变为入栈元素的值，那只需要记录每次入栈的 pair 就好了

type Node struct {
    Val int
    Min int
}

type MinStack struct {
    stack []*Node
}

func Constructor() MinStack {
    return MinStack{
       stack: []*Node{&Node{0, math.MaxInt}},
    }
}

func (t *MinStack) Push(val int) {
    t.stack = append(t.stack, &Node{val, min(t.GetMin(), val)})
}

func (t *MinStack) Pop() {
    t.stack = t.stack[:len(t.stack)-1]
}

func (t *MinStack) Top() int {
    return t.stack[len(t.stack)-1].Val
}

func (t *MinStack) GetMin() int {
    return t.stack[len(t.stack)-1].Min
}

也可以用维护一个单调链表，入栈和出栈时进行修改

树

T2. 二叉树的最近公共祖先

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

  1. p & q 位于同一侧，则返回最上的
  2. p & q 位于两侧，返回公共父节点
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    // 只把自己、p或q向上传递
    // 假设自己是p，q在自己以下，那么自己即是最近的公共祖先
    if root == nil || root == p || root == q {
        return root
    }
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    // 在两侧都能找到，说明p、q各在两侧
    if left != nil && right != nil {
        return root
    }
    // 要么上传找到的，要么就是返回nil
    if left != nil {
        return left
    } else {
        return right
    }
}

T5. 翻转二叉树

Given the root of a binary tree, invert the tree, and return its root.

对于每个结点，翻转它的左右结点，每个翻转操作都是独立的，前中后序遍历都可以，更改一下操作结点即可

后序遍历：

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    invertTree(root.Left)
    invertTree(root.Right)
    temp := root.Left
    root.Left = root.Right
    root.Right = temp
    return root
}

T8. 实现 Trie 前缀树

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings.

There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:

  • Trie () Initializes the trie object.
  • void insert (String word) Inserts the string word into the trie.
  • boolean search (String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
  • boolean startsWith (String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.
  1. 将每一个字符构建成一个结点，每个结点有指向下一个结点的指针数组，并使用 cnt 标记是否为结尾结点（int 或 bool 都可，只是用于标记）
  2. 若可以通过这个数组到达某一结点，则为前缀，若同时 cnt==1，则为一个完整单词
type Trie struct {
    root [26]*Trie
    cnt  int
}

func Constructor() Trie {
    root := [26]*Trie{}
    return Trie{root, 0}
}

func (t *Trie) Insert(word string) {
    if len(word) == 0 {
        return
    }
    cur := t
    for _, ch := range word {
        idx := mapping(ch)
        if cur.root[idx] == nil {
            cur.root[idx] = &Trie{
                root: [26]*Trie{},
                cnt:  0,
            }
        }
        cur = cur.root[idx]
    }
    cur.cnt++
}

func (t *Trie) Search(word string) bool {
    if len(word) == 0 {
        return false
    }
    cur := t
    for _, ch := range word {
        idx := mapping(ch)
        if cur.root[idx] == nil {
            return false
        }
        cur = cur.root[idx]
    }
    return cur.cnt > 0
}

func (t *Trie) StartsWith(prefix string) bool {
    if len(prefix) == 0 {
        return true
    }
    cur := t
    for _, ch := range prefix {
        idx := mapping(ch)
        if cur.root[idx] == nil {
            return false
        }
        cur = cur.root[idx]
    }
    return true
}

func mapping(char int32) int {
    return int(char - 'a')
}

T25. 二叉树中的最大路径和

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node’s values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

递归 + 后序遍历：

  1. 使用全局变量检测最大值变化
  2. 先遍历两个子树，计算各自经过左、右节点所能得到的最大路径和。（注意返回值并不是求得的最大路径和）
  3. 然后计算经过当前节点，加上左右节点，得到当前最大路径和，更新最大值
  4. 返回值应当是当前节点、当前节点加上左子树和当前节点加上右子树中的最大者，注意只能有一颗子树被加上
var ret int

func maxPathSum(root *TreeNode) int {
    if root == nil {
       return 0
    }
    ret = math.MinInt
    postorderTraversal(root)
    return ret
}

func postorderTraversal(root *TreeNode) int {
    if root == nil {
       return 0
    }
    l := postorderTraversal(root.Left)
    r := postorderTraversal(root.Right)
    cur := root.Val
    if l > 0 {
       cur += l
    }
    if r > 0 {
       cur += r
    }
    ret = max(ret, cur)

    // 只能取一边的子结点，或者不取
    return max(root.Val+l, root.Val+r, root.Val)
}

值得注意的是，在 Leetcode 测试时，ret 被初始化过了，必须在函数内部再赋值一次

回溯

T31. 路径总和 III

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

根据当前节点选择开闭，进行回溯。需要注意，节点必须连续选取，所以使用一个 flag 标记上一个节点是否有被选择

var ret int
func pathSum(root *TreeNode, targetSum int) int {
    ret = 0
    dps(root, targetSum, false)
    return ret
}

func dps(root *TreeNode, target int, flag bool) {
    if root == nil {
       return
    }
    if target == root.Val {
       ret++
    }

    if !flag {
       dps(root.Left, target, false)
       dps(root.Right, target, false)
    }
    dps(root.Left, target-root.Val, true)
    dps(root.Right, target-root.Val, true)
}

图

T9. 课程表

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1.

You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.

检测是否有换，求拓扑排序：

  1. 先构造图（邻接表、邻接矩阵）
  2. 接着找到入口（入度为 0 的节点），放入队列
  3. 遍历队列，删去队首元素和其他节点的边，并修改它们的边数，将入边减为 0 的节点入队
  4. 如果存在节点没有入队，则说明不能完成（可以判断遍历过的节点个数和总节点数）

邻接矩阵

func canFinish(numCourses int, prerequisites [][]int) bool {
    // 建图
    graph := make([][]int, numCourses)
    for i := 0; i < numCourses; i++ {
        graph[i] = make([]int, numCourses)
    }
    for _, edge := range prerequisites {
        from, to := edge[0], edge[1]
        graph[from][to] = 1
    }
    // 维护入度为0的节点队列
    q := make([]int, 0, numCourses)
    // 记录入边
    visited, in := make([]bool, numCourses), make([]int, numCourses)
    // 初始化队列和入度数组
    for i := 0; i < numCourses; i++ {
        // 列表示入边
        for j := 0; j < numCourses; j++ {
            in[i] += graph[j][i]
        }
        if in[i] == 0 {
            q = append(q, i)
            visited[i] = true
        }
    }
    // 寻找拓扑排序
    for len(q) > 0 {
        // 取出队首节点，删去它的所有出边
        cur := q[0]
        q = q[1:]
        // 横表示出边
        for i := 0; i < numCourses; i++ {
            if graph[cur][i] == 1 {
                graph[cur][i] = 0
                in[i]--
                if in[i] == 0 && !visited[i] {
                    q = append(q, i)
                    visited[i] = true
                }
            }
        }
    }
    for i := 0; i < numCourses; i++ {
        if !visited[i] {
            return false
        }
    }
    return true
}

邻接表

本题为稀疏图，用邻接表效率更好： #待完成

T11. 岛屿数量

Given an m x n 2D binary grid grid which represents a map of '1' s (land) and '0' s (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Flood Fill，使用 BFS 和 DFS 都可以

var n, m int
var fx = []int{1, -1, 0, 0}
var fy = []int{0, 0, 1, -1}
func numIslands(grid [][]byte) int {
    m, n = len(grid), len(grid[0])
    ret := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == '1' {
                ret++
                bfs(grid, i, j)
            }
        }
    }
    return ret
}
func check(x, y int) bool {
    return 0 <= x && x < m && 0 <= y && y < n
}
func bfs(grid [][]byte, a, b int) {
    // 队列
    q := [][]int{{a, b}}
    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        x, y := cur[0], cur[1]
        for i := 0; i < 4; i++ {
            nx, ny := x+fx[i], y+fy[i]
            if check(nx, ny) && grid[nx][ny] == '1' {
                grid[nx][ny] = '0'
                q = append(q, []int{nx, ny})
            }
        }
    }
}

排序

T7. 数组中第 k 个最大元素

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?

堆排序

难点在于用 Go 实现堆

  • 创建堆：从最后一个非叶子节点开始进行下沉
  • 下沉：比较根左右大小，进行交换
func createHeap(nums []int, size int) {
    // 构造大根堆
    for i := size/2 - 1; i >= 0; i-- {
        // 从最后一个非叶子节点开始，进行下沉
        sink(nums, i, size)
    }
}
func sink(nums []int, x, size int) {
    for {
        left := x*2 + 1
        right := x*2 + 2
        largest := x
        // 找出三个节点中最大的
        if left < size && nums[left] > nums[largest] {
            largest = left
        }
        if right < size && nums[right] > nums[largest] {
            largest = right
        }
        if largest == x {
            break
        }
        // sink
        nums[x], nums[largest] = nums[largest], nums[x]
        x = largest
    }
}
func findKthLargest(nums []int, k int) int {
    n := len(nums)
    createHeap(nums, len(nums))
    // 找出第k大的元素
    var ret int
    for ; k > 0; k-- {
        top := nums[0]
        ret = top
        // 出堆
        nums[0] = nums[n-1]
        n--
        sink(nums, 0, n)
    }
    return ret
}

快速排序

#待完成

T17. 排序链表

Given the head of a linked list, return *the list after sorting it in ascending order*.

  1. 插入排序
  2. 归并排序 1. 使用快慢指针分割链表，不断分割至最小 2. 然后二路归并，合并两个链表
    实际上和数组没什么区别，关键在于将链表分成两半[[#回文链表]]
func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
       return head
    }
    // split to two list
    // [head, slow] && [slow.Next, fast] or [slow.Next, fast)    s, f := head, head.Next
    for f != nil && f.Next != nil {
       s = s.Next
       f = f.Next.Next
    }
    temp := s.Next
    s.Next = nil
    left := sortList(head)
    right := sortList(temp)
    // sort: merge two list
    dummyHead := &ListNode{Val: -1}
    cur := dummyHead
    for left != nil && right != nil {
       if left.Val < right.Val {
          cur.Next = left
          left = left.Next
       } else {
          cur.Next = right
          right = right.Next
       }
       cur = cur.Next
    }
    for left != nil {
       cur.Next = left
       cur = cur.Next
       left = left.Next
    }
    for right != nil {
       cur.Next = right
       cur = cur.Next
       right = right.Next
    }
    return dummyHead.Next
}

但实际上直接转换为数组，然后排序反而更快

动态规划

T6. 最大正方形

Given an m x n binary matrix filled with 0 ‘s and 1 ‘s, find the largest square containing only 1 ‘s and return its area.

  1. 前缀和，判断正方形区块内和是否为平方数
  2. 动态规划
  • f[i][j]
    • 表示矩阵中第 $i$ 行第 $j$ 列的位置，能够形成的最大正方形
    • 大小
  • 计算
    • $f[i][j]=1$ if $matrix[i][j]==1$
    • $f[i][j]=2$ if $matrix[i][j]==1: & : f[i-1][j]==1: & : f[i][j-1]==1: & : f[i-1][j-1]==1$ *
    • $f[i][j]=n$ if $matrix[i][j]==1:&: f[i-1][j]==n-1:&: f[i][j-1]==n-1:&: f[i-1][j-1]==n-1$

即：

$$
f[i][j]=\min{f[i-1][j],f[i][j-1],f[i-1][j-1]}+1,if:matrix[i][j]==1
$$

func maximalSquare(matrix [][]byte) int {
    n, m := len(matrix), len(matrix[0])
    f := make([][]int, n)
    for i := range f {
        f[i] = make([]int, m)
    }
    ret := 0
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if matrix[i][j] == '1' {
                if i == 0 || j == 0 {
                    f[i][j] = 1
                } else {
                    f[i][j] = min(f[i-1][j], f[i][j-1], f[i-1][j-1]) + 1
                }
                if f[i][j] > ret {
                    ret = f[i][j]
                }
            }
        }
    }
    return ret * ret
}

T12. 打家劫舍

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return *the maximum amount of money you can rob tonight without alerting the police*.

动态规划

  • $f[i]$
    • 表示只考虑前 $i$ 个房子，抢劫的所有方案
    • max value
  • 计算
    • 第 $i$ 个抢，那么第 $i-1$ 不能抢：$f[i]=f[i-2]+nums[i]$
    • 第 $i$ 个不抢，继承第 $i-1$ 个：$f[i]=f[i-1]$
    • 取最大值：$f[i]=max{f[i-1], f[i-2]+nums[i]}$
  • 初始化：$f[0]$ 和 $f[1]$
func rob(nums []int) int {
    n := len(nums)
    if n == 1 {
       return nums[0]
    }
    f := make([]int, len(nums))
    f[0], f[1] = nums[0], max(nums[0], nums[1])
    for i := 2; i < n; i++ {
       f[i] = max(f[i-1], f[i-2]+nums[i])
    }
    return f[n-1]
}

T21. 单词拆分

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

  • f[i]
    • 表示前 $i$ 个字符，能被 wordDict 组合的所有组合
    • bool
  • 遍历 wordDict，记每个元素为 word，则 f[i] = f[i-len(word)+1] && s[i-len(word)+1: i+1] == word
    • 判断当前位置能否由前一组组合，和某一单词组成
func wordBreak(s string, wordDict []string) bool {
    n := len(s)
    f := make([]bool, n+1)

    f[0] = true
    for i := 1; i <= n; i++ {
       // s[i-1]
       for _, word := range wordDict {
          if m := i - len(word); m >= 0 {
             f[i] = f[i] || (f[m] && (s[m:i] == word))
          }
       }
    }

    return f[n]
}

T26. 零钱兑换

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

完全背包问题[[_posts/cs/algorithms/java/动态规划#完全背包问题|完全背包问题]]

  • f[i][j]
    • 只使用了前 $i$ 种硬币，凑出金额为 $j$ 的所有组合方案
    • min count
  • 计算
    • 不使用第 $i$ 种硬币
    • 使用 1 个第 $i$ 种硬币
    • 使用 2 个第 $i$ 种硬币
    • …

得到：

$$
f[i][j]=min(f[i-1][j],:f[i-1][j-coins[i]]+1,f[i-1][j-2*coins[i]]+2,…)
$$

此时由于要遍历硬币种类、金额、硬币数量，需要 $O(n^3)$ 时间

取 $f[i][j-coins[i]]$：

$$
f[i][j-coins[i]]=min(f[i-1][j-coins[i]],f[i-1][j-2*coins[i]]+1,…)
$$

将下面的式子代入上面，可得：

$$
f[i][j]=min(f[i-1][j], f[i][j-coins[i]]+1)
$$

消去了数量，只需要控制遍历顺序，就可以将 $O(n^3)$ 简化为 $O(n^2)$

func coinChange(coins []int, amount int) int {
    f := make([]int, amount+1)
    for i := 1; i <= amount; i++ {
       f[i] = 0x3f3f3f3f
    }

    f[0] = 0
    for _, coin := range coins {
       for j := coin; j <= amount; j++ {
          f[j] = min(f[j], f[j-coin]+1)
       }
    }

    if f[amount] == 0x3f3f3f3f {
       return -1
    }
    return f[amount]
}

T27. 目标和

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

  • For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000
  1. 回溯
  2. 动态规划

两个背包，一个背包 package_a 存放标记为正的元素，另一个背包 package_b 存放标记为负的元素。package_a - package_b = target。

设 nums 的元素和为sum, 可以列出方程：

$$
\begin{align}\left{\begin{aligned}
package_a - package_b = target; \
package_a + package_b = sum;
\end{aligned}\right.\end{align}
$$

则  package_a = (sum + target) / 2。
所以根据题意给的target和sum，可以求出package_a的值。

那这道题就可以转化为：给定一个大小为 package_a 的背包，有多少种组合方式能把背包装满？ 即 0-1 背包。

需要注意的是：sum + target 需要为非负偶数

  • 非负：确保能凑出
  • 偶数：确保划分时不会导致小数缺失
func findTargetSumWays(nums []int, target int) int {
    var sum int = 0
    for _, num := range nums {
       sum += num
    }

    // 只有target + sum 为非负偶数时才有可能存在解
    n := sum + target
    if n < 0 || n%2 == 1 {
       return 0
    }
    // package_a = (sum + target) / 2
    n /= 2
    f := make([]int, n+1)
    f[0] = 1
    for _, i := range nums {
       for j := n; j >= i; j-- {
          f[j] += f[j-i]
       }
    }
    return f[n]
}

func abs(x int) int {
    if x > 0 {
       return x
    }
    return -x
}

T32. 分割等和子集

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

先求和 sum，然后判断能否组成 sum/2 就好（0-1 背包），需要注意 sum 必须为偶数

func canPartition(nums []int) bool {
    var sum int = 0
    for _, num := range nums {
       sum += num
    }
    if (sum&1) != 0 {
       return false
    }

    f := make([]bool, sum + 1)
    f[0] = true
    for _, num := range nums {
       for j := sum; j >= num; j-- {
          f[j] = f[j] || f[j-num]
       }
    }
    return f[sum/2]
}

数学

T13. 多数元素

-Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Boyer-Moore 投票算法：一命抵一命，最后留下来的肯定是多数元素

func majorityElement(nums []int) int {
    var count, ret int
    for i := 0; i < len(nums); i++ {
       if count == 0 {
          ret, count = nums[i], 1
          continue
       }
       if ret != nums[i] {
          count--
       } else {
          count++
       }
    }
    return ret
}

也可以用：

  1. 哈希表 ：时间复杂度$O (n)$；空间复杂度$O (n)$
  2. 排序后取中间位置：复杂度视选用的排序方式
  3. 分治

位运算

T22. 只出现一次的数据

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

位运算，两个相同的数进行异或得到 0，一个数和 0 异或得到本身

func singleNumber(nums []int) int {
    ret := nums[0]
    for i := 1; i < len(nums); i++ {
        ret ^= nums[i]
    }
    return ret
}

T28. 汉明距离

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, return the Hamming distance between them.

func hammingDistance(x int, y int) int {
    ret := 0
    for i := 0; i < 32; i, x, y = i+1, x>>1, y>>1 {
       if (x & 1) != (y & 1) {
          ret++
       }
    }
    return ret
}