资讯专栏INFORMATION COLUMN

[LintCode] 604. Design Compressed String Iterator

alin / 550人阅读

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;
    }
}

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

转载请注明本文地址: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 评论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 评论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 评论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 评论0 收藏0
  • Design Patterns - Iterator Pattern(译)

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

    Tony_Zby 评论0 收藏0

发表评论

0条评论

alin

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<