leetcode
leetcode 1651 ~ 1700
哪种连续子字符串更长

哪种连续子字符串更长

难度:

标签:

题目描述

代码结果

运行时间: 18 ms, 内存: 15.9 MB


/*
 * Solution Approach using Java Streams:
 * 1. Convert the string s into a stream of characters.
 * 2. Use a map to store the lengths of all contiguous 1's and 0's segments.
 * 3. Group the characters and find the maximum length for both 1's and 0's.
 * 4. Compare the maximum length of 1's and 0's, and return true if the maximum length of 1's is greater, else false.
 */
import java.util.*;
import java.util.stream.*;

public class Solution {
    public boolean checkZeroOnes(String s) {
        Map<Character, Integer> maxCount = new HashMap<>();
        maxCount.put('1', 0);
        maxCount.put('0', 0);

        IntStream.range(0, s.length())
            .boxed()
            .collect(Collectors.groupingBy(i -> s.charAt(i), Collectors.toList()))
            .forEach((k, v) -> {
                int maxLength = 1;
                int currentLength = 1;
                for (int j = 1; j < v.size(); j++) {
                    if (v.get(j) == v.get(j - 1) + 1) {
                        currentLength++;
                    } else {
                        maxLength = Math.max(maxLength, currentLength);
                        currentLength = 1;
                    }
                }
                maxLength = Math.max(maxLength, currentLength);
                maxCount.put(k, Math.max(maxCount.get(k), maxLength));
            });
        return maxCount.get('1') > maxCount.get('0');
    }
}

解释

方法:

此题解通过滑动窗口的方法,遍历字符串来计算由'0'和'1'组成的最长连续子字符串的长度。首先定义两个变量max_zeros和max_ones来分别存储最长的0串和1串的长度。使用两个指针slow和fast来定义当前考察的子串的起始和结束位置,并通过遍历整个字符串来更新这两个最大值。当遇到当前字符与起始字符相同时,根据是'0'还是'1',更新max_zeros或max_ones。如果当前字符与起始字符不同,则将slow指针移动到fast的位置,这样可以开始新的子串的计数。最后,比较max_ones和max_zeros的值,如果由'1'组成的子字符串长度严格大于由'0'组成的,返回true,否则返回false。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
题解中提到使用滑动窗口方法,这种方法相比于其他可能的解法(如一次遍历统计)有什么优势或特别之处?
滑动窗口方法与一次遍历统计其实在本题中大体相似,主要区别在于语义表达。滑动窗口通常用于动态调整窗口大小以寻找最优解,在处理变长子数组或子串问题时尤为有效。在此题中,使用滑动窗口可以清晰地展现出窗口的移动和调整过程,即便其本质上与一次遍历统计相同。这种方法提供了更好的可读性和易于理解的逻辑流程,特别是在处理更复杂的变长子串问题时,滑动窗口的框架可以直接应用,提高代码的复用性。
🦆
在更新max_zeros或max_ones时,是否有考虑对字符串末尾的连续子字符串进行处理,即当循环结束时如何确保最后一个子字符串被正确计算?
题解中的算法确实没有直接在循环结束时处理末尾的连续子字符串,这可能导致如果最长的连续子字符串恰好在字符串的末尾时,其长度不会被正确更新。为了解决这个问题,可以在循环结束后再进行一次长度更新操作,检查并更新最后一个子字符串的长度。这样可以确保无论连续子字符串是否在末尾,都能被正确计算。
🦆
代码中在遇到不同字符时,将slow指针设为fast,而fast指针减1,然后再fast指针增加1,这样的操作是否有些多余,能否简化这一步骤?
确实,题解中对指针的处理略显复杂和多余。更简洁的方法是在发现不同字符时,直接将slow指针设置为fast,而不需要对fast指针进行减1再加1的操作。这样不仅简化了代码,也提高了其执行效率,因为避免了不必要的指针操作。
🦆
在该算法中,如何处理全为‘0’或全为‘1’的字符串输入,是否存在边界情况未被考虑?
题解中的算法在输入字符串全为‘0’或全为‘1’时,将会正确地更新max_zeros或max_ones的值,因为整个字符串会被视为一个连续子字符串。然而,需要注意的是,如果字符串全为‘0’,则max_ones将保持为0,反之亦然。这在逻辑上是正确的,但应在实际应用中根据具体需求判断是否需要对全0或全1的情况做特殊处理或输出说明。

相关问题