1903. 字符串中的最大奇数

🟢   🔖  贪心 数学 字符串  🔗 力扣 LeetCode

题目

You are given a string num, representing a large integer. Return _thelargest-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 <= 10^5
• num only consists of digits and does not contain any leading zeros.

题目大意

给你一个字符串 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[i] % 2 == 1），说明从字符串开头到 i 的部分是满足条件的最长前缀，直接使用 slice(0, i + 1) 截取从起始到索引 i（包括 i）的子字符串返回。
• 如果没有找到奇数，说明整个字符串没有奇数，返回空字符串。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度，遍历字符串一次。
• 空间复杂度：O(n)，使用了 slice 方法生成子字符串，最坏情况下长度为 n。

代码

/**
 * @param {string} num
 * @return {string}
 */
var largestOddNumber = function (num) {
	// 从后往前遍历，找到最后一个奇数
	for (let i = num.length - 1; i >= 0; i--) {
		if (Number(num[i]) % 2 == 1) {
			return num.slice(0, i + 1);
		}
	}
	// 如果没有奇数，返回空字符串
	return '';
};

相关题目

题号	标题	题解	标签	难度	力扣
2264	字符串中最大的 3 位相同数字	[✓]	字符串	🟢	🀄️ 🔗