求根节点到叶节点数字之和

解题思路

在二叉树的后序遍历算法中，访问一个节点时，栈中保存的是其所有的祖先。可以根据二叉树的后序遍历算法，当访问到叶子节点时，栈中保存的就是从根节点到叶子节点的所有数字，将栈中节点转换为数字，加入到sum中。后序遍历结束后，即可得到从根节点到叶节点生成的所有数字之和sum

解题代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumNumbers(root *TreeNode) int {
    stack := make([]*TreeNode, 0)   // 栈
    cur := root // 当前遍历节点
    var pre *TreeNode   // 上一个遍历过的节点
    var sum int // 数字之和

    for len(stack) >0 || cur != nil {
        for cur != nil {
            // 入栈
            stack = append(stack, cur)
            // 进入左子树
            cur = cur.Left
        }
        if len(stack) > 0 {
            cur = stack[len(stack)-1]
            if cur.Right == nil || pre == cur.Right {
                // 若栈顶节点无右子树，或者右子树刚刚访问过，则访问栈顶节点
                if cur.Left == nil && cur.Right == nil {
                    // 是叶子节点
                    // 计算数字之和
                    sum = sum + stackToInt(stack)
                }
                pre = cur   // 记录上一次访问的节点
                // 栈顶元素访问完成，弹出栈顶
                stack = stack[:len(stack)-1]
                cur = nil
            } else {
                // 否则进入右子树
                cur = cur.Right
            }
        }
    }

    return sum
}

func stackToInt(stack []*TreeNode) int {
    // 将栈中节点转换为数字
    var res int
    for i := 0; i < len(stack); i++ {
        res = res*10 + stack[i].Val
    }

    return res
}

从前序与中序遍历序列构造二叉树

解题思路

对于任意一颗树而言，前序遍历的形式总是[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]，左右子树分别在根节点的两侧。

根据前序遍历结果的第一个节点，即可定位到中序遍历序列中。由此根节点将中序遍历结果分割为左右子树的中序遍历序列，根据左右子树中序遍历序列的节点数目，就可以知道左右子树的节点数，由此可以将前序遍历序列分割为左子树和右子树的前序遍历结果。递归构造左右子树即可构造出完整的二叉树。

解题代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) > 0 {
        // 构造根节点
        root := &TreeNode{}
        root.Val = preorder[0]
        // 从中序遍历中找到根节点坐标
        var inorderRootIndex int
        for i := 0; i < len(inorder); i++ {
            if inorder[i] == root.Val {
                inorderRootIndex = i
                break
            }
        }
        // 中序遍历的左子树，右子树部分
        inorderLeft := inorder[:inorderRootIndex]
        inorderRight := inorder[inorderRootIndex+1:]
        // 前序遍历的左子树，右子树部分
        preorderLeft := preorder[1:1+len(inorderLeft)]
        preorderRight := preorder[1+len(inorderLeft):]
        // 递归构造左子树，右子树
        root.Left = buildTree(preorderLeft, inorderLeft)
        root.Right = buildTree(preorderRight, inorderRight)
        // 返回根
        return root
    } else {
        // 遍历序列为空
        return nil
    }
}

排序链表

对链表进行插入排序

解题思路

对链表进行插入排序，时间复杂度高，达O(n^2)
对链表进行归并排序
- 自顶向下的归并排序
  - 利用快慢指针找到链表的中间节点，以中间节点为界，将链表拆分成两个链表
  - 分别对两个链表进行归并排序
  - 将两个排序后的链表合并
- 自底向上的归并排序
  - 用subLength表示每次排序的子表长度，初始时subLength = 1
  - 每次将排序链表分成若干个长度为subLength的子表进行合并
  - 每次将整个链表都合并一趟过后，将subLength乘以2倍，直到有序子链表的长度大于或等于链表长度

解题代码

插入排序

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func insertionSortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        // 没有元素，或者只有1个元素，直接返回
        return head
    }
    newHead := &ListNode{}  // 虚拟头节点
    newHead.Next = head
    cur, last := head.Next, head // cur为当前待排序节点，last指向已经有序序列的最后一个节点
    for cur != nil {
        p := newHead    // p指向插入位置的前驱
        for p.Next != cur && p.Next.Val < cur.Val {
            // 找到插入位置的前驱节点
            p = p.Next
        }
        // 将cur节点摘下来
        last.Next = cur.Next
        // 将cur节点插入到指定位置
        cur.Next = p.Next
        p.Next = cur
        // cur指向下一个待排序节点
        if last.Next == cur {
            last = last.Next
        }
        cur = last.Next
    }

    return newHead.Next
}

自顶向下的归并排序

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
    return mergeSort(head, nil)    
}

func mergeSort(head, tail *ListNode) *ListNode {  // 归并排序，head指向链表头，rear指向待排序部分链表最后一个节点的下一个节点
    if head == nil {
        // 待排序部分链表为空
        return head
    }
    if head.Next == tail {
        // 待排序部分只有一个节点
        head.Next = nil
        return head
    }
    // 快慢指针，求出中间节点
    low, fast := head, head
    for fast.Next != tail {
        low = low.Next
        fast = fast.Next
        if fast.Next != tail {
            fast = fast.Next
        }
    }
    mid := low
    // 对左右两部分归并排序
    l1 := mergeSort(head, mid)
    l2 := mergeSort(mid, tail)

    return merge(l1, l2)   // 合并左右两部分
}

func merge(l1, l2 *ListNode) *ListNode {    // 合并两个链表
    newHead := &ListNode{}  // 虚拟结果链表头
    rear := newHead  // 指向当前结果链表尾部
    p, q := l1, l2  // p q 分别指向l1 l2
    for p != nil && q != nil {
        // 将值较小的节点挂在结果链表的后面
        if p.Val <= q.Val {
            rear.Next = p
            rear = rear.Next
            p = p.Next
            rear.Next = nil
        } else {
            rear.Next = q
            rear = rear.Next
            q = q.Next
            rear.Next = nil
        }
    }

    // 将还没有合并完的链表直接挂在结果链表后面 
    if p != nil {
        rear.Next = p
    }
    if q != nil {
        rear.Next = q
    }

    return newHead.Next
}

自底向上的归并排序

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
    length := length(head)  // 链表长度
    newHead := &ListNode{ Next: head }  // 虚拟链表头

    for subLength := 1; subLength < length; subLength *= 2 {    // 子表长度小于链表长度时进行归并
        pre, cur := newHead, newHead.Next   // pre当前排序的两个子表的前驱节点，cur当前遍历节点
        for cur != nil {
            head1 := cur    // 待归并的第一段链表头
            for i := 1; i < subLength && cur.Next != nil; i++ {  // 找到第一段链表的最后一个节点
                cur = cur.Next
            }
            head2 := cur.Next   // 待归并的第二段链表头
            cur.Next = nil  // 第一段链表的最后一个节点后继设置为空，使两段链表断开
            cur = head2
            for i := 1; i < subLength && cur != nil && cur.Next != nil; i++ {  // 找到第二段链表的最后一段节点
                cur = cur.Next
            }
            var next * ListNode // 下一组待归并的节点
            if cur != nil {
                next = cur.Next
                cur.Next = nil  // 第二段链表与剩余部分断开
            }
            pre.Next = merge(head1, head2)  // 合并两个有序链表
            for pre.Next != nil {
                pre = pre.Next  // pre指向已经合并的有序链表的最后一个节点
            }
            cur = next
        }
    }

    return newHead.Next
}

func merge(l1, l2 *ListNode) *ListNode {    // 合并两个链表
    newHead := &ListNode{}  // 虚拟结果链表头
    rear := newHead  // 指向当前结果链表尾部
    p, q := l1, l2  // p q 分别指向l1 l2
    for p != nil && q != nil {
        // 将值较小的节点挂在结果链表的后面
        if p.Val <= q.Val {
            rear.Next = p
            rear = rear.Next
            p = p.Next
            rear.Next = nil
        } else {
            rear.Next = q
            rear = rear.Next
            q = q.Next
            rear.Next = nil
        }
    }

    // 将还没有合并完的链表直接挂在结果链表后面 
    if p != nil {
        rear.Next = p
    }
    if q != nil {
        rear.Next = q
    }

    return newHead.Next
}

func length(head *ListNode) int {   // 求出链表长度
    var len int // 链表长度
    p := head
    for p != nil {
        len++
        p = p.Next
    }
    return len
}

字符串转换整数

字符串转换整数 (atoi)

解题思路

手动完成字符串转换整数，依次进行以下步骤：

丢弃无用的前导空格
记录符号位sign：sign = 1时，为正数；sign = -1时，为负数
将字符串转换为整数：从前向后读取，碰到第一个非数字时停止
- 检测是否上溢出，若上溢出，则返回math.MaxInt32
- 检测是否下溢出，若下溢出，则返回math.MinInt32
- res = res*10 + sign*int(s[i]-'0')

解题代码

func myAtoi(s string) int {
    // 丢弃无用的前导空格
    s = ltrim(s)
    if len(s) == 0 {
        // 全为空格
        return 0
    }

    // 记录符号位
    sign := 1
    if s[0] == '+' || s[0] == '-' {
        if s[0] == '-' {
            sign = -1
        }
        // 去除符号位
        s = s[1:]
    }
    
    // 将字符串转换为整数
    var res int  // 结果整数
    for i := 0; i < len(s) && (s[i] >= '0' && s[i] <= '9') ; i++ {    // 从前向后读取，碰到第一个非数字时停止
        if sign == 1 && (res > math.MaxInt32/10 || (res == math.MaxInt32/10 && int(s[i]-'0') > math.MaxInt32%10)) {
            // 上溢出
            return math.MaxInt32
        }
        if sign == -1 && (res < math.MinInt32/10 || (res == math.MinInt32/10 && int(s[i]-'0') > (-math.MinInt32)%10)) {
            // 下溢出
            return math.MinInt32
        }
        // 结果未溢出
        res = res*10 + sign*int(s[i]-'0')
    }

    return res
}

func ltrim(s string) string {   // 丢弃无用的前导空格
    var spaceNum int    // 空格数量
    for i := 0; i < len(s); i++ {
        if s[i] != ' ' {
            // 不是空格退出循环
            break
        }
        spaceNum++
    }

    return s[spaceNum:]
}

最长公共子序列

解题思路

利用动态规划的思想。设dp[i][j]表示，text1从第1个字符到第i个字符，text2从第1个字符到第j个字符的最长公共子序列。

初始化：可以将第0个字符看作是空串，所以dp[i][0]和dp[0][j]被初始化为0
状态转移方程：
- 若text1[i] == text2[j]，说明两个子字符串的最后一位相等，则dp[i][j] = dp[i-1][j-1]+1
- 若text1[i] != text2[j]，说明两个子字符串的最后一位不相等，则dp[i][j] = max(dp[i-1][j], dp[i][j-1])

解题代码

func longestCommonSubsequence(text1 string, text2 string) int {
    len1 := len(text1)
    len2 := len(text2)
    if len1 == 0 || len2 == 0 {
        return 0
    }
    // 声明二维dp数组[len1][len2]
    dp := make([][]int, len1+1)
    for i := 0; i <= len1; i++ {
        dp[i] = make([]int, len2+1)
    }

    // 求dp[i][j]
    for i := 1; i <= len1; i++ {
        for j := 1; j <= len2; j++ {
            if text1[i-1] == text2[j-1] {
                // 更新dp[i][j]
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }

    return dp[len1][len2]
}

func max(n1, n2 int) int {
    if n1 > n2 {
        return n1
    } else {
        return n2
    }
}

Dawn's Blogs

算法刷题笔记 (12) 求根节点到叶节点的数字之和从前序与中序遍历序列构造二叉树排序链表字符串转整数最长公共子序列

求根节点到叶节点数字之和

解题思路

解题代码

从前序与中序遍历序列构造二叉树

解题思路

解题代码

排序链表

解题思路

解题代码

字符串转换整数

解题思路

解题代码

最长公共子序列

解题思路

解题代码