KK's blog

每天积累多一些

0%

Posted on Edited on 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

解题步骤：

运用模板

注意事项：

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

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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]]

伪代码：

1
2
3
4
5
6
7
8
decodeString('3[a2[c]]')
    k = 3  
    acc = decodeString('a2[c]')
         result = a
         k = 2
         'c'  = decodeString('c')
         result = acc
   result = accaccacc

Posted on Edited on Disqus:

LeetCode



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

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 <= from<sub>i</sub>, to<sub>i</sub> < n
from<sub>i</sub> != to<sub>i</sub> 1 <= price<sub>i</sub> <= 10<sup>4</sup>
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

注意事项：

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

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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)

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

算法一比较难想，如果我们用BFS+Heap模板，我们用visited记录单点最贵price。但是此题由于有边数限制的最值问题，所以类似于DP，将限制条件引入作为参数或state。
visited[(node, distance)]=total_price
两处剪枝：

  1. 价格超过visited
  2. 路径长度超过k
    其实法一也是用了两个剪枝条件，因为price低肯定是先出堆，所以只要比较某点最短路径visited即可，后出堆的点如果路径更长(价格肯定更高了)，肯定可以剪枝。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 = {(src, 0): 0} # (node, distance): price
	while heap:
		p, node, dist = heapq.heappop(heap)
		if node == dst:
			return p
		if dist == k + 1:
			continue
		for neighbor, _price in graph[node]:
			if (neighbor, dist + 1) in visited and visited[(neighbor, dist + 1)] <= p + _price:
				continue
			heapq.heappush(heap, (p + _price, neighbor, dist + 1))
			visited[(neighbor, dist + 1)] = p + _price
	return -1

Posted on Edited on 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

注意事项：

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

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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 Edited on Disqus:

算法思路：

递归分前半和后半排序然后合并。

应用：

  1. 排序
  2. 求逆序数

注意事项：

  1. merge函数中更改输入nums。
  2. line 15的等号决定是否stable sort。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def merge_sort(self, nums: List[int]):
	self.m_sort(nums, 0, len(nums) - 1)

def m_sort(self, nums: List[int], start: int, end: int):
	if start >= end:
		return
	mid = start + (end - start) // 2
	self.m_sort(nums, start, mid)
	self.m_sort(nums, mid + 1, end)
	self.merge(nums, start, mid, end)

def merge(self, nums: List[int], start: int, mid: int, end: int):
	i, j, res = start, mid + 1, []
	while i <= mid and j <= end:  # = decides if it is stable sort
		if nums[i] <= nums[j]:
			res.append(nums[i])
			i += 1
		else:
			res.append(nums[j])
			j += 1
	while i <= mid:
		res.append(nums[i])
		i += 1
	while j <= end:
		res.append(nums[j])
		j += 1
	nums[start:end + 1] = res

算法分析：

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

Posted on Edited on Disqus:

算法思路：

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

应用：

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

  1. Leetcode 139
  2. Leetcode 140

与DP的界线：

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

算法步骤：

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

注意事项：

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

Python代码：

1
2
3
4
5
6
7
8
9
10
11
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

注意事项：

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