KK's blog

每天积累多一些

0%

Posted on Disqus:

LeetCode



You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (u<sub>i</sub>, v<sub>i</sub>, w<sub>i</sub>), where u<sub>i</sub> is the source node, v<sub>i</sub> is the target node, and w<sub>i</sub> is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Example 1:



Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2


Example 2:

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1


Example 3:

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1


Constraints:

1 <= k <= n <= 100 1 <= times.length <= 6000
times[i].length == 3 1 <= u<sub>i</sub>, v<sub>i</sub> <= n
u<sub>i</sub> != v<sub>i</sub> 0 <= w<sub>i</sub> <= 100
All the pairs (u<sub>i</sub>, v<sub>i</sub>) are *unique. (i.e., no multiple edges.)

题目大意：

求从某一个点出发的所有能到达的点中的最短时间。若不能都到达返回-1

解题思路：

单源最短路径的最大值，如果有点不能到达返回-1.用BFS+Heap的模板

解题步骤：

N/A

注意事项：

  1. 用queue

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
	# build graph
	graph = collections.defaultdict(list)
	for e in times:
		graph[e[0]].append((e[1], e[2]))
	heap = [(0, k)] # weight, node
	visited = {k: 0}
	while heap:
		weight, node  = heapq.heappop(heap)
		for neighbor, _weight in graph[node]:
			if neighbor in visited and visited[neighbor] <= weight + _weight:
				continue
			heapq.heappush(heap, (weight + _weight, neighbor))
			visited[neighbor] = weight + _weight
	return max(visited.values()) if len(visited) == n else -1

算法分析：

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

Posted on Edited on Disqus:

算法思路：

图用邻接表为输入，思路用Queue实现, 还要一个机制记录节点访问过没有，可以用HashSet，同时它作为结果存储BFS访问结果。
BFS多用于找最短路径
DFS多用于快速发现底部节点和具体路劲问题（如路径和或打印路径）。

BFS优缺点：
同一层的所有节点都会加入队列，所以耗用大量空间
仅能非递归实现
相比DFS较快，空间换时间
适合广度大的图
找环的话需要用拓扑排序

DFS优缺点：
无论是系统栈还是用户栈保存的节点数都只是树的深度，所以空间耗用小
有递归和非递归实现
由于有大量栈操作（特别是递归实现时候的系统调用），执行速度较BFS慢
适合深度大的图
找环的话比较容易实现

如果BFS和DFS都可以用，建议用BFS，因为工业应用中，BFS不用有限的栈空间，可以利用到所有内存。
BFS题目问自己是否需要按层遍历，是否需要visited

注意事项：

  1. 坐标型BFS，注意输入为(i, j)时候，x = node[0] + _dx[0], 用x不要用输入的i
  2. deque([(start[0], start[1])]), set([(startx, starty)])
  3. board[x][y] == ‘+’ 注意矩阵的其他不能遍历的元素，如L200中的0

其他:

  1. 只要把节点放入队列立即标记其为访问，不要在出列的时候才标记。否则同一个节点会入列多次。
    比如下图, 入列顺序为1,2,3,4,4。4入列了两次。
  2. 矩阵的遍历用方向List: OFFSETS = [(1, 0), (-1, 0), (0, 1), (0, -1)]

图遍历

只有是对所有节点BFS题型才需要将visited作为参数传入

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def bfs(self, graph, start) -> List[int]:
	queue, res = deque([start]), []
	visited = {start}
	while queue:
		node = queue.popleft()
		res.append(node)
		for neighbor in graph[node]:
			if neighbor in visited:
				continue
			queue.append(neighbor)
			visited.add(neighbor)
	return res

树模板只要把visited去掉，neighbor改成left和right

注意事项：

  1. visited = {start}不写set([start])
  2. if neighbor in visited在循环里，不是if node in visited
  3. 在bfs_layer2，res.append(level)

计算最短距离的图遍历(最常考的模板)

  • 只要加line 4和14
  • visited在函数内定义
  • 遇到target就返回最短距离，若离开循环返回-1，问清楚是否存在路径不存在的情况
  • 求距离公式不需要用min，因为这个遍历保证了最短距离了。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def bfs_layer(self, graph, start, target) -> int:
	queue = deque([start])
	visited = {start}
	distance = {start: 1}
	while queue:
		node = queue.popleft()
		if node == target:
			return distance[node]
		for neighbor in graph[node]:
			if neighbor in visited:
				continue
			queue.append(neighbor)
			visited.add(neighbor)
			distance[neighbor] = distance[node] + 1
	return -1

写法2

1
2
3
4
5
6
7
8
9
10
11
12
13
def bfs_layer_v2(self, graph, start, target) -> int:
	queue = deque([(start, 1)])
	visited = {start}
	while queue:
		node, distance = queue.popleft()
		if node == target:
			return distance
		for neighbor in graph[node]:
			if neighbor in visited:
				continue
			queue.append((neighbor, distance + 1))
			visited.add(neighbor)
	return -1

按层遍历

核心是加这一行for _ in range(len(queue))
具体还要加line 5, 6和14, 15. 二叉树不需要visited。能用distance dict就尽量不用此法，因为多了一个循环。

注意事项：

  1. 关键行： 多这一行for循环 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def bfs_layer2(self, graph, start) -> List[List[int]]:
	queue, res = deque([start]), []
	visited = {start}
	while queue:
		level = []
		for _ in range(len(queue)):
			node = queue.popleft()
			level.append(node)
			for neighbor in graph[node]:
				if neighbor in visited:
					continue
				queue.append(neighbor)
				visited.add(neighbor)
		res.append(level)
	return res

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
 * graph: 邻接表
 * visited: 记录已访问节点，避免重复访问
 * start: BFS的根节点
 */
public void bfs(HashMap<Integer, LinkedList<Integer>> graph, HashSet<Integer> visited, int start){
	int num=0;
	Queue<Integer> q=new LinkedList<>();
	q.offer(start);
	visited.add(start);
	while(!q.isEmpty()){
		int node = q.poll();
		LinkedList<Integer> children = graph.get(node);
		for(int child : children){
			if (!visited.contains(child)){
				q.offer(child);
				visited.add(child);
			}
		}
	}
}

错误算法：

问题是加入到queue里面的child没有去重，这样容易queue爆炸式增长。

1
2
3
4
5
6
7
8
9
10
11
12
13
public void bfs(HashMap<Integer, LinkedList<Integer>> graph, HashSet<Integer> visited, int start){
	Queue<Integer> q=new LinkedList<>();
	q.offer(start);
	while(!q.isEmpty()){
		int node = q.poll();
		visited.add(node);
		LinkedList<Integer> children = graph.get(node);
		for(int child : children){
			if (!visited.contains(child))
				q.offer(child);
		}
	}
}

按层次遍历：

第一个思路是三重循环，先queue，然后该层所有节点，最后该层每一个节点的儿子。关键在于size = q.size();

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void bfsByLayer3(HashMap<Integer, LinkedList<Integer>> graph, int start){
	Queue<Integer> q=new LinkedList<>();
	int layer = 1;
	q.offer(start);
	while(!q.isEmpty()){
		int size = q.size();
		for(int i = 0; i < size; i++) {// loop this layer
			int node = q.poll();
			System.out.println("node:"+node+" in layer "+ layer);
			LinkedList<Integer> children = graph.get(node);
			for(int child : children){// loop its children
				q.add(child);
			}
		}
		layer++;
	}
}

上述代码三重循环看似可读性不够好，所有可以用hashMap来记录每个点的距离从而减少第二重循环。
nodeToHeight.put(start, 1);
nodeToHeight.put(child, nodeToHeight.get(node) + 1);

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void bfsByLayer4(HashMap<Integer, LinkedList<Integer>> graph, int start){
	Queue<Integer> q = new LinkedList<>();
	q.offer(start);
	Map<Integer, Integer> nodeToHeight = new HashMap<>();
	nodeToHeight.put(start, 1);
	while(!q.isEmpty()){

		int node = q.poll();
		System.out.println("node:"+node+" in layer "+ nodeToHeight.get(node));
		LinkedList<Integer> children = graph.get(node);
		for(int child : children){// loop its children
			q.add(child);
			nodeToHeight.put(child, nodeToHeight.get(node) + 1);
		}
		
	}
}

  1. q.isEmpty() && !q2.isEmpty()

第三思路是用两个队列来实现：用第一个队列存储该层的节点，第二个队列存储第一个队列中节点的儿子节点，
也就是下一次的节点。此思路比较容易实现。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 假设不循环
 * graph: 邻接表
 * start: BFS的根节点
 */
public void bfsByLayer(HashMap<Integer, LinkedList<Integer>> graph, int start){
	Queue<Integer> q=new LinkedList<>();
	Queue<Integer> q2=new LinkedList<>();
	int layer = 1;
	q.offer(start);
	while(!q.isEmpty()){
		int node = q.poll();
		System.out.println("node:"+node+" in layer "+ layer);
		LinkedList<Integer> children = graph.get(node);
		for(int child : children){
			q2.offer(child);
		}
		if(q.isEmpty() && !q2.isEmpty()){
			q = q2;
			q2 = new LinkedList<>(); 
			layer++;
		}
	}
}

第四思路是只用一个队列来实现：层与层之间用结束符间隔，每遇到结束符，表示该层访问结束，下一层的节点也准备好
（不会再有新的节点加入到这一层），此时再往队列加入新的结束符。此思路对数据有一定限制，实现起来注意事项较多。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void bfsByLayer2(HashMap<Integer, LinkedList<Integer>> graph, int start){
	Queue<Integer> q=new LinkedList<>();
	int layer = 1;
	q.offer(start);
	q.offer(-1);
	while(!q.isEmpty()){
		int node = q.poll();
		if(node == -1){
			//确保有非结束符节点
			if(q.size()>0){
				q.offer(-1);
				layer++;
			}
			continue;
		}
		System.out.println("node:"+node+" in layer "+ layer);
		LinkedList<Integer> children = graph.get(node);
		for(int child : children){
			q.offer(child);
		}
	}
}

算法分析：

时间复杂度为O(n)，w为树的所有层里面的最大长度，空间复杂度O(w)。

Posted on Edited on Disqus:

注意事项：

  1. a.next = b。 b赋值给a的next，指向是从左到右，也就是a.next指向b
  2. it = it.next记得移动指针
  3. fake_node如果链首会改变，引入fake_node
  4. 决定是while it还是it.next
  5. 删除节点.next = None

Python代码：

LeetCode 138 Copy List with Random Pointer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def copyRandomList(self, head: 'Node') -> 'Node':
	if not head:
		return None
	old_to_new = {}
	fake_head = Node(0)
	it, it_new = head, fake_head
	while it:
		new_node = Node(it.val)
		it_new.next = new_node
		old_to_new[it] = new_node
		it, it_new = it.next, it_new.next
	it, it_new = head, fake_head.next
	while it:
		if it.random:
			old_to_new[it].random = old_to_new[it.random]
		it = it.next
	return fake_head.next

算法分析：

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

Posted on Edited on Disqus:

Implement a key-value store that can serialize multiple string key-value pairs into a single string and deserialize it back. Both keys and values can contain any characters including delimiters, newlines, and special characters.

Example 1:

Input: {“a,”: “4,,5”, “b”: “”}


题目大意：

实现一个serialize和deserialize键值存储的方法。

解题思路：

用key和value的长度及自定义分隔符[][]来作为serialized的一部分，从而避开delimiter的限制.
上面的例子serialize后变成[2]a,[4]4,,5[1]b[0]

解题步骤：

N/A

注意事项：

  1. 不用+=连接res，用list和join提交效率
  2. 用index方法找自定义分隔符而不是逐字符处理
  3. 重复代码来处理token可以放入子函数，用nonlocal不用作为输入参数且可以修改此变量

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
def serialize(kv):
    tokens = []
    for k, v in kv.items():
        tokens.append(f"[{len(k)}]{k}[{len(v)}]{v}")
    return "".join(tokens)

def deserialize(serialized):
    i = 0
    dict = {}
    while i < len(serialized):

        def get_token(s):
            nonlocal i
            token_len_st = serialized.find("[", i) + 1
            token_len_end = serialized.find("]", i)
            token_len = int(serialized[token_len_st:token_len_end])
            token_st = token_len_end + 1
            i = token_st + token_len
            return serialized[token_st:token_st + token_len]

        k = get_token(serialized)
        v = get_token(serialized)
        dict[k] = v
    return dict

算法分析：

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

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
def serialize2(kv):
    res = ""
    for k, v in kv.items():
        res += f"[{len(k)}]{k}[{len(v)}]{v}"
    return res

def deserialize2(serialized):
    is_key = True
    i, kv_length = 0, -1
    k, v = "", ""
    dict = {}
    serialized += " "
    while i < len(serialized):
        if kv_length >= 0:
            if is_key:
                k = serialized[i:i + kv_length] # a,
            else:
                v = serialized[i:i + kv_length] # 4,,5
                dict[k] = v
            is_key = False if is_key else True
            i += kv_length
            kv_length = -1
        if serialized[i] == "[":
            st = i + 1 # 6
        elif serialized[i] == "]":
            end = i # 2
            kv_length = int(serialized[st:end]) # 4
        i += 1
    return dict

Posted on Edited on Disqus:

算法思路：

  1. 循环条件start + 1 < end。 当跳出循环时，start和end的关系只能是相等或相邻。
    相等是若数组只有一个元素，没有进入循环时出现。当进入过循环，一定是相邻。
  2. 跳出循环后比较start和end的关系从而判断答案。

这可以满足二分法找first position或者last position, peak element的题目。
first position中若等于target，end = mid，因为要在左半部分找，相反last
position在右半部分找，所以start = mid。

应用：

  1. 有序数组找目标
  2. 没给定目标情况下，找峰值， 缺失数(元素间关系)
  3. 没给定目标情况下，求第k小的数，如求根号（数值关系）

找目标

注意事项：

  1. 判断数组是否为空。
  2. 如果只有唯一的target的话，target==nums[mid]可以并入任何一种。end和target的顺序也没关系。其他注意循环后要根据题目条件(如小于或者大于或者等于tgt)，
    再比较一次start和end上的元素，详见下表
  3. start + (end - start) // 2 是// 2
类型 if target = nums[mid] 循环之后 备注
binary_search 任意 任意 N/A
last_position 向右start = mid 先end且是否等于tgt 贪婪法，找最后一个target，所以尽量靠后，先end
first_position 向左end = mid 先start是否等于tgt 贪婪法，找第一个target，所以尽量靠前，先start
smaller(_or_equal)_position 向左end = mid 先end是否小于tgt 贪婪法，找最后一个小于target的数，所以尽量靠近target，先end
greater(_or_equal)_position 向右start = mid 先start是否大于tgt 贪婪法，找第一个大于target的数，所以尽量靠近target，先start

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def binary_search(self, nums: List[int], target: int) -> int:
	if not nums:
		return -1
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if target < nums[mid]:
			end = mid
		else:
			start = mid

	if nums[end] == target:
		return end
	elif nums[start] == target:
		return start
	else:
		return -1

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def last_position(self, nums: List[int], target: int) -> int:
	if not nums:
		return -1
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if target < nums[mid]:
			end = mid
		elif target > nums[mid]:
			start = mid
		else:  # Depends on the target on the right side or left side. For fist pos, use end = mid
			start = mid

	if nums[end] == target:
		return end
	elif nums[start] == target:
		return start
	else:
		return -1

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def first_position(self, nums: List[int], target: int) -> int:
	if not nums:
		return -1
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if target < nums[mid]:
			end = mid
		elif target > nums[mid]:
			start = mid
		else:
			end = mid

	if nums[start] == target:
		return start
	elif nums[end] == target:
		return end
	else:
		return -1

Python代码：

如果是smaller_or_equal_position，Line 13和15取等号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def smaller_position(self, nums: List[int], target: int) -> int:
	if not nums:
		return -1
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if target > nums[mid]:
			start = mid
		elif target < nums[mid]:
			end = mid
		else:
			end = mid
	if nums[end] < target:  # nums[end] <= target for smaller_or_equal_position
		return end
	if nums[start] < target:  # nums[start] < target for smaller_or_equal_position
		return start
	return -1

Python代码：

如果是greater_or_equal_position，Line 13和15取等号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def greater_position(self, nums: List[int], target: int) -> int:
	if not nums:
		return -1
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if target > nums[mid]:
			start = mid
		elif target < nums[mid]:
			end = mid
		else:
			start = mid
	if nums[start] > target:  # nums[start] >= target for greater_or_equal_position
		return start
	if nums[end] > target:  # nums[end] >= target for greater_or_equal_position
		return end
	return -1

找峰值

注意事项：

  1. 判断mid+1的元素不越界
  2. 最后返回start和end之中较大者

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def find_peak(self, nums: List[int]) -> int:
	if not nums:
		return -1
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if mid + 1 <= end and nums[mid] < nums[mid + 1]:
			start = mid
		else:
			end = mid
	return start if nums[start] > nums[end] else end

找第k小的数

注意事项：

  1. 数值比较，所以mid是除2获得不是//2。start，end，mid都是数值而不是索引
  2. k是从0开始，count==k的时候，k在mid的右边，如数组1-10, k=3, mid=3.5, count=3，k是前4个数，所以在mid右边。nums[i] <= mid这个等号有没有也没关系，因为mid是小数，不会相等的。
  3. 最后start，end区间内是一个整数正是所求，所以返回end向下取整

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import math
def binary_select(self, nums: List[int], k: int) -> int:
	if not nums:
		return -1
	start, end, epsilon = min(nums), max(nums), 0.5
	while end - start > epsilon:
		mid = start + (end - start) / 2
		count = len([n for n in nums if n <= mid])
		if k < count:
			end = mid
		elif k > count:
			start = mid
		else:
			start =  mid
	return int(end)

若nums有序，count的统计可以用bisect(nums, mid)完成，记得不需要用+1，而且空数组也无问题
上面line 8可以改成

1
count = bisect.bisect(matrix[i], mid)

算法分析：

时间复杂度为O(nlog(|hi-lo|/delta))，如果数据比较平均也就是差值相当的情况下(比如1,2,3)，复杂度为O(nlogn). 空间复杂度O(1)。
若不需要搜索全数组，前面的n会变成logn

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int lastPosition(int[] nums, int target) {
	if(nums == null || nums.length == 0)
		return -1;
	
	int start = 0, end = nums.length - 1;
	while(start + 1 < end) {
		int mid = start + (end - start) / 2;
		if(nums[mid] < target)
			start = mid;
		else if(nums[mid] == target) 
		// Depends on the target on the right side or left side. For fist pos, use end = mid
			start = mid; 
		else
			end = mid;
	}
	
	if(nums[end] == target)
		return end;
	if(nums[start] == target)
		return start;
	
	return -1;
}

算法分析：

时间复杂度为O(logn)，空间复杂度O(1)。

Free mock interview