604. 迭代压缩字符串
设计并实现一个迭代压缩字符串的数据结构。给定的压缩字符串的形式是，每个字母后面紧跟一个正整数，表示该字母在原始未压缩字符串中出现的次数。
设计一个数据结构，它支持如下两种操作： next 和 hasNext。
next() - 如果原始字符串中仍有未压缩字符，则返回下一个字符，否则返回空格。hasNext() - 如果原始字符串中存在未压缩的的字母，则返回true，否则返回false。
示例 1：
输入：
["StringIterator", "next", "next", "next", "next", "next", "next", "hasNext", "next", "hasNext"]
[["L1e2t1C1o1d1e1"], [], [], [], [], [], [], [], [], []]
输出：
[null, "L", "e", "e", "t", "C", "o", true, "d", true]
解释：
StringIterator stringIterator = new StringIterator("L1e2t1C1o1d1e1");
stringIterator.next(); // 返回 "L"
stringIterator.next(); // 返回 "e"
stringIterator.next(); // 返回 "e"
stringIterator.next(); // 返回 "t"
stringIterator.next(); // 返回 "C"
stringIterator.next(); // 返回 "o"
stringIterator.hasNext(); // 返回 True
stringIterator.next(); // 返回 "d"
stringIterator.hasNext(); // 返回 True
提示：
1 <= compressedString.length <= 1000compressedString 由小写字母、大写字母和数字组成。compressedString 中，单个字符的重复次数在 [1,10 ^9] 范围内。next 和 hasNext 的操作数最多为 100 。原站题解
golang 解法, 执行用时: 8 ms, 内存消耗: 5.4 MB, 提交时间: 2023-10-15 19:38:25
type StringIterator struct {
bs []byte
cs []int
i int
}
func Constructor(compressedString string) StringIterator {
bs, cs := []byte{}, []int{}
s := []byte(compressedString)
i := 0
for i < len(s) {
a := s[i]
i++
n := 0
for ; i < len(s) && s[i] >= '0' && s[i] <= '9'; i++ {
n *= 10
n += int(s[i] - '0')
}
bs = append(bs, a)
cs = append(cs, n)
}
return StringIterator{bs, cs, 0}
}
func (this *StringIterator) Next() byte {
i, l := this.i, len(this.bs)
if i != l {
c := this.cs[i]
if c > 1 {
this.cs[i]--
} else {
this.i++
}
return this.bs[i]
}
return ' '
}
func (this *StringIterator) HasNext() bool {
return this.i < len(this.bs)
}
/**
* Your StringIterator object will be instantiated and called as such:
* obj := Constructor(compressedString);
* param_1 := obj.Next();
* param_2 := obj.HasNext();
*/
java 解法, 执行用时: 13 ms, 内存消耗: 43.1 MB, 提交时间: 2023-10-15 19:37:55
class StringIterator {
class Pair {
char c;
int cnt;
Pair(char c, int cnt) {
this.c = c;
this.cnt = cnt;
}
}
private Deque<Pair> queue = null;
public StringIterator(String compressedString) {
queue = new LinkedList<>();
int idx = 0;
while (idx < compressedString.length()) {
char c = compressedString.charAt(idx++);
int num = 0;
while (idx < compressedString.length() && Character.isDigit(compressedString.charAt(idx))) {
num = num * 10 + compressedString.charAt(idx++) - '0';
}
queue.addLast(new Pair(c, num));
}
}
public char next() {
if (!hasNext()) return ' ';
Pair pair = queue.pollFirst();
assert pair != null;
char ret = pair.c;
pair.cnt--;
if (pair.cnt > 0) queue.addFirst(pair);
return ret;
}
public boolean hasNext() {
return !queue.isEmpty();
}
}
/**
* Your StringIterator object will be instantiated and called as such:
* StringIterator obj = new StringIterator(compressedString);
* char param_1 = obj.next();
* boolean param_2 = obj.hasNext();
*/
cpp 解法, 执行用时: 12 ms, 内存消耗: 13.8 MB, 提交时间: 2023-10-15 19:37:28
class StringIterator
{
public:
vector<pair<char, int>> char_freq;
StringIterator(string compressedString)
{
int n = compressedString.size();
int i = 0;
while (i < n)
{
char c = compressedString[i];
i ++;
int x = 0;
while (i < n && isdigit(compressedString[i]))
{
x = x * 10 + (compressedString[i] - '0');
i ++;
}
char_freq.push_back({c, x});
}
}
char next()
{
if (char_freq.size() == 0)
return ' ';
auto [c, f] = char_freq[0];
if (f == 1)
char_freq.erase(char_freq.begin());
else
char_freq[0].second --;
return c;
}
bool hasNext()
{
return char_freq.size() > 0;
}
};
/**
* Your StringIterator object will be instantiated and called as such:
* StringIterator* obj = new StringIterator(compressedString);
* char param_1 = obj->next();
* bool param_2 = obj->hasNext();
*/
python3 解法, 执行用时: 52 ms, 内存消耗: 16.4 MB, 提交时间: 2023-10-15 19:37:13
class StringIterator:
def __init__(self, compressedString: str):
self.char_freq = []
n = len(compressedString)
i = 0
while i < n:
c = compressedString[i]
x = 0
i += 1
while i < n and compressedString[i].isdigit():
x = x * 10 + int(compressedString[i])
i += 1
self.char_freq.append([c, x])
def next(self) -> str:
if not self.char_freq:
return " "
c, f = self.char_freq[0]
if f == 1:
self.char_freq.pop(0)
else:
self.char_freq[0][1] -= 1
return c
def hasNext(self) -> bool:
return len(self.char_freq) != 0
# Your StringIterator object will be instantiated and called as such:
# obj = StringIterator(compressedString)
# param_1 = obj.next()
# param_2 = obj.hasNext()