[LintCode] 604. Design Compressed String Iterator

alin 发布于2019-08-16 13:34 / 400人阅读

Problem

Design and implement a data structure for a compressed string iterator. It should support the following operations: next and hasNext.

The given compressed string will be in the form of each letter followed by a positive integer representing the number of this letter existing in the original uncompressed string.

next() - if the original string still has uncompressed characters, return the next letter; Otherwise return a white space.
hasNext() - Judge whether there is any letter needs to be uncompressed.

Note:
Please remember to RESET your class variables declared in StringIterator, as static/class variables are persisted across multiple test cases. Please see here for more details.

Example:

StringIterator iterator = new StringIterator("L1e2t1C1o1d1e1");

iterator.next(); // return "L"
iterator.next(); // return "e"
iterator.next(); // return "e"
iterator.next(); // return "t"
iterator.next(); // return "C"
iterator.next(); // return "o"
iterator.next(); // return "d"
iterator.hasNext(); // return true
iterator.next(); // return "e"
iterator.hasNext(); // return false
iterator.next(); // return " "

Solution

class StringIterator {
    Queue queue;
    public StringIterator(String str) {
        queue = new LinkedList<>();
        int i = 0, len = str.length();
        while (i < len) {
            int j = i+1;
            while (j < len && Character.isDigit(str.charAt(j))) j++;
            
            char ch = str.charAt(i);
            int count = Integer.parseInt(str.substring(i+1, j));
            queue.offer(new Node(ch, count));
            
            i = j;
        }
    }
    public char next() {
        if (!hasNext()) return " ";
        Node node = queue.peek();
        node.count--;
        if (node.count == 0) queue.poll();
        return node.val;
    }
    public boolean hasNext() {
        return !queue.isEmpty();
    }
}
class Node {
    char val;
    int count;
    public Node(char c, int n) {
        this.val = c;
        this.count = n;
    }
}

专线服务私有云 Compressed Iterator LintCode Iterator模式

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71959.html

[LintCode] Binary Search Tree Iterator

摘要：建立一个堆栈，先将最左边的结点从大到小压入栈，这样的话，为了实现迭代即返回下一个的函数就要考虑右边的结点。如此，实现函数。 Problem Design an iterator over a binary search tree with the following rules: Elements are visited in ascending order (i.e. an in-o...

silencezwm 2019-08-14 15:33 评论0 收藏0
[LintCode] String Compression

String Compression Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the compressed string w...

Cruise_Chan 2019-08-15 13:24 评论0 收藏0
[LintCode/LeetCode] Flatten Nested List Iterator

摘要：首先，根据迭代器需要不断返回下一个元素，确定用堆栈来做。堆栈初始化数据结构，要先从后向前向堆栈压入中的元素。在调用之前，先要用判断下一个是还是，并进行的操作对要展开并顺序压入对直接返回。 Problem Given a nested list of integers, implement an iterator to flatten it. Each element is either...

spacewander 2019-08-14 15:45 评论0 收藏0
Design Patterns - Iterator Pattern（译）

摘要：迭代器模式属于行为型模式下的一种。实现我们将创建一个接口，该接口描述迭代所需要的方法紧接着声明了一个接口，该接口返回一个对象。我们会创建具体的类实现接口和接口，并去使用它们。第三步使用获得迭代器并且打印。原文地址译者 smallclover希望对你们有所帮助设计模式-迭代器模式迭代器是Java和.Net程序环境下经常使用的一种设计模式。这种设计模式通常用来获取能顺序访问集合对元素...

Tony_Zby 2019-08-14 14:11 评论0 收藏0
[LeetCode/LintCode] Design Twitter/Mini Twitter

摘要：首先建立按时间戳从大到小排列的，找到中的，出其中在中存在的，把每一个的推特链表放入，再从中取头十条推特的放入结果数组。 Design Twitter Note 建立两个HashMap，一个存user，一个存tweets。以及整型的时间戳timestamp。user的k-v pair是userId-follower_set，tweets的k-v pair是userId-tweets_li...

honmaple 2019-08-14 15:31 评论0 收藏0