程序员常用的十种算法（程序员要知道的大厂常见的算法面试题）

忙族 2023-07-06 20:03:35 948

程序员常用的十种算法（程序员要知道的大厂常见的算法面试题）bool StringContain(string &a string &b) { 　　for (int i = 0; i < b.length(); i) 　　{ 　　　　int j; 　　　　for (j = 0; (j < a.length()) && (a[j] != b[i]); j) 　　　　　　; 　　　　if (j >= a.length()) 　　　　{ 　　　　　　return false; 　　　　} 　　} 　　return true; } 如果n是长字符串a的长度，m是短字符串b的长度，那么此算法需要O(nm)次比较。显然，如果n和m很大，时间开销太大，需要寻找更好的办法。参考代码如下：此题初看似乎很简单，但要高效地实现并不轻松。而且，如果面试官步步紧逼，一个一个否决你想到的方法，要

1.2　字符串的包含

题目描述

给定一长字符串a和一短字符串b。请问，如何最快地判断出短字符串b中的所有字符是否都在长字符串a中？请编写函数bool StringContain(string &a string &b)实现此功能。

为简单起见，假设输入的字符串只包含大写英文字母。下面举几个例子。

如果字符串a是"ABCD"，字符串b是"BAD"，答案是true，因为字符串b中的字母都在字符串a中，或者说b是a的真子集。
如果字符串a是"ABCD"，字符串b是"BCE"，答案是false，因为字符串b中的字母E不在字符串a中。
如果字符串a是"ABCD"，字符串b是"AA"，答案是true，因为字符串b中的字母A包含在字符串a中。

分析与解法

此题初看似乎很简单，但要高效地实现并不轻松。而且，如果面试官步步紧逼，一个一个否决你想到的方法，要求你给出更快、更好的方案，恐怕就要费不少脑筋了。

解法一：蛮力轮询

程序员常用的十种算法（程序员要知道的大厂常见的算法面试题）(1)

判断短字符串b中的字符是否都在长字符串a中，最直观也是最简单的思路则是：轮询短字符串b中的每一个字符，逐个与长字符串a中的每个字符进行比较，看是否都在字符串a中。

参考代码如下：

bool StringContain(string &a string &b) { 　　for (int i = 0; i < b.length(); i) 　　{ 　　　　int j; 　　　　for (j = 0; (j < a.length()) && (a[j] != b[i]); j) 　　　　　　; 　　　　if (j >= a.length()) 　　　　{ 　　　　　　return false; 　　　　} 　　} 　　return true; }

如果n是长字符串a的长度，m是短字符串b的长度，那么此算法需要O(nm)次比较。显然，如果n和m很大，时间开销太大，需要寻找更好的办法。

解法二：排序后轮询

程序员常用的十种算法（程序员要知道的大厂常见的算法面试题）(2)

如果允许排序，可以考虑先排序后轮询。例如，可先对这两个字符串中的字母进行排序，然后再对两个字符串依次轮询。

常规情况下，两个字符串的排序需要O(mlogm) O(nlogn)次操作，之后的线性扫描需要O(m n)次操作。关于排序方法，可以采用最常用的快速排序。

参考代码如下：

bool StringContain(string &a string &b) { 　　sort(a.begin() a.end()); 　　sort(b.begin() b.end()); 　　for (int pa = 0 pb = 0; pb < b.length();) 　　{ 　　　　while ((pa < a.length()) && (a[pa] < b[pb])) 　　　　{ 　　　　　　 pa; 　　　　} 　　　　if ((pa >= a.length()) || (a[pa] > b[pb])) 　　　　{ 　　　　　　return false; 　　　　} 　　　　 pb; 　　} 　　return true; }

解法三：素数相乘

有没有比排序后轮询更好的方法呢？

首先，让长字符串a中的每个字母与一个素数对应，如A对应2，B对应3，C对应5，……，依次类推。再遍历长字符串a，把a中的每个字母对应的素数相乘，得到一个整数。然后，让短字符串b中的字母也对应相应的素数，再用b中的每个字母对应的素数除上面得到的整数。如果结果有余数，说明结果为false，当即退出程序；如果整个过程中没有余数，则说明短字符串b是长字符串a的子集。

具体思路总结如下。

（1）按照从小到大的顺序，用26个素数分别代替长字符串a中的所有字母。

（2）遍历长字符串a，求得a中的所有字母对应的素数的乘积。

（3）遍历短字符串b，判断上一步得到的乘积能否被b中的字母对应的素数整除。

（4）输出结果。

上述算法的时间复杂度为O(m n)。当然，最好情况下的时间复杂度为O(n)，即在遍历短字符串b的第一个字母，与长字符串a中所有字符所对应的素数的乘积相除时，当即出现余数，便直接退出程序，返回false。

bool StringContain(string &a string &b) { 　　const int p[26] = { 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 　　　　　　　　　　　 53 59 61 67 71 73 79 83 89 97 101 }; 　　int f = 1; 　　for (int i = 0; i < a.length(); i) 　　{ 　　　　int x = p[a[i] - 'A']; 　　　　if (f % x) 　　　　{ 　　　　　　f *= x; 　　　　} 　　} 　　for (int i = 0; i < b.length(); i) 　　{ 　　　　int x = p[b[i] - 'A']; 　　　　if (f % x) 　　　　{ 　　　　　　return false; 　　　　} 　　} 　　return true; }

这种素数相乘的方法看似可行，实则不可行，因为素数相乘的结果会很大，从而导致整数溢出（前16个字母对应的素数相乘便会超出long long类型所能表示的最大整数范围）。

程序员常用的十种算法（程序员要知道的大厂常见的算法面试题）(3)

解法四：位运算法

如果面试官继续追问，到底有没有更好的办法呢？或许你绞尽脑汁能想到计数排序。但除了计数排序还有别的办法吗？

事实上，可以先把长字符串a中的所有字符都放入一个散列表（hash table）中，然后轮询短字符串b，看b中的每个字符是否都在散列表里，如果都在，说明长字符串a包含短字符串b；否则，说明不包含。

再进一步，可以用位运算（26位整数表示）为长字符串a计算出一个“签名”，再逐一将短字符串b中的字符放到a中进行查找。

参考代码如下：

bool StringContain(string &a string &b) { 　　int hash = 0; 　　for (int i = 0; i < a.length(); i) 　　{ 　　　　hash |= (1 << (a[i] - 'A')); 　　} 　　for (int i = 0; i < b.length(); i) 　　{ 　　　　if ((hash & (1 << (b[i] - 'A'))) == 0) 　　　　{ 　　　　　　return false; 　　　　} 　　} 　　return true; }

这个位运算方法的实质是用一个整数代替了散列表，它的空间复杂度为O(1)，时间复杂度为O(n m)。至此，算是比较完美地解决了这个字符串包含的问题。

程序员常用的十种算法（程序员要知道的大厂常见的算法面试题）(4)