面试笔试题目三结义（BS）

烟雨

1 输入两个整数，要求输出这两个数的乘积。输入的数字可能超过计算机内整形数据的存储范围：
  (算法提示) 输入 string a, string b；计算string c=a*b; 返回 c;
std::string Multiply(std::string a, std::string b)
{
        char* startA = a.data();
        char* startB = b.data();
        int lengthA = a.size();
        int lengthB = b.size();
        int tenOver = 0;
        std::vector<int> resultVector;
        resultVector.resize(lengthA * lengthB + 1);
        for(int i = 0;i < lengthA;++i)
        {
                for(int j = 0;j < lengthB;++j)
                {
                        int muitiplyA = std::atoi(*(startA + lengthA - i - 1));
                        int muitiplyB = std::atoi(*(startB + lengthB - j - 1));
                        ini Result = muitiplyA*muitiplyB;
                        resultVector[i * j] += (Result % 10) + tenOver;
                        tenOver = Result / 10;
                }
        }
        std::vector<char> result;
        result.resize(resultVector.size());
        for(int k = 0; k <  resultVector.size(); ++k)
        {
                if(resultVector[k] > 9)
                {
                        resultVector[k+1] += 1;       
                        resultVector[k] = 9;       
                }
                resultVector[k] += 48;       
        }
        for(int l = 0;l < resultVector.size(); ++l)
      ｛
                result[l] = (char)resultVector[resultVector.size() - l];
       ｝
        return std::string(result.begin(),result.begin());
}

2 不用第三个变量实现两个整形变量的交换
void (int* a , int* b)
{
        *a = *a + *b;
            *b = *a - *b;
             *a = *a - *b;
}

3 爸爸,妈妈,妹妹,小强,至少两个人同一生肖的概率是多少
答：四个人的生肖都有十二种可能，至少两个同意生肖的概率也就是1-没人同生肖概率 = 1 - 1-（12*11*10*9）/（12*12*12*12）=0.427；

4 一个背包刚好装S克东西，有N个物体 重量分别是：W1 W2 W3….WN  请编程 用非递归的方法 得出一组解
bool backInsert(int w[n])
{
        int sum = 0;
        std::sort(w.begin();w.end();[=](int a,int b){return a < b});
        //假设传入参数为N个物体重量的数组
        for(int i < 0; i < n ; ++i)
        {
                sum += W[n - i];
                if(sum > S)
                {
                        int k = n - i
                        while(k < n)
                        {       
                                sum -= W[k];
                                for(int k = i ; k < n ;++k)
                                {
                                if(sum + W[k] == S)
                                return true;
                                }
                                ++k
                        }

                }
        }
        return false;
}

5 写出float x 与“零值”比较的if语句
答：if(x == 0.0f)

6 不能做switch()的参数类型是？
答：除了整型，枚举，字符其他应该都不行。

7 请列举4种排序方法 并描述其实现原理 算法复杂度(举出实例 )
冒泡排序：从待排序的数组从头开始一次和后面一个比较，将大的放后面小的放前面。这样一个循环最大的就是最后，这样依次循环.
平均复杂度为O（n2）;
直接选择排序:第一次循环从待排序数组中选择最小的放在头部，后面依次循环从剩下的中选最小的放在第i个，直到循环N次；
平均复杂度为0（n2）;
快速排序：在待排序的数组中选一个任意基准，小的在左大的在右，再又对左右两部分递归；
平均复杂度为0（logn）;
直接插入排序:把n待排序的数组看成为一个有序表和一个无序表，每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
平均复杂度为O（n2）;