剑指offer答案全集.docx

1、按牛客网上的顺序来。2016.06.03 二维数组中的查找在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 输入描述:array： 待查找的二维数组target：查找的数字输出描述:查找到返回 true，查找不到返回 false代码：class Solution public:bool Find(vector array,int target) int row = array.size();/行数if(row=0) return false;int col = array0.s

2、ize();/列数if(col=0) return false;int i = 0, j = col - 1;/从右上角开始while(i=0)if(target=arrayij)return true;/找到，立即退出else if(targetarrayij) i+;/向下一行else j-;/向前一列if(i=row|jlength) return;char *end = str + newSize;/*end = 0;/最后一个字符置空end-; /往前一步p = str + size - 1; /原字符串的最后一个字符处while(p=str)if(*p= )/当前字符是空格，则替换

3、*end- = 0;*end- = 2;*end- = %;else/否则，不替换*end- = *p;p-;/依次向前分析：时间复杂度 O(N)，N 为字符串长度。思想是先遍历一次得到字符串的长度和空格个数，计算出替换后的字符串长度，这样会在原字符串后面空出一段；然后从后往前，碰到空格就替换。鉴于义军的话：就在牛客网上的那个编辑器里写代码，不要在 VS 里面写，因为 VS 有自动补全功能，而面试的时候是没有自动补全的。所以从现在起，不在 VS 中写代码了，可能会在 VS 里查看有哪些成员函数。2016.06.04 从尾到头打印链表输入一个链表，从尾到头打印链表每个节点的值。代码：/* str

4、uct ListNode * int val;* struct ListNode *next;* ListNode(int x) :* val(x), next(NULL) * * ;*/class Solution public:vector printListFromTailToHead(struct ListNode* head) vector vec;printTmp(head,vec);return vec;void printTmp(ListNode *head, vector printTmp(head-next,vec);vec.push_back(head-val);分析：递

5、归，时间复杂度 O(N)，N 为链表长度。因为要返回一个 vector，所以必须另外写个函数，以便把 vector 作为参数。 重建二叉树输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列1,2,4,7,3,5,6,8和中序遍历序列4,7,2,1,5,3,8,6，则重建二叉树并返回。代码：/* Definition for binary tree* struct TreeNode * int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : va

6、l(x), left(NULL), right(NULL) * ;*/class Solution public:struct TreeNode* reConstructBinaryTree(vector pre,vector in) if(pre.size()=0 | in.size()=0) return NULL;int size = pre.size();return constructTmp(pre,in,0,size-1,0,size-1);TreeNode * constructTmp(vector TreeNode * node = new TreeNode(pre.at(pr

7、ei);int i = ini;while(in.at(i)!=pre.at(prei) i+;int len = i - ini;node-left = constructTmp(pre,in,prei+1,prei+len,ini,i-1);node-right = constructTmp(pre,in,prei+len+1,prej,i+1,inj);return node;分析：时间复杂度 O(nlogn)，n 为节点个数。递归的思想。2016.06.05 用两个栈实现队列用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。 队列中的元素为 int 类型。代码：class

8、 Solutionpublic:void push(int node) stack1.push(node);int pop() while(!stack1.empty()stack2.push(stack1.top();stack1.pop(); int ret = stack2.top();stack2.pop();while(!stack2.empty()stack1.push(stack2.top();stack2.pop(); return ret;private:stack stack1;stack stack2;分析：push 时间复杂度为 O(1)，pop 时间复杂度为 O(n)

9、。需要注意的是栈的操作push、pop （并不返回元素） 、top、empty 。 旋转数组的最小数字把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组3,4,5,1,2为1,2,3,4,5的一个旋转，该数组的最小值为 1。NOTE：给出的所有元素都大于 0，若数组大小为 0，请返回 0。代码：class Solution public:int minNumberInRotateArray(vector rotateArray) int size = rotateArray.size();if(size=0) r

10、eturn 0;int low = 0, high = size - 1, mid;while(lowrotateArraylow) low = mid;else if(rotateArraymid rotateArray) int size = rotateArray.size();if(size=0) return 0;int min = rotateArray0;for(int i=1;i23）为了少用一个变量，采用了红色代码部分。 跳台阶一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。代码：class Solution public

11、:int jumpFloor(int n) if(n=-0.000001) else return 1.0/PowerTmp(base,-exponent);double PowerTmp(double base, int ex)if(ex=0) return 1.0;if(ex=1) return base;double ret = Power(base,ex/2);if(exelse return ret*ret;分析：时间复杂度为 O(logn)，n 为指数。1）首先判断 base 和 exponent 是否合法：0 的负数次幂不合法，0 的 0 次幂默认为 1.2）考虑 exponen

12、t 正负，如果小于 0，返回倒数；3）如果 exponent 为奇数，则 power(base,ex)=power(base,ex/2)*power(base,ex/2)*base;如果 exponent 为偶数，则 power(base,ex)=power(base,ex/2)*power(base,ex/2)；折半比循环快。 调整数组顺序使奇数位于偶数前面输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。代码：class Solution public:void reO

13、rderArray(vector if(size=0) return;int odd = 0, even = 0;/odd 为奇数下标，even 为第一个偶数下标while(arrayeven/找到第一个偶数odd = even + 1;/从第一个偶数后面开始找到第一个奇数while(odd=size) break;/如果没有奇数了，及时退出/将even,odd-1之间的偶数向后移一位int tmp = arrayodd;for(int i=odd;ieven;i-)arrayi = arrayi-1;arrayeven = tmp;/把奇数放到前面even+;odd+;分析：此题要是可以改变相对位置，则有时间复杂度为 O(n)、空间复杂度为 O(1)的方法。但是要保证相对位置不变，要么时间复杂度为 O(n)、空间复杂度为 O(n)，要么时间复杂度为 O(n*n)、空间复杂度为 O(1)。本代码的时间复杂度为 O(n*n)，但运行时间为 0ms。 。 。那么此题的意义何在？ 链表中倒数第 k 个结点输入一个链表，输出该链表中倒数第 k 个结点。代码：/*struct ListNode