Easy

题目描述

给你一个字符串 num，表示一个大整数。返回 num 中最大的奇数（作为字符串），如果不存在奇数，则返回空字符串 ""。

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

示例 1：

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

示例 2：

输入：num = "4206"
输出：""
解释："4206" 中没有奇数。

示例 3：

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

约束条件：

  • 1 <= num.length <= 10^5
  • num 只包含数字且不包含前导零

提示：

  • 你应该按什么顺序遍历数字？
  • 如果存在奇数，这个数字必须从哪里开始？

解题思路

解题思路

这道题的关键在于理解奇数的性质：一个数是奇数当且仅当它的最后一位数字是奇数。

基于这个性质，我们可以得出以下重要结论：

  1. 要找最大的奇数子字符串，我们需要找到字符串中最右边的奇数字符
  2. 一旦找到最右边的奇数字符，那么从字符串开头到这个字符的整个子字符串就是答案

算法步骤：

  1. 从字符串的右端开始向左遍历
  2. 找到第一个奇数字符（1, 3, 5, 7, 9）
  3. 返回从字符串开头到这个奇数字符的子字符串
  4. 如果没有找到奇数字符，返回空字符串

为什么这样做是正确的？

  • 如果存在奇数子字符串，那么包含最右边奇数字符的子字符串一定是最大的
  • 因为我们希望数字尽可能大，所以应该包含尽可能多的前导数字
  • 从开头到最右边奇数字符的子字符串既保证了是奇数，又保证了是最大的

时间复杂度：O(n)，只需要一次遍历 空间复杂度：O(1)，除了返回的子字符串外不需要额外空间

代码实现

class Solution {
public:
    string largestOddNumber(string num) {
        for (int i = num.length() - 1; i >= 0; i--) {
            if ((num[i] - '0') % 2 == 1) {
                return num.substr(0, i + 1);
            }
        }
        return "";
    }
};

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[:i + 1]
        return ""

public class Solution {
    public string LargestOddNumber(string num) {
        for (int i = num.Length - 1; i >= 0; i--) {
            if ((num[i] - '0') % 2 == 1) {
                return num.Substring(0, i + 1);
            }
        }
        return "";
    }
}

/**
 * @param {string} num
 * @return {string}
 */
var largestOddNumber = function(num) {
    for (let i = num.length - 1; i >= 0; i--) {
        if (parseInt(num[i]) % 2 === 1) {
            return num.substring(0, i + 1);
        }
    }
    return "";
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)最坏情况下需要遍历整个字符串
空间复杂度O(1)只使用常数级别的额外空间

相关题目