剑指offer答案全集

《剑指offer答案全集》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、按牛客网上的顺序来。2016.06.03l二维数组中的查找在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。输入描述:array：待查找的二维数组target：查找的数字输出描述:查找到返回true，查找不到返回false代码：classSolution{public:boolFind(vector>array,inttarget){introw=array

2、.size();//行数if(row==0)returnfalse;intcol=array[0].size();//列数if(col==0)returnfalse;inti=0,j=col-1;//从右上角开始while(i=0){if(target==array[i][j])returntrue;//找到，立即退出elseif(target>array[i][j])i++;//向下一行elsej--;//向前一列}if(i==row

3、

4、j<0)returnfalse;//没找

5、到returntrue;//此句执行不到，只是为了编译没问题}}分析：时间复杂度O(m+n)，m和n分别是行数和列数。空间复杂度O(1)。思想是从右上角开始判断，每次判断可以排除一行或一列。l替换空格请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为WeAreHappy.则经过替换之后的字符串为We%20Are%20Happy。代码：//length为牛客系统规定字符串输出的最大长度，固定为一个常数classSolution{public:voidreplaceSpace(c

6、har*str,intlength){if(NULL==str)return;char*p=str;intsize=0;//记录str长度intblankNum=0;//记录空格个数while(*p!='')//一直找到字符串尾部{if(*p=='')blankNum++;size++;p++;}if(blankNum==0)return;//没有空格，直接返回intnewSize=size-blankNum+blankNum*3;//计算新字符串大小//if(newSize>length)

7、return;char*end=str+newSize;//*end='';//最后一个字符置空end--;//往前一步p=str+size-1;//原字符串的最后一个字符处while(p>=str){if(*p==''){//当前字符是空格，则替换*end--='0';*end--='2';*end--='%';}else{//否则，不替换*end--=*p;}p--;//依次向前}}}分析：时间复杂度O(N)，N为字符串长度。思想是先遍历一次得到字符串的长度和空格个数，计算出替换后的字符

8、串长度，这样会在原字符串后面空出一段；然后从后往前，碰到空格就替换。鉴于义军的话：就在牛客网上的那个编辑器里写代码，不要在VS里面写，因为VS有自动补全功能，而面试的时候是没有自动补全的。所以从现在起，不在VS中写代码了，可能会在VS里查看有哪些成员函数。2016.06.04l从尾到头打印链表输入一个链表，从尾到头打印链表每个节点的值。代码：/***structListNode{*intval;*structListNode*next;*ListNode(intx):*val(x),next(N

9、ULL){*}*};*/classSolution{public:vectorprintListFromTailToHead(structListNode*head){vectorvec;printTmp(head,vec);returnvec;}voidprintTmp(ListNode*head,vector&vec){if(NULL==head)return;printTmp(head->next,vec);vec.push_back(head->val);}

10、};分析：递归，时间复杂度O(N)，N为链表长度。因为要返回一个vector，所以必须另外写个函数，以便把vector作为参数。l重建二叉树输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。代码：/***Definitionforbinarytree*structTreeNode{*intval;*TreeNod