剑指offer-学习笔记
剑指offer-学习笔记
前言：18/06/06开始学习，每个程序都会用C写一遍，因书中用C++举例，也会换种思路写，供学习和参考！！！很推荐这本书很不错，准备入手，一般不买实体书，都用电子书，因一般都看一遍，但这本会看很多遍！无论刚毕业，还是跳槽都可以看一下…
面试题3：二维数组中的查找
题目如图，所有题目截图均引自《剑指offer》，接下来不再说明！
书中从右上角开始查找，我的程序从左下角查找：
#include<stdio.h> #include<stdbool.h> bool Find(int (*num)[4],int rows,int column,int number) { bool found = false; if(num!=NULL && rows>0 && column>0) { int col = 0; int row = rows-1; while(col<column && row>=0) { if((*num)[row*column+col] == number) { found = true; break; } if((*num)[row*column+col] < number) ++col; else --row; } } return found; } int main() { int number; int num[4][4] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}}; puts("please input your number:"); scanf("%d",&number); bool res = false; res = Find(num,4,4,number); printf("res:%d\n",res); return 0; }
对逻辑不理解的，可以随时留言，随时解答！！！
面试题4：
代码如下：
#include<stdio.h> void ReplaceBlank(char string[],int length) { if(string==NULL && length<=0) return; int originalLen = 0;//字符串实际长度 int numBlank=0,i=0; while(string[i] != '\0') { ++originalLen; if(string[i] == ' ') ++numBlank; ++i; } //替换后的长度 int newLen = originalLen + numBlank*2; if(newLen > length) return; int indexLen = originalLen; int indexOfNew = newLen; while(indexLen>=0 && indexOfNew>indexLen) { if(string[indexLen] == ' ') { string[indexOfNew--]='0'; string[indexOfNew--]='2'; string[indexOfNew--]='%'; } else { string[indexOfNew--] = string[indexLen]; } --indexLen; } } int main() { char buf[]={"hello world!"}; ReplaceBlank(buf,20); printf("buf:%s\n",buf); return 0; }
注：重点理解从尾到头遍历的时间复杂度为O(n)!!!
面试题5：
#include<stdio.h> #include<stdlib.h> typedef int data_t; //栈结构 typedef struct LIFO { int *data; // 4字节的指针 指向数组（后分配的数组） int maxlen; // 存储数据的个数最大值 int top; }seqstack_t; //链表结构 typedef struct node{ int data; struct node *next; }linknode_t,* linklist_t; //创建空的链表 linknode_t *CreateLink() { linknode_t *H; H = (linklist_t)malloc(sizeof(linknode_t)); H->next = NULL; return H; } //初始化一个空链表 void InitLink(linknode_t *H) { linknode_t *r,*p;//r指向队尾 r = H; int i=0; for(;i<5;i++) { p = (linklist_t)malloc(sizeof(linknode_t)); p->data = i+1; p->next = NULL; r->next = p; r = p;//再将r指向队尾 } } //打印所有节点 linknode_t * ShowLink(linknode_t *H,seqstack_t *T) { linknode_t *p,*r; int temp=0; p = H->next; while(p != NULL) { T->data[T->top]=p->data; p = p->next; T->top++; } --T->top; while(T->top>=0) { printf("data:%-5d",T->data[T->top]); T->top--; } } //清空链表 void ClearLink(linknode_t *H) { linknode_t *p,*q;//p是删除的节点,q记录下一个要删除的节点 q = H->next; while(q != NULL) { p = q; q = p->next; free(p); } printf("\n"); H->next = NULL; } seqstack_t * CreateStack(int max) { seqstack_t *H; // 分配结构体空间 --> 一个栈 H = (seqstack_t *)malloc(sizeof(seqstack_t)); H->data = (data_t *)malloc(sizeof(data_t) * max);// 结构体成员赋值 H->maxlen = max; H->top = 0; return H; } int main() { seqstack_t *T=CreateStack(10); // 获取一个空的栈 linknode_t *H=CreateLink(); InitLink(H); ShowLink(H,T); ClearLink(H); free(H); return 0; }
注：用栈的后进先出LIFO思想实现链表的从尾到头的输出！！！
未完待续……
版权声明：本文为liudw-0215原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。