腾讯2012年4月笔试题附加题
腾讯 笔试
问题描述：两个数组a[N]，b[N]，其中A[N]的各个元素值已知，现给b[i]赋值，b[i] = a[0]*a[1]*a[2]…*a[N-1]/a[i]；
要求：
1.不准用除法运算
2.除了循环计数值，a[N],b[N]外，不准再用其他任何变量（包括局部变量，全局变量等）
3.满足时间复杂度O（n），空间复杂度O（1）
谈谈自己的解题思路吧，拿到这道题的时候，我首先注意到题目的3个要求：1.不准用除法2.不允许使用额外变量；3.o(n)的时间复杂度。由于不允许使用额外变量，所以我想到应该是在b[n]上做文章，结合不能用除法，我想到A^A=0,于是又A^A&1 = 1。再乘以剩下的各个乘子就得到b[i]。
本来以为到这里就结束了，后来发现这个方法有问题，因为这样只解决了不用除法做/a[i]的问
题，没有解决如何乘上除了a[i]以外的数的问题。继续观察b[i]的结构发现，b[i]可以写成BaBb,其中Ba=a[0]*a[1]…*a[i-1],Bb=a[i+1]*a[i+2]…*a[n-1]，自然的就联想到了分别从头和尾部遍历a[n]计算Ba,Bb的方法，话不多说，代码如下：
1 void foo(int a[],int b[],int n){
2        int i;
3        b[0] = 1;//用b[0]做辅助变量;
4        for(i = 1; i < n; i++)
5        {
6            b[0] *= a[i - 1];//从前往后乘得到Ba;
7            b[i] = b[0];
8        }
9        b[0] = 1;
10        for(i = n-2; i > 0; i–)
11        {
12            b[0] *= a[i + 1];//从后往前乘得到Bb;
13            b[i] *= b[0];
14        }
15        b[0] *= a[1];//不能忘记算出b[0];
16        for(i = 0; i < n; i++)
17        {
18            cout << b[i] << ” “;
19        }
由这道题联想到两类题型：
一.对运算方法有限制的题。
例如 题目1：不用乘法或者加法将一个数N增加8/7倍.
思  路：考虑到8为2的倍数，对一个数乘以/除以2就是对其进行左/右移，于是有
增加 8倍：n<<3; 增加7倍(n<<3)-n;
题目2：求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句。
思  路：1+2+…+n=(n^2+n)/2,由上题知道n/2可以通过移位运算获得，只要想办法求n^2。模拟手算乘法的思路，不难得出结果。
#define T(X,Y,i)((Y & 1<<i)) && X+=(Y<<i)//(Y & 1<<i)取出n2进制中为1的那一位，分别乘以N并相加，即得到n^2
int foo(int n)
{
int i,r=n;
T(r,n,0);T(r,n,1);T(r,n,2);T(r,n,3);…T(r,n,31);
return r>>1;
}
这类题的典型思路是，在不能使用四则运算符时，考虑数在计算机中进行运算的方式，可以使用移位，与，或，异或等等位运算符得到结果。
二：可以对所求或所处理内容分块考虑的问题。
例如：
题目：定义字符串的做旋转操作：把字符串前面的若干个字符移动到字符串尾部。
如把字符串abcdef做旋转2位得到字符串cdefab。
实现字符串做旋转的函数，要求对长度为n的字符串操作的时间复杂度为o(n)，空间复杂度为o(1).
思路：不妨令S=abcdef，于是根据题目要求可以将S划分为Sa=ab,Sb=cdef;题目转化为：将S=SaSb,中的SaSb即交换位置，是不是瞬间简单了很多。代码如下：
char* LeftRotateString(char* pStr, unsigned int n)
{
if(pStr != NULL)
{
int nLength = static_cast<int>(strlen(pStr));
if(nLength > 0 && n > 0 && n < nLength)
{
char* pFirstStart = pStr;
char* pFirstEnd = pStr + n – 1;
char* pSecondStart = pStr + n;
char* pSecondEnd = pStr + nLength – 1;
// reverse  Sa
ReverseString(pFirstStart, pFirstEnd);
// reverse Sb
ReverseString(pSecondStart, pSecondEnd);
// reverse S
ReverseString(pFirstStart, pSecondEnd);
}
}
return pStr;
}
void ReverseString(char* pStart, char* pEnd)
{
if(pStart != NULL && pEnd != NULL)
{
while(pStart <= pEnd)
{
char temp = *pStart;
*pStart = *pEnd;
*pEnd = temp;
pStart ++;
pEnd –;
}
}
}