マイクロソフトなどの会社のデータ構造+アルゴリズムを精選して100題の解答を面接します(11-30)

11、二叉木を1つの図と見なし、親子ノード間の連線を双方向と見なす場合、「距離」を2つのノード間のエッジの個数として一応定義します.プログラムを書いて、1本の二叉木の中で最も遠い2つのノード間の距離を求めます.
    構想:木の高さを求める.参照先:http://blog.csdn.net/dazhong159/article/details/7862774
12、テーマ:1+2+...+nを求め、乗除法、for、while、if、else、switch、caseなどのキーワードおよび条件判断文(A?B:C)を使用できないことを要求する.
    &&の短絡特性を利用して,再帰を終了する.

int add_fun(int n)
{
	int sum=0;
	n && (sum=add_fun(n-1));
	return sum+n;
}

13、一方向チェーンテーブル(先頭ノード)を入力し、そのチェーンテーブルの最下位からk番目のノードを出力する.チェーンテーブルの最後から0番目のノードは、チェーンテーブルの末尾ポインタ(最後の要素)です.    構想:2つのポインタで、最初はいずれもヘッドノードを指し、1つのポインタは先にk+1歩、それから2つのポインタは同時に歩く.

struct Node
{
	int m_nKey;
	Node* next;
};

//       
Node* lastK(Node *head, int k) 
{
	if(head==NULL)
	{
		cout<<"      ！"<<endl;
		return NULL;
	}
	if (k<0) 
	{
		cout<<"k     ！"<<endl;
		return NULL;
	}

	Node *p=head, *pk=head;
	for (int i=0;i<=k;i++)   //pk  k+1 
	{
		if (pk!=NULL) 
			pk = pk->next;
		else 
			return NULL;
	}

	while (pk!=NULL) 
	{
		p=p->next;
		pk=pk->next;
	} 
	
	return p;
}

14、昇順に並べ替えられた配列と数字を入力し、配列の中で2つの数を検索し、それらの和が入力された数字になるようにします.要求時間複雑度はO(n)である.複数対の数字の和が入力に等しい数字があれば、いずれかのペアを出力すればよい.たとえば、配列1、2、4、7、11、15、および数字15を入力します.4+11=15のため、4と11が出力される.

void find2Number(int a[], int n, int dest) 
{
	int *f = a, *e = a+n-1;
	int sum = *f + *e;
	while ((sum = *f + *e) != dest && f < e) 
	{
		if (sum < dest) 
			++f;
		else 
			--e;
	}
	if (sum == dest) 
		printf("%d, %d
", *f, *e);
}

15、ツリーをミラーに変換する2元ルックアップツリーを入力します.すなわち、変換後の2元ルックアップツリーでは、左サブツリーのノードが右サブツリーのノードよりも大きいです.ツリーのミラー変換は、再帰とループの2つの方法で完了します.

struct Node
{
	int data;
	Node *left;
	Node *right;
};

//      
void swap(Node ** l, Node ** r) 
{
	Node * p = *l;
	*l = *r;
	*r = p;
}

//   
void mirror(Node * root) 
{
	if (root == NULL) 
		return;
	swap(&(root->left), &(root->right));
	mirror(root->left);
	mirror(root->right);
}

//   
void mirrorIteratively(Node * root) 
{
	if (root == NULL) 
		return;

	stack<Node*> buf;
	buf.push(root);
	while (!buf.empty()) 
	{
		Node *n = buf.top();
		buf.pop();
		swap(&(n->left), &(n->right));
		if (n->left != NULL) 
			buf.push(n->left);
		if (n->right != NULL) 
			buf.push(n->right);
	}
}
    

    再帰の本質はコンパイラが関数呼び出しのスタックを生成することであるため、同じタスクをループで完了する際に最も簡単な方法は、補助スタックで再帰をシミュレートすることである.まず、木の頭の結点をスタックに入れます.ループでは、スタックが空でない限り、スタックのスタックトップノードをポップアップし、左右のサブツリーを交換します.左の木があれば、左の木をスタックに押し込みます.右の木がある場合は、右の木をスタックに押し込みます.これで次のサイクルで息子の結点の左右の子木を交換できます
16、ツリーの各ノードを上から下へ、同じレイヤの中から左から右へと順番に印刷する二元ツリーを入力します.
    参照:http://blog.csdn.net/dazhong159/article/details/7862774
17.1つの文字列に1回だけ表示される最初の文字を見つけます.abaccdeffが入力されるとbが出力される.

char firstSingle(char * str) 
{
	int a[255];  //           
	memset(a, 0, 255*sizeof(int));

	char *p=str;
	while (*p!='\0')  //     ，              
	{
		a[*p]++;
		p++;
	}

	p = str;
	while (*p!='\0')  //     ，              
	{
		if (a[*p] == 1) 
			return *p;
		p++;
	} 
	return '\0'; 
}

18、n個の数字(0,1,...,n-1)は、0から始まる円を形成し、この円からm番目の数字(1番目は現在の数字そのもの、2番目は現在の数字の次の数字)を毎回削除する.1つの数字が削除されると、削除された数字の次の数字からm番目の数字が削除されます.この丸に残った最後の数字を求める.
    参照:http://blog.csdn.net/dazhong159/article/details/7849235

int joseph(int n, int m) 
{
	int fn=0;
	for (int i=2; i<=n; i++) 
	{
		fn = (fn+m)%i; 
	}

	return fn;
}

19、Fibonacci数列(f(0)=0,f(1)=1)にnを入力し、その数列のn番目の項を最速の方法で求める.
    参照:http://blog.csdn.net/dazhong159/article/details/7943803
20、整数を表す文字列を入力し、その文字列を整数に変換して出力する.例えば、文字列「345」を入力すると、整数345が出力される.
    参照:http://blog.csdn.net/dazhong159/article/details/7827952
21、2つの整数nとmを入力、数列1,2,3.....nから任意に数を取り、mと等しくする、その中のすべての可能な組み合わせを列挙することを要求する.

#include "stdafx.h"
#include "stdlib.h"
#include <iostream.h>
#include <string.h>

#define N 1000
int a[N];  //    ，           
int c=0, n=20, m=30; 

void work(int sum, int cc)
{
	//   m，    ，    
	if(sum == m)  
	{ 
		for(int i = 0; i < c; ++i)
			printf("%d ", a[i]);
		printf("
");
		return;
	}
	
	//   1 n    
	for(int i = cc; i <= n; ++i)  
	{
		//   m，      
		if(sum + i > m)  
			return;

		//   m，    
		if(sum + i <= m) 
		{
			a[c++] = i;
			work(sum + i, i + 1);
			--c;   //    
		}
	}
}

int main()
{
	work(0, 1); //    （     0，      1）
	
	return 0;
}

22、赤い札が4枚と青い札が4枚あって、司会者はまず任意の2枚を持って、それからそれぞれA、B、Cの3人のおでこに任意の2枚の札を貼って、A、B、Cの3人はすべて残りの2人のおでこの札を見ることができて、見終わった後に彼らに自分のおでこの上でどんな色の札を当てさせて、Aは知らないと言って、Bは知らないと言って、Cは知らないと言って、それからAは知っています.推理の仕方、Aはどうやって知ったのか教えてください.プログラムを使えば、どうやって実現しますか?23、最も簡単で、最も速い方法で、以下のこの円形が正方形と交差しているかどうかを計算します.「3 D座標系原点(0.0,0.0,0.0)円形:半径r=3.0円心o=(*.*,0.0,*.*)正方形:4個の角座標;1:(*.*,0.0,*.*)2:(*.*,0.0,*.*)3:(*.*,0.0,*.*)4:(*.*,0.0,*.*)
24、チェーンテーブル操作、(1)単一チェーンテーブルをその場で逆置き(2)チェーンテーブルを合併する
    参照:http://blog.csdn.net/dazhong159/article/details/7796344
25、int continumax(char*outputstr,char*intputstr)の原形を持つ関数を書く
機能:文字列の中で最も長い数字の列を見つけて、この列の長さを返して、この最も長い数字の列をその中の1つの関数パラメータoutputstrの指すメモリに支払います.例えば、「abcd 12345 ed 125 ss 123456789」の最初のアドレスがintputstrに伝わった後、関数は9を返して、outputstrの指す値は123456789です.

int continumax(char *outputstr, char *inputstr) 
{
	int len = 0,max=0;    //len          ，max        
	char *pstart = NULL;
	while (*inputstr!='\0')
	{
		if (*inputstr >= '0' && *inputstr <='9') 
		{
			len ++;
		} 
		else 
		{
			if (len > max)  //              
			{
				max=len;
				pstart = inputstr-len;
			}
			len = 0;
		}
		inputstr++;
	}
	
	if (len > max) //              
	{
		max=len;
		pstart = inputstr-len;
	}

	for (int i=0; i<max; i++)
		*outputstr++ = *pstart++;
	*outputstr = '\0';
	
	return max;
}

26、左旋回文字列:文字列の左旋回操作を定義する:文字列の前のいくつかの文字を文字列の末尾に移動する.例えば文字列abcdefを左に2ビット回転して文字列cdefabを得る.文字列左旋回の関数を実現してください.長さnの文字列操作の複雑度はO(n)、補助メモリはO(1)である.      数学における行列転置法則を利用する.

      参照:http://blog.csdn.net/dazhong159/article/details/7768548
27、一つの階段に全部でn級があり、一度に1級跳べば、2級跳べます.全部でどれだけの総跳法があるかを求め、アルゴリズムの時間複雑度を分析します.

       関数f(n)がステップnの総ホップ数を表すと仮定すると、最後のホップは2つのケース(ホップ1段とジャンプ2段)しかないため、すべてのf(n)=f(n-1)+f(n-2)である.一方、f(1)=1,f(2)=2であり、f(0)=1の場合、解を求める問題はfib数列に似ている.28、整数を入力し、その整数のバイナリ表現の中でどれだけの1があるかを求める.例えば、入力10は、バイナリ表現が1010で、2つの1があるため、2を出力する.       xxxxxx10000 & (xxxxxx10000-1) = xxxxxx00000

       参照:http://blog.csdn.net/dazhong159/article/details/7801060 29、2つの整数シーケンスを入力します.1つのシーケンスはスタックのpush順序を表し、別のシーケンスが対応するpop順序である可能性があるかどうかを判断します.簡単にするために、pushシーケンスのいずれかの整数が等しくないと仮定します.例えば、入力されたpushシーケンスが1、2、3、4、5であれば、4、5、3、2、1はpop系列である可能性がある.push 1、push 2、push 3、push 4、pop、pop、pop、pop、pop、pop、pop、popのように得られるpop系列が4、5、3、2、1であるからである.ただし、系列4、3、5、1、2はpush系列列1、2、3、4、5のpop系列であることは不可能である.

#include "stdafx.h"
#include "stdlib.h"
#include <iostream>
#include <string>
#include <stack>
using namespace std;

int IndexOfPushArray(int *pushArray,int start,int n,int val)
{
	for (int i=start;i<n;i++)
	{
		if (pushArray[i]==val)
			return i;
	}

	return -1;
}

bool IsPossiblePop(int *pushArray,int *popArray,int n)
{
	//index1  popArray[i] pushArray    ，index2  popArray[i+1] pushArray    
	int i,j,index1=-1,index2; 
	stack<int> s; //   
	for (i=0;i<n;i++)
	{	
		//s   
		if (!s.empty())
		{
			int m=s.top();
			//      popArray[i]，  pop
			if (s.top()==popArray[i])
			{
				s.pop();
				continue;
			}
			//       popArray[i]，   pushArray   
			else
			{
				index1++;
				index2=IndexOfPushArray(pushArray,index1,n,popArray[i]);
				if (index2!=-1)
				{
					for (j=index1;j<=index2;j++)
					{
						s.push(pushArray[j]);
					}
					s.pop();
					index1=index2;
				}
				else
					return false;
			}
		}
		//s   ， pushArray   
		else
		{
			index1++;
			index2=IndexOfPushArray(pushArray,index1,n,popArray[i]);
			if (index2!=-1)
			{
				for (j=index1;j<=index2;j++)
				{
					s.push(pushArray[j]);
				}
				s.pop();
				index1=index2;
			}
		}
	}

	return true;
}

void main()
{
	int a[]={1,2,3,4,5};
	int b1[]={1,3,2,4,5};
	int b2[]={1,3,4,2,5};
	int b3[]={1,3,5,4,2};
	int b4[]={1,4,2,3,5};
	int b5[]={1,5,2,4,3};

	cout<<IsPossiblePop(a,b1,5)<<endl; //1
	cout<<IsPossiblePop(a,b2,5)<<endl; //1
	cout<<IsPossiblePop(a,b3,5)<<endl; //1
	cout<<IsPossiblePop(a,b4,5)<<endl; //0
	cout<<IsPossiblePop(a,b5,5)<<endl; //0
}

30、整数nを入力し、1からnまでのn個の整数の十進法表現のうち1が現れる回数を求める.
      少し大きい数字21345を例として分析した.1から21345までのすべての数字を2つのセグメント、すなわち1-1345と1346-21345に分けた.まず1346-21345の中で1が現れる回数を見てみる.1の出現は2つの状況に分けられる.1の場合は1が最上位(万位)に現れる.1から21345までの数字のうち、1は10000-19999という10000個の数字の万位に現れ、合計10000(104)回現れた.もう1つは、1が最上位を除く他の位に現れた.例では1346-21345で、この20000個の数字のうち、後ろの4位のうち1が2000回現れた(2*103、うち2の1番目の数値、103は数字の後ろの4桁の数字のうちの1桁が1であるため、残りの3桁の数字は0から9までの10桁を任意に選択することができ、配列の組み合わせから総回数は2*103となる).1から1345までのすべての数字の中で1が現れる回数については、再帰的に求めることができます.これも私たちが1-21345を1-1235と1346-21345の2つのセグメントに分ける理由です.21345の最高位を取り除くと1345になり、再帰的な考え方を採用するのに便利です.        ここまで分析すると、前述の例では、最上位は1より大きい数字であり、このとき最上位1が現れる回数104(5桁に対して)であることに注意する必要がある..しかし、もし最上位が1だったら?例えば12345を入力して、10000から12345までの数字のうち、1万位での出現回数は104回ではなく、2346回です.つまり最上位を除いた残りの数字に1を加えます.先の分析に基づいて、以下のようなコードを書くことができます.参考コードでは、プログラミングの便宜上、数字を文字列に変換しました.

#include "stdafx.h"
#include "stdlib.h"
#include <iostream>
#include <string>
using namespace std;

//   10^n 
int PowerBase10(unsigned int n) 
{ 
	int result = 1;
	for(unsigned int i = 0; i < n; ++ i) 
		result *= 10; 
	return result; 
}

// Find the number of 1 in an integer with radix 10 
int NumberOf1(const char* strN) 
{ 
	//      1
	if(!strN || *strN < '0' || *strN > '9' || *strN == '\0')
		return 0; 
	int firstDigit = *strN - '0'; 
	unsigned int length = static_cast<unsigned int>(strlen(strN)); 

	//       2 
	if(length == 1 && firstDigit == 0) 
	    return 0; 
	if(length == 1 && firstDigit > 0) 
		return 1;

	// suppose the integer is 21345 (12345) 
	// numFirstDigit is the number of the first digit 
	int numFirstDigit = 0;
	if(firstDigit > 1) 
		numFirstDigit = PowerBase10(length - 1); 
	else if(firstDigit == 1) 
		numFirstDigit = atoi(strN + 1) + 1; 

	// numOtherDigits is the number of 1 01346-21345 due to all digits 
	int numOtherDigits = firstDigit * (length - 1) * PowerBase10(length - 2); 

	// numRecursive is the number of 1 of integer 1345 
	int numRecursive = NumberOf1(strN + 1); 
	
	return numFirstDigit + numOtherDigits + numRecursive; 
} 

// Find the number of 1 in an integer with radix 10 
int NumberOf1BeforeBetween1AndN_Solution2(int n) 
{ 
	if(n <= 0) 
		return 0; 
	char strN[50]; 
	sprintf(strN, "%d", n); 
	
	return NumberOf1(strN); 
}
void main()
{
	cout<<NumberOf1BeforeBetween1AndN_Solution2(21345)<<endl;
}

記事の転載先:http://blog.csdn.net/v_JULY_v/article/details/5968678