闘魚C++研究開発春招実生筆記試験総括

試験問題型
全部で10問、最初の6問は空欄、7問目は簡答題、8問目は書き出してプログラムの出力を与える.
空欄の問題は文字列とポインタを考察することが多く、文字列と関係があるので、難しくありません.次に虚関数は2つ試験して、関数のポインタの配列は1つです.第7の簡単な解答問題は3つの例をあげて、constの異なる情況の下での用法に答えます;8番目の問題も虚関数の問題で、何も言うことはありません.第9の道は偽のコードで行列式の解くアルゴリズムの流れを書き出して、第10の問題は2つの質問があって、第1の質問は1つのint配列の中で重複する数字を探し出して、第2の質問は自分の前の質問で書いたコードに対して最適化を行って、構想だけを書き出します.
次は主に最後の問題を振り返ってみましょう.
タイトル:長さn+1の配列のすべての数字は1~nの範囲内にあるので、配列の少なくとも1つの数字は重複している.配列のいずれかの重複する数字を見つけてください.入力した配列は変更できません.配列に同じ数字が1つしかないと仮定します.例えば、入力長が5の配列{1,2,3,4,2}の場合、対応する出力は重複する数字2である.
構想1:二分検索の思想を参考にして、数字1~nを1~mとm+1~nの2つの部分に分割し、数字範囲1~mの中で数字の個数がmより大きい場合、繰り返し数字は1~mの中間で、さもなくば繰り返し数字は必ず数字範囲m+1~nの中で、アルゴリズムの複雑度はO(nlogn)である.

#include 
#include 

using namespace std;

class Solution {
public:
	int duplication(vector vec)
	{
		//    
		int length = vec.size();
		if (vec.size() == 0)
			return -1;

		//     
		for (int i = 0; i < length; ++i)
		{
			if (vec[i]<1 || vec[i]>length - 1)
				return -1;
		}
		//       
		int begin = 1;
		int end = length - 1;

		//             
		while (begin <= end)
		{
			//          
			int mid = (begin + end) >> 1;

			//               
			int count = countrange(vec, begin, mid, length);

			if (end > begin)
			{
				//       
				if (count > (mid - begin + 1))
					end = mid;
				else
					begin = mid + 1;
			}
			else
			{
				if (count > 1)
					return begin;
				else
					break;
			}
		}

		return -1;
	}

	int countrange(vector vec, int begin, int end, int length)
	{
		int count = 0;
		for (int i = 0; i < length; ++i)
		{
			if (vec[i] >= begin && vec[i] <= end)
				++count;
		}

		return count;
	}
};


int main()
{
	vector vec;
	vector vec1 = { 1,2,3,4,5,6,7 };
	vector vec2 = { 1,1,2,3,4,5,6 };
	vector vec3 = { 2,2,3,3,4,5,6 };


	Solution solution;
	cout << solution.duplication(vec) << endl;
	cout << solution.duplication(vec1) << endl;
	cout << solution.duplication(vec2) << endl;
	cout << solution.duplication(vec3) << endl;

	return 0;
}



/*
  ：
-1
-1
 1
 3
*/

構想2:バケツソートのような原理を利用して、配列中のすべての数字は0からn-1であり、これらの数字を配列の下標とすることができ、数値は個数を統計するために使用され、すなわちiは下標であり、a[i]は個数であり、a[i]>1であれば、iは相応の繰り返し数字である.時間的複雑度はO(n),空間的複雑度はO(n)であった.

#include

using namespace std;


bool func(int a[], int length, int *result)
{
	/*      */
	int map[255] = { 0 };
	for (int i = 0; i < length; i++)
	{
		map[a[i]]++;
	}
	for (int i = 0; i < length; i++)
	{
		if (map[i] > 1)
		{
			*result = i;
			return true;
		}
	}
	return false;
}


int main()
{
	int a[] = { 1,2,3,4,4,5,6 };
	int length = sizeof(a) / sizeof(int);
	int *result = a;
	
	func(a, length,result);
	cout << *result << endl;

	return 0;
}


/*
  ：
4
*/

構想3:長さがnであり、値が0からn−1であり、重複する配列がない場合、iは0からn−1であり、対応するa[0]からa[n−1]は同じa[i]を2回指さすことはない.ここで、iについては、まずa[a[i]]に配列長lengthを加算させ、後のiが再び現れると、a[a[i]]は必ずlengthより大きくなり、iは繰り返しの数になる.アルゴリズムの複雑度はO(1)である.

#include

using namespace std;
//a     length      result          
int func(int numbers[], int length)
{
	for (int i = 0; i < length; i++) {
		int index = numbers[i];
		if (index >= length) {
			index -= length;
		}
		if (numbers[index] >= length) {
			return index;
		}
		numbers[index] = numbers[index] + length;
	}
	return -1;
}

int main()
{
	int a[] = { 1,2,3,4,4,5,6 };
	int length = sizeof(a) / sizeof(int);
	int *result = a;
	
	cout << func(a, length);

	return 0;
}



/*
  ：
4
*/

参照先:https://blog.csdn.net/qq_32957239/article/details/80500183
          https://www.cnblogs.com/zijidan/p/9511235.html