这周题目有点多。。周赛、双周赛还有每日一题。。做的慢有点做不过来了
第一题：上升下降字符串
给你一个字符串 s ，请你根据下面的算法重新构造字符串：
从 s 中选出 最小 的字符，将它 接在 结果字符串的后面。
从 s 剩余字符中选出 最小 的字符，且该字符比上一个添加的字符大，将它 接在 结果字符串后面。
重复步骤 2 ，直到你没法从 s 中选择字符。
从 s 中选出 最大 的字符，将它 接在 结果字符串的后面。
从 s 剩余字符中选出 最大 的字符，且该字符比上一个添加的字符小，将它 接在 结果字符串后面。
重复步骤 5 ，直到你没法从 s 中选择字符。
重复步骤 1 到 6 ，直到 s 中所有字符都已经被选过。
在任何一步中，如果最小或者最大字符不止一个 ，你可以选择其中任意一个，并将其添加到结果字符串。
请你返回将 s 中字符重新排序后的 结果字符串 。
示例 1：
输入：s = “aaaabbbbcccc”
输出：”abccbaabccba”
解释：第一轮的步骤 1，2，3 后，结果字符串为 result = “abc”
第一轮的步骤 4，5，6 后，结果字符串为 result = “abccba”
第一轮结束，现在 s = “aabbcc” ，我们再次回到步骤 1
第二轮的步骤 1，2，3 后，结果字符串为 result = “abccbaabc”
第二轮的步骤 4，5，6 后，结果字符串为 result = “abccbaabccba”
示例 2：
输入：s = “rat”
输出：”art”
解释：单词 “rat” 在上述算法重排序以后变成 “art”
示例 3：
输入：s = “leetcode”
输出：”cdelotee”
示例 4：
输入：s = “ggggggg”
输出：”ggggggg”
示例 5：
输入：s = “spo”
输出：”ops”
思路：
统计每个小写字母的个数，然后从前往后再从后往前依次取即可。
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Solution: def sortString(self, s: str) -> str: l = len(s) if l == 0: return '' lowercases = string.ascii_lowercase counts = [0 for i in range(26)] for i in range(26): counts[i] = s.count(lowercases[i]) # 统计每个小写字母的个数 ans = '' left_to_right = True # 是否从左往右取 while l: if left_to_right: for i in range(26): if counts[i]: l -= 1 counts[i] -= 1 ans += lowercases[i] else: for i in range(25, -1, -1): if counts[i]: l -= 1 counts[i] -= 1 ans += lowercases[i] left_to_right = not left_to_right # 反向 return ans |
第二题：每个元音包含偶数次的最长子字符串
给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 ‘a’，’e’，’i’，’o’，’u’ ，在子字符串中都恰好出现了偶数次。
示例 1：
输入：s = “eleetminicoworoep”
输出：13
解释：最长子字符串是 “leetminicowor” ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。
示例 2：
输入：s = “leetcodeisgreat”
输出：5
解释：最长子字符串是 “leetc” ，其中包含 2 个 e 。
示例 3：
输入：s = “bcbcbc”
输出：6
解释：这个示例中，字符串 “bcbcbc” 本身就是最长的，因为所有的元音 a，e，i，o，u 都出现了 0 次。
思路：
这题放在第二题有点难了。。。卡了很久。。。 5个元音字母a，e，i，o，u，出现的次数要么为奇数次，要么为偶数次。因此总共有2^5=32种状态。
统计从开头开始到位置i每个字母的数量，用0-31分别表示每个位置的状态。
状态相同的两个位置之间元音字母必然出现偶数次，从开头到状态为0的位置字母必然出现偶数次。
记录每种状态status的最早出现位置firsts[status]和最后出现位置lasts[status]。
维护一个全局变量ans，遍历每种状态，当lasts[status]和firsts[status]均存在且lasts[status] - firsts[status] > ans时更新ans。
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
class Solution: def findTheLongestSubstring(self, s: str) -> int: letters = ['a', 'e', 'i', 'o', 'u'] orders = [16, 8, 4, 2, 1] firsts = [-1 for i in range(32)] lasts = [-1 for i in range(32)] l = len(s) ans = 0 letters_dict = {i: True for i in letters} firsts[0] = 0 for i in range(l): c = s[i] if c in letters: letters_dict[c] = not letters_dict[c] # 用True和False记录奇偶 bases = [0 if v else 1 for v in letters_dict.values()] status = 0 for j in range(5): status += bases[j] * orders[j] # 位置i的状态 if firsts[status] == -1: firsts[status] = i + 1 lasts[status] = i + 1 for i in range(32): if firsts[i] != -1 and lasts[i] != -1: ans = max(ans, lasts[i] - firsts[i]) return ans |
第三题：二叉树中的最长交错路径
给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：
选择二叉树中 任意 节点和一个方向（左或者右）。
如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
改变前进方向：左变右或者右变左。
重复第二步和第三步，直到你在树中无法继续移动。
交错路径的长度定义为：访问过的节点数目 – 1（单个节点的路径长度为 0 ）。
请你返回给定树中最长 交错路径 的长度。
示例 1：
输入：root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
输出：3
解释：蓝色节点为树中最长交错路径（右 -> 左 -> 右）。
示例 2：
输入：root = [1,1,1,null,1,null,null,1,1,null,1]
输出：4
解释：蓝色节点为树中最长交错路径（左 -> 右 -> 左 -> 右）。
示例 3：
输入：root = [1]
输出：0
思路：
dfs。在搜索过程中分别记录从每个结点结点点开始向左走、向右走以及从该节点的子节点开始走的最长路径。
某个结点的最长交错路径 = max(以该结点为起始点往左走的最长交错路径，以该结点为起始点往右走的最长交错路径，左右子结点的最长交错路径中的最大值)。
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution: def help(self, root: TreeNode): if not root: return (0, 0, 0) l, r, d= 0, 0, 0 # 分别表示该节点开始向左走、向右走以及从该节点的子节点开始走的最长路径 if root.left: tmp = self.help(root.left) l = tmp[1] + 1 # 左子结点再向右走的最长路径 d = max(tmp) # d表示不考虑根结点，只考虑左右子结点的结果 if root.right: tmp = self.help(root.right) r = tmp[0] + 1 # 右子结点再向左走的最长路径 d = max(d, max(tmp)) return (l, r, d) def longestZigZag(self, root: TreeNode) -> int: l, r, d = self.help(root) return max(l, r, d) |
第四题：二叉搜索子树的最大键值和
给你一棵以 root 为根的 二叉树 ，请你返回 任意 二叉搜索子树的最大键值和。
二叉搜索树的定义如下：
任意节点的左子树中的键值都 小于 此节点的键值。
任意节点的右子树中的键值都 大于 此节点的键值。
任意节点的左子树和右子树都是二叉搜索树。
示例 1：
输入：root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
输出：20
解释：键值为 3 的子树是和最大的二叉搜索树。
示例 2：
输入：root = [4,3,null,1,2]
输出：2
解释：键值为 2 的单节点子树是和最大的二叉搜索树。
示例 3：
输入：root = [-4,-2,-5]
输出：0
解释：所有节点键值都为负数，和最大的二叉搜索树为空。
示例 4：
输入：root = [2,1,3]
输出：6
示例 5：
输入：root = [5,4,8,3,null,6,3]
输出：7
思路：
二叉搜索树🌲具有以下重要性质：如果一棵树为二叉搜索树，则它的左右子树也为二叉搜索树。
dfs。在遍历每个结点是时分别计算：该树的最小值，该树的最大值，该树的键值和，该树是否为二叉搜索树。
其中，该树的最小值 = min(左子树的最小值,右子树的最小值,根结点的值)。
该树的最大值 = max(左子树的最大值,右子树的最大值,根结点的值)。
该树的键值和 = sum(左子树的键值和,右子树的键值和,根结点的值)。
该树是否为二叉搜索树 = 左子树是否为二叉搜索树 and 右子树是否为二叉搜索树 and 左子树的最大值小于根结点 and 右子树的最小值大于根结点。
用全局变量ans记录二叉搜索树的最大键值和，如果搜索🔍过程中找到一棵二叉搜索树，且其键值和大于ans，则更新ans。
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
class Solution: def dfs(self, root: TreeNode): assert root min_root = root.val max_root = root.val sum_root = root.val is_search_tree = True if root.left: min_left, max_left, sum_left, is_search_tree_left = self.dfs(root.left) min_root = min(min_root, min_left) max_root = max(max_root, max_left) sum_root += sum_left if max_left >= root.val or not is_search_tree_left: is_search_tree = False if root.right: min_right, max_right, sum_right, is_search_tree_right = self.dfs(root.right) min_root = min(min_root, min_right) max_root = max(max_root, max_right) sum_root += sum_right if min_right <= root.val or not is_search_tree_right: is_search_tree = False if is_search_tree: self.ans = max(self.ans, sum_root) # print(root.val, sum_root) return min_root, max_root, sum_root, is_search_tree def maxSumBST(self, root: TreeNode) -> int: self.ans = 0 if not root: return 0 self.dfs(root) return self.ans |
