1903-字符串中的最大奇数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:30 2023-09-13 16:06:30 Updated    

给你一个字符串 num ，表示一个大整数。请你在字符串 num 的所有 非空子字符串 中找出 值最大的奇数
，并以字符串形式返回。如果不存在奇数，则返回一个空字符串 __"" __ 。

子字符串 是字符串中的一个连续的字符序列。

示例 1：

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

示例 2：

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

示例 3：

**输入：** num = "35427"
**输出：** "35427"
**解释：** "35427" 本身就是一个奇数。

提示：

  • 1 <= num.length <= 105
  • num 仅由数字组成且不含前导零

方法一：贪心

思路与算法

首先，如果 num 中不含有值为奇数的字符，那么 num 的任何子串的值都不可能是奇数，此时应返回空字符串 “”。

下面考虑 num 中含有值为奇数的字符的情况。假设 num}[j] 的数值是奇数，那么所有以 num}[j] 结尾的子串的数值都是奇数。由于 num 不含前导零，且在子串中前缀 num}[0..j+1] 的长度最长，因此这些子串中数值最大的为 num}[0..j+1]。

我们假设 num 中最后一个值为奇数的字符的下标为 j_0，那么对于任意值为奇数的下标 j，一定有 j \le j_0，即 num}[0..j_0+1] 的长度一定大于等于 num}[0..j_0+1] 的长度。同时，上述两个子串均不含前导零。那么，num 中值为奇数且值最大的子字符串即为 num}[0..j_0+1]。

我们从右到左遍历 num 中的字符，当遍历到第一个值为奇数的字符时，我们假设它的下标为 i，此时子字符串 num}[0..i+1] 即为值为奇数且值最大的子字符串，我们返回该子字符串作为答案。而如果 num 中不存在值为奇数的字符，我们则返回空字符串 “”。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string largestOddNumber(string num) {
        int n = num.size();
        for (int i = n - 1; i >= 0; --i){
            if ((num[i] - '0') % 2 == 1){
                // 找到第一个值为奇数的字符，返回 num[0:i+1]
                return num.substr(0, i + 1);
            }
        }
        // 未找到值为奇数的字符，返回空字符串
        return "";
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
class Solution:
    def largestOddNumber(self, num: str) -> str:
        n = len(num)
        for i in range(n - 1, -1, -1):
            if int(num[i]) % 2 == 1:
                # 找到第一个值为奇数的字符，返回 num[0:i+1]
                return num[:i+1]
        # 未找到值为奇数的字符，返回空字符串
        return ""

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 num 的长度。遍历字符串和返回符合要求子串的时间复杂度均为 O(n)。

  • 空间复杂度：O(1)，输出字符串不计入空间复杂度。

 Comments
On this page
1903-字符串中的最大奇数