You are given a very large integer n, represented as a string, and an integer digit x. The digits in n and the digit x are in the inclusive range [1, 9], and n may represent a negative number.
You want to maximize n‘s numerical value by inserting x anywhere in the decimal representation of n. You cannot insert x to the left of the negative sign.
- For example, if
n = 73andx = 6, it would be best to insert it between7and3, makingn = 763. - If
n = -55andx = 2, it would be best to insert it before the first5, makingn = -255.
Return a string representing the maximum value of n after the insertion.
Example 1:
Input: n = "99", x = 9 Output: "999" Explanation: The result is the same regardless of where you insert 9.
Example 2:
Input: n = "-13", x = 2
Output: "-123"
Explanation: You can make n one of {-213, -123, -132}, and the largest of those three is -123.
Constraints:
1 <= n.length <= 1051 <= x <= 9- The digits in
n are in the range[1, 9]. nis a valid representation of an integer.- In the case of a negative
n, it will begin with'-'.
Solution: Greedy
Find the best position to insert x. For positive numbers, insert x to the first position i such that s[i] < x or s[i] > x for negatives.
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { public: string maxValue(string n, int x) { const int l = n.length(); if (n[0] == '-') { for (int i = 1; i <= l; ++i) if (i == l || n[i] - '0' > x) return n.substr(0, i) + static_cast<char>('0' + x) + n.substr(i); } else { for (int i = 0; i <= l; ++i) if (i == l || x > n[i] - '0') return n.substr(0, i) + static_cast<char>('0' + x) + n.substr(i); } return ""; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment