标签 算法 下的文章

二分法的思路比较简单,但往往不容易写对,比如要不要加等号、死循环等问题。实际上,二分法就是一个逐步缩小范围的过程,每次缩小一半。

经典应用

最经典的二分法的应用是:一个有序数组arr(例如升序),数组元素不同,从数组中找数target的索引,如果不存在返回-1。代码比较简单:

阅读全文

计算a的b次方模m:

$$ a^b\ \%\ m $$

暴力的做法是将a乘b次,最后对m取模。不过,这样可能导致溢出,时间复杂度也很高。

现在考虑,求3的10次方,最少需要做几次乘法运算。

阅读全文

引言

有若干节点,并将其中一些节点对进行连接,要判断任意两个节点是否连通(有路径到达,而不要求直接连接),连通后就不会断开连通关系,此时就可以使用并查集。并查集擅长动态维护许多具有传递性的关系,能在无向图中维护节点之间的连通性。

要判断两个节点是否连通,可以把连通的节点加入到各自的集合里,也就是,同一个集合里的节点都是连通的,不同集合里的节点是不连通的。

阅读全文

N-sum 问题还是比较典型的,这里进行一下小结。

首先描述一下 N-sum 问题:有一个数组 nums,要求从数组中选择 n 个数,使得这些数的和恰好为 target ,输出所有不重复的可行组合。

如果采用暴力解法,显然时间复杂度为 $O(N^n)$,这一般是不可取的。

下面是 N-sum 问题的LeeCode链接:

阅读全文

题目

今天面试时,面试官问了这样一个问题:两个单链表相交,怎么求交点。所谓相交,就是两个节点的next指针相同。

阅读全文