leetcode 第 311 场算法比赛

零、背景

这次比赛是面试题，手速拼不过大家了。

一、最小偶倍数

题意：给你一个正整数 n ，返回 2 和 n 的最小公倍数（正整数）。

思路：偶数是自己，奇数乘二。

二、最长的字母序连续子字符串的长度

题意：给一个字符串，求最长的字母连续的子字符串。

思路：记录上个字母为结尾的最优答案。
当前字母连续了，最优答案加一，否则最优答案置为一。

三、反转二叉树的奇数层

题意：给一个完全二叉树，反转奇数层的节点。

思路1：树转数组，奇数层反转，数组转树。

思路2：递归转换。

假设两个子树的根节点需要交换，则根的儿子不能交换。
所以，交换根之后，四个儿子需要交换回原来的位置，即左儿子与左儿子交换，右儿子与右儿子交换。

儿子的位置需要保持不动，儿子的儿子就需要进行交换。

四、字符串的前缀分数和

题意：给一个字符串数组，求每个字符串所有前缀子串的得分和。
字符串的得分：以字符串为前缀的字符串个数。

思路：题目有点绕，相当于求两层前缀。

暴力做法：枚举所有前缀，然后循环判断这个前缀是不是其他字符串的前缀。

trie 树做法：
建树，每个节点记录前缀的个数，记为 k。
查询：查询的路径上的 k 求和。

五、最后

这次比赛比较简单。

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code