常见算法题目解析

Table of Contents

内容包括 leetcode1、matrix67 的题目以及面试过程中遇到的一些题目。 主要是按照 leetcode 题型来分类:

1 Array2(数组)

1.1 数组求和

要求:只用一行代码

int sum(int*a, int n)
{
     return n ==0?0 : sum(a, n -1) + a[n -1];
}

目的:了解循环和递归的关系。

延伸:

1.2 求数组中出现次数超过一半的元素

出自《编程之美》。思路如下: 最直接的解法:对数组进行排序,取 n/2 + 1 个元素即为所求,这种算法的复杂度最坏的情况下是 O(n^2), 平均情况下是 O(n*log2n)。 另一种方式:可以根据不同就抵消,相同就增一的计算器完成。设置一个当前值和当前值的计数器,初始化当前值为数组首元素,计数器值为 1,然后从第二个元素开始遍历整个数组,对于每个被遍历到的值 a[i]:

  • 如果 a[i]==currentValue,则计数器值加 1。
  • 如果 a[i] != currentValue, 则计数器值减 1,如果计数器值小于 0,则更新当前值为 a[i],并将计数器值重置为 1。
#include <stdio.h>
#include <stdlib.h>

int FindMoreValue(int arr[], int n){
    int i;
    int curr_count = 1;
    int curr_value = arr[0];
    for(i = 1; i < n; i++){
        if(arr[i] == curr_value){
            curr_count++;
        }else{
            curr_count--;
            if(curr_count < 0){
                curr_value = arr[i];
                curr_count = 1;
            }
        }
    }
    if(curr_count > 0){
        return curr_value;
    }else{
        //不存在出现次数超过一半的元素
        return -1;
    }
}

延伸:如果是出现次数超过 1/m 的元素呢?

1.3 求数组中元素的最短距离

先对数组排序,然后遍历一次即可

1.4 求两个有序数组的共同元素

1.5 求三个数组的共同元素

1.6 找出出现奇数次的元素

所有元素求异或,结果就是所找的元素。

1.7 求有序数组中满足给定和的数对

1.8 数组循环移位

《编程之美》

1.9 字符串逆序

将一个含有 n 个元素的数组向右循环移动 k 位,要求时间复杂度是 O(n),且只能使用两个额外的变量。

思路:比如数组 1 2 3 4 循环右移 1 位 将变成 4 1 2 3, 观察可知 1 2 3 的顺序在移位前后没有改变,只是和 4 的位置交换了一下,所以等同于 1 2 3 4 先划分为两部分:1 2 3 | 4,然后将 1 2 3 逆序,再将 4 逆序 得到 3 2 1 4,最后整体逆序 得到 4 1 2 3

1.10 组合问题

给定一个含有 n 个元素的整型数组 a,从中任取 m 个元素,求所有组合。比如下面的例子

a = 1, 2, 3, 4, 5
m = 3

输出

1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5, 1 4 5,2 3 4, 2 3 5, 2 4 5,3 4 5

分析:典型的排列组合问题,首选回溯法,为了简化问题,我们将 a 中 n 个元素值分别设置为 1-n

// n 选 m 的所有组合
int buffer[100] ;

void PrintArray(int *a, int n)
{
    for (int i = 0; i < n; ++i)
        cout << a[i] << "";
    cout << endl ;
}

bool IsValid(int lastIndex, int value)
{
    for (int i = 0; i < lastIndex; i++)
    {
        if (buffer[i] >= value)
            return false;
    }
    return true;
}

void Select(int t, int n, int m)
{
    if (t == m)
        PrintArray(buffer, m);
    else
    {
        for (int i = 1; i <= n; i++)
        {
            buffer[t] = i;
            if (IsValid(t, i))
                Select(t + 1, n, m);
        }
    }
}

1.11 合并两个数组

1.12 重排问题

1.13 找出绝对值最小的元素

1.14 数组中前 K 大的数字

使用堆排序,或者 STL 的部分排序。

1.15 寻找出现次数最多的 K 个数

延伸:服务器内存 1G,有一个 2G 的文件,里面每行存着一个 QQ 号(5-10 位数),怎么最快找出出现过最多次的 QQ 号。

解法:

1.将不同的 qq 号码 hash 到 1000 小文件中,然后对单个小文件中的数据进行 hash 统计出现次数,找出该文件中出现次数最多的 qq 号,然后 1000 个 qq 进行排序,找出出现次数最多的。

2.使用位运算计数,使用 m 个 bit 表示 qq 号码,n 个 bit 表示出现的次数,比较适合没有太大极端的情况。

1.16 查找不存在的数字或重复出现的数字

a[n]数组中有 n-1 个取值范围在 0 到 n-1 的数,并且不重复,剩余那个数组项为-1,求不存在的那个数是多少? 解法:用 0 到 n-1 的累计和减去数组的总和,差值就是不存的那个数字。

延伸:

  • 如果有两个不存在的数呢?
  • 如果有 m 个不存在的数呢?

解法:将值为 i 的数字放在 a[i] 位置上,最后值为-1 的位置就是不存在的项。

#include <iostream>
#include <algorithm>

void mNoExistInN(int a[], int n) {
    for(int i=0; i<n-1; ++i) {
        while(a[i]!=i) {
            if(a[i] == -1) {
                std::cout << i << " not exists" << std::endl;
                break;
            }
            else {
                swap(&a[i],&a[a[i]]);
            }
        }
    }
}
  • 一个文件中有 40 亿个整数,每个整数为四个字节,内存为 1GB,写出一个算法:求出这个文件里的整数里不包含的一个整数。

解法:使用一个 bit 表示出现。

  1. 腾讯服务器每秒有 2w 个 QQ 号同时上线,找出 5min 内重新登入的 qq 号并打印出来。

1.17 数组元素随机重新排列

1.18 前缀和与前缀积及其应用

1.18.1 什么是前缀和、前缀积?前缀和、前缀积也称前缀和数组,前缀积数组。

给一数组 A

  • 前缀和:新建一数组 B,数组中每一项 B[i]保存 A 中[0…i]的和;
  • 后缀和:新建一数组 B,数组中每一项 B[i]保存 A 中[i…n-1]的和;
  • 前缀积:新建一数组 B,数组中每一项 B[i]保存 A 中[0…i]的积;
  • 后缀积:新建一数组 B,数组中每一项 B[i]保存 A 中[i…n-1]的积;
题目 1:double a[n],b[n],其中 b[i]=a[0]*a[1]*…*a[i-1]*a[i+1]*…*a[n-1] ,不能使用除法,不允许新开数组。

思路:观察表达式可以发现

b[i]=P[i]*S[i]

其中 P[i]=a[0]*a[1]*…*a[i-1]S[i]=a[i+1]*…*a[n-1] 。进一步观察 b[i]和 b[i-1]关系:

P[i]=P[i-1]*a[i-1]
S[i]=S[i-1]/a[i]

考虑不能使用除法,所以上面第二个式子变换为:

S[i-1]=a[i]*S[i]

可以发现如果求后缀从后往前遍历比较方便。

所以思路也就清除,先遍历 a[i]求前缀积,结果保存 b[i]中,然后遍历一次求后缀积,两者相乘。

void PreSuffAcc(int a[], int b[], int len) {
    for(int i=0; i<len; ++i) {
        b[i] = (i==0) ? 1 : a[i-1]*b[i-1]; //p
    }
    for(int i=n-1,j=1; i>=0;--i) {
        j = (i==n-1)?1:j*a[i+1];//s
        b[i] *= j;
    }
}
题目 2:求数组中连续一段和,绝对值最小?

思路:前缀和的性质: a[i]+a[i+1]+…+a[j]=sum[j]-sum[i-1] 前缀和排序,取最小

题目 3:把一个数组从中间 p 位置分开,使得 a[0]+…+a[p-1]a[p]+a[p+1]+…+a[n-1] 差值最小?

思路:前缀和-(总和-前缀和)=2*前缀和-总和,是该公式最小;

2 Bit Manipulation

2.1 位运算实现四则运算

2.2 判断二进制中 0 或 1 的个数

3 Tree

4 什么是动态规划?动态规划的意义是什么?与递归、分治、贪婪的区别和联系3

下面是知乎上王勐关于这个问题的回答,讲解的很透彻(链接) :

动态规划的本质不在于是递推或是递归,也不需要纠结是不是内存换时间。理解动态规划并不需要数学公式介入,只是完全解释清楚需要点篇幅…

首先需要明白哪些问题不是动态规划可以解决的,才能明白为神马需要动态规划。不过好处是顺便也就搞明白了递推贪心搜索和动规之间有什么关系,以及帮助那些总是把动规当成搜索解的同学建立动规的思路。当然,熟悉了之后可以直接根据问题的描述得到思路,如果有需要的话再补充吧。

动态规划是对于某一类问题的解决方法!!重点在于如何鉴定“某一类问题”是动态规划可解的,而不是纠结解决方法是递归还是递推!怎么鉴定 dp 可解的一类问题需要从计算机是怎么工作的说起…

计算机的本质是一个状态机,内存里存储的所有数据构成了当前的状态,CPU 只能利用当前的状态计算出下一个状态(不要纠结硬盘之类的外部存储,就算考虑它们也只是扩大了状态的存储容量而已,并不能改变下一个状态只能从当前状态计算出来这一条铁律)。当你企图使用计算机解决一个问题时, 其实就是在思考如何将这个问题表达成状态(用哪些变量存储哪些数据)以及如何在状态中转移(怎样根据一些变量计算出另一些变量) 。所以所谓的空间复杂度就是为了支持你的计算所必需存储的状态最多有多少,所谓时间复杂度就是从初始状态到达最终状态中间需要多少步!

太抽象了还是举个例子吧:

比如说我想计算第 100 个斐波那契数,每一个斐波那契数就是这个问题的一个状态,每求一个新数字只需要之前的两个状态。所以同一个时刻,最多只需要保存两个状态,空间复杂度就是常数;每计算一个新状态所需要的时间也是常数且状态是线性递增的,所以时间复杂度也是线性的。

上面这种状态计算很直接,只需要依照固定的模式从旧状态计算出新状态就行(a[i]=a[i-1]+a[i-2]),不需要考虑是不是需要更多的状态,也不需要选择哪些旧状态来计算新状态。对于这样的解法,我们叫递推。

斐波那契那个例子过于简单,以至于让人忽视了 阶段 的概念, 所谓阶段是指随着问题的解决,在同一个时刻可能会得到的不同状态的集合 (注意是集合) 。

斐波那契数列中,每一步会计算得到一个新数字,所以每个阶段只有一个状态。想象另外一个问题情景,假如把你放在一个围棋棋盘上的某一点,你每一步只能走一格,因为你可以东南西北随便走,所以你当你同样走四步可能会处于很多个不同的位置。从头开始走了几步就是第几个阶段,走了 n 步可能处于的位置称为一个状态,走了这 n 步所有可能到达的位置的集合就是这个阶段下所有可能的状态。

现在问题来了, 有了阶段之后,计算新状态可能会遇到各种奇葩的情况,针对不同的情况,就需要不同的算法 ,下面就分情况来说明一下:

假如问题有 n 个阶段,每个阶段都有多个状态,不同阶段的状态数不必相同, 一个阶段的一个状态可以得到下个阶段的所有状态中的几个 (注意不是能够得到下个阶段的所有 状态)。那我们要计算出最终阶段的状态数自然要经历之前每个阶段的某些状态。

好消息是,有时候我们并不需要真的计算所有状态,比如这样一个弱智的棋盘问题:从棋盘的左上角到达右下角最短需要几步。答案很显然,用这样一个弱智的问题是为了帮助我们理解阶段和状态。某个阶段确实可以有多个状态,正如这个问题中走 n 步可以走到很多位置一样。但是同样 n 步中,有哪些位置可以让我们在第 n+1 步中走的最远呢?没错,正是第 n 步中走的最远的位置。换成一句熟悉话叫做 “下一步最优是从当前最优得到的”。所以 为了计算最终的最优值,只需要存储每一步的最优值即可,解决符合这种性质的问题的算法就叫贪心 。如果只看最优状态之间的计算过程是不是和斐波那契数列的计算很像?所以计算的方法是递推。

既然问题都是可以划分成阶段和状态的。这样一来我们一下子解决了一大类问题:一个阶段的最优可以由前一个阶段的最优得到。

如果一个阶段的最优无法用前一个阶段的最优得到呢?

什么你说只需要之前两个阶段就可以得到当前最优?那跟只用之前一个阶段并没有本质区别。

最麻烦的情况在于你 需要之前所有的情况 才行。

再来一个迷宫的例子:在计算从起点到终点的最短路线时,你不能只保存当前阶段的状态,因为题目要求你最短,所以你 必须知道之前走过的所有位置 。因为即便你当前在的位置不变, 之前的路线不同会影响你的之后走的路线 。这时你需要保存的是之前每个阶段所经历的那个状态,根据这些信息才能计算出下一个状态!

每个阶段的状态或许不多,但是每个状态都可以转移到下一阶段的多个状态,所以解的复杂度就是指数的,因此时间复杂度也是指数的。哦哦,刚刚提到的之前的路线会影响到下一步的选择,这个令人不开心的情况就叫做有后效性。

刚刚的情况实在太普遍,解决方法实在太暴力,有没有哪些情况可以避免如此的暴力呢?

契机就在于后效性。

有一类问题,看似需要之前所有的状态,其实不用。不妨也是拿最长上升子序列的例子来说明为什么它不必需要暴力搜索,进而引出动态规划的思路。假装我们年幼无知想用搜索去寻找最长上升子序列。怎么搜索呢?需要从头到尾依次枚举是否选择当前的数字,每选定一个数字就要去看看是不是满足 “上升” 的性质,这里第 i 个阶段就是去思考是否要选择第 i 个数,第 i 个阶段有两个状态,分别是选和不选。哈哈,依稀出现了刚刚迷宫找路的影子!咦慢着,每次当我决定要选择当前数字的时候, 只需要和之前选定的一个数字比较就行了 !这是和之前迷宫问题的本质不同!这就可以纵容我们 不需要记录之前所有的状态 啊!既然我们的选择已经不受之前状态的组合的影响了,那时间复杂度自然也不是指数的了啊!虽然我们不在乎某序列之前都是什么元素,但我们还是需要这个序列的长度的。所以我们只需要记录以某个元素结尾的 LIS 长度就好!因此第 i 个阶段的最优解只是由前 i-1 个阶段的最优解得到的,然后就得到了 DP 方程。

LIS(i) = max{LIS(j)+1} j<i and a[j]<a[i]

所以 一个问题是该用递推、贪心、搜索还是动态规划,完全是由这个问题本身阶段间状态的转移方式决定的! :

  • 每个阶段只有一个状态 -> 递推;
  • 每个阶段的最优状态都是由上一个阶段的最优状态得到的 -> 贪心;
  • 每个阶段的最优状态是由之前所有阶段的状态的组合得到的 -> 搜索;
  • 每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的 -> 动态规划。

每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到这个性质叫做最优子结构;而不管之前这个状态是如何得到的这个性质叫做无后效性。 另:其实动态规划中的最优状态的说法容易产生误导,以为只需要计算最优状态就好,LIS 问题确实如此,转移时只用到了每个阶段 “选” 的状态。但实际上有的问题往往 需要对每个阶段的所有状态都算出一个最优值,然后根据这些最优值再来找最优状态。 比如背包问题就需要对前 i 个包(阶段)容量为 j 时(状态)计算出最大价值。然后在最后一个阶段中的所有状态种找到最优值。

4.1 递归

4.1.1 爬楼梯问题

有 n 层的台阶,一开始你站在第 0 层,每次最多可以爬 m 层,请问爬到第 n 层有多少种不同的方法?

解法:S(k)表示第 k 层的爬法,那么最后一步他爬的楼层可能是 1 到 m 的任意值,所以 S(k)=S(k-1)+….+S(k-m),还是递归问题,并不是动态规划。

void clim_stair(int m, int k) {
    static int a[k];
    if(a[k]==0) {
        //cal a[k]
        if(k==0) {
            a[k] = 1;
        }
        else {
            for(int i=k-1; (i>=k-m)&&(i>=0); --i) {
                a[k] += clim_stair(i);
            }
        }
    }
    return a[k];
}

4.2 Dynamic Programming(动态规划)

4.2.1 最长递增子序列 (LIS)

4.2.2 最大连续子序列之和

给定 K 个整数的序列 {N1, N2, …, NK},其任意连续子序列可表示为 {Ni, Ni+1, …, Nj},其中 1 <= i <= j <= K。最大连续子序列是所有连续子序中元素和最大的一个, 例如给定序列 {-2, 11, -4, 13, -5, -2},其最大连续子序列为 {11, -4, 13},最大和为 20。

状态转移方程:sum[i]=max(sum[i-1]+a[i],a[i])

4.2.3 数塔问题

数塔问题 :要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少?

4.2.4 背包问题

有 n 个重量和价值分别为 vector<int> weight, vector<int> value 的物品;背包最大负重为 W,求能用背包装下的物品的最大价值?

4.2.5 最长公共子序列 (LCS)

一个序列 S,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。

4.3 Greedy(贪婪)

5 Backtracking

6 Linked list

6.1 单链表反转

6.2 单链表判断是否有环

6.3 单链表判断是否相交

7 Math

7.0.1 大数加法

    #include <iostream>
    #include <vector>
    #include <string>
    #include <map>
    #include <memory>
    #include <algorithm>
    #include <cassert>
    #include <functional>

    #include <gtest\gtest.h>

    namespace phenix3443 {
        //建立进制对应的哈希表
        std::shared_ptr<std::map<char, short>> Map_10 () {
            auto r_map = std::make_shared<std::map<char, short>> ();

            for ( int i = 0; i < 10; ++i ) {
                (*r_map)['0' + i] = i;
            }
            return r_map;
        }
        std::shared_ptr<std::map<char, short>> Map_16 () {
            auto r_map = std::make_shared<std::map<char, short>> ();

            for ( int i = 0; i < 10; ++i ) {
                (*r_map)['0' + i] = i;
            }
            for ( int i = 10; i < 16; ++i ) {
                (*r_map)['A' + i - 10] = i;
            }
            return r_map;
        }
        std::map<short, std::function<std::shared_ptr<std::map<char, short>> ()>> build_randix_map = {
            { 10,Map_10 },
            { 16,Map_16 },
        };
        //将 std::string 表示的大数存放在 std::vector<short>中
        inline void str_to_vc (const std::string& str, std::vector<short>& vs, const int base = 10) {
            auto r_map = build_randix_map[base] ();

            std::function<bool (const char&)> f = [&](const char& c) {return (*r_map).count (c) != 0; };
            auto first_dig = find_if (str.begin (), str.end (), f);
            auto last_dig = find_if_not (first_dig, str.end (), f);
            auto sign_at = find (str.begin (), first_dig, '-');
            short sign = (sign_at != first_dig) ? -1 : 1;

            for_each (first_dig, last_dig, [&](const char& e) {vs.push_back (sign*((*r_map)[e])); });
        }
        //将 std::vector<short>中存放的大数放回 std::string 中
        inline void vc_to_str (const std::vector<short>& vs, std::string& str, const int base = 10) {
            auto r_map = build_randix_map[base] ();
            std::map<short, char> tmp_map;
            for ( auto& e : *r_map )
                tmp_map.insert ({ e.second,e.first });
            for_each (vs.begin (), vs.end (), [&](const short& e) {str.push_back (tmp_map[(e + base) % base]); });
            if ( vs[0] < 0 ) str.insert (str.begin (), '-');
        }

        //大整数加法
        //考虑:    1.有效输入,包含正负号,字符串中非数字字符,字符串开始的连续空格,
        //      2.存放的数据结构 std::vector 与 std::string
        //      3.如何处理进位
        //      4.随意输入大数字的长度大小
        //      5.进制

        //知识点:1.字符与数字之间的转换
        //       2.const 在参数列表处的使用
        //       3.STL 算法库使用 find 系列 for_each
        //       4.lamda 函数的使用,值捕获与引用捕获
        //       5.负数取模运算

        int BigSum (const std::string& num1, const std::string& num2, std::string& sum, const int base = 10) {
            assert (!num1.empty () && !num2.empty () && sum.empty ());
            //将 std::string 每一位转换为 voctor<short>对应的数字
            std::vector<short> vbig, vsmall;

            str_to_vc (num1, vbig);
            str_to_vc (num2, vsmall);

            // 保证 vbig 保存了较大的数
            if ( vbig.size () < vsmall.size () ) swap (vbig, vsmall);
            // vbig vsmall 按位累加,不考虑进位
            std::vector<short> vsum (vbig.size (), 0);
            for ( int i = vbig.size () - 1, j = vsmall.size () - 1; i >= 0; --i ) {
                vsum[i] = vbig[i] + ((j >= 0) ? vsmall[j--] : 0);
            }
            // 处理进位
            for ( int i = vsum.size () - 1; i >= 0; --i ) {
                if ( vsum[i] > base ) {
                    vsum[i] -= base;
                    if ( i > 0 )
                        ++vsum[i - 1];
                    else
                        vsum.insert (vsum.begin (), 1);
                }
            }
            //第一步的逆转换
            vc_to_str (vsum, sum);
            return 0;
        }

        TEST(TestBigSum,mul){
            std::string a = "-2222";
            std::string b = "1111";
            std::string sum;
            BigSum (b, a, sum);
            EXPECT_STREQ ("-9999", sum.c_str ());
        }
    }

7.0.2 高精度乘法

两个数相乘,小数点后位数没有限制,请写一个高精度算法

8 String

8.1 字符串逆序

8.2 单词逆序

9 大数据处理

9.1 中位数

在一个文件中有 10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。只写出思路即可。

10 快排 归并 二分查找

11 统计一些数字中出现次数最多的数字

Footnotes:

Author: lsl

Created: 2016-08-07 Sun 19:48

Validate