leetcode
leetcode 1701 ~ 1750
字符串中的最大奇数

字符串中的最大奇数

难度:

标签:

题目描述

代码结果

运行时间: 33 ms, 内存: 16.7 MB


/*
 * 题目思路:
 * 使用 Java Stream 实现寻找最大奇数子字符串。
 * 通过过滤和字符串操作,从末尾向前找到第一个奇数子字符串。
 */

import java.util.stream.IntStream;

public class Solution {
    public String largestOddNumber(String num) {
        return IntStream.range(0, num.length())
                .mapToObj(i -> num.substring(0, num.length() - i))
                .filter(s -> (s.charAt(s.length() - 1) - '0') % 2 == 1)
                .findFirst()
                .orElse(""); // 如果没有找到奇数,返回空字符串
    }
}

解释

方法:

这个题解的核心思路是利用一个逆向遍历来找到字符串中最后一个出现的奇数字符。因为最大的奇数子字符串一定以奇数结尾,所以从字符串的末尾向前查找第一个奇数字符是一个高效的策略。一旦找到这样的字符,整个从字符串开头到这个字符的子字符串就是所求的最大奇数子字符串。如果整个字符串中没有奇数字符,则返回空字符串。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在查找最大的奇数子字符串时,选择从后向前遍历而不是从前向后遍历?
在这个特定的问题中,我们的目标是找到最大的奇数子字符串,即以奇数结尾的最长子字符串。从后向前遍历可以直接定位到最后一个奇数字符,这样可以立即确定从字符串开始到这个奇数字符的子字符串就是答案。如果从前向后遍历,我们需要记录每一个奇数字符的位置,并在遍历完成后确定哪一个奇数字符后的部分最长,这增加了复杂性和可能的计算量。
🦆
在确定最大子字符串时,如果字符串中有多个奇数字符,返回整个从开头到最后一个奇数字符的子字符串是否总是正确?
是的,这是正确的。因为问题要求的是最大的奇数子字符串,所以必须包括第一个字符直到最后一个奇数字符。这样的子字符串包含了可能的最长长度,且确保以奇数结尾,符合题目的要求。
🦆
这种方法为什么没有考虑使用额外的数据结构来存储每个奇数的位置,而是直接遍历查找?
使用额外的数据结构存储每个奇数的位置虽然可以在某些情况下加速查找,但会增加空间复杂度。对于本题,单次逆向遍历已足够高效(时间复杂度为O(n),空间复杂度为O(1)),并且实现简单。在大多数情况下,简单的解决方案在保持代码清晰和易于维护方面是更好的选择。
🦆
如果输入字符串非常长,比如接近上限的105个字符,这种单次遍历的策略在性能上表现如何?
单次遍历的策略在性能上表现良好,即使是在输入字符串长度接近上限的情况下。时间复杂度为O(n),意味着处理时间与输入字符串的长度成线性关系。对于长度达到10^5的字符串,这种线性时间复杂度的算法是适合的,因为处理时间仍然在可接受范围内。

相关问题