迭代压缩字符串

难度:

标签:

题目描述

代码结果

运行时间: 34 ms, 内存: 16.3 MB

/*
 * 题目思路：
 * 使用Java Stream对字符串进行迭代压缩。
 * 压缩规则如下：
 * 1. 如果一个字符连续出现多次，则用该字符后跟出现次数表示。
 * 2. 如果一个字符只出现一次，则直接保留该字符。
 * 例如，对于输入字符串 'aabbccc'，压缩结果为 'a2b2c3'。
 */
 
import java.util.stream.Collectors;
import java.util.stream.IntStream;
 
public class StringCompressionStream {
    public static String compressString(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        StringBuilder compressed = new StringBuilder();
        IntStream.range(0, s.length()).forEach(i -> {
            int count = 1;
            while (i + 1 < s.length() && s.charAt(i) == s.charAt(i + 1)) {
                count++;
                i++;
            }
            compressed.append(s.charAt(i));
            if (count > 1) {
                compressed.append(count);
            }
        });
        return compressed.toString();
    }
 
    public static void main(String[] args) {
        String input = "aabbccc";
        String output = compressString(input);
        System.out.println(output); // 输出: a2b2c3
    }
}

解释

方法:

这个题解的思路是将压缩字符串解压缩并逐个字符返回。在初始化时，它将字符串解析为两个列表：letters 存储字符，counts 存储对应的计数。next() 方法每次返回一个字符，并将对应的计数减 1。当计数减为 0 时，将当前字符和计数从列表中移除。hasNext() 方法判断是否还有剩余的字符可以返回。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

在解析压缩字符串时，你是如何确保数字和字符正确匹配的，特别是在处理多位数字时？

▷

在解析压缩字符串的过程中，我通过遍历每个字符，并检测是否是字母。如果是字母，首先检查临时变量 `n`（用于存放数字）是否非空，如果非空，则说明前一个字符的计数已完整，因此将它转换为整数后添加到 `counts` 列表中，并清空 `n` 以用于下一个数字的累加。如果不是字母，则将字符累加到 `n` 中。这样可以确保即使是多位数也能被正确解析并与前一个字母匹配。最后，循环结束后，还需要检查 `n` 是否非空，以确保最后一个字符的计数也被添加。

🦆

你的解法在初始化时如果遇到大字符串（例如含有数百万个字符的字符串）会如何表现？是否有更高效的方法来处理大规模数据？

▷

当前的解法在初始化时需要遍历整个字符串并构建两个列表 `letters` 和 `counts`，如果输入的字符串非常大，这将导致较高的内存消耗和初始化时间。对于大规模数据，一种更高效的方法是使用生成器或迭代器直接在原始字符串上操作，避免一次性解析整个字符串，而是在调用 `next()` 方法时才逐步解析和返回字符。这样可以大幅减少内存使用，并提高处理大数据的效率。

🦆

对于`next()`函数，当没有剩余字符可以返回时，它返回空格，这种设计有特别的考虑吗？在哪些情境下可能会引发问题？

▷

在 `next()` 函数中返回空格是一种表示没有更多字符可返回的方法。这种设计简单且能够在多数情况下清晰地表明迭代器已经到达尽头。然而，这种设计在处理需要区分空白字符和实际数据的场景中可能导致混淆。例如，在文本解析或编程语言的语法分析中，返回的空格可能被误解为有效数据的一部分。更严谨的设计应返回一个明确的信号，如 `None` 或抛出一个异常，以避免这种潜在的混淆。

🦆

对于`hasNext()`的实现，只检查`letters`和`counts`的长度是否大于0，这种方式是否充分？在实际应用中可能存在哪些边界情况？

▷

当前的 `hasNext()` 实现通过检查 `letters` 和 `counts` 列表的长度是否大于0来确定是否还有未返回的字符。这种方式在大多数情况下是充分的。然而，它假设 `letters` 和 `counts` 列表长度始终保持同步。如果由于某种错误导致两个列表的长度不匹配，这种检查方式可能会引发错误。确保这两个列表在所有操作中都严格同步是很重要的，任何操作导致长度不一致都应该被视为实现错误。

相关问题

LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 10⁵
最多调用 2 * 10⁵ 次 get 和 put

压缩字符串

给你一个字符数组 chars ，请使用下述算法压缩：

从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：

如果这一组长度为 1 ，则将字符追加到 s 中。
否则，需要向 s 追加字符，后跟这一组的长度。

压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。

请在 修改完输入数组后 ，返回该数组的新长度。

你必须设计并实现一个只使用常量额外空间的算法来解决此问题。

示例 1：

输入：chars = ["a","a","b","b","c","c","c"]
输出：返回 6 ，输入数组的前 6 个字符应该是：["a","2","b","2","c","3"]
解释："aa" 被 "a2" 替代。"bb" 被 "b2" 替代。"ccc" 被 "c3" 替代。

示例 2：

输入：chars = ["a"]
输出：返回 1 ，输入数组的前 1 个字符应该是：["a"]
解释：唯一的组是“a”，它保持未压缩，因为它是一个字符。

示例 3：

输入：chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
输出：返回 4 ，输入数组的前 4 个字符应该是：["a","b","1","2"]。
解释：由于字符 "a" 不重复，所以不会被压缩。"bbbbbbbbbbbb" 被 “b12” 替代。

提示：

1 <= chars.length <= 2000
chars[i] 可以是小写英文字母、大写英文字母、数字或符号

不含连续1的非负整数种花问题