如何将网站加入百度图 推广,网络规划设计师备考,网络营销的方式包括,大连 响应式网站制作题目描述 题目分析
这个题目自己大概花了一个小时#xff0c;虽然是一遍AC#xff0c;但是速度有点慢#xff0c;太长时间不写代码导致自己对代码不太敏感#xff0c;写起来慢腾腾的。
看到这个的想法就是#xff0c;要用栈来保存列表的迭代器#xff0c;这样将孩子列表…题目描述 题目分析
这个题目自己大概花了一个小时虽然是一遍AC但是速度有点慢太长时间不写代码导致自己对代码不太敏感写起来慢腾腾的。
看到这个的想法就是要用栈来保存列表的迭代器这样将孩子列表遍历完成后才能重新回到父亲列表中如果栈为空当然就结束了。
首先是对函数调用的分析会首先调用hasNext再调用next这就要求我们如果把后移操作放到hasNext中那么栈顶就要指向当前位置之前对于迭代器来说不容易操作因此我们决定将后移操作放到next函数中
首要要定义栈中保存的迭代器的含义我的想法是该层列表当前指向元素这应该是比较符合直觉的然而就是这种符合直觉的做法导致我的代码要复杂许多。因为这种定义其实是不统一的栈顶的迭代器是直接可以访问元素的而下面的迭代器因为保存的是当前元素的位置所以栈顶访问结束后弹出以后是不能直接访问元素的必须要执行一次后移操作这种对栈中元素处理的不统一性导致代码变得复杂一旦弹出必须要执行一次后移操作。可能这里还不明白为什么变复杂了我再梳理一下需要进行的步骤 首先我们必须在hasNext函数中判断当前栈顶迭代器需不需要弹出如果不需要就要判断当前栈顶迭代器指向的是不是一个整数如果是返回真即可如果不是需要将子列表的迭代器压栈进行访问可是子列表有可能为空因此不能直接访问子列表同样要对新压入栈的迭代器判断需不需要弹出。如果不需要弹出就是正常操作要么继续压栈要么返回。但是如果需要弹出的话还需要对父亲迭代器进行后移操作后移以后首先要判断的同样是需不需要弹出。
可以总结一下
每次后移操作后首先要做的是判断是否需要弹出每次入栈操作以后要判断是否需要弹出
如果我们直接按照上面的顺序进行操作将会写出比较复杂的代码我就是这样可以看到弹出操作比较频繁我们可以将其剥离成一个函数
实现代码
class NestedIterator {
public:NestedIterator(vectorNestedInteger 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 vectorNestedInteger::const_iterator;stackpairvec_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 中存储的是列表的当前遍历位置以及一个尾后迭代器用于判断是否遍历到了列表末尾stackpairvectorNestedInteger::iterator, vectorNestedInteger::iterator stk;public:NestedIterator(vectorNestedInteger 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;}
};只能感叹题解代码的巧妙自己距离这样的水平还很远要多写多思考。这种模拟题感觉对代码能力还是挺有帮助的因为工程中代码更多是这样的注重的是代码的设计效率、是否优雅而不是算法是否巧妙
