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 <= 105numonly consists of digits and does not contain any leading zeros.
Solution: Find right most odd digit
We just need to find the right most digit that is odd, answer will be num[0:r].
Answer must start with num[0].
Proof:
Assume the largest number is num[i:r] i > 0, we can always extend to the left, e.g. num[i-1:r] which is also an odd number and it’s larger than num[i:r] which contradicts our assumption. Thus the largest odd number (if exists) must start with num[0].
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 |
// Author: Huahua class Solution { public: string largestOddNumber(string num) { for (int i = num.length() - 1; i >= 0; --i) if ((num[i] - '0') & 1) return num.substr(0, i + 1); return ""; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment