DesignCompressedStringIterator [source code]
public class DesignCompressedStringIterator {
static
/******************************************************************************/
public class StringIterator {
char[] chs;
int[] counts;
int head;
public StringIterator(String compressedString) {
char[] chStr = compressedString.toCharArray();
int len = chStr.length;
int counter = 0;
for (char c : chStr) {
if (c > 57) counter++;
}
chs = new char[counter];
counts = new int[counter];
counter = 0;
for (int i = 0; i < len; ) {
if (chStr[i] > 57) {
chs[counter] = chStr[i++];
} else {
StringBuilder sb = new StringBuilder();
sb.append(chStr[i]);
while (++i < len && chStr[i] <= 57) {
sb.append(chStr[i]);
}
counts[counter++] = Integer.parseInt(sb.toString());
}
}
head = 0;
}
public char next() {
if (head == chs.length) return ' ';
char res = chs[head];
if (--counts[head] == 0) head++;
return res;
}
public boolean hasNext() {
return !(head == chs.length);
}
}
/******************************************************************************/
public static void main(String[] args) {
String[] inputs = {
"L1e2t1C1o1d1e1",
"L2e2t2C2o2d2e23",
"x6",
};
for (String s : inputs) {
Printer.separator ();
Printer.openColor("red");
System.out.println(s);
Printer.closeColor();
DesignCompressedStringIterator.StringIterator tester = new DesignCompressedStringIterator.StringIterator(s);
for (int i = 0; i < 6; i++) System.out.println("next: " + tester.next());
System.out.println("hasNext: " + tester.hasNext());
System.out.println("next: " + tester.next());
System.out.println("hasNext: " + tester.hasNext());
}
}
}
这个问题, 无论你最后用什么方法来做, 核心问题都是这个 string 你要怎么 parse. 这个 parse 的核心问题在于, 如果 count 超过两位怎么办?
我这个循环的要点在于, 首先, 还是一个 char 和一个 int 组成一组, 然后只有在组的末尾, 也就是 int 处理完了之后, 我们才让 counter 增加; 其次一个问题在于, int 可能有很多位, 所以在处理 char 和处理 int 的时候 i 的增加方式也有区别;
最后的速度是123ms (82%), 可以接受;
大概知道一些罗马数字的 ASICII 码的范围;
java> (int) 'a'
java.lang.Integer res1 = 97
java> (int) 'A'
java.lang.Integer res2 = 65
java> (int) '0'
java.lang.Integer res3 = 48
java> (int) '9'
java.lang.Integer res4 = 57
这里就用到了, 知道一个57用来分界线之后, 程序本身就好写很多;
如果是在是记不得, 起码要知道三个的大小范围, 数字的是最小的, 然后是大写字母, 然后最大的是小写字母: discussion 里面就是有人这么做的, 只要知道'9'或者'A' 可以分界就可以了;
在 editorial 里面他们用到了一个 API:
Character.isDigit(s.charAt(i))
可以直接判断是否是数字, 不过这个其实并不是很必要的一个操作;
这个是 editorial 里面给出的一个 parse 的思路:
public StringIterator(String s) {
int i = 0;
while (i < s.length()) {
char ch = s.charAt(i++);
int num = 0;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
num = num * 10 + s.charAt(i) - '0';
i++;
}
for (int j = 0; j < num; j++)
res.append(ch);
}
}
整体的算法是类似的, 不过他们数字的组合比我这个更直接, 就是自己计算, 而不是用 API; //不过我后来把我的数字组合改成了他们这种做法, 速度并没有快! 感觉可能是因为乘法的速度实际上比我理解的要慢;
editorial 的最终的解是:
public class StringIterator {
String res;
int ptr = 0, num = 0;
char ch = ' ';
public StringIterator(String s) {
res = s;
}
public char next() {
if (!hasNext())
return ' ';
if (num == 0) {
ch = res.charAt(ptr++);
while (ptr < res.length() && Character.isDigit(res.charAt(ptr))) {
num = num * 10 + res.charAt(ptr++) - '0';
}
}
num--;
return ch;
}
public boolean hasNext() {
return ptr != res.length() || num != 0;
}
}
这个解实际上也没有什么核心算法上的提升, 就是做到了一个 laziness, 我是 precompute, 把所有的 char 全都拆出来, 他这个做法就相当于始终只维护一个字母的信息, 直到当前字母被 pop 干净之后, 才 fetch 出来下一个字母的信息;
这个做法理论上的amortized analysis可以达到O(1);
这个是 discussion 里面一个用 queue 的做法;
public class StringIterator {
Queue<int[]> queue = new LinkedList<>();
public StringIterator(String s) {
int i = 0, n = s.length();
while (i < n) {
int j = i+1;
while (j < n && s.charAt(j) - 'A' < 0) j++;
queue.add(new int[]{s.charAt(i) - 'A', Integer.parseInt(s.substring(i+1, j))});
i = j;
}
}
public char next() {
if (queue.isEmpty()) return ' ';
int[] top = queue.peek();
if (--top[1] == 0) queue.poll();
return (char) ('A' + top[0]);
}
public boolean hasNext() {
return !queue.isEmpty();
}
}
也不知道这样做有什么好处;
Problem Description
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 ' '
Difficulty:Easy
Total Accepted:3K
Total Submissions:9.3K
Contributor: nikhiltiware
Companies
google
Related Topics
design
Similar Questions
LRU Cache
/**
- 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();
*/