字符串/数组面试题

た入场券 2022-05-24 12:14 156阅读 0赞

[1     在一个字符串中找到第一个只出现一次的字符，如输入abac，则输出b。][1_abac_b]

[2     输出字符串的所有组合，如"abc"输出a、b、c、ab、ac、bc、abc。][2_abc_a_b_c_ab_ac_bc_abc]

[3     根据条件找出两个数。][3]

[4     求数组（或环状数组）的最大连续（或不连续）子序列和。][4]

#       1     在一个字符串中找到第一个只出现一次的字符，如输入abac，则输出b。 #

本题看似很简单，开个长度为256的表，对每个字符hash计数就可以了，但**很多人写的代码都存在bug，可能会发生越界访问**。这是C/C++语言上的一个陷阱，C/C++中的char有三种类型：char、signed char和unsigned char。char类型的符号是由编译器指定的，一般是有符号的。在对字符进行hash时，应该先将字符转为无符号类型，不然，下标为负值时，就会出现越界访问。

另外，可以用一个cache数组，记录当前找到的只出现一次的字符，避免对原字符串进行第二次遍历。

char get\_first\_only\_one**(**const char str**\[\])**

**\{**

**if** **(**str **==** **NULL)**  **return** 0**;**

const int table\_size **=** 256**;**             //最好写成： 1 << CHAR\_BIT 或 UCHAR\_MAX + 1

unsigned  count**\[**table\_size**\]** **=** **\{** 0**\};**

char      cache**\[**table\_size**\];**

char **\***q **=** cache**;**

**for** **(**const char**\*** p **=** str**;**  **\***p **!=** 0**;** **++**p**)**

**if** **(++**count**\[(**unsigned char**)\***p**\]** **==** 1**)**  **\***q**++** **=** **\***p**;**  //要先转成无符号数!!!

**for** **(**const char**\*** p **=** cache**;** p **<** q**;** **++**p**)**

**if** **(**count**\[(**unsigned char**)\***p**\]** **==** 1**)**  **return** **\***p**;**

**return** 0**;**

**\}**

#       2     输出字符串的所有组合，如"abc"输出a、b、c、ab、ac、bc、abc。 #

本题假定字符串中的所有字符都不重复。根据题意，如果字符串中有n个字符，那么总共要输出2^n – 1种组合。这也就意味着n不可能太大，否则的话，以现在CPU的运算速度，程序运行一次可能需要跑几百年、几千年，而且也没有那么大的硬盘来储存运行结果。因而，可以假设n小于一个常数（比如64）。

本题最简洁的方法，应该是采用递归法。遍历字符串，每个字符只能取或不取。取该字符的话，就把该字符放到结果字符串中，遍历完毕后，输出结果字符串。

n不是太小时，递归法效率很差（栈调用次数约为2^n，尾递归优化后也有2^(n-1)）。注意到本题的特点，可以构照一个长度为n的01字符串（或二进制数）表示输出结果中最否包含某个字符，比如："001"表示输出结果中不含字符a、b，只含c，即输出结果为c，而"101"，表示输出结果为ac。原题就是要求输出"001"到"111"这2^n – 1个组合对应的字符串。

//迭代法

void all\_combine**(**const char str**\[\])**

**\{**

**if** **(**str **==** **NULL** **||** **\***str **==** 0**)** **return;**

const size\_t max\_len **=** 64**;**

size\_t len **=**  strlen**(**str**);**

**if** **(**len **>=** max\_len **)** **\{**

puts**(**"输入字符串太长。\\n你愿意等我一辈子吗？"**);**

**return;**

**\}**

bool used**\[**max\_len**\]** **=** **\{** 0**\};**    //可以用一个64位无符号数表示used数组

char cache**\[**max\_len**\];**

char **\***result **=** cache **+** len**;**

**\***result **=** 0**;**

**while** **(true)** **\{**

size\_t idx **=** 0**;**

**while** **(**used**\[**idx**\])** **\{**      //模拟二进制加法,一共有2^len – 1个状态

used**\[**idx**\]** **=** **false;**

**++**result**;**

**if** **(++**idx **==** len**)**  **return;**

**\}**

used**\[**idx**\]** **=** **true;**

**\*--**result **=** str**\[**idx**\];**

puts**(**result**);**

**\}**

//递归解法

static void all\_combine\_recursive\_impl**(**const char**\*** str**,** char**\*** result\_begin**,** char**\*** result\_end**)**

**\{**

**if** **(\***str **==** 0**)** **\{**

**\***result\_end **=** 0**;**

**if** **(**result\_begin **!=** result\_end**)** puts**(**result\_begin**);**

**return;**

**\}**

all\_combine\_recursive\_impl**(**str **+** 1**,** result\_begin**,** result\_end**);**      //不取\*str

**\***result\_end **=** **\***str**;**

all\_combine\_recursive\_impl**(**str **+** 1**,** result\_begin**,** result\_end **+** 1**);**  //取\*str

**\}**

** **

void all\_combine\_recursive**(**const char str**\[\])**

**\{**

**if** **(**str **==** **NULL)** **return;**

const size\_t max\_len **=** 64**;**

size\_t len **=**  strlen**(**str**);**

**if** **(**len **>=** max\_len **)** **\{**

puts**(**"输入字符串太长。\\n你愿意等我一辈子吗？"**);**

**return;**

**\}**

char result**\[**max\_len**\];**

all\_combine\_recursive\_impl**(**str**,** result**,** result**);**

**\}**

** **

#       3     根据条件找出两个数。 #

**①      数组中，除了两个数字出现奇数次外，其它数字都出现偶数次，找出这两个数字：**

**②      长度为n的数组，由数字1到n组成，其中数字a不出现，数字b出现两次，其它的数字恰好出现一次，在不修改原数组的情况下，找出数字a和数字b。**

①       数组中，只有两个数字出现奇数次，其它数字都出现偶数次。假设这两数为a、b。

利用 异或的性质：a xor a = 0         a xor 0 = a

以及 a xor b = b xor a   (a xor b) xor c  = a xor (b xor c)

对数组中的所有数进行异或，结果c等于(a xor b)。由于a和b不相乘，因而c不为0，假设c的二进制表示中，第m位不为0。根据第m位是否为0，可以将原数组划分为两块，

显然，a和b不可能分在同一块。由于各块中，只有a或b是奇数次出现的，因而各块所有的数的异或值要么等于a、要么等于b。

struct Pair **\{**

int first**;**

int second**;**

**\};**

Pair find\_two\_appear\_once\_number**(**const int data**\[\],** size\_t len**)**

**\{**

assert**(**data **&&** len **>=** 2**);**

int xor\_all **=** 0**;**

**for** **(**size\_t i **=** 0**;** i **<** len**;** **++**i**)** xor\_all **^=** data**\[**i**\];**

//下面的位运算写法只适用于采用二补数的机器。

const int flag **=** xor\_all **&** **-(**unsigned**)**xor\_all**;**

/\*

根据C/C++标准，为了兼容一补数之类的老古董，正确的写法应该是：

const unsigned tx = \*(const unsigned\*)(&xor\_all);

const unsigned ty = tx & -tx;

const int flag = \*(const int\*)&ty;

\*/

int xor\_a **=** 0**;**

**for** **(**size\_t i **=** 0**;** i **<** len**;** **++**i**)**

**if** **(**data**\[**i**\]** **&** flag**)**  xor\_a **^=** data**\[**i**\];**

const Pair ret **=** **\{**  xor\_a**,** xor\_a **^** xor\_all**\};**

**return** ret**;**

**\}**

②       有三种解法：

方法一：如果将1到n这n个数也放入数组中，则数字a出现1次，数字b出现3次，可以利用上面的解法，通过两次遍历找出数字c与d，再通过第三次遍历，只遍历原数组，判断数字c是否在原数组中，从而确定c与d，哪个等于a，哪个是等于b。

方法二：对方法一进行改进。在第一次遍历时，额外计算出a与b的差值，利用该信息，可以确定前两次遍历找出的只出现奇数次的两个数，哪个是a、哪个b。

方法三：只进行一次遍历，计算出a与b的差c，以及它们间的平方差d，由这两个信息可以直接解得a、b的具体值。

方法一与方法二，在实现中必须计算 **0 xor 1 xor 2 xor 3 … xor n，这个有O(1)解法，对偶数a，显然a xor (a + 1) = 1，因而每4个数的异或值为0，即周期为4。同样的，可证明，根据(a xor b)不为0的某一位，把原数组划分两块后，各块每8个数的异或值为0，周期为8。**

方法二与方法三，在实现中，比须考虑到计算过程中可能出现的溢出问题。**避免溢出最好的方法就是将有符号数转为无符号数，利用“无符号数算术运算是采用模运算，不存在溢出”这个特点。（在32位平台，两个无符号数a、b的和是定义为：(a + b) mod 2^32。）**

对方法三的详细解释，可参考本人的文章[《避免计算过程中出现溢出的一个技巧》][Link 1]。

//方法二

Pair find\_number2**(**const int arr**\[\],** unsigned len**)**

**\{**

assert**(**arr **&&** len **>=** 2**);**

const unsigned**\*** const data **=** **(**const unsigned**\*)**arr**;**

unsigned xor\_all **=** 0**,** sum **=** 0**;**

**for** **(**unsigned i **=** 0**;** i **<** len**;** **++**i**)**  **\{**

const unsigned value **=** data**\[**i**\];**

xor\_all **^=**  value**;**

sum **+=** value**;**

**\}**

//1 + 2 + 3 + ... + len = len \* (len + 1) / 2

const unsigned sum\_all **=** **(**len **+** 1**)** **/** 2u **\*** **(**len **+** **(**len **+** 1**)** **%** 2u**);**

const unsigned diff **=** sum\_all **-** sum**;**

// 0 xor 1 xor 2 xor 3 ... xor len   由于每2个数（2\*k与2\*k+1）异或值为1，每4个数的异或值为0，

// 可证明总异或值等于arr\[len % 4\] （其中 arr\[4\] = \{len, 1, len ^ 1 (= len + 1), 0\}）

const unsigned xor\_n **=** **(**len **%** 2u **==** 0 **?** len **:** 1u**)** **^** **(**len **%** 4u **/** 2u**);**

xor\_all **^=** xor\_n**;**

const unsigned flag **=** xor\_all **&** **-**xor\_all**;**

unsigned xor\_a **=** 0**;**

**for** **(**unsigned i **=** 0**;** i **<** len**;** **++**i**)**

**if** **(**data**\[**i**\]** **&** flag**)** xor\_a **^=** data**\[**i**\];**

//每8个数(8\*k到8\*k+7)，根据某一位是否为1，划为两部分后，每部分的异或值均为0

**for** **(**unsigned i **=** len **&** **~**7u**;** i **<=** len**;** **++**i**)**

**if** **(**flag **&** i**)** xor\_a **^=**  i**;**

const unsigned xor\_b **=** xor\_a **^** xor\_all**;**

**if** **(**xor\_a **-** xor\_b **==** diff**)** **\{**

const Pair result **=** **\{**  xor\_a**,** xor\_b**\};**

**return** result**;**

**\}**

const Pair result **=** **\{**  xor\_b**,** xor\_a**\};**

**return** result**;**

**\}**

//方法三， 这是最高效的做法，但也比方法二麻烦很多。缺点很明显，效率太依赖于数组长度n的大小。

//32位CPU平台，长度n一定小于2^16次方时，表示一个数的平方值，可采用32位无符号数类型，效率极高。

//长度n一定小于2^31次方时，就必须用到64位无符号数类型，效率稍差。

//长度n若在\[2^31, 2^32)时，表示 所有数的和sum，就必须改用64位无符号数类型，效率很差。

Pair find\_number3**(**const int arr**\[\],** unsigned len**)**

**\{**

const unsigned bits **=** CHAR\_BIT **\*** **sizeof(**unsigned**);**

\#if SMALL\_ARRAY

const unsigned max\_len **=** 1u **<<** **(**bits **/** 2u**);**

**typedef** unsigned int uint**;**

\#else

const unsigned max\_len **=** 1u **<<** **(**bits **-** 1**);**

**typedef** unsigned long long uint**;**

\#endif

assert**(**arr **&&** len **>=** 2 **&&** len **<** max\_len**);**

const unsigned**\*** const data **=** **(**const unsigned**\*)**arr**;**

unsigned sum **=** 0**;**

uint square\_sum **=** 0**;**

**for** **(**unsigned i **=** 0**;** i **<** len**;** **++**i**)**  **\{**

const unsigned value **=** data**\[**i**\];**

sum **+=** value**;**

square\_sum **+=** **(**uint**)**value **\*** value**;**     //注意两个数的乘积是否会溢出

**\}**

//1 + 2 + 3 + ... + len = len \* (len + 1) / 2

const uint sum\_all **=** **(**len **+** 1**)** **/** 2u **\*** **(**uint**)(**len **+** **(**len **+** 1**)** **%** 2u**);**

//1^2 + 2^2 + 3^2 + ... + len^2 = len \* (len + 1) \* (2 \* len + 1) / 6

const unsigned len2 **=** 2u **\*** len **+** 1**;**

const uint square\_sum\_all **=** len2 **%** 3u **==** 0 **?** len2 **/** 3u **\*** sum\_all **:** sum\_all **/** 3u **\*** len2**;**

unsigned difference **=** **(**unsigned**)**sum\_all **-** sum**;**

uint square\_difference **=** square\_sum\_all **-** square\_sum**;**

const bool is\_negative **=** difference **>** INT\_MAX**;**

**if** **(**is\_negative**)** **\{**

difference **=** **-**difference**;**

square\_difference **=** **-**square\_difference**;**

**\}**

assert**(**difference **!=** 0 **&&** square\_difference **%** difference **==** 0**);**

const unsigned sum\_two **=** square\_difference **/** difference**;**

assert**((**sum\_two **+** difference**)** **%** 2u **==** 0**);**

const unsigned larger  **=** **(**sum\_two **+** difference**)** **/** 2u**;**

const unsigned smaller **=** **(**sum\_two **-** difference**)** **/** 2u**;**

**if** **(**is\_negative**)** **\{**

const Pair result **=** **\{**  smaller**,** larger**\};**

**return** result**;**

**\}**

const Pair result **=** **\{**  larger**,** smaller**\};**

**return** result**;**

**\}**

#       4     求数组（或环状数组）的最大连续（或不连续）子序列和。 #

本题共有4小题。遇到这类题，首先想到的应该是动态规划思想。（下面的代码中，都假定所进行的有符号数算术运算不会发生溢出。可以通过改用64位整数表些某些数，来保证这点。）

**①      数组的最大连续子序列和（连续子序列和的最大值）**

假设f(n)为数组的前n个元素中，以第n个元素结尾的最大连续子序列和，则对第n+1个元素(值为v)，只有两种选择： 将该元素放入前n-1的最大连续子序列后、新开一个子序列。

因而**f(n+1) = max(f(n) + v, v)**。显然 max\{ f(i) | i = 1, 2, 3 .. \}  即为所求

int max\_continuous\_sum**(**const int arr**\[\],** size\_t len**)**

**\{**

assert**(**arr **&&** len **>** 0**);**

int cur\_max\_sum **=** arr**\[**0**\],** max\_sum **=** cur\_max\_sum**;**

**for** **(**size\_t i **=** 1**;** i **<** len**;** **++**i**)** **\{**

cur\_max\_sum **=** max**(**cur\_max\_sum **+** arr**\[**i**\],** arr**\[**i**\]);**

max\_sum     **=** max**(**cur\_max\_sum**,** max\_sum**);**

**\}**

**return** max\_sum**;**

**\}**

**②      环状数组的最大连续子序列和**

从环状数组中任一点A，从0开始编号，

假设环状数组中，和最大的连续子序列，是从下标i开始，到下标j(不包括j)结束。

若i < j, 则可以从A点前面断开，问题转为“求普通数组的最大连续子序列和”。

若i > j，由于:   **所有元素和 = i->j的子序列和 + j->i的子序列和**

求“i->j的子序列和最大” 等价于求 “j->i的子序列和最小”。

即“求普通数组的最小连续子序列和”。

int max\_ring\_continuous\_sum**(**const int arr**\[\],** size\_t len**)**

**\{**

assert**(**arr **&&** len **>** 0**);**

int sum **=** arr**\[**0**\];**

int cur\_min\_sum **=** sum**,** min\_sum **=** sum**;**

int cur\_max\_sum **=** sum**,** max\_sum **=** sum**;**

**for** **(**size\_t i **=** 1**;** i **<** len**;** **++**i**)** **\{**

const int value **=** arr**\[**i**\];**

sum **+=** value**;**

cur\_max\_sum **=** max**(**cur\_max\_sum **+** value**,** value**);**

max\_sum     **=** max**(**cur\_max\_sum**,** max\_sum**);**

cur\_min\_sum **=** min**(**cur\_min\_sum **+** value**,** value**);**

min\_sum     **=** min**(**cur\_min\_sum**,** min\_sum**);**

**\}**

**return** max**(**max\_sum**,** sum **-** min\_sum**);**

**\}**

**③      数组的最大不连续子序列和（不连续子序列和的最大值）**

假设f(i)表示数组arr前i个元素的最大不连续子序列和，对第i个数(arr\[i-1\])只有三种选择：

忽略该数、放在前i-2个元素的最大不连续子序列后、新开一序列。

(由于要保证不连续，不能放在前i-1个元素的最大不连续子序列后)

因而 f(i) = max(f(i-1), f(i-2) + arr\[i-1\], arr\[i-1\])   (i >= 3)

初始值：f(1) = arr\[0\]  (另外，可设f(0) = 0，使f(2)也满足上式)。显然，f(n)即为所求。

int max\_discontinuous\_sum**(**const int arr**\[\],** size\_t len**)**

**\{**

assert**(**arr **&&** len **>** 0**);**

int max\_sum **=** arr**\[**0**\],** prev\_max\_sum **=** 0**;**

**for** **(**size\_t i **=** 1**;** i **<** len**;** **++**i**)** **\{**

const int value **=** arr**\[**i**\];**

const int old\_max\_sum **=** max\_sum**;**

max\_sum  **=** max**(**max\_sum**,** prev\_max\_sum **+** value**,** value**);**

prev\_max\_sum **=** old\_max\_sum**;**

**\}**

**return** max\_sum**;**

**\}**

其它DP方法：

⒈　假设f(i)表示前i个元素中，  以第i个元素结尾的最大不连续子序列和，

g(i)表示前i个元素中，不以第i个元素结尾的最大不连续子序列和，

(也就是前i-1个元素的最大不连续子序列和)

则 f(i) = max(g(i-1)+arr\[i-1\], arr\[i-1\])      (i >= 3)

g(i) = max(f(i-1), g(i-1))                 (i >= 3)

初始值： f(2) = arr\[1\], g(2) = arr\[0\]

当n>=2时，max(f(n), g(n)) 即为所求

⒉　假设f(i)表示前i个元素中，以第i个元素结尾的最大不连续子序列和，

g(i)表示前i个元素中，最大不连续子序列和。

则 f(i) = max(g(i-2)+arr\[i-1\], arr\[i-1\])     (i >= 3)

g(i) = max(f(i), g(i-1))                  (i >= 2)

初始值： g(1) = arr\[0\] (可设g(0) = 0，使f(2)也满足上式）

g(n)即为所求

**④      环状数组的最大不连续子序列和**

假设数组长度为n，若从环状数组中任一点，从0开始编号，则结束编号为n-1。由于要保证不连续，编号为0的元素和编号为n-1的元素不能同时取，则对编号为0到n-2和编号为1到n-1的两个子数组分别求最大不连续子序列和，较大的即为所求。具体实现上，可以先求编号为0到n-1的具有最大和的不连续子序列，是否同时包含编号为0和编号为n-1的元素，若不同时包含的话，所得结果即为所求；若同时包含的话，需要再计算编号为1到n-1的子数组的最大不连续子序列和。这需要遍历数组一到二次，下面是只遍历一次的写法：

int max\_ring\_discontinuous\_sum**(**const int arr**\[\],** size\_t len**)**

**\{**

assert**(**arr **&&** len **>** 0**);**

**if** **(**len **==** 1**)** **return** arr**\[**0**\];**

int max\_sum1 **=** max**(**arr**\[**0**\],** arr**\[**1**\]),** prev\_max\_sum1 **=** arr**\[**0**\];**

int max\_sum2 **=** arr**\[**1**\],** prev\_max\_sum2 **=** 0**;**

**for** **(**size\_t i **=** 2**;** i **<** len **-** 1**;** **++**i**)** **\{**

\#if 0

**if** **(**max\_sum1 **==** max\_sum2**)** **\{**

**for** **(**size\_t j **=** i**;** j **<** len**;** **++**j**)** **\{**

const int value **=** arr**\[**j**\];**

const int old\_max\_sum2 **=** max\_sum2**;**

max\_sum2 **=** max**(**max\_sum2**,** prev\_max\_sum2 **+** value**,** value**);**

prev\_max\_sum2 **=** old\_max\_sum2**;**

**\}**

**return** max\_sum2**;**

**\}**

\#endif

const int value **=** arr**\[**i**\];**

const int old\_max\_sum1 **=** max\_sum1**;**

const int old\_max\_sum2 **=** max\_sum2**;**

max\_sum1 **=** max**(**max\_sum1**,** prev\_max\_sum1 **+** value**,** value**);**

max\_sum2 **=** max**(**max\_sum2**,** prev\_max\_sum2 **+** value**,** value**);**

prev\_max\_sum1 **=** old\_max\_sum1**;**

prev\_max\_sum2 **=** old\_max\_sum2**;**

**\}**

const int value **=** arr**\[**len **-** 1**\];**

max\_sum2  **=** max**(**max\_sum2**,** prev\_max\_sum2 **+** value**,** value**);**

**return** max**(**max\_sum1**,** max\_sum2**);**

**\}**

作者： [ flyinghearts ][flyinghearts]  
出处： [ http://www.cnblogs.com/flyinghearts/ ][flyinghearts]  
本文采用 [知识共享署名-非商业性使用-相同方式共享 2.5 中国大陆许可协议][-_-_ 2.5]进行许可，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。

[1_abac_b]: http://www.cnblogs.com/flyinghearts/archive/2012/03/18/2405118.html#_Toc319785460
[2_abc_a_b_c_ab_ac_bc_abc]: http://www.cnblogs.com/flyinghearts/archive/2012/03/18/2405118.html#_Toc319785461
[3]: http://www.cnblogs.com/flyinghearts/archive/2012/03/18/2405118.html#_Toc319785462
[4]: http://www.cnblogs.com/flyinghearts/archive/2012/03/18/2405118.html#_Toc319785463
[Link 1]: http://www.cppblog.com/flyinghearts/archive/2012/03/18/168267.html
[flyinghearts]: http://www.cnblogs.com/flyinghearts/
[-_-_ 2.5]: http://creativecommons.org/licenses/by-nc-sa/2.5/cn/