1 在一个字符串中找到第一个只出现一次的字符，如输入abac，则输出b。
2 输出字符串的所有组合，如"abc"输出a、b、c、ab、ac、bc、abc。
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。）
对方法三的详细解释，可参考本人的文章《避免计算过程中出现溢出的一个技巧》。
//方法二
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