1903. 字符串中的最大奇数 #

• 标签：贪心、数学、字符串
• 难度：简单

题目大意 #

描述：给定一个字符串 $num$，表示一个大整数。

要求：在字符串 $num$ 的所有非空子字符串中找出值最大的奇数，并以字符串形式返回。如果不存在奇数，则返回一个空字符串 ""。

说明：

• 子字符串：指的是字符串中一个连续的字符序列。
• $1 \le num.length \le 10^5$
• $num$ 仅由数字组成且不含前导零。

示例：

• 示例 1：

1
2
3

输入：num = "52"
输出："5"
解释：非空子字符串仅有 "5"、"2" 和 "52" 。"5" 是其中唯一的奇数。

• 示例 2：

1
2
3

输入：num = "4206"
输出：""
解释：在 "4206" 中不存在奇数。

解题思路 #

思路 1：贪心算法 #

如果某个数 $x$ 为奇数，则 $x$ 末尾位上的数字一定为奇数。那么我们只需要在末尾为奇数的字符串中考虑最大的奇数即可。显而易见的是，最大的奇数一定是长度最长的那个。所以我们只需要逆序遍历字符串，找到第一个奇数，从整个字符串开始位置到该奇数位置所代表的整数，就是最大的奇数。具体步骤如下：

1. 逆序遍历字符串 $s$。
2. 找到第一个奇数位置 $i$，则 $num[0: i + 1]$ 为最大的奇数，将其作为答案返回。

思路 1：代码 #

1
2
3
4
5
6

class Solution:
    def largestOddNumber(self, num: str) -> str:
        for i in range(len(num) - 1, -1, -1):
            if int(num[i]) % 2 == 1:
                return num[0: i + 1]
        return ""

思路 1：复杂度分析 #

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。