一、算法设计
1、设rand(s,t)返回[s,t]之间的随机小数,利用该函数在一个半径为R的圆内找随机n个点,并给出时间复杂度分析。
思路:这个使用数学中的极坐标来解决,先调用[s1,t1]随机产生一个数r,归一化后乘以半径,得到R*(r-s1)/(t1-s1),然后在调用[s2,t2]随机产生一个数a,归一化后得到角度:360*(a-s2)/(t2-s2)
2、为分析用户行为,系统常需存储用户的一些query,但因query非常多,故系统不能全存,设系统每天只存m个query,现设计一个算法,对用户请求的query进行随机选择m个,请给一个方案,使得每个query被抽中的概率相等,并分析之,注意:不到最后一刻,并不知用户的总请求量。
思路:如果用户查询的数量小于m,那么直接就存起来。如果用户查询的数量大于m,假设为m+i,那么在1-----m+i之间随机产生一个数,如果选择的是前面m条查询进行存取,那么概率为m/(m+i),如果选择的是后面i条记录中的查询,那么用这个记录来替换前面m条查询记录的概率为m/(m+i)*(1-1/m)=(m-1)/(m+i),当查询记录量很大的时候,m/(m+i)== (m-1)/(m+i),所以每个query被抽中的概率是相等的。
3、C++ STL中vector的相关问题:
(1)、调用push_back时,其内部的内存分配是如何进行的?
(2)、调用clear时,内部是如何具体实现的?若想将其内存释放,该如何操作?
vector的工作原理是系统预先分配一块CAPACITY大小的空间,当插入的数据超过这个空间的时候,这块空间会让某种方式扩展,但是你删除数据的时候,它却不会缩小。
vector为了防止大量分配连续内存的开销,保持一块默认的尺寸的内存,clear只是清数据了,未清内存,因为vector的capacity容量未变化,系统维护一个的默认值。
有什么方法可以释放掉vector中占用的全部内存呢?
标准的解决方法如下
template < class T >
void ClearVector( vector< T >& vt )
{
vector< T > vtTemp;
veTemp.swap( vt );
}
事实上,vector根本就不管内存,它只是负责向内存管理框架acquire/release内存,内存管理框架如果发现内存不够了,就malloc,但是当vector释放资源的时候(比如destruct), stl根本就不调用free以减少内存,因为内存分配在stl的底层:stl假定如果你需要更多的资源就代表你以后也可能需要这么多资源(你的list, hashmap也是用这些内存),所以就没必要不停地malloc/free。如果是这个逻辑的话这可能是个trade-off
一般的STL内存管理器allocator都是用内存池来管理内存的,所以某个容器申请内存或释放内存都只是影响到内存池的剩余内存量,而不是真的把内存归还给系统。这样做一是为了避免内存碎片,二是提高了内存申请和释放的效率——不用每次都在系统内存里寻找一番。
二、系统设计
正常用户端每分钟最多发一个请求至服务端,服务端需做一个异常客户端行为的过滤系统,设服务器在某一刻收到客户端A的一个请求,则1分钟内的客户端任何其它请求都需要被过滤,现知每一客户端都有一个IPv6地址可作为其ID,客户端个数太多,以至于无法全部放到单台服务器的内存hash表中,现需简单设计一个系统,使用支持高效的过滤,可使用多台机器,但要求使用的机器越少越好,请将关键的设计和思想用图表和代码表现出来。
三、求一个全排列函数:
如p([1,2,3])输出:
[123]、[132]、[213]、[231]、[321]、[312]
求一个组合函数。
方法1:依次从字符串中取出一个字符作为最终排列的第一个字符,对剩余字符组成的字符串生成全排列,最终结果为取出的字符和剩余子串全排列的组合。
#include <iostream>
#include <string>
using namespace std;
void permute1(string prefix, string str)
{
if(str.length() == 0)
cout << prefix << endl;
else
{
for(int i = 0; i < str.length(); i++)
permute1(prefix+str[i], str.substr(0,i)+str.substr(i+1,str.length()));
}
}
void permute1(string s)
{
permute1("",s);
}
int main(void)
{
//method1, unable to remove duplicate permutations.
permute1("abc");
return 0;
}
优点:该方法易于理解,但无法移除重复的排列,如:s="ABA",会生成两个“AAB”。
方法2:利用交换的思想,具体见实例,但该方法不如方法1容易理解。
我们以三个字符abc为例来分析一下求字符串排列的过程。首先我们固定第一个字符a,求后面两个字符bc的排列。当两个字符bc的排列求好之后,我们把第一个字符a和后面的b交换,得到bac,接着我们固定第一个字符b,求后面两个字符ac的排列。现在是把c放到第一位置的时候了。记住前面我们已经把原先的第一个字符a和后面的b做了交换,为了保证这次c仍然是和原先处在第一位置的a交换,我们在拿c和第一个字符交换之前,先要把b和a交换回来。在交换b和a之后,再拿c和处在第一位置的a进行交换,得到cba。我们再次固定第一个字符c,求后面两个字符b、a的排列。
既然我们已经知道怎么求三个字符的排列,那么固定第一个字符之后求后面两个字符的排列,就是典型的递归思路了。
基于前面的分析,我们可以得到如下的参考代码:
void Permutation(char* pStr, char* pBegin)
{
assert(pStr && pBegin);
//if(!pStr || !pBegin)
//return ;
if(*pBegin == '\0')
printf("%s\n",pStr);
else
{
char temp;
for(char* pCh = pBegin; *pCh != '\0'; pCh++)
{
if(pCh != pBegin && *pCh == *pBegin) //为避免生成重复排列,当不同位置的字符相同时不再交换
continue;
temp = *pCh;
*pCh = *pBegin;
*pBegin = temp;
Permutation(pStr, pBegin+1);
temp = *pCh;
*pCh = *pBegin;
*pBegin = temp;
}
}
}
int main(void)
{
char str[] = "aba";
Permutation(str,str);
return 0;
}
如p([1,2,3])输出:
[1]、[2]、[3]、[1,2]、[2,3]、[1,3]、[1,2,3]
这两问可以用伪代码。
分享到:
相关推荐
机械设计试验机sw20可编辑非常好的设计图纸100%好用.zip
JSP基于WEB的图书馆借阅系统的设计与实现(源代码+论文)
1_6_huh猫(扭曲声音)_分p整合猫meme素材90+(持续更新中).mp4
【超炫购物模板】仿拍鞋网商城首页触屏版html5手机wap购物网站模板下载.zip
国内外顶尖评级方法 中诚信评级方法汇总 18个行业评级指标体系文档 募集+法律意 见书+评级报告案例 穆迪评级方法 某公司债券募集说明书及评级报告-经典案例 国 内外顶尖评级方法.part2.rar (13.32 MB)
Unity3D版本游戏源码2-119美食游戏模板—Restaurant & Cooking Starter Kit 1.72提取方式是百度网盘分享地址
LNMP部署wordpress
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
●论文复刻● 中国式融资融券与企业金融化 ——基于分批扩容的准自然实验 通过本案 例可以学习到什么 从基础数据整理到最后的结果输出的完整案例 基础结果:描述性统计 、相关系数矩阵、双重差分回归、绘制走势图 如何对缺失值和异常值处理(缩尾处理) 输出表格结果 组间差异检验 动态平行趋势检验 稳健性检验方法 倾向得分匹配PSM 替换被解释变量 控制省份固定效应 改变计量方法,采用个体和时间上的双重聚类调整 剔除IPO当年的样本 企业金融化的动机(套利动机、股价崩盘) 进一步研究(考察 管理层持股和机构投资者持股的差异、考察产品市场竞争的差异、考察股票市场行情的差异 ) 学习到论文实证分析中常用的命令(merge、logout、esttab、ps match2、cluster2、coefplot、ttest、ranksum等) 内容丰富,绝对超值,建议先下载文献看看,有需要可以下载系统学习,其他相关主题的 论文可速成 模型说明 变量定义 变量符号 定义与度量方式 Fin 企业金融化,金 融资产/总资产 Post List 虚拟变量,公司股票成为融资融券标的以后年度的 样本取值为1;否
触屏版html5响应式手机app网站模板下载 触屏版html5响应式手机,自适应手机wap
VOC2-1-2-2-2-2-2
从头开始训练SSD-python源码.zip
基于faster-rcnn实现的行人检测算法python源码+项目说明+详细注释.zip 使用方法: 1.编译安装faster-rcnn的python接口,代码在:https://github.com/rbgirshick/py 2.下载训练好的caffe模型,百度云链接为:https://pan.baidu.com/s/1w479QUUAwLBS2AJbc-eXIA,将下载的模型文件放到faster-rcnn文件夹的data/faster_rcnn_models文件夹中 3.将本项目中的文件夹替换安装好的faster-rcnn源码中的文件夹 4.使用tools文件夹下的测试脚本运行demo:python person_detect.py
基于Torch Hub的yolo5和ssd推理-python源码.zip
机械设计工件气压测试平台sw18非常好的设计图纸100%好用.zip
JSP机房上机收费管理系统(源代码+论文+外文翻译)
基于Torch Hub的深度估计模型MiDaS-python源码.zip
01. 完整作业流程.xls
2024五一杯b题,c&c++课程设计KTV歌曲系统,学生档案管理系统,个人收支系统,职工管理系统等
触屏版自适应手机wap软件网站模板 触屏版自适应手机wap软件网站模板