温斯顿吴的个人博客 woojean.com

《编程之美》读书笔记

2017-04-05
编程

求二进制数中1的个数。

解法1：对于二进制操作，除以一个2，如果除的过程中有余，那么就表示当前位置有一个1。考虑利用整型数据除法的特点，通过相除和判断余数的值来分析。

int Count ( BYTE v )
{
  int num = 0;
  while(v)
  {
    if(v%2 == 1)
      num++;
    v = v/2;
  }
  return num;
}

解法2：对解法1进行改进，通过移位操作来实现除法。通过与00000001进行与操作来判断当前八位数字最后一位是否为1.

int Count ( BYTE v )
{
  int num = 0;
  while(v)
  {
    num += v & 0x01;
    v >>= 1;
  }
  return num;
}

解法3：在每次判断中仅与1来进行判断，将复杂度由二进制数的位数降低至二进制数中1的个数。v & (v-1)操作每次能消去二进制表示中最后一位1，利用这个技巧可以减少一定的循环次数。

int Count ( BYTE v )
{
  int num = 0;
  while(v)
  {
    v &= (v-1);
    num++;
  }
  return num;
}

解法4：使用分支操作（switch语句），针对8位数据，直接把0~255的情况都罗列出来，并使用分支操作，可以得到答案。不是好的方法。

int Count ( BYTE v )
{
  int num = 0;
  switch( v )
  {
    case 0x0:
      num = 0;
      break;
    case 0x1:
    case 0x2:
    // …
    case 0x80:
      num = 1;
      break;
    case 0x3:
    case 0x6:
    // …
    case 0xc0;
      num = 2;
      break;
    // …
  }
  return num;
}

解法5：查表法，典型的空间换时间算法，把0~255中1的个数直接存储在数组中，v作为数组的下标，countTable[v]就是v中1的个数。算法的时间复杂度仅为1.

int countTable[256] = {0,1,1,2,1,2,2,3,…7,6,7,7,8};

int Count ( BYTE v )
{
  //check parameter
  return countTable[v];
}

寻找发帖“水王”：由水王ID所发的帖子数超过了总帖子数的一半。

最直接的方法，先对所有ID排序，再统计各个ID出现的次数。如果某个ID出现次数超过总数的一半，那么就输出这个ID。这个算法的时间复杂度为O( N*logN + N ) . 如果ID列表已经是有序的，也可以不用扫描统计各个ID的出现次数。如果一个ID出现的次数超过总数N的一半，那么无论水王的ID是什么，这个有序的ID列表的第N/2项（从0开始编号）一定是这个ID。除去排序的时间复杂度后，处理的时间复杂度为O(1)。 上面的方法都需要先对ID列表进行排序，时间复杂度方面没有根本的改进。如果每次删除两个不同的ID，那么在剩下的ID列表中，水王ID出现的次数仍然超过总数的一半（即，哪怕每次拿一个其他ID来同归一个水王的ID，最终剩下的仍然是水王的ID，且只有水王的ID能够满足这种挑战）。可以通过不断重复这个过程，把ID列表中的ID总数降低。从而避免了排序这个耗时的步骤，总的时间复杂度也只有O( N )，且只需要常数的额外内存:

Type Find( Type* ID ,int N )
{
  Type candidate;
  int nTimes, i;
  for( i = nTimes = 0; i<N; i++)
  {
    if( nTimes == 0 )
      candidate=ID[i], nTimes=1;
    else
    {
      if(candidate == ID[i])
        nTimes++;
      else
        nTimes--;
    }
  }
  return candidate;
}

大致思想就是：假设每个ID都有可能是水王，那么在遍历时这个水王就要遇到一种挑战，可能自己的帖子数是会增加的，也可能是遇到挑战的，帖子数要减少的。这样遍历下来，只有水王的帖子增加的减去遇到挑战的帖子数会是大于0的。其他任何帖子假设为水王时都是禁不起挑战的。 步骤：

  1. 可以假设帖子的第一个ID是次数最大的，用candidate记录，次数用nTimes记录。
  2. 遍历下一个ID，如果跟candidate一样，nTimes++，否则，遇到一个挑战，则nTimes–，如果nTimes == 0，下一步就要重复第一步了。
  3. 遍历结束，nTimes>0的那个candidate就是水王ID，他是获胜者。 问题解决的关键在于水王ID超过了总数的一半这一特殊条件。

寻找最大的K个数

解法1：在元素数量不大的情况下，采用快排或者堆排序对所有元素排序，取前K个，时间复杂度为O( NlogN )+O( K )= O( NlogN ); 采用部分排序算法，如选择排序或交换排序，把N个数中的前K个数排序出来，复杂度为O( N*K ); 具体选择取决于K与logN的大小。 解法2：按照快速排序的思路，假设N个数存储在数组S中，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中的元素小于X。这时有两种可能：

  1. Sa中的元素的个数小于K，Sa中所有的数和Sb中最大的K-|Sa|（|Sa|指Sa中元素的个数）个元素就是数组S中最大的K个数。
  2. Sa中元素的个数大于或等于K，则需要返回Sa中最大的K个元素。 如此递归。平均时间复杂度为O( N*logK )。伪代码如下： ```c Kbig( S, K ) if ( k <= 0 ): return [] if ( S. length <= K ): return S ( Sa,Sb ) = Partition( S ) return Kbig( Sa, K ).Append( Kbig( Sb, K - Sa.length ))

Partition(S): Sa=[]; Sb=[]; Swap( s[1], S[random() % S. length] ) p=S[1]

for i in [2: S.length]: S[i] > p ? Sa.Append( S[i] ):Sb.Append( S[i] )

Sa.length < Sb.length ? Sa.Append(p):Sb.Append(p) return (Sa,Sb)


解法3：寻找N个数中最大的K个数，本质上就是寻找最大的K个数中最小的那个，也就是第K大的数。可以`使用二分搜索的策略来寻找N个数中的第K大的数。然后，对于一个给定的数p，可以在O（N）的时间复杂度内找出所有不小于p的数`。
	假如N个数中最大的数为Vmax，最小的数为Vmin，那么这N个数中的第K大数一定在区间[Vmin, Vmax]之间。那么，可以在这个区间内二分搜索N个数中的第K大数p。伪代码如下：

```c
while(Vmax – Vmin > delta)
{
  Vmid = Vmin + (Vmax - Vmin) * 0.5;
  if( f(arr, N, Vmid) >= K)
    Vmin = Vmid;
  else
    Vmax = Vmid;
}

伪代码中f（arr, N, Vmid）返回数组arr[0, …, N-1]中大于等于Vmid的数的个数。 上述伪代码中，delta的取值要比所有N个数中的任意两个不相等的元素差值之最小值小。如果所有元素都是整数，delta可以取值0.5。循环运行之后，得到一个区间（Vmin, Vmax），这个区间仅包含一个元素（或者多个相等的元素）。这个元素就是第K大的元素。整个算法的时间复杂度为O（N * log2（|Vmax - Vmin| /delta））。由于delta的取值要比所有N个数中的任意两个不相等的元素差值之最小值小，因此时间复杂度跟数据分布相关。在数据分布平均的情况下，时间复杂度为O（N * log2（N））。 解法4：当N非常大的情况下，不能一次性装入内存操作。设N > K，前K个数中的最大K个数是一个退化的情况，所有K个数就是最大的K个数。考虑第K+1个数X。如果X比最大的K个数中的最小的数Y小，那么最大的K个数还是保持不变。如果X比Y大，那么最大的K个数应该去掉Y，而包含X。如果用一个数组来存储最大的K个数，每新加入一个数X，就扫描一遍数组，得到数组中最小的数Y。用X替代Y，或者保持原数组不变。这样的方法，所耗费的时间为O（N * K）。 进一步，可以用容量为K的最小堆来存储最大的K个数。最小堆的堆顶元素就是最大K个数中最小的一个。每次新考虑一个数X，如果X比堆顶的元素Y小，则不需要改变原来的堆，因为这个元素比最大的K个数小。如果X比堆顶元素大，那么用X替换堆顶的元素Y。在X替换堆顶元素Y之后，X可能破坏最小堆的结构（每个结点都比它的父亲结点大），需要更新堆来维持堆的性质。更新过程花费的时间复杂度为O（log2K）。 解法5：可以通过改进计数排序、基数排序等来得到一个更高效的算法。但算法的适用范围会受到一定的限制。如果所有N个数都是正整数，且它们的取值范围不太大，可以考虑申请空间，记录每个整数出现的次数，然后再从大到小取最大的K个。比如，所有整数都在（0, MAXN）区间中的话，利用一个数组count[MAXN]来记录每个整数出现的个数（count[i]表示整数i在所有整数中出现的个数）。我们只需要扫描一遍就可以得到count数组。然后，寻找第K大的元素：

for( sumCount = 0, v = MAXN – 1;  v >= 0;  v-- )
{
  sumCount += count[v];
  if( sumCount >= K )
    break;
}
return v;

极端情况下，如果N个整数各不相同，我们甚至只需要一个bit来存储这个整数是否存在。 实际情况下，并不一定能保证所有元素都是正整数，且取值范围不太大。上面的方法仍然可以推广适用。如果N个数中最大的数为Vmax，最小的数为Vmin，我们可以把这个区间[Vmin, Vmax]分成M块，每个小区间的跨度为d =（Vmax – Vmin）/M，即 [Vmin, Vmin+d], [Vmin + d, Vmin + 2d],……然后，扫描一遍所有元素，统计各个小区间中的元素个数，跟上面方法类似地，我们可以知道第K大的元素在哪一个小区间。然后，再对那个小区间，继续进行分块处理。这个方法介于解法三和类计数排序方法之间，不能保证线性。跟解法三类似地，时间复杂度为O（（N+M）* log2M（|Vmax - Vmin|/delta））。遍历文件的次数为2 * log2M（|Vmax - Vmin|/delta）。当然，我们需要找一个尽量大的M，但M取值要受内存限制。

补：寻找第K大的数。

求最大公约数。考虑两个正整数都很大的情况。

欧几里得辗转相除法求最大公约数：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。 如：f(42,30) = f(30,12) = f(12,18) = f(12,6) = f(6,6) = f(6,0) 即：f(x,y) = f(y, x%y) (x >= y > 0) 或f(x,y)=f(x-y, y). 解法1：直接用代码来实现辗转相除法：

int gcd(int x, int y)
{
  return (!y)?x:gcd(y, x%y);
}

解法2：解法1中用到%运算，其中包含除运算，这对于大整数而言将成为算法效率的瓶颈。采用公式f(x,y)=f(x-y, y)，就可以不再需要进行大整数的取模运算，而转换成简单得多的大整数的减法。

BigInt gcd(BigInt x, BigInt y)
{
  if( x < y)
    return gcd(y, x);
  if(y == 0)
    return x;
  else
    return gcd( x-y, y);
}

解法3：结合上两种算法，并采用移位操作。

补：大整数的实现。

寻找数组中的最大值和最小值

解法1：遍历两次，分别求出最大值、最小值。需要比较2N次。 解法2：按顺序将数组中相邻的两个元素看成一组，遍历数组，调整每一组中两个元素的顺序，使大的数在偶数位上，小的数在奇数位上。然后分别从奇数位、偶数位上求出最大最小值，总的比较次数为1.5N次。 解法3：不破坏原数组，仍然将数组每相邻两位看成一组，定义两个变量min、max，遍历数组，相邻两位比较，然后得到的大者与max比较，小者与min比较。总的比较次数仍为1.5N。 解法4：采用分治算法，分别求出前后N/2个数的min和max，然后取较小的min及较大的max。但是总的比较次数仍为1.5N。

快速找出一个数组中的两个数字，其和等于给定值。

解法1：穷举法，时间复杂度O(N); 解法2：变通思路，对数组中的每个数字arr[i]都判别sum-arr[i]在不在数组中。这样就变通为一个查找算法。将数组排序，需要时间O(NlogN)。对于每个arr[i]用二分法查找sum-arr[i]的时间复杂度都为O(logN)，总计NO(logN)+ O(NlogN)= O(NlogN)。 当然也可以用hash的方法简化查找，但是空间效率加大了。 解法3：首先对数组进行排序，时间复杂度为O(NlogN)。 然后令i=0，j=n-1，看arr[i]+arr[j]是否等于sum，如果是则结束，如果小于sum，则i=i+1;如果大于sum，则j=j-1。这样只需要在排好序的数组上遍历一次，就可以得到最后的结果，该步操作的时间复杂度为O(N)。两步加起来的时间复杂度为O(NlogN)。 查找伪码：

for( i=0,j=n-1; i<j; )
  if(arr[i] + arr[j] == sum)
    return (i , j);
  else if( arr[i] + arr[j] < sum)
    i++;
  else
    j--;
return (-1,-1);

求数组的子数组之和的最大值。

解法1：分治法，将所给数组A[0],…A[n-1]分为长度相等的两段数组A[0],…,A[n/2-1]和A[n/2],…,A[n-1],分别求出这两段数组各自的最大子段和，则原数组的最大子段和为以下三种情况的最大值：

  1. A[0],…A[n-1]的最大子段和与A[0],…,A[n/2-1]的最大子段和相同；
  2. A[0],…A[n-1]的最大子段和与A[n/2],…,A[n-1]的最大子段和相同；
  3. A[0],…A[n-1]的最大子段跨过其中间两个元素A[n/2-1]和A[n/2]。 第1和第2两种情况是问题规模减半的相同子问题，可以通过递归求得。 第3种情况只要找到以A[n/2-1]结尾的和最大的一段数组之和S1，以及以A[n/2]开始和最大的一段数组之和S2，那么第3种情况的最大值为S1+S2,只要对原数组进行一次遍历即可。 分治法使得问题被分解为两个问题规模减半的子问题再加上一次遍历算法。总的时间复杂度为O(N*logN)。

解法2：动态规划法，考虑数组的第一个元素A[0]，以及最大的一段数组A[i],…,A[j]跟A[0]之间的关系，有以下几种情况：

  1. 当0=i=j时，元素A[0]本身构成和最大的一段；
  2. 当0=i<j时，和最大的一段以A[0]开始；
  3. 当0<i时，元素A[0]跟和最大的一段没有关系。 这样可以将一个大问题(N)转化为一个较小的问题(N-1)。假设已经知道A[1],…,A[N-1]中和最大的一段数组之和为All[1]，并且已经知道A[1],…,A[N-1]中包含A[1]的和最大的一段数组为Start[1]。则由以上三种分析的情况可看出A[0],…,A[N-1]中问题的解All[0]是三种情况的最大值max{A[0],A[0]+Start[1],All[1]}。通过这样的分析可以看出这个问题无后效性，可以使用动态规划的方法解决。代码如下： 
    int MaxSum(int* A, int n)
{
  Start[n-1] = A[n-1];
  All[n-1] = A[n-1];
  for(i = n-2; i>=0; i--) //从数组末尾往前遍历，直到数组首
  {
 Start[i] = max( A[i], A[i]+Start[i+1]);
 All[i] = max(Start[i],All[i+1]);
  }
  return All[0]; //遍历完数组，All[0]中存放结果
}

    时间复杂度为O(N); 改进： Start[i] = max( A[i], A[i]+Start[i+1]); All[i] = max(Start[i],All[i+1]); 如果Start[i+1]<0，则Start[i]=A[i]。并且在这两个递推式中，其实都只需用两个变量就可以了。Start[k+1]只有在计算Start[k]时使用，而All[k+1]也只有在计算All[k]时使用。所以改进程序只需O(1)的空间就足够了：

    int MaxSum(int* A, int n)
{
  nStart = A[n-1];
  nAll= A[n-1];
  for(i = n-2; i>=0; i--) 
  {
 nStart = max( A[i], A[i]+nStart);
 nAll = max(nStart,nAll);
  }
  return nAll; 
}

数组循环移位：把一个含有N个元素的数组循环右移K位，要求时间复杂度为O(N),且只允许使用两个附加变量。

解法1：循环右移K位之后的情形跟右移k=K%N位之后的情形一样：

RightShift(int* arr, int N, int K)
{
  K %=N;
  while(K--)
  {
    int t=arr[N-1];
    for(int i = N-1; i>0; i--)
      arr[i] = arr[i-1];
    arr[o] = t;
  }
}

时间复杂度为O(N^2). 解法2：假设原数组序列为abcd1234，要求变换成的数组序列为1234abcd，即循环右移了4位。比较之后可以看到其中有两段的顺序是不变的，即1234和abcd，把这两段看成两个整体。右移K位的过程就是把数组的两部分交换一下。变换的过程通过以下步骤完成：

  1. 逆序排列abcd：abcd1234 -> dcba1234;
  2. 逆序排列1234：abcd1234 –> dcba4321;
  3. 全部逆序：abcd1234 -> 1234abcd。 代码： ```c Reverse(int* arr, int b, int e) { for(; b<e; b++,e–) { int temp = arr[e]; arr[e] = arr[b]; arr[b] = temp; } }

RightShift(int* arr, int N, int k) { K %= N; Reverse(arr, 0, N – K – 1); Reverse(arr, N – K, N – 1); Reverse(arr, 0, N – 1); }


## 给定两个字符串s1和s2，要求判定s2是否能够被s1做循环移位得到的字符串包含。例如，给定s1=AABCD和s2=CDAA，返回true；给定s1=ABCD和s2=ACBD,返回false。
解法1：穷举法
```c
char src[] = ”AABBCD”;
char des[] = ”CDAA”;
int len = strlen(src);
for(int i=0;  i<len;  i++)
{
  char tempchar = src[0];
  for(int j=0;  j<len-1;  j++)
    src[j] = src[j+1];
  
  src[len-1] = tempchar;
  if( strstr(str,des)==0 )
    return true;
}
return false;

解法2：空间换时间，对循环移位之后的结果进行分析。假设s1=ABCD，s1循环移位的结果如下： ABCD -> BCDA -> CDAB -> DABC ->ABCD; 若保留前面移走的数据，则可发现如下规律： ABCD -> ABCDA -> ABCDAB -> ABCDABC ->ABCDABCD。 可见对s1做循环移位所得到的字符串都将是字符串s1s1的子字符串。如果s2可以由循环移位得到，那么s2一定在s1s1上。 由此，将问题转换成考察s2是否在s1s1上，可通过调用一次strstr函数得到结果。

计算字符串的相似度。

分析：两个字符串的距离肯定不超过它们的长度之和。 考虑如何才能把这个问题转化成规模较小的同样的问题： 如果两个串A和B的第一个字符是相同的，则只要计算A[2，…lenA]和B[2，…lenB]的距离就可以了。但是如果两个串的第一个字符不相同，那么进行如下操作：

  1. 删除A串的第一个字符，然后计算A[2，…lenA]和B[1，…lenB]的距离；
  2. 删除B串的第一个字符，然后计算A[1，…lenA]和B[2，…lenB]的距离；
  3. 修改A串的第一个字符为B串的第一个字符，然后计算A[2，…lenA]和B[2，…lenB]的距离；
  4. 修改B串的第一个字符为A串的第一个字符，然后计算A[2，…lenA]和B[2，…lenB]的距离；
  5. 增加B串的第一个字符到A串的第一个字符之前，然后计算A[1，…lenA]和B[2，…lenB]的距离；
  6. 增加A串的第一个字符到B串的第一个字符之前，然后计算A[2，…lenA]和B[1，…lenB]的距离；

由题意知，并不在乎两个字符串变得相等之后的字符串是怎样的，所以可以将上面的6个操作合并为：

  1. 一步操作之后，再将A[2，…lenA]和B[1，…lenB]变成相同的字符串；
  2. 一步操作之后，再将A[1，…lenA]和B[2，…lenB]变成相同的字符串；
  3. 一步操作之后，再将A[2，…lenA]和B[2，…lenB]变成相同的字符串； 实现代码： 
    int CalculateStringDistance( string strA, int pABegin, int pAEnd, string strB, int pBBegin, int pBEnd)
{
  if(pABegin > pAEnd)
  {
 if( pBBegin > pBEnd)
   return 0;
 else
   return pBEnd – pBBegin +1;
 }

 if(pBBegin > pBEnd)
 {
   if(pABegin > pAEnd)
     return 0;
   else
     return pAEnd – pABegin + 1;
 }
		 
 if( strA[pABegin] == strB[pBBegin])
   return CalculateStringDistance( strA, pABegin +1, pAEnd, strB, pBBegin +1, pBEnd);
 else
 {
   int t1 = CalculateStringDistance( strA, pABegin, pAEnd, strB, pBBegin +1, pBEnd);
   int t2 = CalculateStringDistance( strA, pABegin +1, pAEnd, strB, pBBegin, pBEnd);
   int t3 = CalculateStringDistance( strA, pABegin +1, pAEnd, strB, pBBegin +1, pBEnd);
   return minValue( t1, t2, t3) + 1;
 }
}
}

    从无头单链表中删除节点（不是第一个，也不是最后一个节点）。

    假设给定指针为pCurrent，Node* pNext = pCurrent->Next。 假设pCurrent指向当前节点为B，B的前一个节点为A，后一个节点为C。因为单链表没有头指针，因此无法追溯到A，假设直接删除B，则无法将A和C相连。 解法：由给定条件可以安全的删除节点C，然后用C中的数据项替换B中的数据项，代码如下：

    pCurrent -> Next = pNext -> Next;
pCurrent -> Data = pNext -> Data;
delete pNext;

设计队列容器的数据结构，使得返回最大元素的操作时间复杂度尽可能的低。

解法1：用传统方式来实现队列，采用一个数组或链表来存储队列的元素，利用两个指针分别指向队尾和队首。如果采用这种方法，那么取最大值的操作需要遍历队列的所有元素。时间复杂度为O(N)； 解法2：考虑用最大堆来维护队列中的元素。堆中每个元素都有指向它的后续元素的指针。这样，取最大值操作的时间复杂度为O(1)，而入队和出队操作的时间复杂度为O( logN )。 解法3：对于栈来讲，Push和Pop操作都是在栈顶完成的，所以很容易维护栈中的最大值，它的时间复杂度为O(1),实现代码如下：

class stack
{
  public:
    stack()
    {
      stackTop = -1;
      maxStackItemIndex = -1;
    }

    void Push( Type x)
    {
      stackTop++;
      if( stackTop >= MAXN ) // 溢出
        ;
      else
      {
        stackItem[stackTop] = x;
        if( x > Max() ) // 当前插入值为最大值
        {
          link2NextMaxItem[stackTop] = maxStackItemIndex; // 之前的最大值成为第二大的值，即当前值（最大值）的下一个最大值
          maxStackItemIndex = stackTop; // 最大值坐标指向当前值
        }
        else
          link2NextMaxItem[stackTop] = -1;
      }	
    }

    Type Pop()
    {
      Type ret;
      if( stackTop < 0 )
        ThrowException(); // 没有元素了
      else
      {
        ret = stackItem[ stackTop ];
        if( stackTop == maxStackItemIndex ) // 当前出栈的为最大值
          maxStackItemIndex = link2NextMaxItem[stackTop];	// 修改最大值坐标
        stackTop--;
      }
      return ret;
    }
		
    Type Max()
    {
      if( maxStackItemIndex >= 0 )
        return stackItem[ maxStackItemIndex];
      else 
        return –INF;
    }
		
  private:
    Type stackItem[MAXN];
    int stackTop;
    int link2NextMaxItem[MAXN]; // 维护一个最大值序列
    int maxStackItemIndex;
}

如果能够用栈有效地实现队列，而栈的Max操作又很容易实现，那么队列的Max操作也就能有效地完成了。考虑使用两个栈A跟B来实现队列。

class Queue
{
public:
  Type MaxValue( Type x, Type y)
  {
    if( x > y )
      return x;
    else
      return y;
  }

  Type Queue::Max()
  {
    return MaxValue( stackA.Max(), stackB.Max() );
  }

  EnQueue( v )
  {
    stackB.push( v );
  }
	
  Type DeQueue()
  {
    if( stackA.empty() )
    {
      while( !stackB.empty() )
        stackA.push( stackB.pop() )
    }
    return stackA.pop();
  }

  private:
	stack stackA;
	stack stackB;
}

从每个元素的角度来看，它被移动的次数最多可能有3次，这3次分别是：从B栈进入、当A栈为空时从B栈弹出并压入A栈、从A栈被弹出。相当于入队经过一次操作，出队经过两次操作。所以这种方法的平均时间复杂度是线性的。

上一篇 《算法》读书笔记

下一篇 《计算机网络》读书笔记

文章目录