本のAS 3データ構造の面接試験問題

2989 ワード

データ構造面接試験機能クラス import out put

テーマ:配列を指定します.例えば、arr=[2,9,1,3,6,4]この関数は、ArSum(arr:Aray,sum:int)を実現し、この関数は、この配列に2つの数の和があるとsumとなると、関数はtrueに戻ります.そうでなければfalseに戻ります.要求時間複雑度O(n^1);
簡単に書いてみました.

package
{
	import flash.display.Sprite;
	
	public class ArrSum extends Sprite
	{
		private var m_arr:Array = [1,3,5,7,9];
		
		public function ArrSum()
		{
			trace(func(m_arr, 2));
			trace(func(m_arr, 20));
			trace(func(m_arr, 8));
			
		}
		private function func(arr:Array, sum:int):Boolean
		{
			var tmpArr:Array = new Array();
			for(var i:int = 0; i < arr.length; i++)
			{
				if(arr[i] < sum)
				{
					var j:int =arr[i];
					if(tmpArr[j] == undefined)
					{
						var sub:int = sum - m_arr[i];
						if(tmpArr[sub] == undefined)
							tmpArr[sub] = sub;
					}
					else
						return true;
				}
			}
			
			return false;
		}
	}
}

Output:
false false trueというアルゴリズムは主にAS 3の配列特性を使用しています.C++で実現すると、tmparrは手動で長さを設定する必要があります.この長さはダイナミックに変化します.最大値はmax(sum-arr[i])です.
同時にメモリmemsetを整理することに注意してください.
または、自分でHashTableを書いて差マップを保存することができます.

暇な時は大丈夫です.C++バージョンと書いてあります.

// ArrSum.cpp :              。
//

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;
bool ArrSum(std::vector<int> arr, int sum);

int _tmain(int argc, _TCHAR* argv[])
{
	std::vector<int> arr;
	arr.push_back(1);
	arr.push_back(3);
	arr.push_back(5);
	arr.push_back(7);
	arr.push_back(9);

	std::cout<<(ArrSum(arr, 2)==true?"true":"false")<<endl;
	std::cout<<(ArrSum(arr, 10)==true?"true":"false")<<endl;
	std::cout<<(ArrSum(arr, 20)==true?"true":"false")<<endl;

	system("PAUSE");
	return 0;
}
bool ArrSum(std::vector<int> arr, int sum)
{
	unsigned int tmpLen = arr.size();//          
	int* tmpArr = new int[tmpLen];
	memset(tmpArr, 0, sizeof(int)*tmpLen);
	for (unsigned int i = 0; i < arr.size(); i++)
	{
		if(arr[i] < sum)
		{
			int j = arr[i];
			if (tmpArr[j] == 0)//  tmpArr[i]  *(tmpArr + i)
			{
				int sub = sum - arr[i];
				if((unsigned int)sub > tmpLen)
				{
					int* newBase = new int[sub];
					memset((void*)newBase, 0, sizeof(int)*sub);
					memcpy((void*)newBase, (void*)tmpArr, sizeof(int)*tmpLen);
					tmpArr = newBase;
					tmpLen = sub;
				}
				if(tmpArr[sub] == 0)
				{
					tmpArr[sub] = sub;
				}
			}
			else
				return true;
		}
	}

	return false;
}

output: false  true  false

HDU 2594データ構造のKMP