1、
设计栈的结构,要求实现min()函数,就是取当前栈中的最小值,要求栈的操作push,pop,min的时间复杂度为0(1)。
/*
百度笔试
问题:设计栈的结构,要求实现min()函数,就是取当前栈中的最小值,要求栈的操作push,pop,min的时间复杂度为0(1)?
*/
/*
思路:用两个定长数组实现,一个存放插入的元素,另外一个存放栈中最小元素的下标
*/
class MyStack
{
public:
MyStack():size(0)
{}
void push(int ele)
{
if (size == 0)//插入第一个元素时
{
arr[size] = ele;
minIndex[size] = 0;
size++;
}
else if (size < MAX_LENTH)//插入其它元素时,要进行比较来确定最小值的位置
{
arr[size] = ele;
if (ele < arr[minIndex[size-1]])
{
minIndex[size] = size;
}
else
{
minIndex[size] = minIndex[size-1];
}
size++;
}
else
{
cout<<"栈已满,不好意思哦!"<<endl;
}
}
void pop()
{
if (size>=0)
{
arr[size] = 0;
minIndex[size]=0;
size--;
}
else
{
cout<<"栈已经空了!"<<endl;
}
}
int min()
{
if (size > 0)
{
return arr[minIndex[size-1]];
}
else
{
cout<<"栈中无元素!"<<endl;
}
}
public:
enum{ MAX_LENTH = 20 };//数组的长度
int arr[MAX_LENTH];
int minIndex[MAX_LENTH];
int size;//指向下一个要插入的元素的位置
};
int main()
{
int arr[] = {5, 3, 7, 9, 3, 1, 8, 9, 4};
int n = sizeof(arr) / sizeof(int);
MyStack my;
for (int i=0; i<n; i++)
{
my.push(arr[i]);
}
for (int i=0; i<n; i++)
{
cout<<"当前的最小元素为:"<<my.min()<<endl;
my.pop();
}
}
第二种方法
/*
百度笔试
问题:设计栈的结构,要求实现min()函数,就是取当前栈中的最小值,要求栈的操作push,pop,min的时间复杂度为0(1)?
*/
/*
思路:用两个栈实现
num1 一个用来入数据,num2 一个用来存min,push时每次判断num1的数据是否小于或等于(记录重复数据)num2栈顶数据,成立入栈
pop时如果数据等于num2栈顶数据,num2出栈
*/
class MyStack
{
public:
MyStack(){}
void push(int ele)
{
if (s1.empty())
{
s1.push(ele);
s2.push(ele);
}
else
{
s1.push(ele);
if (ele <= s2.top())
{
s2.push(ele);
}
}
}
void pop()
{
if(!s1.empty())
{
if(s1.top() == s2.top())
{
s1.pop();
s2.pop();
}
else
{
s1.pop();
}
}
}
int min()
{
if (!s2.empty())
{
return s2.top();
}
}
private:
stack<int> s1;//用来入数据
stack<int> s2;//用来存min
};
int main()
{
int arr[] = {5, 3, 7, 9, 3, 1, 8, 9, 4};
int n = sizeof(arr) / sizeof(int);
MyStack my;
for (int i=0; i<n; i++)
{
my.push(arr[i]);
}
for (int i=0; i<n; i++)
{
cout<<my.min()<<endl;
my.pop();
}
}
2、有一串珠子m个,有n种颜色,要求截取一段,包含所有的颜色,怎么截最短,描述详细的算法过程,计算空间时间复杂度。
/*思路:生成一数组存放原数组及其副本,这样可以避免循环数组的麻烦,但是空间增大*/
#define M 14 //珠子的个数
#define N 5 //串的颜色数
/*
判断是否为新的颜色
参数arr[]存放已有的颜色,n为数组的长度,color为要判断的颜色
*/
bool isNewColor(int arr[], int n, int color)
{
for (int i=0; i<n; i++)
{
if (color == arr[i])
{
return false;
}
}
return true;
}
int main()
{
int list[M]={3,2,3,2,1,2,3,3,3,2,4,4,4,5};
//生成另一数组
int arr[2*M];
memcpy(arr, list, sizeof(list));
memcpy(arr+M, list, sizeof(list));
int minLength = M;//存放最短的串的长度,以便进行比较
int start, end;//起点,及终点
for (int i=0; i<M; i++)
{
int color[N] = {0};//已取得的颜色的数组
int colorNum = 0;//已取得颜色数
color[colorNum] = arr[i];
colorNum++;
for (int j=i+1; j<2*M; j++)
{
if (isNewColor(color, N, arr[j]) && (colorNum < N))
{
color[colorNum] = arr[j];
colorNum++;
}
if (colorNum == N)
{
break;
}
}
//进行比较,以便获得选取最短的
if ((j-i+1) < minLength)
{
minLength = j-i+1;
start = i;
end = j%M;
}
}
printf("最短的串=%d, start=%d, end=%d/n", minLength, start, end);
}
//算法复杂度,个人觉得为o(n^2),但有更高的,自己没想出来
问题来自:
http://topic.csdn.net/u/20101018/17/275aadee-9c49-42e4-859a-4c61bad3c722.html
3、微软面试例题
1、为什么下水道的盖子是圆的?
答:它们并不都是圆的,有些是方的。的确有些圆井盖,但我也看过方的、长方的。
试题点评:该求职者的回答巧妙之处在于敢于提出自己的看法,而不被面试人员的问题吓跑,不限于在面试人员的威逼之下走进死胡同。
2、你让工人为你工作7天,回报是一根金条,这个金条平分成相连的7段,你必须在每天结束的时候给他们一段金条。如果只允许你两次把金条弄断,你如何给你的工人付费?
答: 分成1、2、4三段,第一天给1,第二天给2取回1,第三天给1,第四天给4取回1、2,第五天给1,第六天给2取回1,第七天给1。
3、你有四个装药丸的罐子,每个药丸都有一定的重量,被污染的药丸是没被污染的药丸的重量+1。只称量一次,如何判断哪个罐子的药被污染了?
答:四个罐子中分别取1、2、3、4颗药丸,称出比正常重多少,即可判断出哪个罐子的药被污染了。
5、门外三个开关分别对应室内三盏灯,线路良好,在门外控制开关时候不能看到室内灯的情况,现在只允许进门一次,确定开关和灯的对应关系??
答、三个开关分别:关、开、开10分钟关闭,然后进屋,暗且凉的为开关1控制的灯,亮的为开关2控制的灯,暗且热的为开关3控制的灯。
6、有一辆火车以每小时15公里的速度离开北京直奔广州,同时另一辆火车以每小时20公里的速度从广州开往北京。如果有一只鸟,以每小时30公里的速度和两辆火车同时启动,从北京出发,碰到另一辆车后就向相反的方向返回去飞,就这样依次在两辆火车之间来回地飞,直到两辆火车相遇。请问,这只鸟共飞行了多长的距离?
答、出火车相遇时间,鸟速乘以时间就是鸟飞行的距离。
4、生成一些随机数,从0到52,要求是没有重复的。要求写出O(1)的算法?
/*
生成一些随机数,从0到52,要求是没有重复的。要求写出O(1)的算法!
*/
//参数out[]存放生成的随机数的数组
/*
思想:先生成了从0到52的这53个数,然后随机从中挑选输出,输出了的就不再选了。
*/
void randonNumber(int out[])
{
int arr[53];
int i;
for (i=0; i<53; i++)
{
arr[i] = i;
}
int rnd;
for (i=52; i>=0; i--)
{
rnd = rand() % (i+1);
out[i] = arr[rnd];
arr[rnd] = arr[i];
}
}
int main()
{
int out[53];
randonNumber(out);
copy(out, out+53, ostream_iterator<int>(cout,"/n"));
}