LeetCode 题解工作台
6 和 9 组成的最大数字
给你一个仅由数字 6 和 9 组成的正整数 num 。 你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成 6 。 请返回你可以得到的最大数字。 示例 1： 输入： num = 9669 输出： 9969 解释： 改变第一位数字可以得到 6669 。 改变第二位数字可以得到 9969 。 改…
2
题型
8
代码语言
3
相关题
当前训练重点
简单 · 贪心·invariant
答案摘要
我们将数组转换为字符串，然后从左到右遍历字符串，找到第一个出现的 ，将其替换为 ，然后返回转换后的字符串对应的整数即可。 时间复杂度 $O(\log \textit{num})$，空间复杂度 $O(\log \textit{num})$。其中 为给定的整数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个仅由数字 6 和 9 组成的正整数 num。
你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成 6 。
请返回你可以得到的最大数字。
示例 1：
输入：num = 9669 输出：9969 解释： 改变第一位数字可以得到 6669 。 改变第二位数字可以得到 9969 。 改变第三位数字可以得到 9699 。 改变第四位数字可以得到 9666 。 其中最大的数字是 9969 。
示例 2：
输入：num = 9996 输出：9999 解释：将最后一位从 6 变到 9，其结果 9999 是最大的数。
示例 3：
输入：num = 9999 输出：9999 解释：无需改变就已经是最大的数字了。
提示：
1 <= num <= 10^4num每一位上的数字都是 6 或者 9 。
解题思路
方法一：贪心
我们将数组转换为字符串，然后从左到右遍历字符串，找到第一个出现的 ，将其替换为 ，然后返回转换后的字符串对应的整数即可。
时间复杂度 ，空间复杂度 。其中 为给定的整数。
class Solution:
def maximum69Number(self, num: int) -> int:
return int(str(num).replace("6", "9", 1))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate demonstrates understanding of greedy strategy.
- question_mark
Candidate correctly identifies the most impactful digit to change.
- question_mark
Candidate handles edge cases like when the number consists only of 9's.
常见陷阱
外企场景- error
Forgetting to check if there are any 6's to flip before making a change.
- error
Not handling the case where the number consists entirely of 9's.
- error
Changing more than one digit when the problem allows only one change.
进阶变体
外企场景- arrow_right_alt
What if the number contains other digits aside from 6 and 9? This variant tests the candidate's ability to handle different digit sets.
- arrow_right_alt
Changing the problem's constraints to allow multiple changes rather than one can shift the approach towards a more complex greedy strategy.
- arrow_right_alt
Increasing the size of the number can test the candidate's efficiency in terms of both time and space complexity.