583，字符串中的最大奇数

Original 博哥数据结构和算法 2022-05-19

If you want to understand today , you have to search yesterday.

如果你想参透今天，就必须探究昨天。

问题描述

来源：LeetCode第1903题

难度：简单

给你一个字符串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 仅由数字组成且不含前导零

问题分析

这题是让在字符串num的所有非空子串中找出最大的奇数。我们知道只有个位数是奇数（比如1，3，5，7，9），这个数才可能是奇数，如果个位数是偶数，前面无论怎么截取，最终还是偶数。所以如果想把一个数字变为奇数，唯一能改变的就是他的个位数，所以这题思路就很简单了

先判断字符串num最右边的数字是否是奇数：

如果是奇数直接返回
如果不是奇数在判断他的倒数第2位是不是奇数，如果是奇数就从前面截取，如果不是就继续判断倒数第3位……

看下代码

1public String largestOddNumber(String num) {
2    for (int i = num.length() - 1; i >= 0; i--) {
3        //判断最后一个数字是否是奇数，如果是奇数直接截取返回
4        if (((num.charAt(i) - '0') & 1) == 1)
5            return num.substring(0, i + 1);
6    }
7    return "";
8}