LeetCode/src/main/java/L0341_FlattenNestedListIterator.java at master · LjyYano/LeetCode · GitHub

History

221 lines (195 loc) · 7.05 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

import java.util.ArrayList;

import java.util.Iterator;

import java.util.List;

import java.util.Stack;

/**

* https://leetcode.cn/problems/flatten-nested-list-iterator/

* 给你一个嵌套的整数列表 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

* 嵌套列表中的整数值在范围 [-10^6, 10^6] 内

public class L0341_FlattenNestedListIterator implements Iterator<Integer> {

// 使用栈来存储列表元素

private Stack<NestedInteger> stack;

public L0341_FlattenNestedListIterator(List<NestedInteger> nestedList) {

stack = new Stack<>();

// 将列表元素倒序压入栈中

for (int i = nestedList.size() - 1; i >= 0; i--) {

stack.push(nestedList.get(i));

}

@Override

public Integer next() {

// 确保栈顶元素是整数

if (!hasNext()) {

return null;

}

return stack.pop().getInteger();

}

@Override

public boolean hasNext() {

// 处理栈顶的嵌套列表，直到栈顶为整数或栈为空

while (!stack.isEmpty()) {

NestedInteger current = stack.peek();

if (current.isInteger()) {

return true;

}

// 如果是列表，展开它

stack.pop();

List<NestedInteger> list = current.getList();

for (int i = list.size() - 1; i >= 0; i--) {

stack.push(list.get(i));

}

return false;

}

// 这个接口在 LeetCode 中已经定义，这里为了代码完整性添加

private 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 empty list if this NestedInteger holds a single integer

public List<NestedInteger> getList();

}

public static void main(String[] args) {

// 创建测试用例

List<NestedInteger> nestedList = new ArrayList<>();

nestedList.add(new NestedInteger() {

@Override

public boolean isInteger() {

return false;

}

@Override

public Integer getInteger() {

return null;

}

@Override

public List<NestedInteger> getList() {

List<NestedInteger> list = new ArrayList<>();

list.add(new NestedInteger() {

@Override

public boolean isInteger() {

return true;

}

@Override

public Integer getInteger() {

return 1;

}

@Override

public List<NestedInteger> getList() {

return new ArrayList<>();

}

});

list.add(new NestedInteger() {

@Override

public boolean isInteger() {

return true;

}

@Override

public Integer getInteger() {

return 1;

}

@Override

public List<NestedInteger> getList() {

return new ArrayList<>();

}

});

return list;

}

});

nestedList.add(new NestedInteger() {

@Override

public boolean isInteger() {

return true;

}

@Override

public Integer getInteger() {

return 2;

}

@Override

public List<NestedInteger> getList() {

return new ArrayList<>();

}

});

nestedList.add(new NestedInteger() {

@Override

public boolean isInteger() {

return false;

}

@Override

public Integer getInteger() {

return null;

}

@Override

public List<NestedInteger> getList() {

List<NestedInteger> list = new ArrayList<>();

list.add(new NestedInteger() {

@Override

public boolean isInteger() {

return true;

}

@Override

public Integer getInteger() {

return 1;

}

@Override

public List<NestedInteger> getList() {

return new ArrayList<>();

}

});

list.add(new NestedInteger() {

@Override

public boolean isInteger() {

return true;

}

@Override

public Integer getInteger() {

return 1;

}

@Override

public List<NestedInteger> getList() {

return new ArrayList<>();

}

});

return list;

}

});

// 测试迭代器

L0341_FlattenNestedListIterator iterator = new L0341_FlattenNestedListIterator(nestedList);

List<Integer> result = new ArrayList<>();

while (iterator.hasNext()) {

result.add(iterator.next());

}

System.out.println("扁平化后的列表: " + result); // 预期输出: [1, 1, 2, 1, 1]

}

LeetCode/src/main/java/L0341_FlattenNestedListIterator.java at master · LjyYano/LeetCode · GitHub

Expand file tree

Breadcrumbs

L0341_FlattenNestedListIterator.java

Latest commit

History

Breadcrumbs

L0341_FlattenNestedListIterator.java

File metadata and controls