我的解题思路与分析
在 HarmonyOS 应用开发者高级认证考试 时,我遇到了这道题目。它是一道经典的字符串处理问题,要求我们从给定字符串中找出 最长的元音子串长度。当时我的第一反应是,这题考察的是对字符串连续性问题的处理能力以及代码的优化设计。以下是我在考试中的完整思路和解题过程。
理解题目需求
拿到题目后,我先快速梳理了一下要求,并明确了以下关键点:
- 元音字符:包括
a, e, i, o, u
和它们的大写版本A, E, I, O, U
。 - 子串的定义:子串必须是连续的字符序列,这意味着如果中间出现非元音字符,连续性就会被打断。
- 性能要求:字符串长度可能达到 65,535,这是一个非常大的数据规模。因此,算法必须具有较低的时间复杂度,最好在一次遍历中完成。
基于这些分析,我迅速确定了一个基本思路:采用 线性遍历(O(n)) 来处理这个问题,这样可以在高效完成任务的同时保证代码逻辑的简洁性。
设计解法
在设计算法时,我的主要思路是动态记录 当前连续元音长度 和 最长元音长度:
维护两个变量:
currentLength
:用于记录当前连续的元音子串长度。maxLength
:用于存储在遍历过程中发现的最长元音子串长度。
判断字符是否为元音:
- 使用一个
Set
数据结构存储所有元音字符。相比数组,Set
的查找效率更高(时间复杂度 $O(1)$),可以更快速判断一个字符是否为元音。
- 使用一个
遍历逻辑:
遍历字符串中的每一个字符:
- 如果字符是元音,则将
currentLength
加 1; - 如果字符不是元音,则更新
maxLength
,并将currentLength
重置为 0。
- 如果字符是元音,则将
返回结果:
- 遍历结束后,
maxLength
中存储的就是字符串中的最长元音子串长度。
- 遍历结束后,
代码实现
以下是我在考试中编写的代码:
function doFunc(s) {
let maxLength = 0; // 记录最长元音子串的长度
let currentLength = 0; // 当前连续元音子串的长度
const vowels = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']); // 定义元音集合
// 遍历字符串
for (let i = 0; i < s.length; i++) {
if (vowels.has(s.charAt(i))) {
// 当前字符是元音
currentLength++; // 增加当前连续元音长度
maxLength = Math.max(maxLength, currentLength); // 更新最大值
} else {
// 当前字符不是元音
currentLength = 0; // 重置当前长度
}
}
return maxLength; // 返回最长元音子串长度
}
输入与输出
考试中,题目要求我们通过标准输入输出完成交互,因此我补充了以下代码来读取输入并输出结果:
process.stdin.resume();
process.stdin.setEncoding("utf8");
let input = "";
process.stdin.on("data", (data) => {
input += data;
});
process.stdin.on("end", () => {
let inputArray = input.split("\n");
let inputString = inputArray[0];
let result = doFunc(inputString); // 调用核心函数
console.log(result); // 输出结果
process.exit();
});
我的分析与总结
为什么这个解法是最优的?
时间复杂度:
- 这个算法只需要遍历字符串一次,时间复杂度为 $O(n)$,非常高效。
- 判断一个字符是否为元音时,使用了
Set
数据结构,其查找时间复杂度为 $O(1)$。
空间复杂度:
- 除了元音集合和几个变量外,没有额外的内存开销,空间复杂度为 $O(1)$。
逻辑清晰:
整个代码逻辑非常简单:一个遍历 + 两个变量的维护。即便是面对长度很大的字符串,也能高效运行,同时代码简洁易懂,便于维护。
测试用例分析
在考试过程中,我也在心中模拟了一些测试用例来验证代码的正确性:
普通场景:
输入:
"hellothere"
- 输出:
2
(最长元音子串为"e"
)。
- 输出:
输入:
"beautifulday"
- 输出:
5
(最长元音子串为"eau"
)。
- 输出:
边界场景:
输入:
"aaaaa"
- 输出:
5
(整个字符串都是元音)。
- 输出:
输入:
"bcdfg"
- 输出:
0
(没有元音)。
- 输出:
特殊场景:
输入:
"AeiOU"
- 输出:
5
(元音子串为整个字符串,大小写不敏感)。
这些测试用例覆盖了各种情况,验证了代码的正确性和鲁棒性。
- 输出:
考试中的心得与总结
在考试中,我通过这道题认识到以下几点:
需求分析的重要性:
- 拿到题目后,我第一时间认真拆解了需求,避免了方向性错误。这让我能快速确定高效的解决方案。
选择合适的数据结构:
- 使用
Set
存储元音字符,提高了判断效率。
- 使用
性能意识:
- 考虑到输入规模,我设计了时间复杂度为 $O(n)$ 的解法,既高效又简洁。
最终,我的代码顺利通过了这道题,进一步让我体会到在面对复杂问题时,保持冷静、细致分析的重要性。