一道AS3数据结构面试题-白红宇

一道AS3数据结构面试题

阅读量：4105 次

发布时间：2019-05-25

本文共 1977 字，大约阅读时间需要 6 分钟。

题目：给定一个数组，比如 arr = [2,9,1,3,6,4]；实现一个函数ArrSum(arr:Array, sum:int)，这个函数实现这样的功能：如果在这个数组中存在两个数的和值为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

true

这个算法主要用到AS3中数组特性，如果用C++来实现，那么tmpArr就需要手动设置长度,并且这个长度会动态改变，最大值为max(sum-arr[i])，

同时注意要清理内存memset(tmpArr, 0, sizeof(tmpArr))，

或者可以自己写一个HashTable来保存差值映射；

闲着没事，写了个C++版本的

// ArrSum.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include 
   
    #include 
    
     using namespace std;bool ArrSum(std::vector
     
       arr, int sum);int _tmain(int argc, _TCHAR* argv[]){	std::vector
      
        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")<

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

转载地址：http://nejsi.baihongyu.com/

你可能感兴趣的文章

B 站爆红的数学视频，竟是用这个 Python 开源项目做的！