Last Updated on 2023-12-07 by Clay
題目
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.
返回字串中最長的奇數子序列，比方說 4206 就是無，而 35427 就是 35427 本身。
解題思路
我們可以將這個題目轉換成另外一個視角：什麼是奇數？那就是結尾數字並非 0, 2, 4, 6, 8 的其他數值，就會是奇數。
所以我們要做的事情非常簡單，就是從字串的結尾處開始向開頭找，找到第一個奇數的位置，直接做字串的 slicing。
C++ 範例程式碼
class Solution {
public:
string largestOddNumber(string num) {
// Init
int tail = 0;
unordered_map<char, bool> isEven({
{'0', true},
{'2', true},
{'4', true},
{'6', true},
{'8', true},
});
// Count from the tail
for (int i=num.size()-1; i>=0; --i) {
if (!isEven[num[i]]) {
tail = i + 1;
break;
}
}
return num.substr(0, tail);
}
};Python 範例程式碼
class Solution:
def largestOddNumber(self, num: str) -> str:
# Init
tail = 0
evens = {
'0': True,
'2': True,
'4': True,
'6': True,
'8': True,
}
# Count from tail
for i in range(len(num)-1, -1, -1):
if not evens.get(num[i], False):
tail = i + 1
break
return num[:tail]