Easy

题目描述

给你一个仅由数字 6 和 9 组成的正整数 num。

你最多只能改变一个数字，将 6 变成 9，或者把 9 变成 6。

请返回你能得到的最大数字。

示例 1：

输入：num = 9669
输出：9969
解释：
改变第一位数字可以得到 6669。
改变第二位数字可以得到 9969。
改变第三位数字可以得到 9699。
改变第四位数字可以得到 9666。
其中最大的数字是 9969。

示例 2：

输入：num = 9996
输出：9999
解释：将最后一位 6 改为 9 可以得到最大数字。

示例 3：

输入：num = 9999
输出：9999
解释：不需要改变就已经是最大数字了。

提示：

  • 1 <= num <= 10^4
  • num 仅由数字 6 和 9 组成

解题思路

这是一道贪心算法的经典题目。我们的目标是通过最多改变一个数字来获得最大值。

核心思路： 由于我们想要得到最大的数字，应该优先让高位变得更大。因为数字 9 > 6，所以我们应该：

  1. 从左到右遍历数字的每一位
  2. 找到第一个数字 6，将其改为 9
  3. 如果没有找到 6，说明所有位都是 9，无需改变

为什么这样是最优的？

  • 高位的权重更大，改变高位对结果的影响最大
  • 6 改为 9 能增加数值，而 9 改为 6 会减少数值
  • 由于只能改变一位，我们应该选择影响最大的那一位

实现方法：

  1. 字符串转换法：将数字转为字符串，从左到右找第一个 ‘6’ 并替换为 ‘9’
  2. 数学计算法：通过数学运算找到第一个 6 的位置并计算新值
  3. 暴力枚举法：尝试改变每一位，比较所有可能的结果

推荐使用字符串转换法，代码简洁易懂。

代码实现

class Solution {
public:
    int maximum69Number (int num) {
        string s = to_string(num);
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '6') {
                s[i] = '9';
                break;
            }
        }
        return stoi(s);
    }
};

class Solution:
    def maximum69Number (self, num: int) -> int:
        s = str(num)
        # 找到第一个6并替换为9
        return int(s.replace('6', '9', 1))

public class Solution {
    public int Maximum69Number (int num) {
        string s = num.ToString();
        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '6') {
                s = s.Substring(0, i) + '9' + s.Substring(i + 1);
                break;
            }
        }
        return int.Parse(s);
    }
}

var maximum69Number = function(num) {
    let s = num.toString();
    for (let i = 0; i < s.length; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n)n 为数字的位数，最多遍历一次所有位数
空间复杂度O(n)需要存储字符串形式的数字