算法题

[rrain7]

这里记录出过的算法题

[rrain7]

把二叉树打印成多行

[rrain7]

最大连续子数组

[rrain7]

二叉树最大直径

[rrain7]

最大连续子数组

func maxSubArray(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    max, sum := nums[0], 0
    for i := 0; i < len(nums); i++ {
        if sum < 0 {
            sum = nums[i]
        } else {
            sum += nums[i]
        }

        if sum > max {
            max = sum
        }
    }

    return max
}

[rrain7]

二叉树最大直径

var res int

func diameterOfBinaryTree(root *TreeNode) int {
    res = 0
    dfs(root)
    return res
}

func dfs(root *TreeNode) int {
    if root == nil {
        return 0
    }

    left := dfs(root.Left)
    right := dfs(root.Right)

    res = max(res, left+right)

    return max(left, right)+1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

[rrain7]

把二叉树打印成多行

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }

    queue := []*TreeNode{root}
    result := [][]int{}

    for len(queue) != 0 {
        curQueue := []*TreeNode{}
        item := []int{}
        for _, node := range queue {
            item = append(item, node.Val)

            if node.Left != nil {
                curQueue = append(curQueue, node.Left)
            }

            if node.Right != nil {
                curQueue = append(curQueue, node.Right)
            }
        }

        queue = curQueue
        result = append(result, item)
    }

    return result
}

[rrain7]

go 使用 递归 和 闭包 进行二叉树先序遍历 NB链接

[rrain7]

go 使用 递归 和 闭包 进行二叉树先序遍历 NB链接

type TreeNode struct {
       Val     int
       Left   *TreeNode
       Right *TreeNode
}

func preorder(root *TreeNode) []int {
     result := []int{}
     processNode := func(node *TreeNode) {
           result = append(result, node.Val)
     }

      preorderInternal(root, processNode)

      return result
}

func preorderInternal(root *TreeNode, processNode func(*TreeNode)) {
        if root != nil {
             processNode(root)
             preorderInternal(root.Left, processNode)
             preorderInternal(root.Right, processNode)
         }
}

[rrain7]

二叉树后序遍历

[rrain7]

LeetCode 223 矩阵面积

func computeArea(ax1 int, ay1 int, ax2 int, ay2 int, bx1 int, by1 int, bx2 int, by2 int) int {
        w := min(ax2, bx2) - max(ax1, bx1)
        h := min(ay2, by2) - max(ay1, by1)

        return (ax2-ax1)*(ay2-ay1) + (bx2-bx1)*(by2-by1) - max(0, w)*max(0, h)
}

func min(x, y int) int {
        if x < y {
              return x
        }
        return y
}

func max(x, y int) int {
        if x < y {
            x, y = y, x
        }
        return x
}