好未来2019秋招筆試験問題-テスト開発

1、バイト変数のうち1の個数
1バイト(8 bit)の変数について、そのバイナリ表現の「1」の個数を求める.入力:10100001出力:3参照可能、https://blog.csdn.net/m0_37925202/article/details/800879924つの解法が与えられた.以下の書き方をお勧めします.

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

1つの整数から1を減算し、元の数と演算すると、その整数の右端の1が0になります.バイナリに1が何個あるか、このような操作が何回行われるか.
2、一次元配列の最長増分子シーケンスを求める
入力:1-12-3 4-56-7出力:1 2 4
3、与えられた文字列s 1,s 2は、s 2がs 1サイクルシフトによって得られるか否かを判断する
入力:AABCD DAAB出力:trueは文字列s 1=AABCD,s 2=CDAAを仮定し,s 2がS 1のループシフトで文字列を含むことができるか否かを判断する.s 1が2桁移動するように:1.ABCDA->2.BCDAAはこのときS 2="CDAA"を含む
解題構想:分解s 1の循環シフトを得る:AABCD,ABCDA,BCDAA,CDAAB,…前に移動した文字列を残すと、AABCD、AABCDA、AABCDAA、AABCDAAB、AABCDAABC、AABCDAABCDがあります.
ここで,実際にs 1のループシフトに対して得られた文字列は実際にs 1 s 1であることが分かった.では、s 2がs 1サイクルシフトによって含まれるか否かを判断するには、s 1 s 1にs 2が含まれているか否かを判断するだけでよい.空間的複雑度を高めることで時間的複雑度の低減の目的を取り替える.

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"<else
        cout<<"false "<return 0;
}

関数名:strstrに含まれるファイル:string.h関数プロトタイプ:extern char*strstrstr(char*str 1,char*str 2);機能:str 1文字列の中でstr 2文字列が最初に出現した位置(str 2の列終端子を除く)を探し出す.戻り値:その位置を返すポインタ、見つからない場合は空のポインタを返す.そのパラメータは従来のchar*型文字列であり、string型データ型はそのパラメータとして使用できない.ただしstringメンバー関数string::c_str()char*タイプに変換します.
参照先:https://blog.csdn.net/themagickeyjianan/article/details/9340005
4、一次元配列のサブ配列の最大和
1次元配列には複数のサブ配列があり、これらのサブ配列の和の最大値を求めます.入力: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; iif(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にもありますから、もっと問題をつけましょう^^.