面试题精解之二： 字符串、数组（1）
本篇文章发表在下面三个博客中，如果出现排版问题，请移步到另一个博客。
http://www.cppblog.com/flyinghearts
http://www.cnblogs.com/flyinghearts
http://blog.csdn.net/flyinghearts
1 在一个字符串中找到第一个只出现一次的字符，如输入abac，则输出b。
2 输出字符串的所有组合，如"abc"输出a、b、c、ab、ac、bc、abc。
3 根据条件找出两个数。
4 求数组（或环状数组）的最大连续（或不连续）子序列和。
本题看似很简单，开个长度为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;
}
本题假定字符串中的所有字符都不重复。根据题意，如果字符串中有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);
}
① 数组中，除了两个数字出现奇数次外，其它数字都出现偶数次，找出这两个数字：
② 长度为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。）
对方法三的详细解释，可参考本人的文章《避免计算过程中出现溢出的一个技巧》。
//方法二
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小题。遇到这类题，首先想到的应该是动态规划思想。（下面的代码中，都假定所进行的有符号数算术运算不会发生溢出。可以通过改用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);
}