算法解析

数组

数组问题注意点总结

1. 一定要确定 left 和 right 的语义，到底是闭还是开, 我一般使用 [left, right)
2. 如果说滑动窗口的话，得记住，滑动窗口的 left 和 right 都是增大的!

01.二分查找

题目

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

思路

1. 首先注意 递增 数组，从小到大进行存储，可以定义 left 和 right 两个指针，用于指向处理数据的左右范围。
2. 接下来定义 left 和 right 的含义。以后统一用前闭后开的方式 [left, right) , 接下来就能有循环条件， left < right
3. 每一次获取到 left 和 right 中间的点 mid， 如果 mid 点比 target 小，说明目标值在 (mid, right 之间，反之也是一样的道理。当 mid 位置的值为 target 的时候，返回 mid, 当循环结束后，返回 -1

实现

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

02.移除元素

题目

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

思路

1. 定义变量 last 表示 [0, last) 是满足要求的区间
2. 遍历原始数组，遇到不需要被删除的元素，则扩展满足要求的区间。最后方法返回 last 就是剩下的长度
   时间复杂度O(n), 空间复杂度O(1)

实现

func removeElement(nums []int, val int) int {
    // last: 表示 [0, last) 是满足要求的区间
    last := 0
    for _, v := range nums {
        if val != v {
            // 不需要被删除，满足要求区间扩展
            nums[last] = v
            last ++
        }
    }
    return last
}

03.有序数组的平方

题目

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

思路

1. 题目说数组 nums 是一个非递减数列，因此平方后，最小值的位置是不固定的。如果全是正数，或者全是负数，那么平方后的最小值就在最左或者最右，但是如果有正有负，那么最小值就不固定了，不好以平方最小值下手。
2. 但是平方最大值的话，肯定要么在最左要么在最右边。这样就好办了，每次找到最大值，填充在要返回的数组的最右边，按照这个逻辑进行循环就完事了

实现

func sortedSquares(nums []int) []int {
    // 令 [left,right] 是还未处理的区间
    // (right, len(nums)) 是已经处理的区间
    result := make([]int, len(nums))
    cur := len(result) - 1
    left, right := 0, len(nums) - 1
    for left <= right {
        leftV := nums[left]
        rightV := nums[right]
        a := leftV * leftV
        b := rightV * rightV
        if(a > b) { // 左侧平方是最大值
            result[cur] = a
            left++
            cur--
        }else{ // 右侧平方是最大值
            result[cur] = b
            right--
            cur--
        }
    }
    return result
}

04.长度最小的子数组

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

思路

1. 这道题使用滑动窗口解决，定义 left,right,curSum 使得在 [left, right) 中, 和为 curSum
2. 窗口继续的条件是 right < len(nums)。每一次循环的时候，将窗口右移一位 right++, 获得新的 curSum
3. 获取到新的 curSum 后，尝试将窗口从左侧减少, 并同时更新 curSum, left++。当此时的长度小于历史的最小值时，更新最小长度
4. 最后返回历史最小长度即可

实现

func minSubArrayLen(target int, nums []int) int {
    // 当前窗口为 [left, right)
    left, right := 0, 0
    curSum := 0
    result := math.MaxInt
    for right < len(nums) {
        // 将 right 放入窗口
        curSum += nums[right]
        right ++
        // 进行判断是否满足要求
        for curSum >= target {
            // 满足要求，尝试更新结果
            if right - left < result {
                result = right - left
            }
            // 尝试减少左侧的数据
            curSum -= nums[left]
            left ++
        }
    }
    if result == math.MaxInt {
        return 0
    }
    return result
}

链表

链表问题注意点总结

1. 使用 dummy 节点，能更加方便统统统一的处理首节点
2. 快慢指针也能很方便的解决类似带环的问题

01.移除链表元素

题目

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

思路

1. 使用一个 dummy 节点，用来统一所有的节点的操作
2. 遍历节点，将等于 val 的节点给忽略掉

实现

func removeElements(head *ListNode, val int) *ListNode {
    dummy := &ListNode{}
    cur := dummy

    for head != nil {
        tmpNext := head.Next
        if head.Val != val {
            cur.Next = head
            cur = cur.Next
            cur.Next = nil
        }
        head = tmpNext
    }

    return dummy.Next
}

02.反转链表

题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思路

1. 遍历整个链表，每一轮都保存上一个节点 prev
2. 在每一轮的遍历上，进行节点交换

实现

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode

    for head != nil {
        tmpNext := head.Next
        head.Next = prev
        prev = head
        head = tmpNext
    }

    return prev
}

03.两两交换链表中的节点

题目

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

思路

1. 需要使用 dummy 来统一所有节点的操作
2. 一组一组的处理，维护两个变量 first 和 next, 作为需要交换的两个节点的标识
3. 每一轮循环交换 first 和 next 的位置，并且还要更新 cur, first, next 的值

实现

func swapPairs(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    dummy := &ListNode{}
    cur := dummy // cur 指向进行交换的一组的前一个节点

    first := head
    next := head.Next
    for next != nil {
        // 交换 first 和 next 位置
        tmpNext := next.Next
        next.Next = first
        first.Next = tmpNext
        cur.Next = next

        // 更新变量
        cur = first
        first = first.Next
        if first == nil {
            break
        }
        next = first.Next
    }

    return dummy.Next
}

删除链表的倒数第 N 个结点

题目

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

思路

1. dummy + 快慢指针 fast, slow
2. fast 先走 n 步, 然后 fast 和 slow 一起走，当 fast 为 nil 的时候, slow 就是需要被删除的节点的前一个节点了
3. 要注意两个边界条件
   1. 当判断到 fast 为 nil 的时候，一定记得跳出循环
   2. 删除节点的时候，一定要判断 slow.Next 是否为空

实现

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{}
    dummy.Next = head

    fast := dummy
    slow := dummy
    // fast 到了 nil, 那么 slow 就是要被删除节点的前面一个

    for i := 0; i < n; i ++ {
        fast = fast.Next
    }

    for {
        fast = fast.Next
        if fast == nil {
            break
        }
        slow = slow.Next
    }
    if slow.Next != nil {
        slow.Next = slow.Next.Next
    }

    return dummy.Next
}

面试题 02.07. 链表相交

题目

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

思路

1. 先分别计算出 headA 和 headB 的长度, 找到哪一个是最长的链表，哪一个是短的链表
2. 较长的链表先走 长度差 次，然后两个链表一起走
3. 当两个链表相同的时候，就说明到了第一个交点
4. 当两个链表为 nil 的时候，说明没有交点，返回 nil

实现

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    tmpA, tmpB := headA, headB

    // 1. 找到长短链表
    len1, len2 := 0, 0
    for tmpA != nil {
        len1 ++
        tmpA = tmpA.Next
    }
    for tmpB != nil {
        len2 ++
        tmpB = tmpB.Next
    }
    var long, short *ListNode
    var distance int
    if len1 > len2 {
        long = headA
        short = headB
        distance = len1 - len2
    } else {
        long = headB
        short = headA
        distance = len2 - len1
    }

    // 2. 长的先走 n 步, 然后同时走
    for i := 0; i < distance; i++ {
        long = long.Next
    }
    for long != nil && short != nil {
        if long == short {
            return long
        }
        long = long.Next
        short = short.Next
    }
    return nil
}

环形链表 II

题目

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

思路

思路1 使用集合

1. 创建一个集合 m
2. 遍历链表，如果遍历到了 nil 则说明不存在环
3. 每次遍历都将遍历到的节点加入集合 m
4. 如果某次遍历的节点存在于 m 时，那么这个节点就是环的入口

思路2 快慢指针

1. 创建 fast 和 slow 指针
2. fast 每次走两步, slow 每次走一步, 当 fast 为 nil 的时候，说明链表没有环，直接返回 nil
3. 当 fast 和 slow 相遇的时候，说明出现了环，此时将 fast 返回到 head 的位置
4. 接着 fast 和 slow 同时走，当 fast == slow 的时候，就找到了入环第一个节点

实现

实现1

func detectCycle(head *ListNode) *ListNode {
    m := map[*ListNode]struct{}{}
    for head != nil {
        if _, ok := m[head]; ok {
            return head
        }
        m[head] = struct{}{}
        head = head.Next
    }
    return nil
}

实现2

func detectCycle(head *ListNode) *ListNode {
    fast, slow := head, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next

        if fast == slow { // 追到的话，肯定有环
            fast = head
            for fast != slow {
                fast = fast.Next
                slow = slow.Next
            }
            return fast
        }
    }
    return nil
}

哈希

哈希注意的点

1. 遍历字符串的时候，记得还有一个索引属性 _, ch := range t
2. 使用 make 创建 []int 的时候，记得指定数组长度

有效的字母异位词

题目

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

思路

1. 使用 map 统计 s 中每一个字符出现的次数
2. 遍历 t, 的字符，将 map 中对应的字符 -1 如果小于了 0 则返回 false
3. 遍历 map, 如果存在值不为 0 的键，返回 false

实现

func isAnagram(s string, t string) bool {
    m := map[rune]int{} // 记录 s 出现的次数

    for _, ch := range s {
        m[ch] ++
    }
    for _, ch := range t {
        m[ch]--
        if m[ch] < 0 {
            return false
        }
    }
    for _, v := range m {
        if v != 0 {
            return false
        }
    }
    return true
}

两个数组的交集

题目

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

思路

1. 将 nums1 的元素装在 map 中, 相当于去重
2. 遍历 nums2, 将存在于 map 中的元素，放到另外一个 map2 中，也是去重
3. 最后遍历 map2, 将所有的 key 放入列表中即可

实现

func intersection(nums1 []int, nums2 []int) []int {
    result := make([]int, 0)
    resultSet := make(map[int]struct{})
    m := make(map[int]struct{})

    for _, n := range nums1 {
        m[n] = struct{}{}
    }
    for _, n := range nums2 {
        if v, ok := m[n]; ok {
            resultSet[n] = v
        }
    }
    for k, _ := range resultSet {
        result = append(result, k)
    }
    return result
}

快乐数

题目

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

思路

1. 使用 map 来保存已经遇到过的数据
2. 每次循环都计算每个位上的平方和, 如果 ==1 则跳出循环

实现

func getSum(n int) int {
    result := 0
    for n != 0 {
        last := n % 10
        result += last * last
        n = n / 10
    }
    return result
}

func isHappy(n int) bool {
    m := map[int]struct{}{}

    for n != 1 {
        n = getSum(n)
        if _, ok := m[n]; ok {
            return false // 出现循环
        }
        m[n] = struct{}{}
    }
    return true
}

两数之和

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

思路

1. 遍历 nums 数组
2. 维护字典 m, 每次遍历将遍历到的 value 作为 key, index 作为 value 放入字典中
3. 每次遍历的时候，判断 target - value 是否存在于字典中，如果存在，说明找到了，返回即可

实现

func twoSum(nums []int, target int) []int {
    m := make(map[int]int) // value -> index
    for i, v := range nums {
        aim := target - v
        if index, ok := m[aim]; ok {
            return []int{i, index}
        }
        m[v] = i
    }
    return nil
}

四数相加 II

题目

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

思路

1. 维护一个字典 m, 将 nums1 和 nums4 中的元素和为 key, 出现次数为 value 进行赋值
2. 遍历 nums3 和 nums4, 如果 0-n3-n4 在 m 中，那么结果就加上对应的 value
3. 最后返回结果

Go实现

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
    m := make(map[int]int, len(nums1) * len(nums2))
    result := 0

    for _, v1 := range nums1 {
        for _, v2 := range nums2 {
            m[v1 + v2]++
        }
    }

    for _, v1 := range nums3 {
        for _, v2 := range nums4 {
            result += m[-v1-v2]
        }
    }

    return result
}

赎金信

题目

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

思路

1. 使用一个字典，保存 magazine 中所有字符出现的个数
2. 遍历 ransomNote, 并将 magazine 中对应字符 -1
3. 如果对应字符出现小于0的情况，则返回 false
4. 最后返回 true

Go实现

func canConstruct(ransomNote string, magazine string) bool {
    m := make(map[rune]int)

    for _, ch := range magazine {
        m[ch]++
    }
    for _, ch := range ransomNote {
        m[ch] --
        if m[ch] < 0 {
            return false
        }
    }
    return true
}

可以进行优化，因为是26个字母，所以可以考虑使用数组进行存储

func canConstruct(ransomNote string, magazine string) bool {
    if len(magazine) < len(ransomNote) {
        return false
    }
    m := make([]int, 26)

    for _, ch := range magazine {
        m[ch - 'a']++
    }
    for _, ch := range ransomNote {
        i := ch - 'a'
        m[i] --
        if m[i] < 0 {
            return false
        }
    }
    return true
}

字符串

反转字符串

题目

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

思路

1. 双指针法
2. 一个指向最左边，一个指向最右边
3. 两个指针往中间考虑，每靠拢一次交换一次

Go实现

func reverseString(s []byte)  {
    left, right := 0, len(s) - 1
    for left < right {
        s[left], s[right] = s[right], s[left]
        left ++
        right --
    }
}

二叉树

二叉树注意点

1. 可能会涉及到递归操作, 内部定义函数的时候，一定要先使用 var 再进行实现

二叉树的前序遍历

题目

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

思路

1. 定义一个函数
2. 递归二叉树，进行一个前序遍历

Go实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func preorderTraversal(root *TreeNode) []int {
    var result = make([]int, 0)
    var t func(*TreeNode)
    t = func(root *TreeNode) {
        if root == nil {
            return
        }
        result = append(result, root.Val)
        t(root.Left)
        t(root.Right)
    }
    t(root)
    return result
}

二叉树的后序遍历

题目

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

思路

略

Go实现

func postorderTraversal(root *TreeNode) (result []int) {
    if root == nil {
        return
    }
    var f func(*TreeNode)
    f = func(n *TreeNode) {
        if n == nil {
            return
        }
        f(n.Left)
        f(n.Right)
        result = append(result, n.Val)
    }
    f(root)
    return
}

完全二叉树的节点个数

题目

思路

Go实现

最简单的方法，就是直接遍历一遍，但是这样的时间复杂度是 O(n)

func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return countNodes(root.Left) + countNodes(root.Right) + 1
}

但是可以根据完全二叉树的特性，进行优化

func countLevel(root *TreeNode) (level int){
    for root != nil {
        level++
        root = root.Left
    }
    return
}

func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }
    leftLevel := countLevel(root.Left)
    rightLevel := countLevel(root.Right)
    if leftLevel == rightLevel {
        // 左节点一定是满二叉树, 右节点不一定
        return countNodes(root.Right) + int(math.Pow(2, float64(leftLevel)))
    } else {
        // leftLevel > rightLevel, 右节点一定是满二叉树(层比left小的满二叉树)， 左节点不一定
        return countNodes(root.Left) + int(math.Pow(2, float64(rightLevel)))
    }

平衡二叉树

题目

给定一个二叉树，判断它是否是高度平衡的二叉树。

思路

1. 递归判断左右子树是否为平衡二叉树
2. 如果左右都不全是平衡二叉树，那么当前节点就不是平衡二叉树
3. 如果左右都是平衡二叉树，那么判断左右子树的高度差是否小于等于1
4. 如果小于等于1，那么当前节点就是平衡二叉树, 否则就不是

Go实现

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func abs(k int) int {
    if k > 0 {
        return k
    }
    return -k
}

func f(root *TreeNode) (bool, int) {
    if root == nil {
        return true, 0
    }
    left, leftLevel := f(root.Left)
    if !left {
        return false, 0
    }
    right, rightLevel := f(root.Right)
    if !right {
        return false, 0
    }
    if abs(rightLevel - leftLevel) > 1 {
        return false, 0
    }
    return true, max(rightLevel, leftLevel) + 1
}

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    b, _ := f(root)
    return b
}