面试题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...
