KK's blog

LeetCode 341 Flatten Nested List Iterator

Posted on 2026-05-27 Edited on 2026-06-03 Disqus:

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList. int next() Returns the next integer in the nested list.
boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

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

If res matches the expected flattened list, then your code will be judged as correct.

Example 1:

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:

Input: nestedList = [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

Constraints: 1 <= nestedList.length <= 500
* The values of the integers in the nested list is in the range [-106, 106].

题目大意：

实现Nested List的Iterator。Nested List是NestedInteger的数组，NestedInteger可以是int，也可以是Nested List
nestedList = [NestedInteger]
NestedInteger 用isInteger()来判断
-> 2 by getInteger()
-> [2, 3] by getList()

解题思路：

有点似括号题但区别是从前往后读取。用Queue或Stack都可以，插入或删除其一需要反序，删除nestedinteger(=list)后要将它里面所有nestedinteger加入。Queue要从队首加入和删除，Stack要从栈顶加入和删除，用Stack比较方便。

Nested List题目：
LeetCode 341 Flatten Nested List Iterator Iterator - Stack
LeetCode 339 Nested List Weight Sum - BFS
LeetCode 364 Nested List Weight Sum II - BFS

解题步骤：

Iterator题目都是用Stack，比如BST Iterator
init和next都可以假设是用int来完成，用reversed加入
next则要考虑两种情况

注意事项：

用Stack，逆序将nestedList中nestedinteger加入到stack，直到栈顶元素为int，hasNext才算结束

Python代码：

class NestedIterator(TestCases):

    def __init__(self, nestedList):
        self.stack = []
        for i in reversed(range(len(nestedList))):
            self.stack.append(nestedList[i])

    def next(self) -> int:
        if self.hasNext():
            return self.stack.pop().getInteger()
        return None

    def hasNext(self) -> bool:
        while self.stack and not self.stack[-1].isInteger():
            nestedList = self.stack.pop().getList()
            for i in reversed(range(len(nestedList))):
                self.stack.append(nestedList[i])
        return True if self.stack else False

算法分析：

next操作时间复杂度为O(V/N)或O(1)，空间复杂度O(L + N), N为所有数，V为nested list数，O(N + V)/N. O(1)如果不存在nested list

LeetCode 394 Decode String

Posted on 2026-05-27 Edited on 2026-06-03 Disqus:

LeetCode

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Example 1:

Input: s = “3[a]2[bc]”
Output: “aaabcbc”

Example 2:

Input: s = “3[a2[c]]”
Output: “accaccacc”

Example 3:

Input: s = “2[abc]3[cd]ef”
Output: “abcabccdcdcdef”

Example 4:

Input: s = “abc3[cd]xyz”
Output: “abccdcdcdxyz”

Constraints:

1 <= s.length <= 30 s consists of lowercase English letters, digits, and square brackets '[]'.
s is guaranteed to be a valid input. All the integers in s are in the range [1, 300].

题目大意：

将循环体表示展开

Stack解题思路(推荐)：

见到括号就考虑用Stack，此题有字符和数字，所以考虑用两个Stack

解题步骤：

运用模板

注意事项：

同级为括号外（包括括号以左，以右），但数字和字符分别存于两个stack。括号内为另一级，入栈。
prev_res+prev_num*[res]
两个stack存储优先级较低的字符以及数字，类似于多重括号2*(3*(4))

Python代码：

def decodeString(self, s: str) -> str:
	stack_num, stack_char, num, char_str = [], [], 0, ""
	# char_str + num[<>]
	for c in s:
		if c.isdigit():
			num = 10 * num + int(c)
		if c.isalpha():
			char_str += c
		if c == "[":
			stack_num.append(num)
			stack_char.append(char_str)
			num = 0
			char_str = ""
		if c == "]":
			prev_char = stack_char.pop()
			prev_num = stack_num.pop()
			char_str = prev_char + prev_num * char_str
	return char_str

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

递归算法II解题思路(不推荐)：

用index作为全局变量，扫每一个字符，类似于Leetcode 297。
遇到字符append到result，遇到数字记录次数k，遇到左括号就递归decodeString(s), 递归返回decodedString, 跳过右括号，result.append(decodedString) k次，最后返回result。

如3[a2[c]]

伪代码：

decodeString('3[a2[c]]')
    k = 3  
    acc = decodeString('a2[c]')
         result = a
         k = 2
         'c'  = decodeString('c')
         result = acc
   result = accaccacc

LeetCode 787 Cheapest Flights Within K Stops

Posted on 2026-05-27 Edited on 2026-06-03 Disqus:

LeetCode

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return-1.

Example 1:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation: The graph is shown.
The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.

Example 2:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation: The graph is shown.
The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.

Constraints:

1 <= n <= 100 0 <= flights.length <= (n * (n - 1) / 2)
flights[i].length == 3 0 <= fromi, toi < n
fromi != toi 1 <= pricei <= 104
There will not be any multiple flights between two cities. 0 <= src, dst, k < n
* src != dst

题目大意：

求只允许停k个站情况下，最便宜机票价格

解题思路：

BFS + Heap
这是单源最短路径的典型应用。可以用Dijkstra，机票价格相当于单源最短路径问题中的路径大小。一开始我用BFS，但得到TLE，因为存在循环，导致节点被重复访问(同一路径)。但一个节点的确可以被用不同路径访问。所以引入visited[node] = dis

解题步骤：

N/A

注意事项：

node需要被多次访问，所以跟模板不同，visited的检测要放在neighbor循环之外且用node且初始化为空。visited不再是set，它需要记录node离src的距离。一方面用于循环检测，因为如果存在循环，会出现dist >= visited[node]。若该节点的当前距离小于之前的最小距离，此时也要加入到heap，因为贪婪法，虽然此路径费用较高，但它距离更近，当k限制比较小时，此路径可能满足要求。这就是为什么一个节点会被多次访问的原因。
若路径不存在返回-1

Python代码：

def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
	graph = collections.defaultdict(list)
	for pair in flights:
		graph[pair[0]].append((pair[1], pair[2]))
	heap = ([(0, src, 0)]) # price, node_id, distance
	visited = {}
	while heap:
		p, node, dist = heapq.heappop(heap)
		if node == dst and dist <= k + 1:
			return p
		if node in visited and dist >= visited[node]:
			continue
		visited[node] = dist
		for neighbor, _price in graph[node]:
			heapq.heappush(heap, (p + _price, neighbor, dist + 1))
	return -1

算法分析：

时间复杂度为O(VlogV)，空间复杂度O(V)

LeetCode 095 Unique Binary Search Trees II

Posted on 2026-05-27 Edited on 2026-06-03 Disqus:

LeetCode

Given an integer n, return all the structurally unique BST’s (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

Example 1:

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

Example 2:

Input: n = 1
Output: [[1]]

Constraints:

* 1 <= n <= 8

题目大意：

给定n，求所有val为1-n的BST的所有可能性,返回结果是所有可能的root的集合。

解题思路：

DFS中比较难的catalan类型。

解题步骤：

N/A

注意事项：

root = TreeNode(i)要在最内层for循环中
返回结果是解的集合，所以终止条件返回也需要是一个[None]

Python代码：

# catelan dfs (type 4) LeetCode 095 Unique Binary Search Trees II
# return the root of all the possible trees
def generateTrees(self, n: int) -> List[TreeNode]:
	nums = [_ + 1 for _ in range(n)]
	return self.dfs4(nums, 0, n)

def dfs4(self, nums, start, end): # [start, end)
	if start >= end:
		return [None] # remember becaues we want the 2 for-loop happen
	res = []
	for i in range(start, end):
		left_root_nodes = self.dfs4(nums, start, i) # 0, 0
		right_root_nodes = self.dfs4(nums, i + 1, end) # 1, 1
		for left_root_node in left_root_nodes:
			for right_root_node in right_root_nodes:
				node = TreeNode(nums[i])
				node.left = left_root_node
				node.right = right_root_node
				res.append(node)
	return res

算法分析：

时间复杂度Catalan数为O(C[n] += C[i-1]*C[n-i])，空间复杂度O(1)

记忆性搜索

Posted on 2026-05-27 Edited on 2026-06-03 Disqus:

算法思路：

DFS将子问题的解存于结果中。cache[st] = result. st是子问题边界。

应用：

用于求所有可能性，且这些可能性有重复，记忆性搜索可以用于剪枝。

Leetcode 139
Leetcode 140

与DP的界线：

状态转移特别麻烦如有循环依赖, 不是顺序性。如棋盘，上下左右四个方向如1197 Minimum Knight Moves和word ladder
初始化状态不是特别容易找到

算法步骤：

key为子问题索引st，value为子问题的解。不含path和res因为类似于Catalan，用子问题返回结果来组成此轮结果。f(input, st, endIndex, cache) -> List
紧跟终结条件，若在cache中，返回子问题的解。
循环结束，将子问题的结果存于cache。

注意事项：

cache是一个解的集合，所以终止条件返回也需要是一个list

Python代码：

def dfs(self, input, cache) -> List[int]:
	if <终止条件>:
		return [] # remember to use list
	if input in cache:
		return cache[input]
	res = []
	for i in range(len(input)):
		anwser = self.dfs(input[:i], cache)
		res.append(anwser)
	cache[input] = res
	return res

算法分析：

时间复杂度为O(解大小)，空间复杂度O(解大小).

例子：

LeetCode 140 Word Break II
这是单边catalan

def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
	word_set = set(wordDict)
	res = []
	cache = {}
	res = self.dfs(s, word_set, cache) #cat
	return res
# dfs(s) = word + dfs(s[i+1:])
def dfs(self, s, word_set, cache):
	if s == "":
		return [""]
	if s in cache:
		return cache[s]
	res = []
	for i in range(len(s)):
		if s[:i + 1] not in word_set:
			continue
		cur_list = self.dfs(s[i + 1:], word_set, cache) # i = 2, dfs("")
		for _s in cur_list: # [""]
			res.append((s[:i + 1] + " " + _s).strip()) #cat
	cache[s] = res
	return res

注意事项：

终止条件返回[‘’]而不是[]，正如L017，空字符串作为初始结果。返回到上层要strip(), 因为ss可能为空
子问题用f=word + f并不是f=f + word, 这样最后结果避免反转。
s[:i + 1]判断是否在字典中，而不是s[:i]，单词包括整个字符串。