常用算法复习归纳

[TOC]

字符串算法

  1. 旋转字符串
    把abcdef的ef放前面,变成efabcd

    思路:摇手法,先把这两组分别旋转,再一起翻转。

    dcba fe -> ef abcd

    所以解题思路分两步

    1,写一个通用的内部旋转方法。

    reverseStr(s, from, to)
    while(from<to)
        t=s[from]
        s[from++]=s[to]
        s[to--]=t
    

    这个旋转使用了临时变量,也可以使用异或运算来交换字符串,不使用临时变量
    2,利用摇手法三步完成。

  2. 包含字符串

    aef是否在abcdefgA中,不用考虑次序,只考虑单个包含

    思路:把长字符串映射到一个hashtable中

    26个字母可以放到32位的int中,每个占一个次序的标识符

    对每个字母遍历放入int a中

    while(int i=0;i<s.length();i++)
        a |= 1<<(s[i]-'A');
    

    这儿的1<<shift是一个常用方法,把0x01左移用来代表某位的标示,这儿用位或运算|来忽略重复的情况
    然后把要算的aef等字符转换成同样的int,取位与运算,若为0退出

  3. 回文判断,abcdcba这种

    这种首先可以从两边向中间推进,两个指针,每次的值都应该相等。

    然后用栈也行,先依次压入栈,出来的时候就是反向的,也应该等于原来的字符串。

  4. 栈的应用

    栈先入后出,有对称的特性,所以可以处理这类问题,比如括号,引号这类。

    处理路径/a/b/../c/d/../e/f,这种化简也用栈处理,先分隔,然后依次压栈,碰到..后,弹出栈顶的元素。

  5. 求最大回文字串,12212321

    参考:

    Manacher’s ALGORITHM: O(n)时间求字符串的最长回文子串

    Longest Palindromic Substring Part II 最长回文子串

数组队列

  1. 寻找最小的K个数

    一共有n个数,寻找最小的k个,无需排序

    思路:先排序然后直接定位前k个?时间复杂度太高

    其实只要找出前k个的kmax就行了,把比他小的找出来

    先把n分成k块和n-k块

    对前面k个数选出最大的,这时的时间复杂度为O(k),最大值为kmax

    然后用kmax和后面的n-k个数进行比对,当kmax<i,继续

    当kmax>i,交换kmax和i,然后重新对前k个数排序,找出kmax

    所以有O(k(n-k))=O(kn)
    这类问题一般都是维持一个大小为k的容器来处理

查找排序

  1. 找出n个的数组中次数超过一半的数

    思路:可以用hash,val=>次数,再遍历hash

    或设两个临时值,candidate是值,ntimes是次数

    遍历:

    1,当前值赋给ca,nt为1

    2,如果下一个也是它,则nT+1

    如果不是,则nT-1

    如果上面nT-1=0了,还需要把ca重新复制为当前值,nT=1

    3,最后留下的就是超过半数的。

  2. 已知数组中找和为定值k的两个数

    思路:1,用k-i得到互补的数组,然后遍历一个数组遍历另一个数组。

    2,首先排序,O(NlogN)

    然后有a[i]+a[j]=k

    最开始i=0,j=n-1

    while(i<j)
        if(a[i]+a[j]>k) j--;
        elseif(a[i]+a[j]<k) i++;
        else return;
    

    这是一个常用的方法,这儿要意识到是个有序数组,从小到大,所以a[i]只能增大,a[j]只会减小,所以a[i]+a[j]>k,只有a[j]减小来实现,反之亦然。

  3. n阶台阶,每次可挑1或2阶,共有多少种跳法。

    思路:当n为1时,有一种,n为2时,有两种。

    当n为3时,有两种情况,第一步为1阶或2阶,当第一步为1阶时,剩下的为f(2)种,当第一步为2阶,剩下的为f(1)种。

    同理,n阶时,也只有第一步为1阶或2阶的情况,既有f(n)=f(n-1)+f(n-2)种。

    即为一个斐波那契数列,调用递归解决。

    fib(n)
        n<=2: return ret[n);
        else: return fib(n-1)+fib(n-2);
    
  4. 有序数组中找出某值是否存在。

    思路:二分查找

    i=0;j=n-1;
    while(i<j)
        mid=i+(j-i)>>1
        if(a[mid]>k) j=mid-1;
        elseif(a[mid]<k) i=mid+1;
        else return mid;
    

    这是个很经典的方法,两个指针,依次推进。

交集,智力题

  1. 1000瓶药,其中一个是毒药,只能试一次,最少多少老鼠可以试出。

    思路:2^10=1024>1000,用二进制编号,从0000000001到1111101000,而毒药必在其中

    0 0 0 0 0 0 0 0 0 1

    0 0 0 0 0 0 0 0 1 0

    ….

    0 0 0 1 0 1 0 0 1 0

    1 1 1 1 1 0 1 0 0 0

    这样共有10位,从上到下全部含有1的药混合起来给小鼠吃,若死了则毒药在其中,则该列为1.

    全部测完可得到为1的编号,因为只有一瓶毒药,所以得到的二进制数字就是毒药编号。

  2. 约瑟夫问题

← PHP的一些底层笔记  LINUX下字符相关命令 →