题目不让我干什么,我偏要干什么

2021年11月24日 阅读数:3
这篇文章主要向大家介绍题目不让我干什么,我偏要干什么,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

 

https://labuladong.gitee.io/algo/2/18/29/java

 

读完本文,你不只学会了算法套路,还能够顺便去 LeetCode 上拿下以下题目:git

341.扁平化嵌套列表迭代器(中等)算法

———–设计模式

今天来说一道很是有启发性的设计题目,为何说它有启发性,咱们后面再说。数据结构

1、题目描述

这是 LeetCode 第 341 题扁平化嵌套列表迭代器,我来描述一下题目:oop

首先,如今有一种数据结构 NestedInteger,这个结构中存的数据多是一个 Integer 整数,也多是一个 NestedInteger 列表。注意,这个列表里面装着的是 NestedInteger,也就是说这个列表中的每个元素多是个整数,可能又是个列表,这样无限递归嵌套下去……spa

NestedInteger 有以下 API:设计

public class NestedInteger { // 若是其中存的是一个整数,则返回 true,不然返回 false public boolean isInteger(); // 若是其中存的是一个整数,则返回这个整数,不然返回 null public Integer getInteger(); // 若是其中存的是一个列表,则返回这个列表,不然返回 null public List<NestedInteger> getList(); } 

咱们的算法会被输入一个 NestedInteger 列表,咱们须要作的就是写一个迭代器类,将这个带有嵌套结构 NestedInteger 的列表「拍平」:code

public class NestedIterator implements Iterator<Integer> { // 构造器输入一个 NestedInteger 列表 public NestedIterator(List<NestedInteger> nestedList) {} // 返回下一个整数 public Integer next() {} // 是否还有下一个元素? public boolean hasNext() {} } 

咱们写的这个类会被这样调用,先调用 hasNext 方法,后调用 next 方法:blog

NestedIterator i = new NestedIterator(nestedList);
while (i.hasNext())
    print(i.next());

好比示例 1,输入的列表里有三个 NestedInteger,两个列表型的 NestedInteger 和一个整数型的 NestedInteger

学过设计模式的朋友应该知道,迭代器也是设计模式的一种,目的就是为调用者屏蔽底层数据结构的细节,简单地经过 hasNext 和 next 方法有序地进行遍历。

为何说这个题目颇有启发性呢?由于我最近在用一款相似印象笔记的软件,叫作 Notion(挺有名的)。这个软件的一个亮点就是「万物皆 block」,好比说标题、页面、表格都是 block。有的 block 甚至能够无限嵌套,这就打破了传统笔记本「文件夹」->「笔记本」->「笔记」的三层结构。

回想这个算法问题,NestedInteger 结构实际上也是一种支持无限嵌套的结构,并且能够同时表示整数和列表两种不一样类型,我想 Notion 的核心数据结构 block 估计也是这样的一种设计思路。

那么话说回来,对于这个算法问题,咱们怎么解决呢?NestedInteger 结构能够无限嵌套,怎么把这个结构「打平」,为迭代器的调用者屏蔽底层细节,获得扁平化的输出呢?

_____________