面試題21 包含min函數(shù)的棧

實現(xiàn)一個能夠得到棧的最小元素的min函數(shù)，在該棧中調用min，push，pop的時間復雜度都是O(1)
思路 把每次的最小元素保存起來放到另一個輔助棧里
代碼

#pragma mark-包含min函數(shù)的棧
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 二叉樹的層次遍歷

思路 每一次打印一個節(jié)點的時候，如果該節(jié)點有子節(jié)點，則把該節(jié)點的子節(jié)點放到一個隊列的末尾。該節(jié)點出隊，直至隊列為空。
代碼

#pragma mark-層次遍歷二叉樹
void Toptobottom(struct BinaryTreeNode     *root,struct queue *q){
if (!root) {
    return;
}
//把根節(jié)點加入隊列
q->tail++;
q->data[q->tail]=root;
//當隊列不空時
while (q->tail-q->head!=0) {
    //取出隊列頭節(jié)點
    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 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字

思路 數(shù)組中一個數(shù)字出現(xiàn)次數(shù)超過一半，說明其他元素出現(xiàn)次數(shù)總和沒有它多。我們保存兩個值，一個是數(shù)組中的數(shù)字，一個是次數(shù)，該數(shù)字出現(xiàn)一次次數(shù)加一，出現(xiàn)別的數(shù)字就減一，如果次數(shù)為0，保存新的數(shù)字，到最后保存的數(shù)字就是數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字。
代碼

 #pragma mark-數(shù)組中出現(xiàn)次數(shù)超過一半的元素
 //思路 一個數(shù)出現(xiàn)次數(shù)超過一半 那么它出現(xiàn)次數(shù)比其他所有數(shù)總和還要多 那么每出現(xiàn)一次加1 出現(xiàn)別的數(shù)減1 最后該數(shù)肯定大于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個整數(shù)，找出其中最小的k個數(shù)

思路一 利用快排的思想
代碼

//利用快排的思想 快速排序一趟過后 比基準元素小的元素全在左邊 只要左邊的數(shù)目等于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個數(shù)
if (i==k) {
    for (int i=0; i<k; i++) {
        printf("%d",a[i]);
    }
    //如果i大于k 則對i左邊繼續(xù)排
}else if (i>k){
    kmin(left, i-1, a, k);
    //如果i小于k 則對i右邊繼續(xù)排
}else{
    kmin(i+1, right, a, k);
}
}

另一種思路 如果n很大，是海量數(shù)據(jù)怎么辦
創(chuàng)建一個大小為k的容器，每次讀進一個數(shù)字。
若容器不滿，數(shù)字加入容器。
若容器滿，找出容器中的最大值和數(shù)字進行比較，若數(shù)字較小，則替換。由于我們需要經(jīng)常進行替換和查找最大值的工作，所以容器可以選擇為紅黑樹。