雁过无痕

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::

面试题精解之二: 字符串、数组(1

 

本篇文章发表在下面三个博客中,如果出现排版问题,请移步到另一个博客。

http://www.cppblog.com/flyinghearts

http://www.cnblogs.com/flyinghearts

http://blog.csdn.net/flyinghearts

 

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

2     输出字符串的所有组合,如"abc"输出abcabacbcabc

3     根据条件找出两个数。

4     求数组(或环状数组)的最大连续(或不连续)子序列和。

 

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

本题看似很简单,开个长度为256的表,对每个字符hash计数就可以了,但很多人写的代码都存在bug,可能会发生越界访问。这是C/C++语言上的一个陷阱,C/C++中的char有三种类型:charsigned charunsigned charchar类型的符号是由编译器指定的,一般是有符号的。在对字符进行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"输出abcabacbcabc

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

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

n不是太小时,递归法效率很差(栈调用次数约为2^n,尾递归优化后也有2^(n-1))。注意到本题的特点,可以构照一个长度为n01字符串(或二进制数)表示输出结果中最否包含某个字符,比如:"001"表示输出结果中不含字符ab,只含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的数组,由数字1n组成,其中数字a不出现,数字b出现两次,其它的数字恰好出现一次,在不修改原数组的情况下,找出数字a和数字b

 

       数组中,只有两个数字出现奇数次,其它数字都出现偶数次。假设这两数为ab

 

利用 异或的性质: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)。由于ab不相乘,因而c不为0,假设c的二进制表示中,第m位不为0。根据第m位是否为0,可以将原数组划分为两块,

显然,ab不可能分在同一块。由于各块中,只有ab是奇数次出现的,因而各块所有的数的异或值要么等于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;

}

 

       有三种解法:

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

 

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

    

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

 

方法一与方法二,在实现中必须计算 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位平台,两个无符号数ab的和是定义为:(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*k2*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*k8*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的大小。

//32CPU平台,长度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)表示数组arri个元素的最大不连续子序列和,对第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的元素不能同时取,则对编号为0n-2和编号为1n-1的两个子数组分别求最大不连续子序列和,较大的即为所求。具体实现上,可以先求编号为0n-1的具有最大和的不连续子序列,是否同时包含编号为0和编号为n-1的元素,若不同时包含的话,所得结果即为所求;若同时包含的话,需要再计算编号为1n-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); 

}

 

posted on 2012-03-18 21:28 flyinghearts 阅读(3651) 评论(2)  编辑 收藏 引用 所属分类: 面试题精解

评论

# re: 面试题精解之二: 字符串、数组(1)[未登录] 2012-05-20 00:59 galaxy
③ 数组的最大不连续子序列和(不连续子序列和的最大值)

这个问题不就是把数组内的正常加起来么??为什么要动态规划??  回复  更多评论
  

# re: 面试题精解之二: 字符串、数组(1) 2012-05-20 19:31 flyinghearts
@galaxy

所求序列中的任意两个数字,在原数组中是不相邻的。
  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理