HTML5教程

前端工程师的 LeetCode 之旅 - 夜喵专场（21）

本文主要是介绍前端工程师的 LeetCode 之旅 - 夜喵专场（21），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！



01
5336.上升下降字符串



题目描述【Easy】


给你一个字符串 s ，请你根据下面的算法重新构造字符串：
1、从 s 中选出 最小 的字符，将它 接在 结果字符串的后面。
2、从 s 剩余字符中选出 最小 的字符，且该字符比上一个添加的字符大，将它 接在 结果字符串后面。
3、重复步骤 2 ，直到你没法从 s 中选择字符。
4、从 s 中选出 最大 的字符，将它 接在 结果字符串的后面。
5、从 s 剩余字符中选出 最大 的字符，且该字符比上一个添加的字符小，将它 接在 结果字符串后面。
6、重复步骤 5 ，直到你没法从 s 中选择字符。
7、重复步骤 1 到 6 ，直到 s 中所有字符都已经被选过。
在任何一步中，如果最小或者最大字符不止一个 ，你可以选择其中任意一个，并将其添加到结果字符串。
请你返回将 s 中字符重新排序后的 结果字符串 。
示例：
输入：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'



本道题的解法主要涉及以下知识点：

  • JavaScript 的 Map 数据结构

  • JavaScript 常用的 sort 排序方法

题中所说的算法实际上就是：按照奇偶次数不断的将当前字符的递减递增序列插入到结果字符串中。

首先，采用 Map 记录字符串中各个字符的数量。

再通过判断当前次数的奇偶性，获取不同的单调递增递减序列即可解题。




02
元音包含偶数次的最长子字符串



题目描述【Medium】


给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。
示例：
输入：s = 'eleetminicoworoep'
输出：13
解释：最长子字符串是 'leetminicowor' ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。



本道题的解法涉及以下知识点：

  • 剪枝算法（pruning）

  • 位运算

第一种解法：采用暴力枚举的方法，不断验证子字符串是否满足要求。

但是这种方法一般无法 AC ，由于本道题目求解最长子字符串，所以可以过滤掉比当前结果短的子字符串，从而达到剪枝优化的目的。

第二种解法比较巧妙，因为总共 5 种字符（aeiou），并且每一个字符有两种状态，那么一共就是 32 种状态，所以可以采用二进制来存储状态并且通过异或运算符来计算状态。




03
二叉树中最长交叉路径



题目描述【Medium】


给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：
选择二叉树中 任意 节点和一个方向（左或者右）。
如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
改变前进方向：左变右或者右变左。
重复第二步和第三步，直到你在树中无法继续移动。
交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。
请你返回给定树中最长 交错路径 的长度。
示例：
输入：[1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
输出：3
解释：蓝色节点为树中最长交错路径（右 -> 左 -> 右）。



本道题主要考察数据结构 -- 二叉树。

解决本道题的关键在于：

  • 递归遍历的过程中需要记录当前子树的状态（左子树还是右子树），来保证当前路径为交叉路径的合法性

  • 递归遍历的过程中需要记录当前交叉路径的长度，从而比较得出最长长度

递归思想实现的代码可读性非常好，这里不再赘述。




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



题目描述【Hard】


给你一棵以 root 为根的 二叉树 ，请你返回 任意 二叉搜索子树的最大键值和。
二叉搜索树的定义如下：
任意节点的左子树中的键值都 小于 此节点的键值。
任意节点的右子树中的键值都 大于 此节点的键值。
任意节点的左子树和右子树都是二叉搜索树。
示例：
输入：[1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
输出：20
解释：键值为 3 的子树是和最大的二叉搜索树。



本道题考察 BST 相关的特性。

解决本题的套路与第三道题类似：

  • 递归遍历过程中判断当前子树是否为 BST

  • 递归遍历过程中记录当前 BST 的和值

回顾判断子树为 BST 的条件：

  • 左子树为 BST

  • 右子树为 BST

  • 左子树中任意节点都小于此节点的值

  • 右子树中任意节点都大于此节点的值

由上述条件可知，子树是否为一颗 BST 取决于它的左子树和右子树，那么在递归遍历的过程中需要向上返回当前子树的四个状态：

  • 当前子树是否为 BST

  • 当前子树中节点的最小值

  • 当前子树中节点的最大值

  • 当前子树的和值




05
往期精彩回顾









这篇关于前端工程师的 LeetCode 之旅 - 夜喵专场（21）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航