LeetCode 第21场双周赛

这周题目有点多。。周赛、双周赛还有每日一题。。做的慢有点做不过来了

第一题:上升下降字符串

  给你一个字符串 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”

思路:
  统计每个小写字母的个数,然后从前往后再从后往前依次取即可。

代码:

第二题:每个元音包含偶数次的最长子字符串

  给你一个字符串 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个元音字母aeiou,出现的次数要么为奇数次,要么为偶数次。因此总共有2^5=32种状态。
  统计从开头开始到位置i每个字母的数量,用0-31分别表示每个位置的状态。
  状态相同的两个位置之间元音字母必然出现偶数次,从开头到状态为0的位置字母必然出现偶数次。
  记录每种状态status的最早出现位置firsts[status]和最后出现位置lasts[status]
  维护一个全局变量ans,遍历每种状态,当lasts[status]firsts[status]均存在且lasts[status] - firsts[status] > ans时更新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(以该结点为起始点往左走的最长交错路径以该结点为起始点往右走的最长交错路径左右子结点的最长交错路径中的最大值)。

代码:

第四题:二叉搜索子树的最大键值和

  给你一棵以 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
   代码:

发表评论

电子邮件地址不会被公开。 必填项已用*标注