编程之美--结构之法

 1 给定字符串s1和s2,要求判定s2是否能够被s1做循环移位得到的字符串包含。例如，给定s1=AABCD和s2=CDAA,返回true;给定s1=ABCD,s2=ACBD,返回false;
解法一：这类题目最简单的做法就是将s1做循环移位，每移位一次就做一下比较，但是这样当字符串的长度很长时，效率会很低。
解法二：以s1=ABC为例，我们对s1进行一次循环移位之后，有以下过程：
ABC-》CAB-》BCA-》ABC，如果我们保留每次移位后的前缀，再把它加到s1那里就有，s1s1=ＡＢＣＡＢＣ，可以看出，其实ｓ１循环之后的结果都是ｓ１ｓ１的字串，那么问题就变成了ｓ２是否是ｓ１ｓ１的字串，这是典型的用空间来换时间的方法。
２　从无头单链表中删除节点。
解法，注意到链表的节点中没有前趋节点的信息，只有后继节点的信息，又不是一个循环节点，看似是无法删除节点而保证链表不截断成两半的。但是，细心想一下，我们无法得知前驱节点的信息，但是我们可以知道后继节点的信息，那么我们可以删除这个后继的节点，然后将这个后继节点的信息填充到我们要删除的节点那里，可以说，这是一种变相的删除了。
３　电话号码对应的英语单词
　电话的号码盘一般可以用于输入字母。如用２可以输入Ａ，Ｂ，Ｃ，用３可以输入Ｄ，Ｅ，Ｆ等，请你罗列出这些号码盘所能代表的字母集合。
其实这个问题就是一个简单的循环遍历过程，我们其实可以用一个二维数组来表示０－９这九个数字所代表的字母，如下所示：
char c[10][10]={
      "abc",
       "def"
......
}
定义一个数组来表示每个数字所能代表的字符总数：
int total[10]= {....};
一个用来记录电话位数的数组
int number[TelLength];
一个用来记录对应字符位置的数组
int answer[TelLength]，
对应代码如下
while(true){
  
   for(int i = 0;i < TelLength-1;i++){
         print(c[number[i],answer[i]])
   }
   int k = TelLength - 1;
   while(k>0){
     if(answer[k] < total[number[k]] - 1){
              answer[k] ++;
              break;

     }else{
           answer[k] = 0;k--;
   }
   }
if(k<0)
break;
}

4 假设有这样一个拥有三个操作队列：
 一 EnQueue(v):将v加入队列中
 二 DeQueue:使队列中的队首元素删除并返回此元素
 三 MaxElement:返回队列中的最大元素
思路：这里介绍两种解决的方法
第一种：就是用传统的队列，用两个指针分别指向队列的队首和队尾，然后找最大的元素的过程，实际上就是遍历整个队列的过程，时间复杂度为O（n）
第二种：其实可以用一个堆来存储这些数据，构造一个大顶堆，那么其实取最大值的的时间复杂度便变成了O（1），每次入队和出队的时间复杂度变成了O（logn）;
5 二分法找错
int bisearch(char** arr,int b,int e,char *v)
{
   int minIndex = b,maxIndex = e,midIndex;
  //这里要特别注意循环结束的条件，如果查找个数是偶数，那么结束的条件是minIndex = maxIndex
  //如果查找个数是奇数，minIndex == maxIndex - 1
   while(minIndex < maxIndex - 1){
       //这里本来可以可以写成（maxIndex+minIndex）/2,但是为了避免可以出现的溢出，所以先减后加
       midMax = minIndex;
        }else {
        //这里并没有加一或减一
        midMax = maxIndex;
        }
    }
if(arr[midIndex] == v){
return midMax;
}else if(arr[maxIndex] == v){
return maxIndex;
}else {
return -1;
}


}