C/C++校招笔试面接经典题目まとめ8

タイトル72:以下のプログラムの時間複雑度は(そのうちm>1,e>0)()

x = m;
y = 1;
while （x - y > e）
{
x = (x + y) / 2;
    y = m / x;
}
print(x);

A:log m B:mの平方C:mの1/2方D:mの1/3方
解析:
1.x=(x+y)/2=(m+1)/2 mは非常に大きく、x=m/2である.
y=m/x、x=m/2ならy=2;
2.x=(x+y)/2=(m/2+2)/2=m/4+1 mが非常に大きい場合、x=m/4;
y=m/x、x=m/4ならy=4; 
3.x=(x+y)/2=(m/4+4)/2=m/8+2 mは非常に大きく、x=m/8である.
y=m/x、x=m/8ならy=8;
.........
x=m/2n,y=2n
x-y=m/2 n-2 n=0のときm/2 n-2 n=0 m=22 n=>n=(logm)/2
タイトル73:fun(484)の戻り値を求める()

bool fun(int n){
     int sum=0;
     for(int i=1;n>sum;i=i+2)
         sum=sum+i;
     return (n==sum);
}

A:
True
B:False
この问题は间违っていて、単纯に毎回2をプラスすると思って、最后にプラスして奇数です.実は程勲の運行過程はこうです.
loop 1:sum=1, i=3 loop 2:sum=4, i=5 loop 3:sum=9, i=7 loop 4:sum=16,i=9 loop 5:sum=25,i=11 loop 6:sum=36,i=13 loop 7:sum=49,i=15
... 法則によりsumの値はサイクル回数の二乗,22*22=484,サイクル終了時sum=484,関数はtrueを返すことが分かった.
題目74:以下の関数のf(1)の値は()

int f(int n){
    static int i=1;
     if(n>=5)
         return n;
     n=n+i;
     i++;
     return f(n);
}

A:5   B:6   
C:7  D:8
解析:この問題は主にstaticを調べ、このキーワードを持ってから変数は一度だけ初期化されます.この関数は再帰呼び出しです.f(1):n=2;i=2;呼び出しf(2)f(2):n=4;i=3;呼び出しf(4)f(4):n=7;i=4;呼び出しf(7)f(7):戻り7、すなわち最終関数戻り結果7
タイトル75:指定された文字列(ASCIIコード0-255)配列は、余分なスペースを開かずに開始と終了のスペースを削除し、中間の複数の連続するスペースを1つにまとめてください.例えば、「i am a little boy.「i am a little boy」となり、言語は限定されませんが、偽のコードで答えないでください.関数の入出力は以下の関数のプロトタイプを参照してください.

C++    ：
void FormatString(char str[],int len){ }

解析:

void FormatString(char str[],int len)
{
    assert(str!=NULL);  
    int i=0,j=0,k=0;
    while(str[i]==' ')i++;//i          
    while(str[i]!='\0')
    {
        if(str[i]==' '&&str[i+1]==' '||str[i+1]=='\0')
        {
            i++;
            continue;
        }
    str[j++]=str[i++];//   if                  ，  str[i]==' '&&str[i+1]!=''   

    }
    str[j]='\0';
}

タイトル76:2つのツリーと、その中の2つのnode(アドレスは空ではありません)が与えられ、この2つのnodeの共通の親ノードが与えられ、この親ノードと2つのノードのパスの和が最小になるように要求されます.あなたのプログラムの最悪の時間の複雑さを説明して、そして具体的な関数を実現して、関数の入出力は以下の関数の原型を参照してください:C++関数の原型:

strucy TreeNode{
     TreeNode* left;   //     
     TreeNode* right;   //     
     TreeNode* father;   //      
};
TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second){ }

解析:この問題では木のノードに親ノードへのポインタがあるので,比較的やりやすい.コードは次のとおりです.

int getHeight(TreeNode *node) {
    int height = 0;
    while (node) {
        height++;
        node = node->parent;
    }
    return height;
}
 
TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second) {
    int height1 = getHeight(first), height2 = getHeight(second), diff = height1 - height2;
    if (diff < 0) {
        diff = -diff;
        while(diff--) {
             second = second->parent;
        }
    } else {
        while(diff--) {
            first = first->parent;
        }
    }
    while (first != second) {
        first = first->parent;
        second = second->parent;
    }
    return first;
}

ツリー構造の中に親ノードへのポインタがないと仮定すると、この問題はどうすればいいのでしょうか.剣指offerの上にはこのような状況に関する議論があり、下には他山の石がある.まず2つのノードへの経路を取得し、それから経路の中で最後の共通点を探すことに転化し、この共通点は2つのノードの最低の共通祖先である.

bool GetNodePath(TreeNode* pRoot, TreeNode* pNode, list& path)
{
    if(pRoot == pNode)
        return true;
 
    path.push_back(pRoot);
 
    bool found = false;

    vector::iterator i = pRoot->m_vChildren.begin();
    while(!found && i < pRoot->m_vChildren.end())
    {
        found = GetNodePath(*i, pNode, path);
        ++i;
    }
 
    if(!found)
        path.pop_back();
 
    return found;
}

TreeNode* GetLastCommonNode
(
    const list& path1, 
    const list& path2
)
{
    list::const_iterator iterator1 = path1.begin();
    list::const_iterator iterator2 = path2.begin();
    
    TreeNode* pLast = NULL;
 
    while(iterator1 != path1.end() && iterator2 != path2.end())
    {
        if(*iterator1 == *iterator2)
            pLast = *iterator1;
 
        iterator1++;
        iterator2++;
    }
 
    return pLast;
}

TreeNode* GetLastCommonParent(TreeNode* pRoot, TreeNode* pNode1, TreeNode* pNode2)
{
    if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
        return NULL;
 
    list path1;
    GetNodePath(pRoot, pNode1, path1);
 
    list path2;
    GetNodePath(pRoot, pNode2, path2);
 
    return GetLastCommonNode(path1, path2);
}

今日はこれで、まだ終わっていません.