[LintCode] 604. Design Compressed String Iterator

alin 發布于2019-08-16 13:34 / 570人閱讀

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

云服務器 GPU云服務器 Compressed Iterator LintCode Iterator模式

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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
[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
Design Patterns - Iterator Pattern（譯）

摘要：迭代器模式屬于行為型模式下的一種。實現我們將創建一個接口，該接口描述迭代所需要的方法緊接著聲明了一個接口，該接口返回一個對象。我們會創建具體的類實現接口和接口，并去使用它們。第三步使用獲得迭代器并且打印。原文地址譯者 smallclover希望對你們有所幫助設計模式-迭代器模式迭代器是Java和.Net程序環境下經常使用的一種設計模式。這種設計模式通常用來獲取能順序訪問集合對元素...

Tony_Zby 2019-08-14 14:11 評論0 收藏0