leetcode.341. 扁平化嵌套列表迭代器

心已赠人 2022-11-12 09:49 208阅读 0赞

### 文章目录 ###

*  341. 扁平化嵌套列表迭代器
 *  模板
 *   *  java
     *  cpp
 *  思路与代码
 *   *  方法一：
     *  方法三：
     *   *  cpp深度优先搜索
         *  c语言深度优先搜索
         *  方法四：栈(面试的时候需要写出来)
 *  测试
 *   *  NestedInteger接口类
     *  SingletonInteger 实现类
     *  NestedList 实现类
     *  NestedIterator类
     *  测试类

# 341. 扁平化嵌套列表迭代器 #

给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。

列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。

**示例 1:**

输入: [[1,1],2,[1,1]]
    输出: [1,1,2,1,1]
    解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。

**示例 2:**

输入: [1,[4,[6]]]
    输出: [1,4,6]
    解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。

# 模板 #

## java ##

public class NestedIterator implements Iterator<Integer> {
    
        public NestedIterator(List<NestedInteger> nestedList) {
            
        }
    
        @Override
        public Integer next() {
            
        }
    
        @Override
        public boolean hasNext() {
            
        }
    }

## cpp ##

/**
     * // This is the interface that allows for creating nested lists.
     * // You should not implement it, or speculate about its implementation
     * class NestedInteger {
     *   public:
     *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
     *     bool isInteger() const;
     *
     *     // Return the single integer that this NestedInteger holds, if it holds a single integer
     *     // The result is undefined if this NestedInteger holds a nested list
     *     int getInteger() const;
     *
     *     // Return the nested list that this NestedInteger holds, if it holds a nested list
     *     // The result is undefined if this NestedInteger holds a single integer
     *     const vector<NestedInteger> &getList() const;
     * };
     */
    
    class NestedIterator {
    public:
        NestedIterator(vector<NestedInteger> &nestedList) {
            
        }
        
        int next() {
            
        }
        
        bool hasNext() {
            
        }
    };
    
    /**
     * Your NestedIterator object will be instantiated and called as such:
     * NestedIterator i(nestedList);
     * while (i.hasNext()) cout << i.next();
     */

# 思路与代码 #

## 方法一： ##

java

public class NestedIterator implements Iterator<Integer> { 
        private List<Integer> vals;
        private Iterator<Integer> cur;
    
        public NestedIterator(List<NestedInteger> nestedList) { 
            vals = new ArrayList<Integer>();
            dfs(nestedList);
            cur = vals.iterator();
        }
    
        @Override
        public Integer next() { 
            return cur.next();
        }
    
        @Override
        public boolean hasNext() { 
            return cur.hasNext();
        }
    
        private void dfs(List<NestedInteger> nestedList) { 
            for (NestedInteger nest : nestedList) { 
                if (nest.isInteger()) { 
                    vals.add(nest.getInteger());
                } else { 
                    dfs(nest.getList());
                }
            }
        }
    }

## 方法三： ##

### cpp深度优先搜索 ###

class NestedIterator { 
    private:
        vector<int> vals;
        vector<int>::iterator cur;
    
        void dfs(const vector<NestedInteger> &nestedList) { 
            for (auto &nest : nestedList) { 
                if (nest.isInteger()) { 
                    vals.push_back(nest.getInteger());
                } else { 
                    dfs(nest.getList());
                }
            }
        }
    
    public:
        NestedIterator(vector<NestedInteger> &nestedList) { 
            dfs(nestedList);
            cur = vals.begin();
        }
    
        int next() { 
            return *cur++;
        }
    
        bool hasNext() { 
            return cur != vals.end();
        }
    };

### c语言深度优先搜索 ###

struct NestedIterator { 
        int *vals;
        int size;
        int cur;
    };
    
    void dfs(struct NestedIterator *iter, struct NestedInteger **nestedList, int nestedListSize) { 
        for (int i = 0; i < nestedListSize; i++) { 
            if (NestedIntegerIsInteger(nestedList[i])) { 
                (iter->vals)[(iter->size)++] = NestedIntegerGetInteger(nestedList[i]);
            } else { 
                dfs(iter, NestedIntegerGetList(nestedList[i]), NestedIntegerGetListSize(nestedList[i]));
            }
        }
    }
    
    struct NestedIterator *nestedIterCreate(struct NestedInteger **nestedList, int nestedListSize) { 
        struct NestedIterator *ret = malloc(sizeof(struct NestedIterator));
        ret->vals = malloc(sizeof(int) * 20001);
        ret->size = 0;
        ret->cur = 0;
        dfs(ret, nestedList, nestedListSize);
        return ret;
    }
    
    bool nestedIterHasNext(struct NestedIterator *iter) { 
        return iter->cur != iter->size;
    }
    
    int nestedIterNext(struct NestedIterator *iter) { 
        return (iter->vals)[(iter->cur)++];
    }
    
    void nestedIterFree(struct NestedIterator *iter) { 
        free(iter->vals);
        free(iter);
    }

### 方法四：栈(面试的时候需要写出来) ###

[负雪明烛][Link 1]

class NestedIterator {
    public:
        NestedIterator(vector<NestedInteger> &nestedList) {
            for (int i = nestedList.size() - 1; i >= 0; --i) {
                st.push(nestedList[i]);
            }
        }
    
        int next() {
            NestedInteger cur = st.top(); st.pop();
            return cur.getInteger();
        }
    
        bool hasNext() {
            while (!st.empty()) {
                NestedInteger cur = st.top();
                if (cur.isInteger()) {
                    return true;
                }
                st.pop();
                for (int i = cur.getList().size() - 1; i >= 0; --i) {
                    st.push(cur.getList()[i]);
                }
            }
            return false;
        }
    private:
        stack<NestedInteger> st;
    };

# 测试 #

## NestedInteger接口类 ##

public interface NestedInteger { 
    	     // @return true if this NestedInteger holds a single integer, rather than a nested list.
    	     public boolean isInteger();
    	
    	     // @return the single integer that this NestedInteger holds, if it holds a single integer
    	     // Return null if this NestedInteger holds a nested list
    	     public Integer getInteger();
    	
    	     // @return the nested list that this NestedInteger holds, if it holds a nested list
    	     // Return null if this NestedInteger holds a single integer
    	     public List<NestedInteger> getList();
    }

## SingletonInteger 实现类 ##

/**处理单个整数*/
    public class SingletonInteger implements NestedInteger { 
    	
    	private int value;
    	
    	public SingletonInteger(int value) { 
    		super();
    		this.value = value;
    	}
    
    	@Override
    	public boolean isInteger() { 
    		return true;
    	}
    
    	@Override
    	public Integer getInteger() { 
    		return value;
    	}
    
    	@Override
    	public List<NestedInteger> getList() { 
    		return null;
    	}
    
    }

## NestedList 实现类 ##

/** 处理List */
    public class NestedList implements NestedInteger { 
    
    	private List<NestedInteger> list = new ArrayList<NestedInteger>();
    	
    	public NestedList(NestedInteger ...values) { 
    		for(NestedInteger value: values) { 
    			list.add(value);
    		}
    	}
    
    	@Override
    	public boolean isInteger() { 
    		return false;
    	}
    
    	@Override
    	public Integer getInteger() { 
    		return null;
    	}
    
    	@Override
    	public List<NestedInteger> getList() { 
    		return list;
    	}
    
    }

## NestedIterator类 ##

//深度优先搜索
    //先遍历整个嵌套列表，将所有整数存入一个数组，然后遍历该数组从而实现next和 hasNext方法。
    public class NestedIterator implements Iterator<Integer> { 
        private List<Integer> vals;
        private Iterator<Integer> cur;
    
        public NestedIterator(List<NestedInteger> nestedList) { 
            vals = new ArrayList<Integer>();
            dfs(nestedList);
            cur = vals.iterator();
        }
    
        @Override
        public Integer next() { 
            return cur.next();
        }
    
        @Override
        public boolean hasNext() { 
            return cur.hasNext();
        }
    
        private void dfs(List<NestedInteger> nestedList) { 
            for (NestedInteger nest : nestedList) { 
                if (nest.isInteger()) { 
                    vals.add(nest.getInteger());
                } else { 
                    dfs(nest.getList());
                }
            }
        }
    }

## 测试类 ##

public class TestNestedInteger { 
    
    	public static void main(String[] args) { 
    		// [1,[4,[6]]]
    		SingletonInteger s1 = new SingletonInteger(1);
    		SingletonInteger s4 = new SingletonInteger(4);
    		SingletonInteger s6 = new SingletonInteger(6);
    
    		List<NestedInteger> nestedList = new ArrayList<NestedInteger>();
    		nestedList.add(s1);
    		nestedList.add(new NestedList(s4, new NestedList(s6)));
    		// 测试
    		NestedIterator i = new NestedIterator(nestedList);
    		while (i.hasNext()) { 
    			System.out.println(i.next());
    		}
    		
    	}
    
    }

输出

1
    4
    6

[Link 1]: https://leetcode-cn.com/problems/flatten-nested-list-iterator/solution/fu-xue-ming-zhu-xiang-jie-ti-yi-shu-li-d-n4qa/