KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:



Input: board = [[“o”,”a”,”a”,”n”],[“e”,”t”,”a”,”e”],[“i”,”h”,”k”,”r”],[“i”,”f”,”l”,”v”]], words = [“oath”,”pea”,”eat”,”rain”]
Output: [“eat”,”oath”]


Example 2:



Input: board = [[“a”,”b”],[“c”,”d”]], words = [“abcb”]
Output: []


Constraints:

m == board.length n == board[i].length
1 <= m, n <= 12 board[i][j] is a lowercase English letter.
`1 <= words.length <= 3 104*1 <= words[i].length <= 10*words[i]consists of lowercase English letters. * All the strings ofwords` are unique.

算法思路：

N/A

注意事项：

  1. 用Trie来保存单词列表，这样每次DFS的每一步都可以O(1)时间知道是否和单词吻合，而不是O(n)
  2. 难点1: Trie的接口有startswith, search, insert，仅insert可以用，其他两个不支持与DFS同步搜索。所以要写一个新函数：其实修改startsWith将for循环去掉当然DFS的API也要改，去掉word, word_index加入trie, trie_node, path, res
  3. TLE错误，因为比如矩阵为[abc]，单词列表为abc, abc, abc，这样abc加入到结果后就不应该再搜abc，因为结果不能重且效率大打折扣。如果找到了单词，就应该将它从Trie中去掉，避免无谓的搜索，条件是该节点children长度为0，就父节点就将key删除。如果还有儿子节点只能标记is_end为False。Line 29 - 31和35 - 36

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
OFFSETS = [(0, 1), (1, 0), (-1, 0), (0, -1)]
class Solution(TestCases):

    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        if not board or not board[0] or not words:
            return []
        trie, res = Trie(), []
        for word in words:
            trie.insert(word)

        visited = [[False for _ in range(len(board[0]))] for _ in range(len(board))]
        for i in range(len(board)):
            for j in range(len(board[0])):
                self.dfs(board, i, j, visited, trie, trie.get_head(), '', res)
        return list(res)

    def dfs(self, board, start_x, start_y, visited, trie, trie_node, path, res):
        if start_x < 0 or start_x >= len(board) or start_y < 0 or start_y >= len(board[0]):
            return
        if visited[start_x][start_y]:
            return
        trie_child = trie.search_one_node(board[start_x][start_y], trie_node)
        if not trie_child:
            return
        visited[start_x][start_y] = True
        path += board[start_x][start_y]
        if trie_child.is_end:
            res.append(path)
            trie_child.is_end = False
            if len(trie_child.children) == 0 and board[start_x][start_y] in trie_node.children:
                trie_node.children.pop(board[start_x][start_y])
        for dx, dy in OFFSETS:
            self.dfs(board, start_x + dx, start_y + dy, visited, trie, trie_child, path, res)
        path = path[:-1]
        visited[start_x][start_y] = False
        if len(trie_child.children) == 0 and board[start_x][start_y] in trie_node.children:
            trie_node.children.pop(board[start_x][start_y])


class Trie:
    def __init__(self):
        self.head = TrieNode()

    def insert(self, word: str) -> None:
        if not word:
            return
        it = self.head
        for i in range(len(word)):
            it = it.children[word[i]]
        it.is_end = True

    def search_one_node(self, c: str, trie_node):
        if c not in trie_node.children:
            return None
        else:
            return trie_node.children[c]

class TrieNode:

    def __init__(self):
        self.children = collections.defaultdict(TrieNode)  # {}
        self.is_end = False

上述代码比较复杂，可以先写这个LTE版本, 它在最后结果去重，但是对于重复单词会LTE，如[‘a’, … ‘a’]. 所以演变成最优版本，需要删除Trie的节点

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
	...
	return list(set(res))

def dfs(self, board, start_x, start_y, visited, trie, trie_node, path, res):
	if start_x < 0 or start_x >= len(board) or start_y < 0 or start_y >= len(board[0]):
		return
	if visited[start_x][start_y]:
		return
	trie_child = trie.search_one_node(board[start_x][start_y], trie_node)
	if not trie_child:
		return
	visited[start_x][start_y] = True
	path += board[start_x][start_y]
	if trie_child.is_end:
		res.append(path)
	for dx, dy in OFFSETS:
		self.dfs(board, start_x + dx, start_y + dy, visited, trie, trie_child, path, res)
	path = path[:-1]
	visited[start_x][start_y] = False

算法分析：

时间复杂度为O(n2*4*3L-1)，空间复杂度O(n2), n是矩阵长度，L是最大单词长度.
3是因为访问过的节点不合法，也就是来的节点不能再走一次，所以只能3个方向,第一个可以4个方向，其他步是3个方向

有一个方法是不用Trie而是将单词所有prefix放入到set中，但会TLE，因为时间复杂度为O(n23n*n)，它不会剪枝，从顶点出发，最差情况是z型走完board，此时路径长度为n*n.

Posted on Edited on Disqus:

LeetCode



A website domain "discuss.leetcode.com" consists of various subdomains. At the top level, we have "com", at the next level, we have "leetcode.com" and at the lowest level, "discuss.leetcode.com". When we visit a domain like "discuss.leetcode.com", we will also visit the parent domains "leetcode.com" and "com" implicitly.

A count-paired domain is a domain that has one of the two formats "rep d1.d2.d3" or "rep d1.d2" where rep is the number of visits to the domain and d1.d2.d3 is the domain itself.

For example, "9001 discuss.leetcode.com" is a count-paired domain that indicates that discuss.leetcode.com was visited 9001 times.

Given an array of count-paired domains cpdomains, return an array of the count-paired domains of each subdomain in the input. You may return the answer in any order.

Example 1:

Input: cpdomains = [“9001 discuss.leetcode.com”]
Output: [“9001 leetcode.com”,”9001 discuss.leetcode.com”,”9001 com”]
Explanation: We only have one website domain: “discuss.leetcode.com”.
As discussed above, the subdomain “leetcode.com” and “com” will also be visited. So they will all be visited 9001 times.


Example 2:

Input: cpdomains = [“900 google.mail.com”, “50 yahoo.com”, “1 intel.mail.com”, “5 wiki.org”]
Output: [“901 mail.com”,”50 yahoo.com”,”900 google.mail.com”,”5 wiki.org”,”5 org”,”1 intel.mail.com”,”951 com”]
Explanation: We will visit “google.mail.com” 900 times, “yahoo.com” 50 times, “intel.mail.com” once and “wiki.org” 5 times.
For the subdomains, we will visit “mail.com” 900 + 1 = 901 times, “com” 900 + 50 + 1 = 951 times, and “org” 5 times.


Constraints: 1 <= cpdomain.length <= 100
1 <= cpdomain[i].length <= 100 cpdomain[i] follows either the "rep<sub>i</sub> d1<sub>i</sub>.d2<sub>i</sub>.d3<sub>i</sub>" format or the "rep<sub>i</sub> d1<sub>i</sub>.d2<sub>i</sub>" format.
rep<sub>i</sub> is an integer in the range [1, 10<sup>4</sup>]. d1<sub>i</sub>, d2<sub>i</sub>, and d3<sub>i</sub> consist of lowercase English letters.

题目大意：

统计所以domain和子域名个数

解题思路：

遍历每个domain，将domain和个数存入dict，再对domain按点号break，将每个sub-domain存入dict

解题步骤：

N/A

注意事项：

  1. Line 64根据题意倒转统计，Line 65记得非空时候加点号

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def subdomainVisits(self, cpdomains: List[str]) -> List[str]:
	domain_to_count = collections.defaultdict(int)
	for pair_str in cpdomains:
		pair = pair_str.split(' ')
		count = int(pair[0])
		domain = pair[1]
		subdomain = ''
		for segment in domain.split('.')[::-1]:
			subdomain = segment + ('.' + subdomain if subdomain else '')
			domain_to_count[subdomain] += count
	return ['{} {}'.format(_count, _domain) for _domain, _count in domain_to_count.items()]

算法分析：

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

Posted on Edited on Disqus:

LeetCode



There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:

There are no self-edges (graph[u] does not contain u). There are no parallel edges (graph[u] does not contain duplicate values).
If v is in graph[u], then u is in graph[v] (the graph is undirected). The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.

A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

Return true if and only if it is bipartite.

Example 1:



Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.


Example 2:



Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}.


Constraints:

graph.length == n 1 <= n <= 100
0 <= graph[u].length < n 0 <= graph[u][i] <= n - 1
graph[u] does not contain u. All the values of graph[u] are unique.
* If graph[u] contains v, then graph[v] contains u.

题目大意：

无向图中是否存在一个划分，将节点分为两集合，任何一条边都连接着两个集合，也就是不存在一条边在单一集合内。

解题思路：

图上色法。两种颜色，将节点上色0，儿子上色1，若某个节点已经上的色和将要上的色矛盾（来自的路径不同），即不合法

解题步骤：

N/A

注意事项：

  1. 图上色法。两种颜色，将节点上色0，儿子上色1，若某个节点已经上的色和将要上的色矛盾（来自的路径不同），即不合法
  2. 题意表示，图可能是有几个连通图，所以要从每个节点做BFS，除非节点已访问过， Line 4. node_to_color作为visited的功能
  3. return True在两个函数中要写，否则返回None

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def isBipartite(self, graph: List[List[int]]) -> bool:
	node_to_color = collections.defaultdict(int)
	for i in range(len(graph)):
		if i in node_to_color: # disconnected nodes
			continue
		node_to_color[i] = 0
		if not self.bfs(graph, i, node_to_color):
			return False
	return True

def bfs(self, graph, n, node_to_color):
	queue = collections.deque([n])
	while queue:
		node = queue.popleft()
		for neighbor in graph[node]:
			if neighbor in node_to_color and node_to_color[neighbor] != 1 - node_to_color[node]:
				return False
			if neighbor in node_to_color:
				continue
			queue.append(neighbor)
			node_to_color[neighbor] = 1 - node_to_color[node]
	return True

算法分析：

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

Posted on Edited on Disqus:

LeetCode 309 Best Time to Buy and Sell Stock with Cooldown

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

  • You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
  • After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example: 

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

题目大意：

给定一个数组，第i个元素代表某只股票在第i天的价格。 设计一个算法计算最大收益。你可以完成多次交易（多次买入、卖出同一只股票），需要满足下列限制：
你不可以在同一时间参与多个交易（在买入股票之前必须卖出）。
在卖出股票之后，你不可以在第二天马上买入。（需要一天的冷却（CD）时间）。也就是卖出后过两天才能买入。

解题思路：

因为有限制条件，所以没有特别方法，只能计算所有结果，也就是用动态规划。动态规划首先是写出递归式（数学归纳法）。

  1. 定义f(n)为第n日卖出股票（一定要卖出，不能持有）的利润，加强了命题。
  2. 递归式如下图，f(n)只能由f(n-1)卖出后立刻买入（相当于n-1时候不卖出）或者f(n-3)卖出n-1时候买入两种情况。

    现在可以写出递归式：

    F(x)=max{f(1),…,f(n)}求加强命题最大值即为本题解。
    这里考虑到负数，方便程序实现，否则，f(n)的前3个值计算就不能放入循环而要特别处理了。

注意事项：

  1. 数组为空或者1个
  2. 负数组的实现方法

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxProfit(int[] prices){
	int sell[] = new int[prices.length];
	int max = 0;
	for(int i=1;i<prices.length;i++){
		sell[i] = Math.max(f(i-3, sell), f(i-1, sell))+ prices[i]-prices[i-1];
		if(sell[i]>max)
			max = sell[i];
	}
	return max;		
}

public int f(int i, int[] r){
	if(i<1)
		return 0;
	else
		return r[i];

这个实现有个错误就是忽略了一种重要的情况：f(n-4),…,f(1)的情况。看以下例子：[6,1,6,4,3,0,2]

Index 0 1 2 3 4 5 6
price 6 1 6 4 3 0 2
f(n) 0 -5 5 3 2 2 5

按照上面算法结果为5，但是很容易看出来1->6, 0->2结果是7。问题出在最后一个f(6)=max{f(3),f(5)}+2=max{3,2}+2。很明显，第3天卖出获利为3并不是最佳，第二天卖出获利为5才是最佳，我们忽略了f(n-3)之前的所有情况。解决方案是再创建一个数组维护前n天最大获利值。
定义g(n)为第n日（包括第n日）前卖出股票（不一定要第n天卖出）的利润。修改递归式为，把f(n-3)改为g(n-3)：

Java代码：

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
public int maxProfit2(int[] prices){
	int sell[] = new int[prices.length];
	int preSell[] = new int[prices.length];
	int max = 0;
	for(int i=1;i<prices.length;i++){
		sell[i] = Math.max(g(i-3, preSell), f(i-1, sell))+ prices[i]-prices[i-1];
		if(sell[i]>max)
			max = sell[i];
		
		preSell[i] = Math.max(preSell[i-1], sell[i]);
	}
	return max;		
}

public int f(int i, int[] r){
	if(i<1)
		return 0;
	else
		return r[i];
}

public int g(int i, int[] g){
	if(i<1)
		return 0;
	else
		return g[i];
}

算法分析：

时间复杂度为O(n)，n为数组长度，空间复杂度O(n)。

current, first分别通过f和g的计算公式计算，second是通过current获得

Python代码：

1
2
3
4
5
6
7
8
# g(n) = max{f(n), g(n-1)}
# f(n) = A[n] - A[n - 1] + max{f(n - 1), g(n-3)}
def maxProfit(self, prices: List[int]) -> int:
	# g(n-3), f(n-2), f(n-1)
	first, second, current = 0, 0, 0
	for i in range(1, len(prices)):
		current, second, first = prices[i] - prices[i - 1] + max(current, first), current, max(second, first)
	return max(current, second, first)

空间优化：

由于此题目，f(n)只与前三个状态有关f(n-1), f(n-2)(虽然没直接关系，但程序实现需要记录),g(n-3)。四个状态可以用三个变量
推进，如sell=Math.max(preSell, sell)，同一个变量旧状态更新到新状态，所以可以避免维护数组开销。
代入preSell=g(n-3), sell_1=f(n-2), sell=f(n-1)到公式即得
f(n) = sell = max{preSell, sell}+prices[n]-prices[i-1]
g(n-2) = preSell = max{g(n-3), f(n-2)} = max{preSell, sell_1}
f(n-1) = sell_1 = PreValue(sell)
本题解就是preSell, sell_1, sell的最大值。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
public int maxProfit(int[] prices){
	//g(n-3), f(n-2), f(n-1)
	int preSell=0, sell_1=0, sell = 0;
	for(int i=1;i<prices.length;i++){
		int tmp = sell;
		sell = Math.max(preSell, sell)+ prices[i]-prices[i-1];
		preSell = Math.max(preSell, sell_1);
		sell_1 = tmp;
	}
	return Math.max(Math.max(preSell, sell_1), sell);		
}

算法分析：

时间复杂度为O(n)，n为数组长度，空间复杂度O(1)。本题有更简单解法但比较难想出。

最后注意事项：

  1. 数组为空或者1个
  2. 三种情况f(n-1),f(n-3),g(n-3)可以得到f(n)。解就是preSell, sell_1, sell的最大值。
  3. DP流程，定义函数（是否加强）、递归式、空间优化。

相关题目：

LeetCode 121 Best Time to Buy and Sell Stock
LeetCode 122 Best Time to Buy and Sell Stock II
LeetCode 309 Best Time to Buy and Sell Stock with Cooldown
LeetCode 123 Best Time to Buy and Sell Stock III

Posted on Edited on Disqus:

LeetCode



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.

The depth of an integer is the number of lists that it is inside of. For example, the nested list [1,[2,2],[[3],2],1] has each integer’s value set to its depth.

Return the sum of each integer in nestedList multiplied by its depth.

Example 1:



Input: nestedList = [[1,1],2,[1,1]]
Output: 10
Explanation: Four 1’s at depth 2, one 2 at depth 1. 12 + 12 + 21 + 12 + 12 = 10.


Example 2:



Input: nestedList = [1,[4,[6]]]
Output: 27
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 11 + 42 + 63 = 27.


Example 3:

Input: nestedList = [0]
Output: 0


Constraints:

1 <= nestedList.length <= 50 The values of the integers in the nested list is in the range [-100, 100].
The maximum *depth of any integer is less than or equal to 50.

题目大意：

求NestedInteger的和。越深，权重越高

最后计算权重解题思路(推荐)：

BFS按层遍历

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

解题步骤：

N/A

注意事项：

  1. Line 9中，需要将NestedInteger展开，里面的所有的NestedInteger入列。Python中，用extend来加入list中所有元素到另一个list，而不是append
  2. 按层遍历模板中，不需要level变量，for可以达到。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def depthSum(self, nestedList) -> int:
	queue = collections.deque(nestedList)
	sums, max_depth, res = [], 0, 0
	while queue:
		layer_sum = 0
		for _ in range(len(queue)):
			node = queue.popleft()
			if node.isInteger():
				layer_sum += node.getInteger()
			else:
				queue.extend(node.getList()) # remember
		sums.append(layer_sum)
		max_depth += 1
	for i, n in enumerate(sums):
		res += n * (i + 1)
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(k), k为每层最多节点数 + 最大层数

每层计算权重算法II解题思路：

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def depthSum(self, nestedList) -> int:
	queue = collections.deque(nestedList)
	res, layer = 0, 1
	while queue:
		level_sum = 0
		for _ in range(len(queue)):
			node = queue.popleft()
			if not node.isInteger():
				queue.extend(node.getList()) # remember
			else:
				level_sum += node.getInteger()
		res += level_sum * layer
		layer += 1
	return res

算法分析：

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

Free mock interview