Skip to content

Latest commit

 

History

History
508 lines (423 loc) · 14.4 KB

File metadata and controls

508 lines (423 loc) · 14.4 KB

English Version

题目描述

给你一个嵌套的整数列表 nestedList 。每个元素要么是一个整数,要么是一个列表;该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化,使之能够遍历这个列表中的所有整数。

实现扁平迭代器类 NestedIterator

  • NestedIterator(List<NestedInteger> nestedList) 用嵌套列表 nestedList 初始化迭代器。
  • int next() 返回嵌套列表的下一个整数。
  • boolean hasNext() 如果仍然存在待迭代的整数,返回 true ;否则,返回 false

你的代码将会用下述伪代码检测:

initialize iterator with nestedList
res = []
while iterator.hasNext()
    append iterator.next() to the end of res
return res

如果 res 与预期的扁平化列表匹配,那么你的代码将会被判为正确。

 

示例 1:

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

示例 2:

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

 

提示:

  • 1 <= nestedList.length <= 500
  • 嵌套列表中的整数值在范围 [-106, 106]

解法

方法一:递归

根据题意要求可以将 NestedInteger 数据结构视作一个 N 叉树,当元素为一个整数时,该节点是 N 叉树的叶子节点,当元素为一个整数数组时,该节点是 N 叉树的非叶子节点,数组中的每一个元素包含子树的所有节点。故直接递归遍历 N 叉树并记录所有的叶子节点即可。

方法二:直接展开

调用 hasNext 时,如果 nestedList 的第一个元素是列表类型,则不断展开这个元素,直到第一个元素是整数类型。 调用 Next 方法时,由于 hasNext() 方法已确保 nestedList 第一个元素为整数类型,直接返回即可。

Python3

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
# class NestedInteger:
#    def isInteger(self) -> bool:
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        """
#
#    def getInteger(self) -> int:
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        """
#
#    def getList(self) -> [NestedInteger]:
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        """


class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        def dfs(nestedList):
            for e in nestedList:
                if e.isInteger():
                    self.vals.append(e.getInteger())
                else:
                    dfs(e.getList())

        self.vals = []
        dfs(nestedList)
        self.cur = 0

    def next(self) -> int:
        res = self.vals[self.cur]
        self.cur += 1
        return res

    def hasNext(self) -> bool:
        return self.cur < len(self.vals)


# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

Java

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * 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();
 * }
 */
public class NestedIterator implements Iterator<Integer> {

    private List<Integer> vals;

    private Iterator<Integer> cur;

    public NestedIterator(List<NestedInteger> nestedList) {
        vals = new ArrayList<>();
        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 e : nestedList) {
            if (e.isInteger()) {
                vals.add(e.getInteger());
            } else {
                dfs(e.getList());
            }
        }
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */

C++

/**
 * // 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) {
        dfs(nestedList);
    }

    int next() {
        return vals[cur++];
    }

    bool hasNext() {
        return cur < vals.size();
    }
private:
    vector<int> vals;
    int cur = 0;

    void dfs(vector<NestedInteger> &nestedList) {
        for (auto& e : nestedList) {
            if (e.isInteger()) {
                vals.push_back(e.getInteger());
            } else {
                dfs(e.getList());
            }
        }
    }
};

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i(nestedList);
 * while (i.hasNext()) cout << i.next();
 */

TypeScript

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *     If value is provided, then it holds a single integer
 *     Otherwise it holds an empty nested list
 *     constructor(value?: number) {
 *         ...
 *     };
 *
 *     Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     isInteger(): boolean {
 *         ...
 *     };
 *
 *     Return the single integer that this NestedInteger holds, if it holds a single integer
 *     Return null if this NestedInteger holds a nested list
 *     getInteger(): number | null {
 *         ...
 *     };
 *
 *     Set this NestedInteger to hold a single integer equal to value.
 *     setInteger(value: number) {
 *         ...
 *     };
 *
 *     Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
 *     add(elem: NestedInteger) {
 *         ...
 *     };
 *
 *     Return the nested list that this NestedInteger holds,
 *     or an empty list if this NestedInteger holds a single integer
 *     getList(): NestedInteger[] {
 *         ...
 *     };
 * };
 */

class NestedIterator {
    private vals: number[];
    private index: number;

    constructor(nestedList: NestedInteger[]) {
        this.index = 0;
        this.vals = [];
        this.dfs(nestedList);
    }

    dfs(nestedList: NestedInteger[]) {
        for (const v of nestedList) {
            if (v.isInteger()) {
                this.vals.push(v.getInteger());
            } else {
                this.dfs(v.getList());
            }
        }
    }

    hasNext(): boolean {
        return this.index < this.vals.length;
    }

    next(): number {
        return this.vals[this.index++];
    }
}

/**
 * Your ParkingSystem object will be instantiated and called as such:
 * var obj = new NestedIterator(nestedList)
 * var a: number[] = []
 * while (obj.hasNext()) a.push(obj.next());
 */

Rust

// #[derive(Debug, PartialEq, Eq)]
// pub enum NestedInteger {
//   Int(i32),
//   List(Vec<NestedInteger>)
// }
struct NestedIterator {
    index: usize,
    vals: Vec<i32>,
}


/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl NestedIterator {

    fn dfs(nestedList: &Vec<NestedInteger>, vals: &mut Vec<i32>) {
        for ele in nestedList.iter() {
            match ele {
                NestedInteger::Int(val) => vals.push(*val),
                NestedInteger::List(list) => Self::dfs(list, vals),
            }
        }
    }

    fn new(nestedList: Vec<NestedInteger>) -> Self {
        let mut vals = vec![];
        Self::dfs(&nestedList, &mut vals);
        Self {
            vals,
            index: 0,
        }
    }

    fn next(&mut self) -> i32 {
        let res = self.vals[self.index];
        self.index += 1;
        res
    }

    fn has_next(&self) -> bool {
        self.index < self.vals.len()
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * let obj = NestedIterator::new(nestedList);
 * let ret_1: i32 = obj.next();
 * let ret_2: bool = obj.has_next();
 */

Go

递归:

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * type NestedInteger struct {
 * }
 *
 * // Return true if this NestedInteger holds a single integer, rather than a nested list.
 * func (this NestedInteger) IsInteger() bool {}
 *
 * // 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
 * // So before calling this method, you should have a check
 * func (this NestedInteger) GetInteger() int {}
 *
 * // Set this NestedInteger to hold a single integer.
 * func (n *NestedInteger) SetInteger(value int) {}
 *
 * // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 * func (this *NestedInteger) Add(elem NestedInteger) {}
 *
 * // Return the nested list that this NestedInteger holds, if it holds a nested list
 * // The list length is zero if this NestedInteger holds a single integer
 * // You can access NestedInteger's List element directly if you want to modify it
 * func (this NestedInteger) GetList() []*NestedInteger {}
 */

type NestedIterator struct {
	iterator      []int
	index, length int
}

func Constructor(nestedList []*NestedInteger) *NestedIterator {
	result := make([]int, 0)
	var traversal func(nodes []*NestedInteger)
	traversal = func(nodes []*NestedInteger) {
		for _, child := range nodes {
			if child.IsInteger() {
				result = append(result, child.GetInteger())
			} else {
				traversal(child.GetList())
			}
		}
	}
	traversal(nestedList)
	return &NestedIterator{iterator: result, index: 0, length: len(result)}
}

func (this *NestedIterator) Next() int {
	res := this.iterator[this.index]
	this.index++
	return res
}

func (this *NestedIterator) HasNext() bool {
	return this.index < this.length
}

直接展开:

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * type NestedInteger struct {
 * }
 *
 * // Return true if this NestedInteger holds a single integer, rather than a nested list.
 * func (this NestedInteger) IsInteger() bool {}
 *
 * // 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
 * // So before calling this method, you should have a check
 * func (this NestedInteger) GetInteger() int {}
 *
 * // Set this NestedInteger to hold a single integer.
 * func (n *NestedInteger) SetInteger(value int) {}
 *
 * // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 * func (this *NestedInteger) Add(elem NestedInteger) {}
 *
 * // Return the nested list that this NestedInteger holds, if it holds a nested list
 * // The list length is zero if this NestedInteger holds a single integer
 * // You can access NestedInteger's List element directly if you want to modify it
 * func (this NestedInteger) GetList() []*NestedInteger {}
 */

type NestedIterator struct {
	nested *list.List
}

func Constructor(nestedList []*NestedInteger) *NestedIterator {
	nested := list.New()
	for _, v := range nestedList {
		nested.PushBack(v)
	}
	return &NestedIterator{nested: nested}
}

func (this *NestedIterator) Next() int {
	res := this.nested.Front().Value.(*NestedInteger)
	this.nested.Remove(this.nested.Front())
	return res.GetInteger()
}

func (this *NestedIterator) HasNext() bool {
	for this.nested.Len() > 0 && !this.nested.Front().Value.(*NestedInteger).IsInteger() {
		front := this.nested.Front().Value.(*NestedInteger)
		this.nested.Remove(this.nested.Front())
		nodes := front.GetList()
		for i := len(nodes) - 1; i >= 0; i-- {
			this.nested.PushFront(nodes[i])
		}
	}
	return this.nested.Len() > 0
}

...