leetcode
leetcode 751 ~ 800
较大分组的位置

较大分组的位置

难度:

标签:

题目描述

代码结果

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


// 思路:
// 使用Stream API处理字符串,找到所有由连续相同字符组成的分组。
// 如果分组长度大于等于3,则将其起始和终止下标添加到结果列表中。
// 返回结果列表。

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public List<List<Integer>> largeGroupPositions(String s) {
        List<List<Integer>> result = new ArrayList<>();
        
        IntStream.range(0, s.length())
            .collect(ArrayList::new, (list, i) -> {
                if (list.isEmpty() || s.charAt(list.get(list.size() - 1)) != s.charAt(i)) {
                    list.add(i);
                }
            }, ArrayList::addAll)
            .stream()
            .collect(Collectors.toList())
            .stream()
            .map(start -> {
                int end = start;
                while (end < s.length() && s.charAt(end) == s.charAt(start)) {
                    end++;
                }
                return new int[]{start, end - 1};
            })
            .filter(pair -> pair[1] - pair[0] >= 2)
            .forEach(pair -> result.add(List.of(pair[0], pair[1])));
        
        return result;
    }
}

解释

方法:

这个题解采用了双指针的思路。使用 left 和 right 两个指针分别表示当前分组的起始和结束位置。遍历字符串,如果当前字符与前一个字符相同,则 right 指针向右移动;否则,判断 left 和 right 之间的长度是否大于等于3,如果是则将 [left, right] 加入结果,并将 left 和 right 都置为当前位置 i,表示开始一个新的分组。最后再判断最后一个分组是否满足条件。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在代码实现中,如何确保在字符串最后一个字符后正确处理边界情况,尤其是当最后一个分组是较大分组时?
在代码中,处理最后一个字符后的边界情况是通过在循环结束后再次检查`right - left + 1 >= 3`来实现的。如果循环结束时最后一个分组的长度满足大于等于3的条件,则将这个分组的起始和结束位置添加到结果列表中。这样做确保了即使最后一个分组也能被正确处理。
🦆
代码中使用了`now_char = s[i]`来更新当前字符,这种更新是否有可能导致某些情况下分组不准确,比如连续字符在更新点断开?
代码中的`now_char = s[i]`用于更新当前正在检查的字符。当遇到与`now_char`不同的字符时,这表示前一个字符的连续序列已结束,并开始一个新的字符序列。因此,这种更新方式不会导致连续字符错误地断开,而是恰当地标记了连续字符序列的结束,并且正确地开始新的分组。
🦆
在判断`if right - left + 1 >= 3`时,为什么选择这个条件来确定是否是较大分组,这里的'1'是如何计算的?
在判断`if right - left + 1 >= 3`时,`right - left + 1`计算的是当前分组的长度。这里的'1'是因为索引是从0开始的,所以需要加1来得到正确的元素数量。例如,如果`left`和`right`分别是0和2,实际上包括的元素是索引为0, 1, 2的三个元素,总共3个元素。选择这个条件是因为题目中定义较大分组为长度至少为3的连续相同字符的序列。
🦆
示例输出显示边界闭合的区间[3,6],但在代码中`right`指针是如何处理以确保正确表示分组的结束位置?
在代码中,`right`指针在遇到连续字符时递增,并且在添加到结果列表时,`right`自然就是当前分组的结束位置。由于处理逻辑保证了每次更新分组时`right`都指向当前分组的最后一个字符,所以当满足条件被添加到结果列表时,`right`已正确表示了分组的结束位置。

相关问题