LeetCode Weekly Contest 21（双周赛）

算法

字数统计: 902阅读时长: 4 min

 2020/03/08   Share

上升下降字符串

先从小到大选一波，再从大到小选一波，重复上述步骤，直到选完。

直接模拟一下。（数据量大的话不要直接用 + 拼接，效率太低，而且浪费内存）

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。

由于求的是最长子串，那么记录一下每个状态出现的第一次位置，再次出现该状态时做差取最大值即可。

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
}

二叉树中的最长交错路径

记录一下来源方向，交错路径加一，相同方向置零。

/**
 * 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)
    }
}

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

给你一棵树的根结点，请在符合二叉搜索树要求的子树中求出其最大键值和。

首先得判断该子树是否为二叉搜索树，记录下键值和，还要尽可能减少重复计算。

回顾一下，如何验证二叉搜索树。

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)
}

改改代码就行了。

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
}

原文作者：wywwzjj

原文链接：https://wywwzjj.top/2020/03/08/LeetCode-Weekly-Contest-21/

发表日期：March 8th 2020, 12:30:38 am

更新日期：May 15th 2021, 11:53:20 am

Next Post

LeetCode Weekly Contest 179
Previous Post

LeetCode Weekly Contest 177

CATALOG

1. 上升下降字符串
2. 每个元音包含偶数次的最长子字符串
3. 二叉树中的最长交错路径
4. 二叉搜索子树的最大键值和

