LeetCode 1323: 6和9组成的最大数字
LeetCode 1323: 6和9组成的最大数字 - 详细解题思路与Python实现
题目描述
给定一个由数字6和9组成的正整数num，你最多只能翻转一位数字，将6变成9，或者将9变成6。返回你可以得到的最大的数字。
示例
输入：num = 9669
输出：9969
解释：改变第一位数字可以得到 6669，改变第二位数字可以得到 9969，改变第三位数字可以得到 9699，改变第四位数字可以得到 9666。
其中最大的数字是 9969。
约束条件
- 1 <= num <= 10^4
- num 仅由数字 6 和 9 组成
解题思路
核心思想
要获得最大的数字，我们需要理解一个关键点：在数字的某一位上，9比6大。因此，如果我们想要通过翻转一位数字来获得最大值，应该将6改为9，而不是将9改为6。
算法步骤
- 将数字转换为字符串：便于逐位处理
- 从左到右遍历每一位：找到第一个6
- 将第一个6改为9：这样能获得最大的数字
- 返回结果：如果没有找到6，说明原数字已经是最大的
为什么这样是正确的？
- 贪心策略：我们总是选择将最左边的6改为9，因为这样能获得最大的数字
- 数学原理：在相同位数的情况下，高位数字越大，整个数字就越大
- 最优性：由于只能翻转一次，将最左边的6改为9是最优选择
代码实现
方法一：逐位遍历
class Solution:def maximum69Number(self, num: int) -> int:"""将数字中的第一个6改为9，以获得最大数字Args:num (int): 输入的正整数，只包含6和9Returns:int: 修改后能得到的最大数字"""# 将数字转换为字符串，便于逐位处理num_str = str(num)# 从左到右遍历每一位数字for i in range(len(num_str)):# 找到第一个6，将其改为9if num_str[i] == '6':# 构造新的字符串：前i位保持不变，第i位改为9，后面保持不变new_num_str = num_str[:i] + '9' + num_str[i+1:]return int(new_num_str)# 如果没有找到6，说明原数字已经是最大的（全是9）return num
方法二：字符串替换
def maximum69Number_alternative(self, num: int) -> int:"""另一种实现方法：使用字符串替换Args:num (int): 输入的正整数，只包含6和9Returns:int: 修改后能得到的最大数字"""# 将数字转换为字符串num_str = str(num)# 使用replace方法，只替换第一个6# 如果字符串中没有6，replace不会做任何改变new_num_str = num_str.replace('6', '9', 1)return int(new_num_str)
复杂度分析
时间复杂度
- O(log n)：其中n是数字的位数
- 我们需要遍历数字的每一位，数字的位数是log₁₀(n)
空间复杂度
- O(log n)：需要存储字符串形式的数字
- 字符串的长度等于数字的位数
测试用例
def test_solution():"""测试函数，验证算法的正确性"""solution = Solution()# 测试用例test_cases = [(9669, 9969), # 标准测试用例(9996, 9999), # 6在最后一位(9999, 9999), # 全是9，无需修改(6666, 9666), # 全是6，修改第一位(6969, 9969), # 6和9交替(6, 9), # 单个数字6(9, 9), # 单个数字9]for i, (input_num, expected) in enumerate(test_cases, 1):result = solution.maximum69Number(input_num)status = "✓" if result == expected else "✗"print(f"测试用例 {i}:")print(f" 输入: {input_num}")print(f" 期望输出: {expected}")print(f" 实际输出: {result}")print(f" 状态: {status}")print("-" * 30)
测试结果
测试用例 1:输入: 9669期望输出: 9969实际输出: 9969状态: ✓测试用例 2:输入: 9996期望输出: 9999实际输出: 9999状态: ✓测试用例 3:输入: 9999期望输出: 9999实际输出: 9999状态: ✓测试用例 4:输入: 6666期望输出: 9666实际输出: 9666状态: ✓测试用例 5:输入: 6969期望输出: 9969实际输出: 9969状态: ✓测试用例 6:输入: 6期望输出: 9实际输出: 9状态: ✓测试用例 7:输入: 9期望输出: 9实际输出: 9状态: ✓
算法优化思路
1. 数学方法优化
如果我们想要进一步优化，可以考虑使用数学方法：
def maximum69Number_math(self, num: int) -> int:"""使用数学方法：找到最高位的6，然后加上相应的差值"""# 找到最高位的6的位置temp = numdigit = 1max_digit = 1while temp > 0:if temp % 10 == 6:max_digit = digittemp //= 10digit *= 10# 如果找到了6，将其改为9if max_digit > 1:return num + 3 * (max_digit // 10)return num
2. 位运算方法（如果适用）
虽然这个题目不直接涉及位运算，但我们可以思考类似的优化思路。
常见错误分析
错误1：将9改为6
# 错误示例
if num_str[i] == '9':new_num_str = num_str[:i] + '6' + num_str[i+1:]return int(new_num_str)
问题：将9改为6会使数字变小，这与我们的目标相反。
错误2：修改多个数字
# 错误示例
for i in range(len(num_str)):if num_str[i] == '6':num_str[i] = '9' # 修改了原字符串
问题：题目要求只能修改一位数字，而且字符串是不可变的。
错误3：不考虑边界情况
# 错误示例
if num_str[0] == '6':return int('9' + num_str[1:])
问题：没有考虑数字只有一位的情况，或者没有6的情况。
总结
这道题目是一个很好的贪心算法入门题，主要考察以下几点：
- 贪心思想：选择最优的局部解
- 字符串处理：熟练使用字符串操作
- 边界情况处理：考虑各种输入情况
- 算法效率：理解时间复杂度和空间复杂度
关键要点
- 贪心策略：总是将最左边的6改为9
- 字符串操作：使用切片操作构造新字符串
- 边界处理：考虑全是9的情况
- 代码简洁性：使用replace方法可以简化代码
这道题目虽然简单，但很好地体现了算法设计中的贪心思想，是学习算法基础的好题目。
标签：#LeetCode #Python #算法 #贪心算法 #字符串处理 #每日一题
相关题目：
- LeetCode 7: 整数反转
- LeetCode 9: 回文数
- LeetCode 12: 整数转罗马数字