cavenkaka
- 浏览: 201989 次
- 性别:
- 来自: 武汉
-
文章列表
题目：给定一个函数rand5()，该函数可以随机生成1-5的整数，且生成概率一样。现要求使用该函数构造函数rand7()，使函数rand7()可以随机等概率的生成1-7的整数。思路：很多人的第一反应是利用rand5() + rand()%3来实现rand7()函数，这个方法确实可以产生1-7之间的随机数，但是仔细想想可以发现数字生成的概率是不相等的。rand()%3 产生0的概率是1/5，而产生1和2的概率都是2/5，所以这个方法产生6和7的概率大于产生5的概率。正确的方法是利用rand5()函数生成1-25之间的数字，然后将其中的1-21映射成1-7，丢弃22-25。例如生成(1，1)，(1 ...
虚函数：虚函数是C++中用于实现多态(polymorphism)的机制。核心理念就是通过基类访问派生类定义的函数。是C++中多态性的一个重要体现，利用基类指针访问派生类中的成员 函数，这种情况下使用虚函数，这种情况下采用的是动态绑定技术。
虚函数必须是基类的非静态成员函数，其访问权限可以是protected或public，在基类的类定义中定义虚函数的一般形式：
virtual 函数返回值类型 虚函数名（形参表）
{ 函数体 }
STL学习之stack
- 博客分类：
- STL
栈（statck）这种数据结构在计算机中是相当出名的。栈中的数据是先进后出的（First In Last Out, FILO）。栈只有一个出口，允许新增元素（只能在栈顶上增加）、移出元素（只能移出栈顶元素）、取得栈顶元素等操作。在STL中，栈是以别的容器作为底部结构，再将接口改变，使之符合栈的特性就可以了。因此实现非常的方便。下面就给出栈的函数列表和VS2008中栈的源代码，在STL中栈一共就5个常用操作函数（top()、push()、pop()、 size()、empty() ），很好记的。
可以看出，由于栈只是进一步封装别的数据结构，并提供自己的接口，所以代码非 ...
STL 学习之deque
- 博客分类：
- STL
deque双向队列是一种双向开口的连续线性空间，可以高效的在头尾两端插入和删除元素，deque在接口上和vector非常相似，下面列出deque的常用成员函数：
deque的实现比较复杂，内部会维护一个map（注意！不是STL中的map容器）即一小块连续的空间，该空间中每个元素都是指针，指向另一段（较大的）区域，这个区域称为缓冲区，缓冲区用来保存deque中的数据。因此deque在随机访问和遍历数据会比vector慢。具体的deque实现可以参考《STL源码剖析》，当然此书中使用的SGI STL与VS2008所使用的PJ STL的实现方法还是有区别的。下面给出了deque的结构图：
...
稀里糊涂的就投了一个大众点评网，没过多久就收到了笔试通知，居然是在线测试，感觉这种方式很新颖。
2013.4.24当天就在线做了题目，比较坑爹的发现，我们三个人做的题目是一样的，自己居然是第一个做的，前面的逻辑题与数学推理题还算是比较简单的，有一点毛病就是自己太不淡定了，碰到不会做的东西就比较着急，找借口，这也是自己性格中的毛病之一吧。
大概过了一个礼拜之后，就接到了大众点评的面试电话，电面，问了自己算法的知识，主要是问了排序算法的复杂度问题，还问了关于CSDN密码泄露的事情，这两个问题由于自己本身都比较熟悉，就回答的还不错。接下来就是问我是不是愿意搞JAVA以及搞了之后多久能上手的问 ...
2012年4月，腾讯发来通知，让去参加笔试，由于腾讯一直是自己喜欢的单位，就很认真的在准备腾讯的笔试。由于是第一次参见笔试，没有什么经验，看往年试卷有很多网络与操作系统的知识，自己就无从复习，无奈之下就看完了面试宝典还有往年的试题。
4.12号去参加笔试，发现卷子的那一瞬间发现几乎都是往年的原题，自己当时那个悔啊，自己总有这个毛病，眼高手低，很多东西都以为自己会了，其实自己没有完全理解，就这样稀里糊涂的做完了试卷，感觉还不错。过了大概一周吧，腾讯发来通知说让去参加面试，由于是人生中的第一场面试，感觉很激动，很开心，就提前一个小时到了面试现场。等了大概20分钟后，就去面试了，发现腾讯的面试官都 ...
选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，
冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。
冒泡排序是稳定的，算法时间复杂度是O(n ^2)。
2.2 选择排序（Selection Sort）
选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。 选择排序是不稳定的，算法复杂度是O(n ^2 )。
2.3 插入排序 （Insertion Sort）
插入排序的基本思想是，经过i-1遍处理后,L[1..i- ...
题意：作者要开一个生日party，他现在拥有n块高度都为1的圆柱形奶酪，已知每块奶酪的底面半径为r不等，作者邀请了f个朋友参加了他的party，他要把这些奶酪平均分给所有的朋友和他自己（f+1人），每个人分得奶酪的体积必须相等（这个值是确定的），形状就没有要求。现在要你求出所有人都能够得到的最大块奶酪的体积是多少？
思路：贪心的思想+二分。复杂度为O(nlogM)，M为初始时的high-low。初始状态，上界high为每个人分得奶酪的体积sum，下界low = 0（或者是最小块的奶酪）。然后二分，每次的mid值为（low+high）/ 2，然后根据mid值（估计值）遍历n块奶酪，看看 ...
题意：给你天数n，和每天需要花的钱，让你把这些天分成m份（每份都是连续的天），要求每份的和尽量少，输出这个和。 一开始二分的上界为n天花费的总和（相当于分成1份），下界为每天花费的最大值（相当于分成n份），然后二分，每次的mid值为（上界 + 下界）/ 2，然后根据mid值遍历n天花费，对n天的花费进行累加，每当超过mid值 份数++，看看这个mid值能把n天分成几份，如果份数大于m，表示mid偏小，下界 = mid + 1，反之小于等于mid，上界 = mid - 1，然后输出最后的mid值即可，复杂度为 O(nlogM)，M约为第一次的上界。
代码如下：
#includ ...
算法复习贪心算法poj2393
- 博客分类：
- 贪心算法
题意：一个工厂每周要提供不同数量单位的酸奶酪，每周生产单位酸奶酪的成本是不同的，你可以选择预先生产然后库存给以后的周，但是有额外的成本，告知一共要提供 N 周酸奶酪，库存每单位酸奶酪每周的代价是 S，告知每周的单位生产成本 C 和 每周需求 Y，问最小代价是多少。
思路：直接贪心
代码如下：
#include <stdio.h>
int c[10001], y[10001];
int main()
{
int N, S,i;
scanf("%d %d", &N, &S);
for(i = 0; i < N; ...
算法复习之贪心算法poj2709
- 博客分类：
- 贪心算法
题意：一套涂料有3~12种颜色，每种颜色50ml。Emily上课需要n种颜色的涂料，第i种颜色需要color[i]ml，此外，Emily还需要gray ml的灰色涂料，每ml灰色的涂料需要3种不同颜色的其他涂料各1ml融合而成。问emily要上课，至少需要买几套涂料？ 思路：贪心。由于n很小，所以每次1ml的其他涂料融合成灰色时，再对他们进行排序。
代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
const int Max = 15;
int main()
{ ...
算法复习之贪心算法poj 065
- 博客分类：
- 贪心算法
题意：有n条木棒，给出它们每条的l和w，用一台机器对它们进行加工，如果机器正加工的木条，与在它之前加工的木块有关系：l <= l'和w <= w'，则机器不用准备时间，否则需准备1分钟。问加工完全部木棒，机器最少需要准备多久。 思路：贪心。对length进行上升序列的排序，特别应注意两length相等时，应按weight的上升序列的排序。排序号之后，就是找出weight的最小上升序列数了。
代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
const int ...
算法复习之贪心算法之poj 1323
- 博客分类：
- 贪心算法
题意：一次card比赛，有m个参赛者（包括你），每个参赛者有n张卡片。每张卡片的编号都不一样。每一轮，所有参赛者都打出一张卡片，编号最大的赢。问你至少能赢几局。 思路：简单贪心
代码如下：
#include<iostream>
using namespace std;
const int mMax = 22;
const int nMax = 52;
struct data
{
int num;
bool my;
bool small;
}card[mMax * nMax];
int main()
{
int ...
算法复习之贪心算法poj2586
- 博客分类：
- 贪心算法
题意：对于MS Inc来说，每个月如果盈利则必盈利sur，如果亏空则必亏空def（这个公司很怪）。它每五个月进行一次统计，共统计八次（1-5月一次，2-6月一次...）。统计的结果是这八次都亏空。判断MS Inc全年否能盈利，如果能则求出最大的盈利。如果不能则输出"Deficit"。 思路：贪心，符合最优子结构性质。5个月统计一次都亏空，那么有5种情况： 1、若SSSSD亏空，那么全年可能最大盈利情况为: SSSSDSSSSDSS 2、若SSSDD亏空，那么全年可能最大盈利情况为：SSSDDSSSDDSS 3、若SSDDD亏空，那么全年可能最大盈 ...
算法复习之贪心算法 poj 1328
- 博客分类：
- 贪心算法
题意：地图的x轴的上方为海，下方为陆地，海中有n个小岛，坐标为(isl[i].x,isl[i].y)。有一种雷达，能探测到的范围为以d为半径的圆。问海岸线上至少造多少雷达可以把所有的小岛都包含在内。注意雷达是建在海岸线上的，也就是x轴上的。
思路：贪心，从左到右建立雷达，要尽量多地覆盖岛屿。以岛屿为圆心，以d为半径画圆，如果画出的圆与x轴没有交点，则不能实现。存在交点的话，计算出第i个岛屿与x轴的交点坐标保存在结构体数组rad[i].sta与rad[i].end中。对结构体数组排序，按照rad[i].end进行升序排列，然后一次从左到右找雷达。对于rad[i].end为当前最右边的左坐标 ...