您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

LeetCode C++ 1881. Maximum Value after Insertion【贪心/字符串】

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 = 73 and x = 6, it would be best to insert it between 7 and 3, making n = 763.
  • If n = -55 and x = 2, it would be best to insert it before the first 5, making n = -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 <= 105
  • 1 <= x <= 9
  • The digits in n​​​ are in the range [1, 9].
  • n is a valid representation of an integer.
  • In the case of a negative n,​​​​​​ it will begin with '-'.

题意:给你一个非常大的整数 n 和一个整数数字 x ,大整数 n 用一个字符串表示。n 中每一位数字和数字 x 都处于闭区间 [1, 9] 中,且 n 可能表示一个 负数

你打算通过在 n 的十进制表示的任意位置插入 x最大化 n数值 ​​​​​​。但 不能 在负号的左边插入 x 。返回插入操作后,用字符串表示的 n 的最大值。


解法 贪心

贪心的插入字符串 xn 中。具体来说,当 n 是正数的时候,要使得结果最大,就必须从高位到低位(从左到右)遍历,遇到一个字符小于 x 时,将 x 插入到该位置;如果字符等于 x ,不确定后面有无小于 x 的字符(有的话应该插入那个位置,插入此处可能使得整个数变小),因此不插入;如果到末尾都没有这种字符,则插到字符串结尾。

n 是负数时,要使得结果最大,就必须从高位到低位(从左到右从 1 下标开始)遍历,遇到一个字符大于 x 时,将 x 插入到该位置;如果字符等于 x ,不确定后面有无大于 x 的字符(有的话应该插入那个位置,插入此处可能使得整个数变小),因此不插入;如果到末尾都没有这种字符,则插到字符串结尾。

不过上述做法都局限于 x 只有一位数的情况,当 x 也是一个超过一位数的整数时,代码应该这样写:

class Solution {
public:
    string maxValue(string n, int x) {
        string sx = to_string(x);
        bool flag = n[0] == '-';
        int xl = sx.size(), i = flag;
        for (int nl = n.size(); i < nl; ++i) {
            string s = n.substr(i, xl);
            if ((flag && s > sx) || (!flag && s < sx))
                return n.substr(0, i) + sx + n.substr(i); //负数
        }
        return n + sx;
    }
};

运行效率如下:

执行用时:84 ms, 在所有 C++ 提交中击败了26.33% 的用户
内存消耗:33.9 MB, 在所有 C++ 提交中击败了51.03% 的用户

由于 x 只有一位数,比较 n[i]x[0] 即可:

class Solution {
public:
    string maxValue(string n, int x) {
        bool flag = n[0] == '-';
        for (int i = flag, nl = n.size(); i < nl; ++i) 
            if ((flag && n[i] > x + '0') || (!flag && n[i] < x + '0'))
                return n.substr(0, i) + to_string(x) + n.substr(i); //负数
        return n + to_string(x);
    }
};

运行效率如下:

执行用时:72 ms, 在所有 C++ 提交中击败了68.40% 的用户
内存消耗:33.4 MB, 在所有 C++ 提交中击败了60.88% 的用户

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进