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

 

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

 

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

　　

  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 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); 

}