Amazon题库
今天开始一道一道刷Amazon的面试题吧！题目列表是从 这里 找的，不知道准不准。
二叉树的最大深度
给一个二叉树，这个二叉树有几层？
这也太简单了，按层遍历一波带走
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if root:
queue = [root]
depth = 0
while queue:
size = len(queue)
for _ in range(size):
node = queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
depth += 1
return depth
else:
return 0
二叉树是否是另一棵二叉树的子树
给两个二叉树
s, t，t是否是s的子树？
遍历 s 的每个子树，看有没有哪个子树和 t 相等就好了。
首先要写一个helper function，判断两个二叉树是否是相等。很简单，用递归写就好了
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
queue = [s]
while queue:
node = queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if self.isEqualTree(node, t):
return True
return False
def isEqualTree(self, s: TreeNode, t: TreeNode) -> bool:
if s == None and t == None:
return True
elif s != None and t != None:
return s.val == t.val and self.isEqualTree(s.left, t.left) and self.isEqualTree(s.right, t.right)
else:
return False
一组一组地颠倒链表
给一个链表，每次数 \(k\) 个元素，颠倒一下。如果到最后不满 \(k\) 个，就不动。
比如
1, 2, 3, 4, 5
如果 \(k = 2\) ，那么结果是
2, 1, 4, 3, 5如果 \(k = 3\) ，那么结果是
3, 2, 1, 4, 5
如果我自己写，很简单，我肯定先把链表转换成List，然后做颠倒，然后再转换回来。但是这道题要求常数空间，所以就不能这么做了。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
不使用内建函数实现 \(x^n\)
注意 \(n\) 可能是是负数哦。
分情况讨论吧
如果 \(x = 0\)
并且 \(n = 0\) ，那么未定义
否则就是0
如果 \(x \neq 0\)
如果 \(n = 0\) ，那么是1
如果 \(n < 0\) ，那么是 \({1 \over x^{-n}}\)
如果 \(n > 0\) 并且是个偶数，那么做一下转换
\[x^n = x^{2 \cdot {n \over 2}} = (x^2)^{n \over 2}\]如果 \(n > 0\) 并且是个奇数，那么 \(n - 1\) 就是偶数了啊
\[x^n = x^{1 + (n - 1)} = x \cdot x^{n - 1}\]
注意Python虽然int不会overflow，但是float会overflow……这点真的好奇怪。
而且 x ** 2 和 x * x 效果还不一样啊！ x ** 2 可能会overflow但是 x * x 就不会overflow。
class Solution:
def myPow(self, x: float, n: int) -> float:
if x == 0:
if n == 0:
return float("nan")
else:
return 0
else:
if n == 0:
return 1
elif n < 0:
return 1 / self.myPow(x, -n)
elif n % 2 == 0:
return self.myPow(x * x, n // 2) # 很奇怪，我也不知道为什么这里用x * x就不会overflow，但是用x ** 2就会overflow
else:
return x * self.myPow(x, n - 1)
垂直遍历二叉树
这道是人民币玩家才能做的……
我还是先把最高频的50道做完吧_(:з」∠)_
2 sum
这个说烂了。
竖式加法
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
sentinel = ListNode(None)
head = sentinel
carry = 0
while l1 != None or l2 != None:
summation = carry
if l1:
summation += l1.val
l1 = l1.next
if l2:
summation += l2.val
l2 = l2.next
if summation >= 10:
carry = 1
summation -= 10
else:
carry = 0
head.next = ListNode(summation)
head = head.next
if carry == 1:
head.next = ListNode(1)
return sentinel.next
实现LRU缓存
用linked list和hash map实现。
根本矛盾是
linked list可以保存顺序信息，但是没法做到 \(O(1)\) 访问任意一个节点
hash map可以做到 \(O(1)\) 访问，但是没法保存顺序信息
所以这两个是互补的，同时用它们，就可以做到既能保存顺序信息、又能 \(O(1)\) 访问。怎么做呢？
hash map的key存key，value不存value，存linked list里的节点的引用
linked list里的节点既存key又存value
为什么要这么麻烦？你仔细想一下每个流程
\(O(1)\) 判断key是否存在
可以用hash map做到
\(O(1)\) 返回一个key对应的value
这个也可以用hash map做到
如果缓存满了，又要加入新的key，需要 \(O(1)\) 删除最远使用的key
这个绝对没问题，这样安排linked list：越靠左边的节点，代表越最近访问的key。linked list可以做到 \(O(1)\) 删除最后一个节点。
删除linked list里最后一个节点的时候，hash map里的条目也要跟着删除，可是linked list里面的节点里只存value，不知道对应的是hash map里的哪一个条目啊。
那就让linked list里面的节点不光要存value，也要存key就好了。
如果是访问一个缓存中已经存在的key，需要 \(O(1)\) 把那个key移动到最近
这个就有点难了，linked list并不能做到 \(O(1)\) 其中任意一个节点。
那怎么办？hash map可以做到啊，让hash map的不存value、而是存节点的引用不就好了？
再次总结一下重点
需要hash map和double linked list这是肯定的，我能想到
hash map的value存的是节点的引用，而不是value
linked list里面的节点存的是key和value
class DoubleLinkedListNode:
def __init__(self, value):
self.value = value
self.previous = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.keyNodeMapping = {} # key是key，value不是value，而是节点的引用，不然做不到所有操作都是O(1)
self.head = DoubleLinkedListNode(None) # 头虚节点
self.tail = DoubleLinkedListNode(None) # 尾虚节点
self.head.previous = None
self.head.next = self.tail
self.tail.previous = self.head
self.tail.next = None
self.capacity = capacity
def get(self, key: int) -> int:
if key in self.keyNodeMapping: # 缓存里存在这个key
node = self.keyNodeMapping[key] # 取出节点
# 下面的操作是把节点取出来、放到linked list的最前面
left = node.previous # left先是节点的前面一个节点
right = node.next # right先是节点的后面一个节点
left.next = right # left直接指向right，绕过节点
right.previous = left # right直接指向left，绕过节点
# 这样节点就从list里删除了
# 下面要把节点插入到最前面
left = self.head # left变成最前面的虚节点
right = self.head.next # right变成第一个节点
left.next = node # left指向节点
right.previous = node # right指向节点
node.next = right # 节点指向left
node.previous = left # 节点指向right
return node.value[1]
else:
return -1
def put(self, key: int, value: int) -> None:
if key in self.keyNodeMapping: # 如果key在缓存里面了
self.get(key) # 先取一次，这样间接做到了把节点放到最前面
self.keyNodeMapping[key].value = (key, value) # 再更新value的值
return
else: # 如果key不在缓存里面
if len(self.keyNodeMapping) >= self.capacity: # 先看下缓存有没有满，如果满了，要先删掉linked list最后那个节点
node = self.tail.previous
left = node.previous
right = self.tail
left.next = right
right.previous = left
del self.keyNodeMapping[node.value[0]]
# 建一个新节点，放到linked list的最前面
node = DoubleLinkedListNode((key, value))
left = self.head
right = self.head.next
node.previous = left
node.next = right
left.next = node
right.previous = node
self.keyNodeMapping[key] = node
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
最长回文substring
岛屿的数量
Union find基础题，不多说了。
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if grid == []:
return 0
rowCount = len(grid)
columnCount = len(grid[0])
mapping = {}
for rowIndex, row in enumerate(grid):
for columnIndex, box in enumerate(row):
if box == "1":
position = (rowIndex, columnIndex)
mapping[position] = mapping.get(position, position)
neighbors = [
(rowIndex - 1, columnIndex),
(rowIndex + 1, columnIndex),
(rowIndex, columnIndex - 1),
(rowIndex, columnIndex + 1),
]
for neighbor in neighbors:
if 0 <= neighbor[0] < rowCount and 0 <= neighbor[1] < columnCount and grid[neighbor[0]][neighbor[1]] == "1":
mapping[neighbor] = mapping.get(neighbor, neighbor)
self.union(mapping, position, neighbor)
return len({self.rootOf(mapping, k) for k in mapping.keys()})
def union(self, mapping: dict, p: "Type", q: "Type") -> None:
rootOfP = self.rootOf(mapping, p)
rootOfQ = self.rootOf(mapping, q)
mapping[rootOfP] = rootOfQ
def rootOf(self, mapping: dict, p: "Type") -> "Type":
while p != mapping[p]:
mapping[p] = mapping[mapping[p]]
p = mapping[p]
return p
def isConnected(self, mapping: dict, p: "Type", q: "Type") -> bool:
return self.rootOf(mapping, p) == self.rootOf(mapping, q)
实现LFU缓存
class DoubleLinkedListNode:
def __init__(self, value):
self.value = value
self.previous = None
self.next = None
class LFUCache:
def __init__(self, capacity: int):
self.keyNodeMapping = {}
self.capacity = capacity
self.head = DoubleLinkedListNode(None)
self.tail = DoubleLinkedListNode(None)
self.head.next = self.tail
self.tail.previous = self.head
def get(self, key: int) -> int:
if key in self.keyNodeMapping:
node = self.keyNodeMapping[key]
left = node.previous
right = node.next
left.next = right
right.previous = left
node.value[-1] += 1
while True:
if left.previous == None:
break
elif left.value[-1] > node.value[-1]:
break
else:
left = left.previous
left = left
right = left.next
node.next = right
node.previous = left
left.next = node
right.previous = node
return node.value[1]
else:
return -1
def put(self, key: int, value: int) -> None:
if self.capacity == 0:
return
if key in self.keyNodeMapping:
self.get(key)
self.keyNodeMapping[key].value[1] = value
return
else:
if len(self.keyNodeMapping) >= self.capacity:
node = self.tail.previous
left = node.previous
right = node.next
left.next = right
right.previous = left
del self.keyNodeMapping[node.value[0]]
node = DoubleLinkedListNode([key, value, 0])
left = self.tail.previous
right = self.tail
left.next = node
right.previous = node
node.previous = left
node.next = right
self.keyNodeMapping[key] = node
self.get(key)
# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
关键通路
哇，这题很有意思的
给一个无向无权图 \(G = (V, E)\) ，含有 \(n\) 个节点，起点是0号节点，终点是 \(n - 1\) 号节点。图中哪些边满足，仅仅就删掉这一条边之后，就没有办法从起点走到终点了呢？
class Solution:
def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
def rootOf(self, mapping: dict, p: "Type") -> "Type":
while p != mapping[p]:
mapping[p] = mapping[mapping[p]]
p = mapping[p]
return p
def union(self, mapping: dict, p: "Type", q: "Type") -> None:
rootOfP = self.rootOf(mapping, p)
rootOfQ = self.rootOf(mapping, q)
mapping[rootOfP] = rootOfQ
def isConnected(self, mapping: dict, p: "Type") -> bool:
return self.rootOf(mapping, p) == self.rootOf(mapping, q)
验证括号嵌套
简单的，用stack
class Solution:
def isValid(self, s: str) -> bool:
stack = []
for v in s:
if v in "([{":
stack.append(v)
else:
if stack == []:
return False
else:
if stack[-1] == "(" and v == ")":
stack.pop()
elif stack[-1] == "[" and v == "]":
stack.pop()
elif stack[-1] == "{" and v == "}":
stack.pop()
else:
return False
return stack == []
合并两个排好序的链表
想象一下在你面前有两列从小到大排列好的扑克牌，你会怎么把它们合并成一个扑克牌呢？肯定是分别比较两列扑克牌的最前面、最小的那张，看哪个牌堆的第一张扑克牌小，取出来。如果某列扑克牌取完了，就直接把剩下的那一堆移动过来就好了。
这样写其实我不喜欢，我觉得改变了原来的链表，最好应该能生成一个新的。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
sentinel = ListNode(None)
head = sentinel
while l1 != None and l2 != None:
if l1.val > l2.val:
head.next = l2
l2 = l2.next
else:
head.next = l1
l1 = l1.next
head = head.next
if l1 == None:
head.next = l2
else:
head.next = l1
return sentinel.next
合并多个排好序的链表
我好怀疑这个题是不是上一题的follow-up，频率都离得这么近。
Merge sort里会用到这个函数。
做法是不停地两个两个合并（可以直接利用上一题的函数），直到最后只有一个linked list为止。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if len(lists) == 0:
return None
res = lists
while len(res) != 1:
temp = []
if len(res) % 2 == 0:
for i in range(len(res) // 2):
list1 = res[2 * i]
list2 = res[2 * i + 1]
temp.append(self.merge2Lists(list1, list2))
else:
for i in range((len(res) - 1) // 2):
list1 = res[2 * i]
list2 = res[2 * i + 1]
temp.append(self.merge2Lists(list1, list2))
temp.append(res[-1])
res = temp
return res[0]
def merge2Lists(self, l1: ListNode, l2: ListNode) -> ListNode:
sentinel = ListNode(None)
head = sentinel
while l1 != None and l2 != None:
if l1.val > l2.val:
head.next = l2
l2 = l2.next
else:
head.next = l1
l1 = l1.next
head = head.next
if l1 == None:
head.next = l2
else:
head.next = l1
return sentinel.next
排序两种日志字符串
这个毫无难度。按照它说的做就好了。先把letter log和digit log分成两堆，然后用自定义key排序digit log，注意它说的
先按identifier后面的排序
如果出现重复的，再按identifier后面的日志内容排序
class Solution:
def reorderLogFiles(self, logs: List[str]) -> List[str]:
letterLogs = []
digitLogs = []
for log in logs:
if log.split()[1].isdigit():
digitLogs.append(log)
else:
letterLogs.append(log)
return sorted(letterLogs, key=lambda v: " ".join(v.split()[1: ] + v.split()[0: 1])) + digitLogs
链表深复制
我的做法很简单，搞一个hash map，key是老节点，value是新节点。第一遍遍历把所有新节点对象都造好，第二遍遍历的时候利用hash map解决引用问题。
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
sentinel = head # 保存好旧链表头
oldNewMapping = {
None: None
} # key是老节点，value是新节点
while head: # 第一遍遍历
oldNewMapping[head] = Node(head.val) # 只要复制出新节点就行，先不要解决引用问题
head = head.next
head = sentinel
while head: # 第二遍遍历，解决引用问题
oldNewMapping[head].next = oldNewMapping[head.next] # 新节点的next指向旧节点next指向的那个节点对应的新节点
oldNewMapping[head].random = oldNewMapping[head.random]
head = head.next # 新节点的random指向旧节点random指向的那个节点对应的新节点
return oldNewMapping[sentinel] # 返回head对应的新节点
整数的英文说法
class Solution:
def numberToWords(self, num: int) -> str:
string = str(num)
units = string[-3: ]
thousands = string[-6: -3]
序列化和反序列化二叉树
最少需要多少间会议室
给一些左闭右开的区间，代表会议的时间区间，至少需要多少间会议室？
这个题目的 简单版本 是
给一些左闭右开区间，代表时间区间，这些时间区间是否两两之间都互相兼容、没有时间冲突？
from typing import *
import heapq
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
intervals = sorted(intervals, key=lambda v: v[0])
roomFinishingTimes = []
heapq.heapify(roomFinishingTimes)
for v in intervals:
if roomFinishingTimes:
if heapq.nsmallest(1, roomFinishingTimes)[0] <= v[0]:
heapq.heappop(roomFinishingTimes)
heapq.heappush(roomFinishingTimes, v[1])
else:
heapq.heappush(roomFinishingTimes, v[1])
else:
heapq.heappush(roomFinishingTimes, v[1])
return len(roomFinishingTimes)
s = Solution()
print(s.minMeetingRooms([[0, 30],[5, 10],[15, 20]])) # 2
print(s.minMeetingRooms([[7,10],[2,4]])) # 1
print(s.minMeetingRooms([[2,15],[36,45],[9,29],[16,23],[4,9]])) # 2
离原点最近的 \(k\) 个点
太简单了吧……这种题怎么会高频考。
class Solution:
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
return sorted(points, key=lambda v: v[0] ** 2 + v[1] ** 2)[: K]
pub struct Solution;
impl Solution {
pub fn k_closest(points: Vec<Vec<i32>>, k: i32) -> Vec<Vec<i32>> {
let mut points: Vec<Vec<i32>> = points.iter().cloned().collect();
points.sort_by_key(|v: Vec<i32>| {
v[0].pow(2) + v[1].pow(2)
});
return points[..k as usize].to_vec();
}
}
乱序字符分组
给一堆字符串，把anagram相同的都归到一组。
如果两个字符串互为anagram，那么给它们按字典序排序之后得到相同的字符串。
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
mapping = {}
for string in strs:
anagram = "".join(sorted(string))
if anagram in mapping:
mapping[anagram].append(string)
else:
mapping[anagram] = [string]
return list(mapping.values())
设计插入、删除、随机选取都是 \(O(1)\) 的数据结构
这个真的太牛逼了，我看了答案觉得啧啧称奇，自己估计永远都没法想出来。
首先是插入和删除都要 \(O(1)\) 这个需求，很容易想到用hash set或者hash map。但是随机选取要 \(O(1)\) 这个需求用hash set和hash map是没法做到的，因为hash系列（hash set和hash map）都是无序的，而随机选取的本质是生成一个随机地址，然后选择那个随机地址上的内容。
有人说，那没问题啊，我先把hash map里所有的key都放在array list里面，再随机好不好啊？那这样把hash map转换成array list的复杂度就是 \(O(n)\) 了。不满足要求了。
所以这里需要用一下hash map和array list的结合，同时又要避免转换的过程。我想到了LRU那道题里面的做法。回忆一下LRU那道题，hash map里面存的是linked list里的node，node里面存的是key、value。
那么这里是不是也可以这样搞呢？可以啊，让hash map的key存题目里那个 val ，value存array list里key所在的下标，然后array list里再存key。想想这样是不是可以做到随机选取是 \(O(1)\) ？可以的，给随机数之后， \(O(1)\) 时间内能定位到array list的某一个元素，而这个元素正好是某个 val ，那不就是 \(O(1)\) 了吗？
插入的时候可以做到 \(O(1)\) 吗？可以的，直接在hash map里建一个新的条目，再在array list的最后追加一个元素 val ，让新条目的value指向这个元素（也就是存这个元素的下标）就好了。
但是问题是删除没法做到 \(O(1)\) 。我一开始的想法是，删除某个 val 的时候，只需要删掉hash map里对应的条目，array list里面的东西不管，随机选取的时候，如果抽中某个hash map不存在的 val 就再抽一次……这样有一个问题就是如果hash map里元素基本上都删掉了，随机选取就会很慢，因为总是抽到hash map里面没有的东西。
怎么解决这个问题呢？精妙的部分来了。删除的时候，array list里面的元素也是要跟着删除的，然而这里有一个矛盾，删除array list里的某个元素的复杂度是 \(O(n)\) ，因为假如你删的是最后一个元素，没问题，删掉就好了；假如不巧你删掉的是第一个元素，那么后面所有的元素都要往前顺位。
那我用linked list好不好？linked list虽然避免了删除 \(O(n)\) 的缺点，但是linked list没有随机访问的性质啊，访问linked list的第一个元素和最后一个元素的复杂度是不一样的，那么这样的话随机选取 \(O(1)\) 那个需求就没法满足了。
怎么办？刚才其实暗示过了，删除array list的最后一个元素是最快的，那我不如把我要删的那个元素和array list的最后一个元素调换一下位置。啥意思呢？假设我要删除的条目是 (key1, value1) ，array list的最后一个元素存的是 key2 ，那么很简单，我调换一下 value1, value2 ，两个条目变成
(key1, value2) -> value2 指向array list的最后一个元素
(key2, value1)
再让 array[value1] = value1, array[value2] = value2 ，然后删掉hash map中的 (key1, value2) 和array list中的最后一个元素，是不是就好了？
简单画了一个图
import random
class RandomizedSet:
def __init__(self):
"""
Initialize your data structure here.
"""
self.mapping = {} # key存val，value存val在array list中的下标
self.buffer = [] # 这就是那个array list，存的是val
def insert(self, val: int) -> bool: # 插入的时候比较简单
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
"""
if val in self.mapping: # 如果本来就在里面
return False # 啥也不做
else: # 如果不在里面
self.mapping[val] = len(self.buffer) # 开一个新的条目，key存val，value指向array list的最后一个格子
self.buffer.append(val) # array list的最后建一个新的格子，存val
return True
def remove(self, val: int) -> bool: # 删除的时候是最麻烦的
"""
Removes a value from the set. Returns true if the set contained the specified element.
"""
if val in self.mapping: # 如果val存在
thatValue = self.buffer[-1] # 先看下array list的最后一个元素是什么
self.mapping[val], self.mapping[thatValue] = self.mapping[thatValue], self.mapping[val] # 调换一下两个条目的value
# self.buffer[self.mapping[val]] = val # 没有必要更新这个条目的value指向的array list里那个格子里的元素，因为反正要删掉的
self.buffer[self.mapping[thatValue]] = thatValue # 更新一下那个条目的value指向的array list里那个格子里的元素
self.buffer.pop() # 删掉array list的最后一个元素
self.mapping.pop(val) # 删掉hash map里对应的条目
return True
else: # 如果val不存在
return False # 啥也不做
def getRandom(self) -> int: # 随机取也很简单
"""
Get a random element from the set.
"""
index = random.randint(0, len(self.buffer) - 1) # 随机产生一个下标
return self.buffer[index] # 到array list里面去取那个下标的val
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()
二叉树中最大路径和
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
res = float("-inf")
queue = [root]
while queue:
size = len(queue)
for _ in range(size):
node = queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res = max(res, self.maxPathSumPassingHere(node))
return res
def maxPathSumStartingHere(self, root: TreeNode) -> int:
if root:
res = root.val
else:
return 0
def maxPathSumPassingHere(self, root: TreeNode) -> int:
嵌套列表降维
就是把类似 [1, 2, [1, 2, [3]], [2, 3]] 这种东西展平成 [1, 2, 1, 2, 3, 2, 3] 。
我自己做的话肯定是一下子就把整个列表弄出来存在那里，然后需要的时候一个一个吐出来。
但是面试的时候可能会叫你用online的方法，因为这样省内存。
想了很久，中间试过递归之类的办法，但是好像都不省内存。最后看了答案，发现超级简单。
用一个queue，每次 hasNext() 的时候，保证最前面的元素是integer就可以了。如果发现最前面的元素不是integer，就不停地展开，直到最前面的元素是integer为止。这样在 next() 的时候，只需要把第一个元素pop出来就好了。
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger(object):
# def isInteger(self):
# """
# @return True if this NestedInteger holds a single integer, rather than a nested list.
# :rtype bool
# """
#
# def getInteger(self):
# """
# @return the single integer that this NestedInteger holds, if it holds a single integer
# Return None if this NestedInteger holds a nested list
# :rtype int
# """
#
# def getList(self):
# """
# @return the nested list that this NestedInteger holds, if it holds a nested list
# Return None if this NestedInteger holds a single integer
# :rtype List[NestedInteger]
# """
# class NestedIterator(object):
# def __init__(self, nestedList):
# """
# Initialize your data structure here.
# :type nestedList: List[NestedInteger]
# """
# self.buffer = sum((NestedIterator.flatten(v) for v in nestedList), [])
# @staticmethod
# def flatten(array: "NestedIterator") -> "List":
# if array.isInteger():
# return [array.getInteger()]
# else:
# res = []
# for v in array.getList():
# if v.isInteger():
# res.append(v.getInteger())
# else:
# res.extend(NestedIterator.flatten(v))
# return res
# def next(self):
# """
# :rtype: int
# """
# return self.buffer.pop(0)
# def hasNext(self):
# """
# :rtype: bool
# """
# return self.buffer != []
# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())
# 像上面的做法面试里面一定会被批判的，因为太浪费内存了
import collections
class NestedIterator:
def __init__(self, nestedList: [NestedInteger]):
self.queue = collections.deque(nestedList) # 搞一个queue
def next(self) -> int:
return self.queue.popleft().getInteger() # 只要把第一个元素pop出来就可以了
def hasNext(self) -> bool:
while self.queue: # queue当然不能为空
if self.queue[0].isInteger(): # 如果发现第一个元素已经是integer了
return True # 那下一次next()就pop这个
else: # 如果发现第一个元素不是integer
toExpand = collections.deque(self.queue.popleft().getList()) # 把第一个元素展开
self.queue = toExpand + self.queue # 展开之后放到最前面。到下一个迭代再来检测第一个元素到底是不是integer，如果还不是的话，继续展开，直到是integer为止
return False # queue为空说明没有下一个了
# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())