面试题4:二维数组中的查找

/*
 测试数据：
 查找7:
 4
 1 2 8 9
 2 4 9 12
 4 7 10 13
 6 8 11 15
 1
 
 -----
 
 查找14：
 4
 1 2 8 9
 2 4 9 12
 4 7 10 13
 6 8 11 15
 0
 */

#include <stdio.h>

//注意：二维数组用做函数形参
int searchIna(int a[][4],int s,int n) {
    int i = 0,j = n-1;
    while (a[i][j] > s) {
        while (a[i][j]>s) {
            j--;
        }
        while (a[i][j]<s) {
            i++;
        }
        if (a[i][j] == s) {
            return 1;
        }
    }
    return 0;
}

int main(int argc, const char * argv[]) {
    int n = 0;
    scanf("%d",&n);
    int a[n][n];
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            scanf("%d",&a[i][j]);
        }
    }
//    for (int i = 0; i<n; i++) {
//        for (int j = 0; j<n; j++) {
//            printf("%d ",a[i][j]);
//        }
//        printf("\n");
//    }
    printf("%d\n",searchIna(a, 14, 4));
    return 0;
}

面试题6:从尾到头打印链表

单链表从尾到头打印（用栈或递归）

单链表结构

//从尾到头打印链表（递归）
void printfList(LinkedList L) {
    L = L->next;//跳过头节点
    if (NULL == L->next) {
        printf("%d ",L->data);
        return;
    }
    printfList(L);
    printf("%d ",L->data);
}

面试题7：重建二叉树

根据先序遍历序列和中序遍历序列，重建二叉树

二叉树结构

//根据先序遍历序列和中序遍历序列重建二叉树
BiTree Construct(int *ptree,int *itree,int length)
{
    if(ptree==NULL || itree==NULL || length<=0)
        return NULL;
    return ConstructCode(ptree,ptree+length-1,itree,itree+length-1);
}

/****************************************************************
 *args:
 *   ptree_start:先序遍历开始位置指针
 *   ptree_end:先序遍历结束位置指针
 *   itree_start:中序遍历开始位置指针
 *   itree_end:中序遍历结束位置指针
 ****************************************************************/
BiTree ConstructCode(int *ptree_start,int *ptree_end,int *itree_start,int *itree_end)
{
    BiTree root_node;
    root_node=(BiTree)malloc(sizeof(BiTNode));
    root_node->data=ptree_start[0];                          /*根节点*/
    root_node->lChild=NULL;
    root_node->rChild=NULL;
    
    if(ptree_start==ptree_end)                              /*该节点是子树最后一个节点*/
    {
        if(itree_start==itree_end && *ptree_start==*ptree_end)
        {
            return root_node;
        }else
        {
            printf("ConstructCode is error!\n");
            exit(1);
        }
    }
    int *tmp_itree=itree_start;
    int left_length=0;
    while((*itree_start!=root_node->data) && (itree_start<itree_end))/*在中序遍历中寻找跟节点的指针*/
    {
        itree_start++;
    }
    left_length=itree_start-tmp_itree;                      /*根节点在中序遍历中的位置，用于求在先序遍历中右子树的开始位置*/
    if(left_length>0)                                        /*左子树递归*/
    {
        root_node->lChild=ConstructCode(ptree_start+1,ptree_start+left_length,tmp_itree,itree_start-1);
    }
    if(left_length<(ptree_end-ptree_start))                  /*右子树递归，pend-pstart>left_length说明遍历序列比左子树长，右子树有节点*/
    {
        root_node->rChild=ConstructCode(ptree_start+left_length+1,ptree_end,itree_start+1,itree_end);
    }
    return root_node;
}

面试题8:二叉树的(中序遍历序列)下一个节点

非标准答案，改中序遍历，添加标记打印。

二叉树结构

//中序遍历 找出节点的下一个节点
void MiddleOrderBiTreeFindNextData(BiTNode *T,int s,int flag)
{
    if (T == NULL)
    {
        return;
    }
    else
    {
        MiddleOrderBiTreeFindNextData(T->lChild,s,flag);
        if (flag == 1) {
            printf("%d ",T->data);
            return;
        }
        if (T->data == s) {
            flag = 1;
        }
        MiddleOrderBiTreeFindNextData(T->rChild,s,flag);
    }
}

面试题10：斐波那契数列

//递归，效率低，存在重复计算项
int fabonacci(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fabonacci(n -1) + fabonacci(n - 2);
    }
}

//改进,用c记录前一项值。时间复杂度：O(n)
int fabonacci2(int n) {
    int resu[2] = {0,1};
    int a = 0, b = 1, c = 0;
    if (n < 2) {
        return resu[n];
    } else {
        for (int i = 2; i <= n; i++) { //要加上等于，因为斐波那契数列从第0项计算
            c = a + b;
            a = b;
            b = c;
        }
    }
    return c;
}

面试题11：旋转数组的最小数字

时间复杂度：O(n)

//遍历一遍数组
int minInA1(int a[],int n) {
    int min = -999999;
    for (int i = 0; i < n; i++) {
        if (a[i] > a[i+1]) {
            min = a[i+1];
        }
    }
    return min;
}

时间复杂度：O(logn) (未考虑特殊情况：1 1 1 0 1)

//改进(类似二分查找法，递归写法)
int minInA2(int a[],int low,int high) {
    int mid = (low + high)/2;
    if (low<high) {
        if (high - low == 1) {
            return a[mid+1];
        } else if (a[low] <= a[mid]) {
            return minInA2(a, mid, high);
        } else if (a[low] > a[mid]) {
            return minInA2(a, low, mid);
        }
    }
    return -1;
}

把前两种综合起来，完整的算法

//考虑特殊情况：1 1 1 0 1
int minInA3(int a[],int low,int high) {
    int mid = (low + high)/2;
    if (a[mid] == a[low] && a[mid] == a[high]) {
        return minInA1(a, high+low+1);
    } else return minInA2(a, low, high);
}

面试题14：剪绳子

动态规划

int maxProducyAfterCounting(int n) {
    if (n < 2) {
        return 0;
    } else if (n == 2) {
        return 1;
    } else if (n == 3) {
        return 2;
    } else {
        int product[n+1];
        product[0] = 0;
        product[1] = 1;
        product[2] = 2;
        product[3] = 3;
        int max;
        
        for (int i = 4; i<=n; i++) {
            max = 0;
            for (int j = 1; j<=i/2; j++) {
                int producter = product[j] * product[i - j];
                if (max<producter) {
                    max = producter;
                }
                product[i] = max;
            }
        }
        max = product[n];
        
        return max;
    }
}

贪婪算法

int maxProducyAfterCounting2(int n) {
    if (n < 2) {
        return 0;
    } else if (n == 2) {
        return 1;
    } else if (n == 3) {
        return 2;
    } else {
        int timesOf3 = n/3;
        if (n - timesOf3 == 1) {
            timesOf3 = timesOf3 - 1;
        }
        
        int timesOf2 = (n - timesOf3 * 3)/2;
        return pow(3, timesOf3) * pow(2, timesOf2);
    }
}

and so on...