19个基本的算法面试问题 *

如果数字不相等或相反, 我们按绝对值排序, but if they are, 我们根据它们的标志来分类. 最后，基于此的解决方案现在非常简单:

函数find_numbers_with_opposites(数字)
	answer = List
	Sorted_numbers = sort_by(number, compare)
	FOR n IN [1..sorted_numbers.length()]
		IF sorted_numbers[n] > 0 AND sorted_numbers[n - 1] == -sorted_numbers[n]
			answer.push(n)
		END IF
	END FOR
	RETURN answer

这个实现在最坏情况下的运行时复杂度为O(N log N), 排序算法是瓶颈.

使用哈希表可以实现O(N)的最佳平均情况时间复杂度. 我们将数字映射到它们的绝对值，并检查它们的对立面是否已经在哈希表中.

函数find_numbers_with_opposites(数字)
	table = HashTable
	answer = List
	以数求数
		IF number == 0
			CONTINUE
		END IF
		键= abs(数字)
		IF键不在表中
			Table [key] = number
		如果表[key] = -number
			answer.push(key)
			table[key] = 0
		END IF
	END FOR

我们将表中的值更改为永远不会等于数组中的任何数字的值，这样我们就不会从重复匹配中返回重复的结果.

所有哈希表操作的平均时间复杂度为0(1)。, 我们的复杂度是执行N次操作的结果.

如果中间子问题不重叠，那么我们就有一个分而治之的例子.

查找两个数组之间的最长公共子序列(LCS)是使用动态规划的一个经典示例. 设数组长度为M和N，并存储为变量a[0:M]和b[0:N]. Let’s use L[p, q] to mark the length of the LCS for subarrays a[0:p] and b[0:q]; that is, L[p, q] == LCS(a[0:p]), b[0:q]). 我们也把矩阵L[p]形象化, Q]看起来就像一对“香蕉”和“凉鞋”.

如果p或q为0，那么L[p, q] = 0因为我们有一个空子数组. 所有其他字段都有一个简单的规则连接它们- L[p], Q]等于以下选项的最大值:

• L[p - 1, q] - LCS没有改变，我们只是在数组a中增加了一个字母来实现L[p, q]
• L[p, q - 1] -类似于数组b
• L[p - 1, Q - 1]+1 -给a和b加上相同的字母, 当然，这不是每个领域都能做到的

如果你再看一下这张表, 你可以看到，数字总是等于它的上邻数或左邻数的最大值, 除非该字段中的值相等, 在这种情况下，它们将最大值增加1. 因此，用下面的算法给出了这个问题的解.

函数lcs(a, b)
	M = a.length()
	N = b.length()
	L =矩阵[M + 1, N + 1]
	FOR i IN [0..M]
		L[i, 0] = 0
	END FOR
	FOR i IN [0..N]
		L[0, i] = 0
	END FOR
	FOR i IN [1..M]
		FOR j IN [1..N]
			L[i, j] = max(L[i, j]， L[i, j-1])
			如果a[i-1] == b[j-1]
				L[i, j] = max(L[i, j]， L[i-1, j-1] + 1)
			END IF
		END FOR
	END FOR
	RETURN L[M, N]

这个解的时间复杂度是0 (MxN)

N [k] = N [k-1] + N [k-2] + N [k-3] + N [k-4] + N [k-5]

解决方案是一个简单的for循环.

函数方法(N)
	Array n[N+1]
	n[0] = 1
	FOR k IN [1..N]
		n[k] = 0
		FOR d IN [1..min(5, k)+1]
			N [k] += N [k - d]
		END FOR
	END FOR
	RETURN n[N]

这个解的时间复杂度为0 (N). 但是，我们可以有更好的表现. 给定的和可以表示为由1组成的1x5矩阵乘以由先前元素组成的5x1矩阵. 如果我们用同样的方法进行平移，我们可以得到关系B[k] = A * B[k-1]，其中:

B[k] =
	[n[k-4]	]
	[n[k-3]	]
	[n[k-2]	]
	[n[k-1]	]
	[n[k]	]
A =
	[0	1	0	0	0]
	[0	0	1	0	0]
	[0	0	0	1	0]
	[0	0	0	0	1]
	[1	1	1	1	1]

如果B[0] =[0 0 0 0 1] '，则[0 0 0 0 1]* B[k] = n[k]. 现在，由于B[k] = A * B[k-1] B[k] = A^T * B[0]. With that, 我们问题的解可以表示为关系n[n] = [0 0 0 0 1] * a ^ n * [0 0 0 0 1] '. 如果我们使用前面提到的最优方法来计算功率(A), N), 这个解的时间复杂度是0 (log N). 我们必须记住这个复杂度有一个很高的常数, 因为矩阵乘法需要时间. 但是，对于足够大的N，这个解是最优的.

红黑树是对二叉搜索树的改进. 二叉搜索树使用二叉树来执行命名操作, 但是树的深度是不受控制的，因此操作可能会比预期花费更多的时间. 红黑树通过将树中的所有节点标记为红色或黑色来解决这个问题, 并设定如何处理节点之间某些位置的规则. 不用讲太多细节, 此方法保证最长分支的长度不超过最短分支的两倍, 所以每个分支都小于2*log_base2(N).

这是实现有序映射和优先级队列的理想结构. b树分为K- 2k分支(对于给定的数字K)，而不是2个, 这是典型的二叉树. 除此之外，它们的行为和二叉搜索树很相似. 这样做的好处是减少了访问操作, 当数据存储在二级存储器或远程位置时，哪个特别有用. This way, 我们可以请求更大块的数据, 当我们处理完之前的请求时, 我们的新请求可以处理了. 这种结构经常用于实现数据库, 因为它们有很多二级存储访问.

函数square_size(董事会)
	M = board.height()
	N = board.width()
	size = Matrix[M + 1, N + 1]
	FOR i IN [0..M]
		size[i, 0] = 0
	END FOR
	FOR i IN [0..N]
		size[0, i] = 0
	END FOR
	answer = 0
	FOR i IN [0..M]
		FOR j IN [0..N]
			大小(i + 1, j + 1) = max(大小(i, j + 1),大小(i + 1, j),大小(i, j)) + 1
			Answer = max(Answer, size[i+1, j+1])
		END FOR
	END FOR
	RETURN answer

这两种算法都有类似的实现. 我们将演示如何计算距离和生成树的大小, 但解的形状很容易推导出来.

函数dijkstra(graph, start_point, end_point)
	heap = MinHeap
	数组[图].node_count()]
	heap.添加(连接(start_point, 0))
	WHILE !heap.empty()
		n = heap.pop()
		IF visited[n.point]
			CONTINUE
		END IF
		IF n.Point == end_point
			RETURN n.distance
		END IF
		visited[n.point] = true
		图中的孩子[n].point].children()
			IF !visited[child.point]
				heap.add(连接(孩子.point, n.距离+孩子.distance)
			END IF
		END FOR
	END WHILE
	返回错误("没有找到路径")

函数的(图)
	heap = MinHeap
	tree_size = 0
	tree_count = 0
	数组[图].node_count()]
	heap.add(连接(0,0))
	WHILE !heap.empty()
		n = heap.pop()
		IF visited[n.point]
			CONTINUE
		END IF
		tree_size += n.distance
		tree_count += 1
		visited[n.point] = true
		图中的孩子[n].point].children()
			IF !visited[child.point]
				heap.add(连接(孩子.point, child.distance)
			END IF
		END FOR
	END WHILE
	IF tree_count != graph.node_count()
		返回错误(“图形未连接”)
	ELSE
		返回tree_size
	END IF

如果你仔细观察, 您将看到唯一的区别(除了返回数据计算)是添加到堆中的数据:而Dijkstra累加距离, 普里姆只是利用树枝的距离. 这两种算法通过从MinHeap中获取价格最小的分支来形成树. In Dijkstra, 离起始点最近的点价格最小, 而在普里姆，离母点最近的点价格最小.

使用普通的二进制堆，我们不能阻止添加重复项. 因此，堆中添加的项目可以和图中边的数量一样多. 如果V表示顶点的数量, E是边的个数, 那么复杂度就是O((E+V) log V).

瓶颈是这样一个事实，在最坏的情况下，我们将在某个点将所有边添加到堆中. 多条边可以指向一个顶点, 所以所有指向那个顶点的边都会在访问检查中被丢弃. To prevent that, 我们可以允许堆直接访问该元素, 如果更好的话，更新边缘, 然后heapify来修复订单的任何更改. 这个操作的复杂度是O(log V). 在斐波那契堆中，此操作的复杂度为0 (1). 因此，通过使用斐波那契堆，这种复杂性可以降低到O(E + V log V)。.

该算法比Dijkstra算法有优势，因为它可以处理带有负边的图, 而Dijkstra仅限于非负的. 它唯一的限制是具有整体负路径的循环图, 但这意味着没有有限解.

让我们再次实现寻找距离，而不是它所代表的实际路径:

函数bellman_ford(graph, start_node, end_node)
	dist =数组[图].node_count()]
	FOR n IN [0..graph.node_count()]
		Dist [n] =∞
	END FOR
	updated = False
	FOR x in [0..graph.node_count()]
		updated = false
		FOR n in [0..graph.node_count()]
			对于图[n]中的p.parents()
				New_distance = dist[p ..point] + p.distance
				IF dist[n] > new_distance
					Dist [n] = new_distance
					updated = true
				END IF
			END FOR
		END FOR
		IF !updated
			BREAK
		END IF
	END FOR
	IF updated
		返回错误("包含负循环，不可解")
	如果dist[end_node] == infinity
		返回错误("开始和结束节点之间没有连接")
	ELSE
		返回dist [end_node]
	END IF

该算法的复杂度为O(V * E)，在大多数情况下比Dijkstra算法要慢. 所以这个算法应该只用在我们期望存在负边的情况下.

它通过使用一种启发式方法来逼近一个节点到目标节点的距离. 这是最简单的解释图，表示空间中的路径网格. 如果我们的目标是找到从a点到B点的路径, 我们可以将启发式设置为被查询点到B点的欧氏距离, 按选定的因子进行缩放.

这个启发式是通过将它加到我们到起点的距离来使用的. 除此之外，实现的其余部分与Dijkstra相同.

该算法的主要优点是平均运行时间短. 主要的缺点是它找不到最优解, 但是任何符合启发式的解.

第一个问题包括计算数组的和. 没有预处理，我们只做一个复杂度为0 (N)的求和运算.

第二个问题需要多次计算和. 因此，执行预处理以降低每个查询的复杂性是明智的. 让我们替换为数组a[0:N]创建一个子数组s[0:N+1]，即:

s[0] = 0
FOR k in [1..N+1]
	S [k] = S [k-1] + a[k-1]
END FOR

现在每个元素k存储了a[0:k]的和. 查询子数组a[p:q]的和。, 取到q s[q]的所有元素的和，减去p s[p]之前的所有元素的和, 这就是subsum(p, Q) = s[Q] - s[p]

此方法的预处理需要O(N)时间，但执行每个查询需要O(1)时间.

最难的问题是对任意数量的数据更新和查询作出响应. 首先，让我们看看之前的解决方案. 第一个解决方案的插入复杂度为0(1)，查询复杂度为0 (N). 第二个解决方案正好相反，O(N)个插入和O(1)个查询. 对于一般情况，这两种方法都不是理想的. 理想情况下，我们希望实现这两个操作的低复杂度.

A 芬威克树(或二叉索引树) 是解决这个问题的理想方法吗. 我们维护一个数组树[0:N+1]的值, 其中每N项存储和(a[M:N]), 其中M等于N，将其二进制表示中最不重要的1替换为0. So for example, N = 19 = b10011, M = 18=b10010; N = 20 = b10100, M=16 = b10000. 现在我们可以很容易地计算和，通过跟踪M直到0. 更新是在相反的方向进行的.

A = Array[N]
树=数组[N+1]

函数之和(结束)
	result = 0
	WHILE end > 0
		Result += tree[end]
		last_one = end & -end
		end -= last_one
	END WHILE
	RETURN result

函数更新(index, value)
	增量= value - a[索引]
	WHILE index < tree.length()
		树[索引]+=增量
		Last_one =索引 & -index
		索引+= last_one
	END WHILE

函数查询(p, q)
	RETURN sum(q) - sum(p)

这两种操作都需要O(log N)复杂度，这比之前的任何一种方法都要好.

算法执行后, 如果列表的元素没有任务的数量那么多, 我们有循环依赖. 否则，我们有一个解决方案:

函数的时间表(节点)
	dependencies =数组[节点].length()]
	FOR节点中的节点
		FOR子节点.children
			依赖项[child] += 1
		END FOR
	END FOR
	queue = Queue
	solution = List
	FOR n IN [0..nodes.length()]
		IF依赖项[n] == 0
			queue.push(n)
		END FOR
	END FOR
	WHILE !queue.empty()
		node = queue.pop()
		solution.push(node)
		FOR n IN nodes[节点].children
			依赖关系[n] -= 1
			IF依赖项[n] == 0
				queue.push(n)
			END IF
		END FOR
	END WHILE
	IF solution.length() != nodes.length()
		返回错误("问题包含循环依赖项")
	ELSE
		RETURN solution
	END IF

RETURN !(rect1.x > rect2.x + rect2.width
      || rect1.x  + rect1.width < rect2.x
      || rect1.y > rect2.y + rect2.height
      || rect1.y + rect1.height < rect2.y);

2. 计算两个中心在x和y上的距离，并将其与它们的宽度和高度之和的一半进行比较, respectively:

返回abs(通过rect1.x - rect2.x) <= (rect1.height + rect2.height) / 2;

唯一的边缘情况是其中一个矩形完全包含在另一个矩形内, 由于“相交”一词在这种情况下不一定是非常明确的行为. 两种算法都认为这是一个交集, 如果这不是我们需要的, 要拆除这个箱子还需要额外检查几次.

总体时间复杂度为O(NlogN)，因为:

1. 按开始日期对间隔进行排序. 时间复杂度为O(NlogN).

2. 将第一个区间作为实际范围. 循环时间间隔和当前StartDate是否在实际范围内, 如果需要，扩展实际范围的EndDate，如果需要，扩展到目前为止所达到的最大时间跨度. 否则，使用当前间隔作为新的实际范围. 时间复杂度为O(N).

该算法运行的时间复杂度为0 (N)，这是我们所能得到的最高效率. 解决方案的伪代码如下:

函数place_server(load_router_wires)
	Overall_load = sum(loads)
	Router_count = loads.length()
	连接数=数组[router_count]
	拥塞=数组[router_count]
	对于router_wires中的分支
		连接(分支.first].push(branch.second)
		连接(分支.second].push(branch.first)
	END FOR
	connections_left = Array[router_count]
	[router_count]
	queries = Queue
	FOR n IN [0..router_count]
		Connections_left [n] = connections[n].length()
		如果connections_left[n] == 1
			queries.push(n)
		END IF
	END FOR
	WHILE !queries.empty()
		id = queries.pop()
		如果connections_left [n] != 1
			CONTINUE
		END IF
		Connections_left [n] = 0
		Outbound_data =流入[id] +负载[id]
		IF overall_load - outbound_data > congestion[id]
			拥塞[id] = overall_loadoutbound_data
		END IF
		FOR connection IN connections[id]
			如果connections_left[connection] == 0
				CONTINUE
			END IF
			流入[连接]+= outbound_data
			IF outbound_data > congestion[connection]
				拥塞[connection] = outbound_data
			END IF
			Connections_left [connection] -= 1
			如果connections_left[connection] == 1
				queries.push(连接)
			END IF
		END FOR
	END WHILE
	返回minimum_index(堵塞)