【CodeTop】TOP 100 刷题 41-50

41. 复原 IP 地址

题目链接：93. 复原 IP 地址

题目描述

代码与解题思路

func restoreIpAddresses(s string) []string {
    path, ans := make([]string, 0), make([]string, 0)
    var dfs func(int) 
    dfs = func(start int) { // start 作为的是起始字符位置
        if len(path) == 4 { // 分成四段了, 可以 return 了
            if start == len(s) { // 这里证明整个 s 已经走完了
                str := strings.Join(path, ".")
                ans = append(ans, str)
            }
            return 
        }
        for i := start; i < len(s); i++ {
            if i != start && s[start] == '0' { // 含有前导 0，无效
                break
            }
            str := s[start:i+1]
            num, _ := strconv.Atoi(str) // 字符串转数字
            if num >= 0 && num <= 255 { // 符合 IP 的要求
                path = append(path, str)
                dfs(i+1)
                path = path[:len(path)-1]
            } else { // 如果不满足条件，再往后也不可能满足条件，直接退出
                break
            }
        }
    }
    dfs(0)
    return ans
}

经典的 dfs 题目，题目的代码细节非常的多，必须非常细致的分析

1. 如果已经将 ip 分成四段了，这种情况就已经走完了，就可以返回了
2. 如果 start == len(s)，证明这次递归刚好用完所有字符，证明是一个正确情况，就追加到 ans 数组中
3. 遍历 s 字符串，搜索每一种情况
4. IP 地址不含前导零
5. 将字符串转数字，判断是否符合 IP 地址 num >= 0 && num <= 255 的要求
6. 如果符合条件，将该字符串追加到 path 数组，等到追加到四段就能判断是否符合条件了
7. 继续 dfs 搜索，给 start 传 i+1，继续搜索 s 字符串之后的字符

42. 排序链表

题目链接：148. 排序链表

题目描述

代码与解题思路

func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    
    mid := getMid(head) // 从中间分
    next := mid.Next
    mid.Next = nil

    list1 := sortList(head) // 将链表分割
    list2 := sortList(next)
    return mergeSortList(list1, list2) // 归并排序
}

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

func mergeSortList(head1, head2 *ListNode) *ListNode {
    phead := &ListNode{}
    prev := phead
    for head1 != nil && head2 != nil {
        if head1.Val < head2.Val {
            prev.Next = head1
            head1 = head1.Next
        } else {
            prev.Next = head2
            head2 = head2.Next
        }
        prev = prev.Next
    }
    if head1 != nil {
        prev.Next = head1
    }
    if head2 != nil {
        prev.Next = head2
    }
    return phead.Next
}

这道题说实话并不难，思路太清晰了，先取中分割链表，然后进行归并排序，归并排序有两种实现方式，可以用迭代来实现，也可以用递归来实现，我推荐是用迭代的方法，实现起来最清晰，这里我都抽象出来：

迭代法，通过 prev 节点将两个有序链表合并成一个有序链表

func mergeSortList(head1, head2 *ListNode) *ListNode {
    phead := &ListNode{}
    prev := phead
    for head1 != nil && head2 != nil {
        if head1.Val < head2.Val {
            prev.Next = head1
            head1 = head1.Next
        } else {
            prev.Next = head2
            head2 = head2.Next
        }
        prev = prev.Next
    }
    if head1 != nil {
        prev.Next = head1
    }
    if head2 != nil {
        prev.Next = head2
    }
    return phead.Next
}

递归法，自行领悟：

func mergeSortList(head1, head2 *ListNode) *ListNode {
    // 如果走到 next 了, 就让 next 直接接上另一个链表
    if head1 == nil {
        return head2
    }
    if head2 == nil {
        return head1
    }

    // 哪个小就让哪个走 next
    if head1.Val < head2.Val { 
        head1.Next = mergeSortList(head2, head1.Next)
        return head1
    } else {
        head2.Next = mergeSortList(head1, head2.Next)
        return head2
    }
}

43. 下一个排列

题目链接：31. 下一个排列

题目描述

代码与解题思路

func nextPermutation(nums []int)  {
    i, j := len(nums)-2, len(nums)-1
    for i >= 0 && nums[i] >= nums[i+1] {
        i--
    }
    if i >= 0 {
        for j >= 0 && nums[i] >= nums[j] {
            j--
        }
        nums[i], nums[j] = nums[j], nums[i]
    }
    
    // reverse
    l, r := i+1, len(nums)-1
    for l < r {
        nums[l], nums[r] = nums[r], nums[l]
        l++
        r--
    }
}

难爆了，这思路谁想的出来：

先找一个 nums[i] < nums[i+1] 的数，然后找一个 nums[j] > nums[i] 的数，交换，然后让后面的区间反转

就是这个思路，我也不知道为什么可行，总之背下来准没错，算法苦手再次落泪了

44. x 的平方根

题目链接：69. x 的平方根

题目描述

代码与解题思路

func mySqrt(x int) (ans int) {
    left, right := 0, x
    for left <= right {
        mid := left+(right-left)/2
        if x < mid*mid {
            right = mid-1
        } else {
            ans = mid
            left = mid+1
        }
    }
    return ans
}

这道题可以用二分的思路来做，记住要更新 ans，和二分的模板就行。

45. 爬楼梯

题目链接：70. 爬楼梯

题目描述

代码与解题思路

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

最基础的 dp 算法，创建 dp 数组，初始化，根据状态转移方程填表。

46. 字符串转换整数 (atoi)

题目链接：8. 字符串转换整数 (atoi)

题目描述

代码与解题思路

func myAtoi(s string) (ans int) {
    length := len(s)

    // 去除前导空格
    index := 0
    for index < length {
        if s[index] != ' ' {
            break
        }
        index++
    }

    // 如果全是空格, 那就可以直接返回了
    if index == length {
        return 0
    }

    // 判断正负
    sign := 1
    if s[index] == '+' {
        index++
    } else if s[index] == '-' {
        sign = -1
        index++
    }

    // 将后续出现的数字字符进行转换
    maxInt := math.MaxInt32
    minInt := math.MinInt32
    for index < length {
        // 判断不合法的情况
        if s[index] < '0' || s[index] > '9' {
            break
        }
        // 字符转整形
        num, _ := strconv.Atoi(string(s[index]))
        // 题目要求只能存储 32 位大小的有符号整数
        // ans 接下来会乘 10, 如果 ans*10 == maxInt, 那就比较 num 和 maxInt%10
        if ans > maxInt/10 || (ans == maxInt/10 && num > maxInt%10) {
            return maxInt
        }
        if ans < minInt/10 || (ans == minInt/10 && num > -(minInt%10)) {
            return minInt
        }
        ans = ans*10 + num*sign
        index++
    }
    return ans
}

这道题最重要的就是分析题目要求，把题目要求分析完善了，然后再对照着需求写代码就行了：

1. 读入字符串并丢弃无用的前导空格
2. 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果正。
3. 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串其余部分将被忽略。
4. 将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” ->32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 始）。
5. 如果整数数超过 32 位有符号整数范围 [?231, 231 ? 1] ，需要截断这个数，使其保持在这个范围内。具体来说，小于 ?231 的整数应该被固定为 ?231 大于 231 ? 1 的整数应该被固定为 231 ? 1 。
6. 返回整数作为最终结果。

按照这六个要求，逐个实现，代码中有清晰的注释信息引导了。

47. 括号生成

题目链接：22. 括号生成

题目描述

代码与解题思路

func generateParenthesis(n int) (ans []string) {
    var dfs func(string, int, int)
    dfs = func(s string, left, right int) {
        if left < 0 || left > right {
            return
        }
        if left == 0 && right == 0 {
            ans = append(ans, s)
            return
        }
        dfs(s+"(", left-1, right)
        dfs(s+")", left, right-1)
    }
    dfs("", n, n)
    return ans
}

这是一道经典的搜索题目，而这个解法是评论区的一个大佬想出来的，非常的巧妙，dfs 用的非常的传神，好好学习一下别人清晰的思路

48. 两数相加

题目链接：2. 两数相加

题目描述

代码与解题思路

如果说，LeetCode 第一题劝退了 90% 从第一题开始刷的铁头娃，那 LeetCode 的第二题，劝退了剩下的 99%。这就是我对这道题的评价。

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    nxtVal := 0
    phead := &ListNode{}
    cur := phead;
    for l1 != nil && l2 != nil {
        sum := l1.Val + l2.Val + nxtVal
        newnode := &ListNode{Val: sum%10}
        cur.Next = newnode
        cur = cur.Next
        nxtVal = sum/10
        l1 = l1.Next
        l2 = l2.Next
    }
    if l1 == nil {
        for l2 != nil {
            sum := l2.Val + nxtVal
            newnode := &ListNode{Val: sum%10}
            cur.Next = newnode
            cur = cur.Next
            nxtVal = sum/10
            l2 = l2.Next
        }

    }
    if l2 == nil {
        for l1 != nil {
            sum := l1.Val + nxtVal
            newnode := &ListNode{Val: sum%10}
            cur.Next = newnode
            cur = cur.Next
            nxtVal = sum/10
            l1 = l1.Next
        }
    }
    if nxtVal > 0 {
        cur.Next = &ListNode{Val: nxtVal, Next: nil}
    }
    return phead.Next
}

我这里就是非常经典的模拟操作，两个链表同时操作，然后再单独操作比较长的链表，最后特判一下进位的情况，代码比较屎山，但是我能够独立写出来

还有一种放法是题解的方法，代码简短且巧妙，但我想不出来这种解法，看看就好：

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        auto dummy = new ListNode(); // 哨兵节点
        auto cur = dummy;
        int carry = 0; // 进位
        while (l1 || l2 || carry) { // 有一个不是空节点，或者还有进位，就继续迭代
            carry += (l1 ? l1->val : 0) + (l2 ? l2->val : 0); // 节点值和进位加在一起
            cur = cur->next = new ListNode(carry % 10); // 每个节点保存一个数位
            carry /= 10; // 新的进位
            if (l1) l1 = l1->next; // 下一个节点
            if (l2) l2 = l2->next; // 下一个节点
        }
        return dummy->next; // 哨兵节点的下一个节点就是头节点
    }
};

49. 滑动窗口最大值

题目链接：239. 滑动窗口最大值

题目描述

代码与解题思路

func maxSlidingWindow(nums []int, k int) (ans []int) {
    q := make([]int, len(nums))
    for i, v := range nums {
        // 维护单调队列, 把比 v 小的队尾全部踢出队列
        for len(q) > 0 && nums[q[len(q)-1]] <= v {
            q = q[:len(q)-1]
        }
        q = append(q, i)

        // 如果滑动窗口大小超过 k, 就去出队头, 缩小滑动窗口
        if i - q[0] >= k {
            q = q[1:]
        }

        // 滑动窗口 >= k 之后, 就需要开始更新答案了
        if i >= k-1 {
            ans = append(ans, nums[q[0]])
        }
    }
    return ans
}

看着不难，但是做起来不简单的题目，我一开始的思路是用优先级队列来做，理论上是可行的，但，go 手写堆我写不出来

用单调队列来做也行，不过得熟悉单调队列该怎么组织起来，最重要的就是每次入队前都要维护队列的单调性，用多几次估计就熟悉了。

50. 比较版本号

题目链接：165. 比较版本号

题目描述

代码与解题思路

func compareVersion(version1 string, version2 string) int {
    arr1, arr2 := strings.Split(version1, "."), strings.Split(version2, ".")
    for i := 0; i < max(len(arr1), len(arr2)); i++ {
        val1, val2 := getVal(arr1, i), getVal(arr2, i)
        if val1 > val2 {
            return 1
        } else if val1 < val2 {
            return -1
        }
    }
    return 0
}

func getVal(arr []string, i int) int {
    if i < len(arr) {
        ans, _ := strconv.Atoi(arr[i])
        return ans
    }
    return 0
}

非常巧妙的调用 go 的库，必须学会：

1. 先是用 strings.Split 将 string 根据分隔符切割成数组
2. 然后用 strconv.Atoi 将 字符串转整数，最重要的是直接把前导零解决了

好好学习一下大佬的库使用