这周的双周赛玩脱了，完全脱离状态，只做了 1 道题，其他题目都飞了，整个做完状态就是懒得看了，睡觉为先。

图 1：第 21 场双周赛排名

Q1：上升下降字符串

这一题因为题目的规模很小，所以可以直接暴力解答（如果规模上来了，估计我也是要跪的）

[[email protected]]# cat Q1.go
func sortString(s string) string {
    var (
        i, num int
        length = len(s)
        count  = make([]int, 26)
        rst    = make([]uint8, length)
    )

    for i = 0; i < length; i++ {
        count[s[i]-'a']++
    }
    for num < length {
        for i = 0; i < 26; i++ {
            if count[i] > 0 {
                rst[num] = uint8('a' + i)
                num++
            }
            count[i]--
        }
        for i = 25; i >= 0; i-- {
            if count[i] > 0 {
                rst[num] = uint8('a' + i)
                num++
            }
            count[i]--
        }
    }
    return string(rst)
}

Q2：每个元音包含偶数次的最长子字符串

这一题是坑，其实很多人吐槽第二和第四的位置交换了，（确实我也是因为在这道题浪费了太多的时间，从而导致后面状态下滑了，因为我一直觉得我就要做出来了）。

后面来反思一下这道题，其实还是有些难度的，然后学习了一下人家的题解发现这是一个自己不知道的方式：状态压缩（似乎之前见过？没印象），然后问题就变得容易理解了（果然，还是需要学习一个）。

这里的做法就是找到相同状态（例如都是多了一个 e）的下标位置，因为这两个位置都是都是多了一个e，那么他们之间的子字符串就刚刚好所有的字符都是偶数的。然后求他们的最大差值就是结果了：

[[email protected]]# cat Q2.go
var target = map[uint8]int{
    'a': 1,
    'e': 2,
    'i': 4,
    'o': 8,
    'u': 16,
}

func findTheLongestSubstring(s string) int {
    var (
        i, curr, rst, st int
        ok               bool
        length           = len(s)
        status           = make([]int, 32)
    )
    for i = 0; i < 32; i++ {
        status[i] = math.MaxInt32
    }
    status[0] = -1
    for i = 0; i < length; i++ {
        if st, ok = target[s[i]]; ok {
            curr ^= st
        }
        if status[curr] == math.MaxInt32 {
            status[curr] = i
        } else {
            rst = max(rst, i-status[curr])
        }
    }
    return rst
}

Q3：二叉树中的最长交错路径

这道题我在解答的时候用了递归，然后毫无疑问，在一个大规模的 case 下超时了。

图 2：Q3 大规模 Case 超时

现在有宽松的时间让我重构一番，其实这不用那么麻烦，用 BFS 和 DFS 都可以，只需要维护每个节点在左遍历和右遍历的时候的最大值就可以了，我这里用了一个 BFS：

[[email protected]]# cat Q3.go
type obj struct {
    node  *TreeNode
    left  int
    right int
}

func longestZigZag(root *TreeNode) int {
    var (
        rst  int
        curr obj
        l    = list.New()
    )
    if root == nil {
        return 0
    }
    l.PushBack(obj{
        node:  root,
        left:  0,
        right: 0,
    })

    for l.Len() != 0 {
        curr = l.Remove(l.Front()).(obj)
        if curr.node.Left != nil {
            l.PushBack(obj{
                node:  curr.node.Left,
                left:  curr.right + 1,
                right: 0,
            })
        } else {
            if curr.right > rst {
                rst = curr.right
            }
        }
        if curr.node.Right != nil {
            l.PushBack(obj{
                node:  curr.node.Right,
                left:  0,
                right: curr.left + 1,
            })
        } else {
            if curr.left > rst {
                rst = curr.left
            }
        }
    }
    return rst
}

Q4：二叉搜索子树的最大键值和

这道题其实是很简单的，但是，因为我的粗心，对于 BST 的判断，我只判断了是否大于 left.Val 和小于 right.Val，其实应该返回 left.Max 和 right.Min，因为对于这点没有把握好，所以导致一直出错：

图 3：一直出错的 Q4

其实这道题就是可以简单的递归，求子树是不是 BST：

[[email protected]]# cat Q4.go
func maxSumBST(root *TreeNode) (rst int) {
    isBST(root, &rst)
    return rst
}

func isBST(root *TreeNode, maxSum *int) (is bool, sum, minVal, maxVal int) {
    if root == nil {
        return true, 0, math.MaxInt32, math.MinInt32
    }

    leftIs, leftSum, leftMin, leftMax := isBST(root.Left, maxSum)
    rightIs, rightSum, rightMin, rightMax := isBST(root.Right, maxSum)

    if leftIs && rightIs {
        if root.Val > leftMax && root.Val < rightMin {
            if root.Left == nil {
                leftMin = root.Val
            }
            if root.Right == nil {
                rightMax = root.Val
            }
            rootSum := root.Val + leftSum + rightSum
            if rootSum > *maxSum {
                *maxSum = rootSum
            }
            return true, rootSum, leftMin, rightMax
        }
        return false, max(leftSum, rightSum), math.MaxInt32, math.MinInt32
    } else {
        return false, max(leftSum, rightSum), math.MaxInt32, math.MinInt32
    }
}

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