leetcode
leetcode 1951 ~ 2000
字符串中最大的 3 位相同数字

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

难度:

标签:

题目描述

代码结果

运行时间: 28 ms, 内存: 16.0 MB


/* 
 * 思路:
 * 1. 使用 Java Stream API 遍历字符串 num,检查每一个长度为3的子字符串。
 * 2. 判断子字符串是否由相同的字符组成。
 * 3. 使用 max 方法获取最大的优质整数。
 * 4. 返回最大的优质整数,如果不存在则返回空字符串。
 */
import java.util.Optional;
import java.util.stream.IntStream;

public class Solution {
    public String largestGoodInteger(String num) {
        Optional<String> maxGoodInteger = IntStream.range(0, num.length() - 2)
                .mapToObj(i -> num.substring(i, i + 3))
                .filter(sub -> sub.charAt(0) == sub.charAt(1) && sub.charAt(1) == sub.charAt(2))
                .max(String::compareTo);
        return maxGoodInteger.orElse("");
    }
}

解释

方法:

该题解的思路是从最大的数字9开始,依次检查到最小的数字0,看是否存在由相同的一个数字连续重复三次组成的子字符串。一旦找到这样的子字符串,即返回它作为最大的优质整数。这种方法保证了找到的第一个匹配的三位数字是最大的,因为它从最大的数字开始检查。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在遍历检查数字时,为什么选择从9到0而不是从0到9或其他顺序?
在这个算法中,从9到0的遍历顺序是为了确保第一个找到的三位连续相同数字是最大的。因为数字9是所有数字中最大的,逐步向下检查到0可以保证我们立即返回的是最大的可行值,无需再进行额外的比较或存储。如果从0到9进行检查,则需要记录下每次发现的三个连续相同的数字,并在遍历结束后比较哪个是最大的,这显然增加了算法的复杂性和运行时间。
🦆
如果输入字符串`num`非常长,这种方法的性能表现如何?是否有更优的搜索策略?
当输入字符串`num`非常长时,这种方法可能会表现出一定的性能瓶颈,因为对于每一个数字(从9到0),我们都需要在整个字符串中搜索一个长度为3的子字符串。这种搜索的时间复杂度为O(n),其中n是字符串的长度。更优的搜索策略可以是一次遍历字符串,使用一个长度为3的滑动窗口来检查每一组连续的三个字符是否相同,并记录下遇到的最大数字。这种策略的时间复杂度仍然是O(n),但它只需要遍历字符串一次,从而减少了重复的工作量。
🦆
在检查子字符串是否存在时,你是如何处理字符串两端的边界情况的?
在这种特定的算法实现中,边界情况自然地被处理了,因为我们是在搜索一个长度恰好为3的固定子字符串。当使用`in`关键字在Python中检查子字符串时,它会处理所有包括字符串开头和结尾的情况。例如,如果子字符串是字符串的前三个或最后三个字符,这种方法也能正确识别出来。因此,不需要特别处理这些边界情况。
🦆
该算法在找到第一个匹配的三位数字后就停止搜索,是否可能存在多个相同的最大优质整数,我们是否需要考虑它们的位置?
根据题目要求和算法设计,我们只需要返回最大的三位连续相同数字,而不需要关心它在字符串中的位置或出现的次数。因此,一旦我们找到了第一个(也是最大的)匹配的三位数字,就没有必要继续搜索了。这是因为我们的搜索策略已经从最大的可能数值开始,向下进行,保证了首次找到的三位连续数字就是所求的最大值。

相关问题