上升下降字符串
先从小到大选一波，再从大到小选一波，重复上述步骤，直到选完。
直接模拟一下。（数据量大的话不要直接用 拼接，效率太低，而且浪费内存）
func sortString(s string) string {
m := [26]uint8{}
for i := range s {
m[s[i]-97]
}
var ans strings.Builder
for i := 0; i < len(s); {
for j := 0; j < 26; j {
if m[j] > 0 {
ans.WriteString(string(j 97))
m[j]--
i
}
}
for j := 25; j >= 0; j-- {
if m[j] > 0 {
ans.WriteString(string(j 97))
m[j]--
i
}
}
}
return ans.String()
}每个元音包含偶数次的最长子字符串
给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 ‘a’，’e’，’i’，’o’，’u’ ，在子字符串中都恰好出现了偶数次（含 0 次）。
这题卡了很久，如果暴力做的话肯定会超时，这个状态表示太妙了。
每个元音字母出现次数是否为偶数次可用 0、1 来表示，那么 5 个元音字母就 32 个状态，其中题目要求的全为偶数次的状态——00000。
如果 s[0…i] 与 s[0…j] 状态相同，那么 s[i 1...j] 的状态一定是 00000。
由于求的是最长子串，那么记录一下每个状态出现的第一次位置，再次出现该状态时做差取最大值即可。
代码语言：javascript复制func findTheLongestSubstring(s string) int {
first := make([]int, 32)
for i := range first {
first[i] = math.MinInt32
}
first[0] = -1 // 特殊处理，如果出现 s[0...i] 状态为 0，那么其长度为 i 1。
ans, cur := 0, 0
for i := range s {
switch s[i] {
case 'a':
cur ^= 1
case 'e':
cur ^= 2
case 'i':
cur ^= 4
case 'o':
cur ^= 8
case 'u':
cur ^= 16
}
if first[cur] == math.MinInt32 {
first[cur] = i
} else {
if i-first[cur] > ans {
ans = i - first[cur]
}
}
}
return ans
}二叉树中的最长交错路径
记录一下来源方向，交错路径加一，相同方向置零。
代码语言：javascript复制/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var maxLen int
func longestZigZag(root *TreeNode) int {
maxLen = 0
helper(root.Right, 0, false)
helper(root.Left, 0, true)
return maxLen
}
func helper(root *TreeNode, cnt int, dir bool) {
if root == nil {
return
}
cnt
if cnt > maxLen {
maxLen = cnt
}
if dir {
helper(root.Right, cnt, false)
helper(root.Left, 0, true)
} else {
helper(root.Left, cnt, true)
helper(root.Right, 0, false)
}
}二叉搜索子树的最大键值和
给你一棵树的根结点，请在符合二叉搜索树要求的子树中求出其最大键值和。
首先得判断该子树是否为二叉搜索树，记录下键值和，还要尽可能减少重复计算。
回顾一下，如何验证二叉搜索树。
代码语言：javascript复制func isValidBST(root *TreeNode) bool {
return helper(root, nil, nil)
}
// 边界法
func helper(root, min, max *TreeNode) bool {
if root == nil {
return true
}
if (min != nil && root.Val <= min.Val) || (max != nil && root.Val >= max.Val) {
return false
}
return helper(root.Left, min, root) && helper(root.Right, root, max)
}改改代码就行了。
代码语言：javascript复制var ans int
func maxSumBST(root *TreeNode) int {
ans = 0
helper(root)
return ans
}
func helper(root *TreeNode) (int, int, int, bool) {
if root == nil {
return math.MinInt32, math.MaxInt32, 0, true
}
lMax, lMin, lSum, lValid := helper(root.Left)
rMax, rMin, rSum, rValid := helper(root.Right)
sum, valid := 0, false
if lValid && rValid && lMax < root.Val && root.Val < rMin {
sum = lSum root.Val rSum
ans = max(ans, sum)
valid = true
}
return max(rMax, root.Val), min(lMin, root.Val), sum, valid // 更新边界
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
