[LeetCode] 1903. Largest Odd Number in String

You are given a string num, representing a large integer. Return the largest-valued odd integer (as a string) that is a non-empty substring of num, or an empty string “” if no odd integer exists.

A substring is a contiguous sequence of characters within a string.

Example 1:
Input: num = “52”
Output: “5”
Explanation: The only non-empty substrings are “5”, “2”, and “52”. “5” is the only odd number.

Example 2:
Input: num = “4206”
Output: “”
Explanation: There are no odd numbers in “4206”.

Example 3:
Input: num = “35427”
Output: “35427”
Explanation: “35427” is already an odd number.

Constraints:
1 <= num.length <= 105
num only consists of digits and does not contain any leading zeros.

字符串中的最大奇数。

给你一个字符串 num ,表示一个大整数。请你在字符串 num 的所有 非空子字符串 中找出 值最大的奇数 ,并以字符串形式返回。如果不存在奇数,则返回一个空字符串 “” 。
子字符串 是字符串中的一个连续的字符序列。

思路

思路是贪心。因为只允许删除字符,但是从左往右删除字符是无法改变数字的奇偶性的,所以思路是从右往左遍历 input 字符串,看看最右边一个字符串到底是奇数还是偶数。如果是奇数就可以直接返回了;如果是偶数,则删除当前字符,接着看左边的字符。

复杂度

时间O(n)
空间O(1)

代码

Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public String largestOddNumber(String num) {
int n = num.length();
for (int i = n - 1; i >= 0; i--) {
int d = num.charAt(i) - '0';
if (d % 2 == 1) {
String str = num.substring(0, i + 1);
return str;
}
}
return "";
}
}

[LeetCode] 1903. Largest Odd Number in String
https://shurui91.github.io/posts/399132142.html
Author
Aaron Liu
Posted on
December 7, 2023
Licensed under