面试题21 包含min函数的栈
实现一个能够得到栈的最小元素的min函数，在该栈中调用min，push，pop的时间复杂度都是O(1)
思路 把每次的最小元素保存起来放到另一个辅助栈里
代码
#pragma mark-包含min函数的栈
void push(struct stack *data,struct stack *min,int x){
data->top++;
data->data[data->top]=x;
//如果辅助栈为空或者新加入的值小于最小值
if (min->top==-1 || x<min->data[min->top]) {
min->top++;
min->data[min->top]=x;
}else{
int t=min->data[min->top];
min->top++;
min->data[min->top]=t;
}
}
void pop(struct stack *data,struct stack *min){
data->top--;
min->top--;
}
int min(struct stack *min){
if (min->top==-1) {
return 0;
}else{
return min->data[min->top];
}
}
void minstack(){
struct stack s1,s2;
s1.top=-1;
s2.top=-1;
push(&s1, &s2, 3);
push(&s1, &s2, 4);
push(&s1, &s2, 2);
push(&s1, &s2, 5);
printf("%d", min(&s2));
}
面试题23 二叉树的层次遍历
思路 每一次打印一个节点的时候，如果该节点有子节点，则把该节点的子节点放到一个队列的末尾。该节点出队，直至队列为空。
代码
#pragma mark-层次遍历二叉树
void Toptobottom(struct BinaryTreeNode *root,struct queue *q){
if (!root) {
return;
}
//把根节点加入队列
q->tail++;
q->data[q->tail]=root;
//当队列不空时
while (q->tail-q->head!=0) {
//取出队列头节点
struct BinaryTreeNode *node=q->data[q->head];
printf("%d",node->value);
q->head++;
//将左右孩子加入队列
if (node->leftchild) {
q->tail++;
q->data[q->tail]=node->leftchild;
}
if (node->rightchild) {
q->tail++;
q->data[q->tail]=node->rightchild;
}
}
}
面试题29 数组中出现次数超过一半的数字
思路 数组中一个数字出现次数超过一半，说明其他元素出现次数总和没有它多。我们保存两个值，一个是数组中的数字，一个是次数，该数字出现一次次数加一，出现别的数字就减一，如果次数为0，保存新的数字，到最后保存的数字就是数组中出现次数超过一半的数字。
代码
#pragma mark-数组中出现次数超过一半的元素
//思路 一个数出现次数超过一半 那么它出现次数比其他所有数总和还要多 那么每出现一次加1 出现别的数减1 最后该数肯定大于0
int MorethanHalf(int a[],int length){
int temp=a[0];
int count=1;
for (int i=1; i<length; i++) {
if (count==0) {
temp=a[i];
count++;
}else if (a[i]==temp){
count++;
}else{
count--;
}
}
return temp;
}
void checkMorethanHalf(){
int a[5]={2,2,3,4,2};
printf("%d",MorethanHalf(a, 5));
}
面试题30 输入n个整数，找出其中最小的k个数
思路一 利用快排的思想
代码
//利用快排的思想 快速排序一趟过后 比基准元素小的元素全在左边 只要左边的数目等于k 即符合题意
void kmin(int left,int right,int a[],int k){
int i,j,t,temp;
if (left>right) {
return;
}
temp=a[left];
i=left;
j=right;
while (i!=j) {
while (a[j]>=temp && i<j) {
j--;
}
while (a[i]<=temp && i<j) {
i++;
}
if (i<j) {
t=a[j];
a[j]=a[i];
a[i]=t;
}
}
a[left]=a[i];
a[i]=temp;
//如果i等于k 则i左边正好有k个数
if (i==k) {
for (int i=0; i<k; i++) {
printf("%d",a[i]);
}
//如果i大于k 则对i左边继续排
}else if (i>k){
kmin(left, i-1, a, k);
//如果i小于k 则对i右边继续排
}else{
kmin(i+1, right, a, k);
}
}
另一种思路 如果n很大，是海量数据怎么办
创建一个大小为k的容器，每次读进一个数字。
若容器不满，数字加入容器。
若容器满，找出容器中的最大值和数字进行比较，若数字较小，则替换。由于我们需要经常进行替换和查找最大值的工作，所以容器可以选择为红黑树。
