力扣每日一题1月8号 字符串中最大的3位相同数字解析

字符串中最大的3位相同数字解析

在本文中，我们将深入解析LeetCode第2264题：“字符串中最大的3位相同数字”。我们将从代码的语法入手，逐步理解解决问题的方法，并通过一道例题来巩固所学知识。最后，我们将提供完整的Python代码实现。

题目描述

给你一个字符串 num ，表示一个大整数。如果一个整数满足下述所有条件，则认为该整数是一个 优质整数：

1. 该整数是 num 的一个长度为3的子字符串。
2. 该整数由唯一一个数字重复3次组成。

以字符串形式返回 最大的优质整数。如果不存在满足要求的整数，则返回一个空字符串 ""。

注意：

• 子字符串是字符串中的一个连续字符序列。
• num 或优质整数中可能存在前导零。

示例

示例1：

输入：num = "6777133339"
输出："777"
解释：num 中存在两个优质整数："777" 和 "333"。
"777" 是最大的那个，所以返回 "777"。

示例2：

输入：num = "2300019"
输出："000"
解释："000" 是唯一一个优质整数。

示例3：

输入：num = "42352338"
输出：""
解释：不存在长度为3且仅由一个唯一数字组成的整数。因此，不存在优质整数。

解题思路

这道题的核心在于寻找字符串中所有连续三个相同的数字，并从中选取最大的一个。我们可以使用 双指针 的方法来高效地解决这个问题。

代码语法解析

让我们逐行解析提供的Python代码，以理解其工作原理。

class Solution:
    def largestGoodInteger(self, num: str) -> str:
        i, n = 0, len(num)
        res = []
        
        while i < n:
            j = i + 1
            while j < n and num[i] == num[j]:
                j += 1
                if j - i == 3:
                    res.append(num[i:j])
            i = j
        
        if not res:
            return ""
        else:
            max_num = max(int(x) for x in res)
            return str(max_num) if max_num != 0 else '000'

1. 类和方法定义

class Solution:
    def largestGoodInteger(self, num: str) -> str:

• class Solution:: 定义一个名为 Solution 的类，这是LeetCode提交代码的标准格式。
• def largestGoodInteger(self, num: str) -> str:: 定义一个名为 largestGoodInteger 的方法，接受一个字符串 num 作为输入，并返回一个字符串。

2. 初始化变量

i, n = 0, len(num)
res = []

• i, n = 0, len(num): 初始化指针 i 为0，n 为字符串 num 的长度。
• res = []: 初始化一个空列表 res，用于存储所有符合条件的优质整数。

3. 主循环：遍历字符串

while i < n:
    j = i + 1
    while j < n and num[i] == num[j]:
        j += 1
        if j - i == 3:
            res.append(num[i:j])
    i = j

• while i < n:: 使用指针 i 遍历字符串，直到 i 达到字符串末尾。

  • j = i + 1: 初始化另一个指针 j，指向 i 的下一个位置，用于查找连续相同的数字。

  • while j < n and num[i] == num[j]:: 当 j 未超出字符串范围且 num[j] 与 num[i] 相同时，继续移动指针 j。

    • j += 1: 移动指针 j 到下一个位置。

    • if j - i == 3:: 检查从 i 到 j 的子字符串长度是否为3。

      • res.append(num[i:j]): 如果满足条件，将该子字符串加入结果列表 res。

  • i = j: 将指针 i 更新为 j，跳过已经检查过的部分，继续寻找下一个可能的优质整数。

4. 结果处理

if not res:
    return ""
else:
    max_num = max(int(x) for x in res)
    return str(max_num) if max_num != 0 else '000'

• if not res:: 如果结果列表 res 为空，说明没有找到任何优质整数，返回空字符串 ""。

• else:: 否则，执行以下操作：

  • max_num = max(int(x) for x in res): 将 res 中的所有字符串转换为整数，并找出最大的一个。

  • return str(max_num) if max_num != 0 else '000':

    • 如果最大的数字不为0，返回其字符串形式。
    • 如果最大的数字为0，返回字符串 '000'，以保留前导零。

代码实现

综合以上解析，以下是完整的Python代码实现：

class Solution:
    def largestGoodInteger(self, num: str) -> str:
        i, n = 0, len(num)
        res = []
        
        while i < n:
            j = i + 1
            while j < n and num[i] == num[j]:
                j += 1
                if j - i == 3:
                    res.append(num[i:j])
            i = j
        
        if not res:
            return ""
        else:
            max_num = max(int(x) for x in res)
            return str(max_num) if max_num != 0 else '000'

例题解析

让我们通过一道例题来应用上述代码，并加深理解。

例题

输入：

num = "999888777666555444333222111000"

期望输出：

"999"

解析

根据题目要求，我们需要找到所有长度为3且由相同数字组成的子字符串，并返回其中最大的一个。

• 遍历字符串：

  • “999”：符合条件，加入 res。
  • “888”：符合条件，加入 res。
  • “777”：符合条件，加入 res。
  • “666”：符合条件，加入 res。
  • “555”：符合条件，加入 res。
  • “444”：符合条件，加入 res。
  • “333”：符合条件，加入 res。
  • “222”：符合条件，加入 res。
  • “111”：符合条件，加入 res。
  • “000”：符合条件，加入 res。

• 结果列表 res：

  ["999", "888", "777", "666", "555", "444", "333", "222", "111", "000"]
  

• 找到最大的数字：

  max_num = 999
  

• 返回结果：

  "999"
  

执行代码

使用上述代码执行该例题：

solution = Solution()
print(solution.largestGoodInteger("999888777666555444333222111000"))  # 输出: "999"

输出：

999