LeetCode Design Compressed String Iterator 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 ' '

---

本题设计了一种压缩字符串格式，即把多个连续相同字符用单个字符已经频率代替了，比如”L1e2t1C1o1d1e1″展开其实就是”LeetCode”。现在要针对这种压缩字符串，设计一个迭代器，实现next和hasNext函数。 我一开始上暴力，即首先把压缩字符串展开成常规字符串，然后直接下标操作。代码如下： [cpp] class StringIterator { private: string line; int cur, n; public: StringIterator(string compressedString) { line = ""; cur = n = 0; vector<char> letters; vector<int> rep; string digits = ""; for (int i = 0; i < compressedString.size(); ++i) { if (isalpha(compressedString[i])) { letters.push_back(compressedString[i]); if (digits != "") { rep.push_back(atoi(digits.c_str())); digits = ""; } } else digits += string(1, compressedString[i]); } rep.push_back(atoi(digits.c_str())); for (int i = 0; i < letters.size(); ++i) { line += string(rep[i], letters[i]); } n = line.size(); } char next() { if (cur < n)return line[cur++]; else return ‘ ‘; } bool hasNext() { return cur < n; } }; [/cpp] 本代码MLE了。因为有个样例是“a1234567890b1234567890”，我表示无语，如果展开确实会MLE。 其实写上面的代码的时候我就知道可以优化，不对压缩字符串展开，而是表示成(a,1234567890)和(b,1234567890)，next的时候只对频率递减。这样只需要存储少量字符以及对应的频率。 代码如下： [cpp] typedef long long ll; class StringIterator { private: int cur, n; vector<char> letters; vector<ll> rep; public: StringIterator(string compressedString) { cur = n = 0; string digits = ""; for (int i = 0; i < compressedString.size(); ++i) { if (isalpha(compressedString[i])) { letters.push_back(compressedString[i]); if (digits != "") { rep.push_back(atoll(digits.c_str())); digits = ""; } } else digits += string(1, compressedString[i]); } rep.push_back(atoi(digits.c_str())); n = letters.size(); } char next() { if (rep[cur] > 0) { char ans = letters[cur]; –rep[cur]; return ans; } else { if (cur == n – 1)return ‘ ‘; else { char ans = letters[++cur]; –rep[cur]; return ans; } } } bool hasNext() { return cur < n – 1 || (cur == n – 1 && rep[cur] > 0); } }; [/cpp] 本代码提交AC，用时13MS。]]>

LeetCode Flatten Nested List Iterator Given a nested list of integers, implement an iterator to flatten it. Each element is either an integer, or a list — whose elements may also be integers or other lists. Example 1: Given the list [[1,1],2,[1,1]], By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1]. Example 2: Given the list [1,[4,[6]]], By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

---

本题自定义了一个【嵌套的整数】，【嵌套的整数】可以是一个真正的整数，也可以是一个包含整数的数组。现在要实现针对【嵌套的整数】的一个迭代器，迭代器包含next()和hasNext()函数。 解题思路是先解析这个【嵌套的整数】数组，解析的方法就是递归的解析，把解析出来的真正的整数存到一个vector数组中。接下来的迭代器就好实现了，用pos表示当前访问的数组下标，next()函数先访问pos指向元素，然后++pos；hasNext()就判断一下pos是否走到末尾了。 完整代码如下： [cpp] class NestedIterator { private: vector<int> vi; int pos; public: void parseNestedInteger(NestedInteger& ni) { if (ni.isInteger())vi.push_back(ni.getInteger()); else { vector<NestedInteger> vni = ni.getList(); for (int i = 0; i < vni.size(); ++i) { parseNestedInteger(vni[i]); } } } NestedIterator(vector<NestedInteger> &nestedList) { for (int i = 0; i < nestedList.size(); ++i) { parseNestedInteger(nestedList[i]); } pos = 0; } int next() { return vi[pos++]; } bool hasNext() { return pos < vi.size(); } }; [/cpp] 本代码提交AC，用时29MS。]]>