部分算法题解题思路

其实算法更加注重的是解题思路和数学功底,具体到如何实现则因人而异,但是其思想是不变的.一般的,如果遇到的是现实生活中的问题,则通常将问题转换成相应的数学模型,从而解之.如果转换之后,实现起来还是很麻烦,则可以进一步将数学模型分解,即所谓的分而治之,当然并不是所有的问题都可以分而治之的,具体的一些条件目前我也无法阐释清楚,感兴趣的可以参考一些算法书籍,里面一般都有讲解.

下面记录一些常见算法题的解题思路,主要来自《编程之美》和平时的一些记录.

1.求二进制中1的个数

首先我们要知道,一个数x,经过执行x&(x-1)后,x的二进制表示中第一位1(低位开始)会变成0,所以只需统一x执行了多少次x&(x-1)后,其值变成了0,即可知道x的二进制表示中有多少个1.其时间复杂度为o(M),M为x的二进制表示中1的个数.

当然如果所求二进制的位数是固定的,我们也可以建立一个数组,数组中存储的是其数组访问下标所对应的二进制表示中1的个数,达到空间换时间的效果,其时间复杂度为o(1).

2.阶层N!中末尾0的个数

首先N!=1*2*3*…*N=(2^x)*(3^y)*(5^z)…,由于10=2*5,所以N!末尾0的个数与N!质因数分解中2和5的个数,即x和z,有关,我们可以得出N!末尾0的个数M=min(x,z),而显然质因数分解中x>=z,所以M=z;题目转换成了求N!中质因数5的个数,我们不必求出N!,而只需求1~N中,每个数中质因数5的个数;或者使用算式:z=[N/5]+[N/(5^2)]+[N/(5^3)]+…..,其中[N/5]表示不大于N的数中5的倍数贡献一个5,[N/(5^2)]表示不大于N的数中5^2的倍数贡献一个5….依此类推

3.阶层N!的二进制表示中最低位1的位置

因为在二进制中,一个数乘以2(10),则其低位多出一个0(即算术左移一位),所以我们只需求出N!中质因数2的个数,即可求出N!的二进制表示数中末尾0的个数(是不是有点像上一题),再加上1,即为最低位1的位置;同样可以采样上一题中的两种解法求出质因数2的个数,再加上1,即得答案.

4.求整数1到N中1出现的次数

最基本的,求1到N中每个数中出现1个次数,然后对所有个数求和即可,即时间复杂度为o(NlgN),lgN为求一个数中1的个数的时间复杂度.

我们注意到1出现的次数=个位上1出现的次数+十位上1出现的次数+百位上1出现的次数+……,那么1在每个位置上出现的次数是否有规律可循呢,我们可以先从1位数列举观察,进而2位数列举观察,进而3位数列举观察,…..,我们可以发现其中确实有规律存在,有了规律之后,我们就可以使用数学方法来计算了.至于具体的规律,有兴趣的可以自行google,这里就不详细说明了.

5.求两数的最大公约数

最基本的,辗转相除法实现起来应该是没有问题的,但是辗转相除法涉及到大量的取模运算,是比较耗费时间的,当然我们可以把取模运算转换成多次的减法运算,可是效果并不理想,那么我们可不可以直接对二进制数做操作呢?

我们知道对两个数x,y来说,假设x=k*x1,y=k*y1,那么f(x,y)=k*f(x1,y1);

另外,如果x=p*x1,p为素数,并且y%p!=0(即y不能被p整除),则f(x,y)=f(p*x1,y)=f(x1,y)

利用上面两条规则,我们取p为2,因为对2的除法操作我们可以采用位移,于是得出如下运算规则:

若x,y均为偶数,f(x,y)=2*f(x>>1,y>>1)
若x为偶数,y为奇数,f(x,y)=f(x>>1,y)
若x为奇数,y为偶数,f(x,y)=f(x,y>>1)
若x,y均为奇数,f(x,y)=f(y,x-y)

6.求数组中的最大值和最小值

最基本的,我们可以扫描两次,分别求出最大值和最小值,比较次数为2*N(假设数组中有N个元素);

如何降低比较次数呢?我们可以逻辑上将数组中相邻的2个元素分为一组,如元素1、2一组,元素3、4一组 ,依此类推.我们每次比较一组,将一组中的较大值放入奇数下标,将一组中的较小值放入偶数下标.接着从所有奇数下标中找出最大主,从所有偶数下标中找出最小值.总共比较次数为1.5*N;

上述方法破坏了原数组,我们可以不破坏原数组吗?当然是可以的,我们只需加两个变量用于存储当前求得的最小值和最大值,同样采用第二种方法中的逻辑分组,只是分组比较之后,我们不在调整元素位置,而是与当前求得的最小值和最大值比较,如果更小或者更大,则相应的更新最小值或者最大值,比较次数依然为1.5*N;

当然我们也可以采用分治算法,然后综合比较每个分治的结果,其比较次数依然为1.5*N;

7.求平面N个点中,距离最近的两个点

最基本的,穷举法,时间复杂度为o(N^2);

如何优化?我们可以采用分治法.将所有点根据其x坐标值,用直线x=M,划分成点数基本相等的左右两个部分(即M在所有点数x坐标值的中位数附件),然后分别求出左右两个部分的最短距离MinDist(Left),MinDist(Right),接下去我们要做的是寻找是否存在两个点,其中一个点来自左半部分,另外一个点来自右半部分,而这两个点的距离小于Min(MinDist(Left),MinDist(Right)),我们可以采用穷举法,但显然在这里这不是什么好算法.注意到,我们只关心距离小于Min(MinDist(Left),MinDist(Right))的两个点,那么我们只需穷举存在距离可能小于Min(MinDist(Left),MinDist(Right))区域的点即可,那么这个区域是什么呢?显示这个区域为x=M-Min(MinDist(Left),MinDist(Right))到x=M+Min(MinDist(Left),MinDist(Right));通过分治算法,我们将时间复杂度降低为o(NlgN);

8.数组中寻找和为M的两个数(假设至少有一个解)

最基本的,穷举结果,直到找到符合要求的,时间复杂度为o(N^2)(假设数组有N个元素);

如何优化?我们可以依次取出数组中的元素,如arr[0],并查找数组中是否存在N-arr[0],如果不存在,继续分析arr[1],直到找到一组符合要求的,其时间复杂度依然为o(N^2).但是注意到题目其实已经转换成了查找,为了优化查找,我们可以对数组先排序,再二分查找,时间复杂度降低为o(NlgN+NlgN)=o(NlgN);

如果操作非常频繁的话,我们也可以考虑空间换时间的做法,对数组元素建立一个HashMap,这样时间复杂度降低为了o(N);

除了基于查找,我们还可以怎么做呢?在对数组排完序后,我们可以尝试判断arr[0]+arr[N-1]是否满足要求,如果过小则判断arr[1]+arr[N-1],如果过大则判断arr[0]+arr[N-2],依此类推,直到找到符合要求的,其时间复杂度为o(NlgN+N)=o(NlgN);

9.N个元素,求任意(N-1)个元素乘积的最大值

最基本的,穷举结果,然后遍历找出最大值,因为有N种不同组合,所以时间复杂度o(N^2);

如何优化?我们可以令s[i]表示前i个元素的乘积,t[i]表示后N-i个元素乘积,显然s[i]=s[i-1]*arr[i](s[0]=1为边界),t[i]=t[i+1]*arr[i],令p[i]表示去除第i个元素时,(N-1)个元素的乘积,显然p[i]=s[i-1]+t[i],只需遍历p找出最大值即可,时间复杂度为o(N);

当然我们也可以计算出N个元素的乘积M,再对乘积M分别为0,正数,负数做相应的分析,然后剔除出一个数X,使得M/X为最大,其时间复杂度为o(N);

10.数组循环移位

如将数组abcd1234,向右循环移4位得1234abcd,那么如何快速得到移位后的结果呢?

首先明确一点,不管循环移位K为多大,我们只需移位K%N即可(N为数组元素个数).

老老实实的来做移位当然可以得到结果,但是时间复杂度为o(K*N);

一种更好的解法是,将数组分成N-K和K两部分,对每一部分分别做逆序,然后再对整个数组做逆序,其时间复杂度为0(N).如下:

N-K(8-4)部分(abcd)逆序:abcd1234->dcba1234
K(4)部分(1234)逆序    :dcba1234->dcba4321
整个数组逆序		  :dcba4321->1234abcd

另一种解法是,做一个2倍于原来长的数组,内容重复一次,即abcd1234abcd1234,只需截取新数组的第(N-K)~(N-K)+8位的元素即可,时间复杂度依然为o(N),但是空间上有所损失;

11.字符串移位包含问题

给定字符串s1和s2,判断s2是否能够被s1做循环移位得到的字符串包含.如s1=aabcd,s2=cdaa,则包含;如s1=abcd,s2=acbd,则不包含.

最基本的穷举遍历当然没有问题,时间复杂度为o(N^2);

但是注意到上述第10个问题的第三种解法,我们可以发现,新的数组包含了原有数组的所有循环移位的情况,因此我们只需将s2与新数组判断是否有包含关系即可,如下:

第一种情况:s1=aabcd 新数组=aabcdaabcd s2=cdaa 显然新数组包含s2
第二种情况:s1=abcd 新数组=abcdabcd s2=acbd 显然新数组不包含s2

12.删除单链表中指针所指的结点

假设有一个单链表A->B->C->D,假如我们需要删除B,一般的,我们会将A的指针指向C,得A->C->D,完成删除操作.但是现在只有一个指向B的指针,我们需要删除B结点,如何做?

用一般的做法,我们可以删除C结点,但是显然无法删除B结点,这时我们需要另一种方式,我们可以将C结点的值域覆盖B结点值域,然后删除C结点,来达到删除B结点一样的效果.

13.判断两个单链表是否相交

基本的,判断第一个链表中的结点是否在第二个链表有出现,时间复杂度为o(N*M)(N为第一个链表长度,M为第二个链表长度);

对上述方法进行简单的改进,我们可以采用空间换时间的做法,为其中一个链表结点的地址做HashMap,这样可以加快查找速度,时间复杂度为o(N);

将第一个链表的尾结点指针指向第二个链表的头结点,如果两个链表相交,则会产生环链表,我们只需从第二个链表开始遍历,看是否会回到头结点即可,时间复杂度为o(N);

假设两个链表相交,那么这两个链表的尾结点肯定是一样的,所以我们只需遍历两个链表,比较尾结点是否相同即可,时间复杂度为o(N);

14.判断字符串s1中的所有字符是否都出现在字符串s2中(s1长度小于s2)

基本的,穷举遍历,时间复杂度o(N*M)(N为字符串s1长度,M为字符串s2长度);

对查找做一个优化,对字符串s2中的字符做字典排序,时间复杂度降低为o(MlgM+NlgM)=o((M+N)lgM);

如果操作非常频繁的话,我们可以采用空间换时间的做法,对s2做一个HashMap,时间复杂度降低为o(N);

我们还可以为每一个字母映射为一个素数,计算出s2中字母对应素数的乘积X(相同字母只计算一次),然后用s1中字母对应的素数去除X(相同字母只计算一次),如果每次除都没有余数,那么说明s1中的字母都出现在s2中.

15.判断一个链表是否有环

简单的,我们可以记录下每一个访问过的结点的地址,然后每次访问下一个结点时,判断一下是否当前结果已经访问过;

我们也可以设置两个指针,其中一个指针每次往前移动一步(我们称它为慢指针),另一个指针每次往前移动多步(我们称它为快指针),如果有环,则快指针会追上慢指针,类似于田径场上长跑运动员的套圈;

16.访问单链表倒数第N个结点

我们可以遍历一次单链表,得到链表结点个数,然后再遍历一次,这一次只需遍历到倒数第N个结点;

我们也可以用两个指针,同时指向头结点,当第一个指针往前移动N步后,第二个指针才开始移动,当第一个指针访问到尾结点时,第二个指针正好访问到倒数第N个结点;