LeetCode 604. Design Compressed String Iterator （设计压缩字符迭代器）$

2022-11-22 11:47:36

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 ' '

题目标签：Design

　　这道题目给了我们一个string， string是由一个char 紧接着一个正数int 这种重复排列。让我们设计一个迭代器，把每一个字母按照它后面那个数字来print出。

　　StringIterator: 当我们创造一个 StringIterator object 的时候，我们要把这个string 保存好，以便于之后可以call next 和 hasNext。

　　　　　　　　我们可以建立两个list， counts 和 letters。遍历compressedString，判断这一个char 是不是 letter，是的话，直接把char 存进letters list。如果这个char 是数字digit 的话，那么我们需要继续往后找，直到找到一个不是数字的char，或者它超出size了。

　　　　　　　　因为数字可以是1位，也可以2位或者更多。

　　Next()：当我们存好了letters 和counts，就利用counts 来return 相对应的char，每次用完一个char，要把它的count - 1。如果当这个count = 0 的时候，那么我们需要移动到下一个char。这里我们需要一个cursor_index 来跟踪我们的char。

　　hasNext()：这里只需要判断，如果我们的cursor_index 超出了任意一个list 的size，就表示已经用完了所有的char。

Java Solution:

Runtime beats 86.01%

完成日期：07/10/2017

关键词：Design

关键点：用两个list和一个cursor来找到char和对应char的count

 public class StringIterator

 {

     ArrayList<Integer> counts;

     ArrayList<Character> letters;

     int cursor_index = 0;

     public StringIterator(String compressedString)

     {

         counts = new ArrayList<>();

         letters = new ArrayList<>();

         for(int i=0; i<compressedString.length(); i++)

         {

             // if find a letter

             if(Character.isLetter(compressedString.charAt(i)))

                 letters.add(compressedString.charAt(i));

             // if find a digit

             else if(Character.isDigit(compressedString.charAt(i)))

             {

                 int end = i+1;

                 // find the next non-digit char within the length

                 while(end < compressedString.length() &&

                         Character.isDigit(compressedString.charAt(end)))

                     end++;

                 counts.add(Integer.parseInt(compressedString.substring(i, end)));

                 i = end - 1;

             }

         }

     }

     public char next()

     {

         char c;

         // meaning string is finished

         if(!hasNext())

             return ' ';

         c = letters.get(cursor_index);

         counts.set(cursor_index, counts.get(cursor_index) - 1);

         if(counts.get(cursor_index) == 0)

             cursor_index++;

         return c;

     }

     public boolean hasNext()

     {

         // if string is finished

         if(cursor_index > counts.size() - 1 )

             return false;

         else  // if string is not finished

             return true;

     }

 }

 /**

  * 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();

  */

参考资料：N/A

LeetCode 算法题目列表 - LeetCode Algorithms Questions List

码农公寓

相关文章