好未来2019秋招笔试题-测试开发

1、字节变量中1的个数

对于一个字节（8bit）的变量，求其二进制表示中“1”的个数。
输入：10100001
输出：3
可参考，https://blog.csdn.net/m0_37925202/article/details/80087992，给出了四种解法。
推荐下面的写法：

int Count(unsigned char byt)
{
    int num=0;
    while (byt)
    {
        byt = byt & (byt-1);
        num++;
    }
    return num;
}

把一个整数减去1，再和原来的数做与运算，将把该整数最右边的1变成0。二进制中有多少个1，将会进行多少次这样的操作。

2、求一维数组的最长递增子序列

输入：1 -1 2 -3 4 -5 6 -7
输出：1 2 4 6

3、给定字符串s1,s2, 判断s2能否通过s1循环移位得到

输入：
AABCD
DAAB
输出：
true
假设字符串s1=AABCD,s2=CDAA,判断s2是否可以通过S1的循环移位得到字符串包含。
如 s1移两位： 1.ABCDA->2.BCDAA 则此时包含了 S2=”CDAA”

解题思路：
分解s1的循环移位得到：
AABCD,ABCDA,BCDAA,CDAAB,…..
如果我们将前面移走的字符串保留下来，则有：
AABCD,AABCDA,AABCDAA,AABCDAAB,AABCDAABC,AABCDAABCD

这里，我们可以发现，实际对s1的循环移位得到的字符串实际为s1s1。
那么我们判断s2是否可以通过s1循环移位得到包含，则只需要判断s1s1中是否含有s2即可以。
用提高空间复杂度来换取时间复杂度的减低的目的。

bool rotstr(string src,string des)
{
    string tmp = src;
    src = src + tmp;
    if(strstr(src.c_str(),des.c_str()) == NULL)
    {
        return false;   
    }
    return true;

}

int main()
{
    string src="AABBCD";
    string des="DAAB";
    if(rotstr(src,des))
        cout<<"true"<<endl;
    else
        cout<<"false "<<endl;
    return 0;
}

函数名: strstr
　 包含文件：string.h　　
　 函数原型：extern char *strstr(char *str1, char *str2);
　功能：找出str2字符串在str1字符串中第一次出现的位置（不包括str2的串结束符）。
　返回值：返回该位置的指针，如找不到，返回空指针。
其参数是传统的char *型字符串，string型数据类型是不能作为其参数的。但可以通过string成员函数string::c_str()转换成char*类型。

参考：https://blog.csdn.net/themagickeyjianan/article/details/9340005

4、一维数组子数组的最大和

一维数组有多个子数组，求这些子数组之和的最大值。
输入：1 -2 3 5 -3 2
输出：8

int FindMax(int a[], int n)
{
    if(a == NULL || n <= 0)
        return -1000; //约定返回此值时，输入是无效的
    int sum = 0;
    int max = 0;
    for(int i=0; i<n; i++)
    {
        if(sum <= 0)
            sum = a[i];
        else
            sum += a[i];
        if(sum > max)
            max = sum;
    }
    return max;
}

详见：https://blog.csdn.net/u014259820/article/details/79628758
扩展：https://blog.csdn.net/u010585135/article/details/42431943

5、给定二叉树的前序序列和中序序列，重建二叉树

ps：几乎都是编程之美中的原题啊，剑指offer中也有，还是要多刷题的^_^。