題目描述

題目分析

這個題目自己大概花了一個小時，雖然是一遍AC，但是速度有點慢，太長時間不寫代碼導致自己對代碼不太敏感，寫起來慢騰騰的。

看到這個的想法就是，要用棧來保存列表的迭代器，這樣將孩子列表遍歷完成后才能重新回到父親列表中，如果棧為空當然就結束了。

首先是對函數調用的分析，會首先調用hasNext再調用next，這就要求我們如果把后移操作放到hasNext中，那么棧頂就要指向當前位置之前，對于迭代器來說不容易操作，因此我們決定將后移操作放到next函數中

首要要定義棧中保存的迭代器的含義：我的想法是該層列表當前指向元素，這應該是比較符合直覺的，然而就是這種符合直覺的做法導致我的代碼要復雜許多。因為這種定義其實是不統一的，棧頂的迭代器是直接可以訪問元素的，而下面的迭代器因為保存的是當前元素的位置，所以棧頂訪問結束后彈出以后是不能直接訪問元素的，必須要執行一次后移操作，這種對棧中元素處理的不統一性導致代碼變得復雜：一旦彈出必須要執行一次后移操作。可能這里還不明白為什么變復雜了，我再梳理一下需要進行的步驟：
首先，我們必須在hasNext函數中判斷，當前棧頂迭代器需不需要彈出，如果不需要，就要判斷當前棧頂迭代器指向的是不是一個整數，如果是，返回真即可，如果不是，需要將子列表的迭代器壓棧進行訪問，可是子列表有可能為空，因此不能直接訪問子列表，同樣要對新壓入棧的迭代器判斷需不需要彈出。如果不需要彈出就是正常操作：要么繼續壓棧，要么返回。但是如果需要彈出的話，還需要對父親迭代器進行后移操作，后移以后首先要判斷的同樣是需不需要彈出。

可以總結一下：

• 每次后移操作后首先要做的是判斷是否需要彈出
• 每次入棧操作以后要判斷是否需要彈出

如果我們直接按照上面的順序進行操作，將會寫出比較復雜的代碼（我就是這樣），可以看到彈出操作比較頻繁，我們可以將其剝離成一個函數

實現代碼

class NestedIterator {
public:NestedIterator(vector<NestedInteger> &nestedList) {S.emplace(nestedList.cbegin(), nestedList.cend());}int next() {return (S.top().first++)->getInteger();}bool hasNext() {return !is_empty() && move_to_integer();}
private:using vec_iter = vector<NestedInteger>::const_iterator;stack<pair<vec_iter, vec_iter>> S;bool is_empty() {//檢查列表是否為空，應該在每次執行++操作后進行檢查//如果為空返回真if (S.empty()) return true;while(S.top().first == S.top().second) {//如果棧頂部的迭代器已經失效，則將其彈出S.pop();if (S.empty()) return true;++S.top().first;}return false;}bool move_to_integer() {//將迭代器指向整數，如果不是整數，則將當前迭代器壓入棧//返回假表示后面沒有整數，只有空列表while( !( S.top().first -> isInteger()) ) {auto &tp = S.top();//如果當前迭代器指向的不是整數，則得到其指向的列表const auto &lst = tp.first -> getList();if (lst.empty()) {//如果指向的列表為空，則不用處理該列表，直接跳過++tp.first;if (is_empty()) {//如果后面沒有有效元素，直接返回假return false;}} else {//如果列表不為空，則將列表的迭代器壓棧S.emplace(lst.cbegin(), lst.cend());}}return true;}
};

寫代碼遇到一個小問題就是我將聲明語句放到了表達式中，但是總報錯，經過測試發現聲明語句不能寫在表達式中。

AC之后我又去看了一下官方題解，發現思路大同小異，但是發現人家的代碼十分簡潔，主要的區別在于hasNext函數中題解通過將上面幾個函數放到同一個循環里面，通過安排代碼的順序來完成任務：

• 先判斷是否需要彈出，如果需要彈出則彈出后直接continue判斷是否非空，然后再次執行循環，這時候就體現出設計的重要性了，題解中棧保存的是下次應該訪問的迭代器地址，這就要求父列表迭代器在壓入子列表迭代器后同時向后移動一位，因此彈出棧頂迭代器后就不需要再次向后移動了。如果不這樣做，彈出后需要先判斷棧是否為空，然后再后移，然后再判斷是否需要彈出，將導致代碼復雜
• 彈出后判斷是否是一個整數，如果是直接返回true，如果不是則不斷壓棧，直到是一個整數。如果是一個空列表，則重新執行循環以后會彈出，因此不需要做多余的處理。

題解代碼

class NestedIterator {
private:// pair 中存儲的是列表的當前遍歷位置，以及一個尾后迭代器用于判斷是否遍歷到了列表末尾stack<pair<vector<NestedInteger>::iterator, vector<NestedInteger>::iterator>> stk;public:NestedIterator(vector<NestedInteger> &nestedList) {stk.emplace(nestedList.begin(), nestedList.end());}int next() {// 由于保證調用 next 之前會調用 hasNext，直接返回棧頂列表的當前元素，然后迭代器指向下一個元素return stk.top().first++->getInteger();}bool hasNext() {while (!stk.empty()) {auto &p = stk.top();if (p.first == p.second) { // 遍歷到當前列表末尾，出棧stk.pop();continue;}if (p.first->isInteger()) {return true;}// 若當前元素為列表，則將其入棧，且迭代器指向下一個元素auto &lst = p.first++->getList();stk.emplace(lst.begin(), lst.end());}return false;}
};

只能感嘆題解代碼的巧妙，自己距離這樣的水平還很遠，要多寫多思考。這種模擬題感覺對代碼能力還是挺有幫助的，因為工程中代碼更多是這樣的，注重的是代碼的設計效率、是否優雅，而不是算法是否巧妙