此内容仅提供解题思路，应自行尝试撰写具体代码

1.数组中重复的数字查找：查找数组中重复的数字，数组长度为n，取值范围为0~（n-1）。       方法一：（修改原本数组）对数组进行比较排序，第i位的数据m与i比较，如果相等，则跳至下一位；如果不相等，则与第m位比较，如果m与第m位的数不相同，则交换；如果相等，则m即为重复的数据。       方法二：（不修改数组）类似于二分法。将数组按定义域分为两部分，定义域任何侧的出现次数若大于该定义域内的整数个数，则表示该定义域内存在重复的数字。以此再进行分隔，不断递归直到找到重复的数字。2.二维数组中查找：二维数组中从左到右递增，从上到下递增，输入一个整数判断该二维数组中是否含有此数。       思路：先切列再切行。       因为首行最后一位（右上角）是第一行最大、第四列最小的数，因此拿它进行比较，如果目标整数比它更小，则存在区域矩形往左移动一列，若比到刚好更小，则开始行判断，若存在必然在右上角找到该数。

3.空格替换（字符替换）

将字符串中的空格替换成”%20”。

思路：提前移动(3-1)Xn个位置以便替代，之后从后往前进行扫描。

设置双指针，把第一个指针指向第一个字符串的末尾，第二个指针指向替换后的字符串末尾。将第一个指针的内容复制到第二个指针，当第一个指针碰到空格的时候停下，第二个指针往前赋上“%20”。以此反复，直到两个指针重合。

4.从尾到头进行链表打印

思路：运用栈的思想，又因为递归本身就是一种栈结构，因此可以用递归。

扫到链表的最末位的时候，才开始打印value并且返回上层。

5.二叉树重建：输入二叉树的前序遍历和中序遍历的结果，重建二叉树

思路：前序遍历第一位为根节点，后面跟左子树和右子树；中序遍历的根节点的左侧为左子树，右侧为右子树。

6.二叉树的下一个节点：给定一个二叉树和一个节点，按照此中序遍历序列找出下一个节点。（此树的节点包含左右子节点的指针和父节点的指针。）

思路：下一个结点有以下的判断基准。

A.若此节点有右子树，则右子树的最左子节点（若左子节点不为空时，则不断往下推导，知道找到最左子节点）就是下一个结点。

B.若没有右子树，则判断该点是不是父节点的的左子节点，若是则父节点就是下一个结点。

C.若经过以上筛选之后，此节点为是父节点的右子节点，则往上查找父节点，直到找到一个节点，它是它的父节点的左子节点，则该节点的父节点为该结点的下一个结点。

7.用两个栈实现队列：实现两个函数appendTail和deleteHead，完成尾部加入节点和队列头部删除节点的功能。

思路：加入的节点先堆入栈1，删除节点时，当栈2为空，则将栈1的数值不断推入栈2，直到全部入栈2.接着删除栈2顶的的数据。若栈2不为空，则表示栈首仍然存在栈2，则直接删除栈2的栈首。

8.斐波那契数列：案例1：输入n，求斐波那契数列的第n项。

实用解法：循环计算各项的数值并存入数列（而非利用递归的方式）。

时间复杂度O(log n)的方法：

类似的乘方算法：当n为偶数时，a^n=a^(n/2)*a^(n/2);n为奇数时，a^n=a^((n-1)/2)*a^((n-1)/2)*a。

案例2：青蛙一次可以跳上1级或2级台阶，问上一个n级台阶有多少种方法。逆推：f(n)时，可以是f(n-1)的次数（因为这之上只能有跳1级这种情况）加上f(n-2)（因为相差2级，若两级一起跳则算一种，若分一级一级跳则和f(n-1)再跳一级的情况有重合），则从本质上看依然是斐波那契数列的项数求解。

9.打印从1到最大的n位十进制数（1~999，即最大的3位数）

隐藏问题：大数溢出

解决办法：字符串或数组来表达，用char *number = new char[n+1];menset(number,'0',n);的形式创建地址空间。此处应使用ascii码制来保存数值。

    可以看作是打印n位的全排列，每一位从0到9变化，只要把有效数字前面的0不予显示就行。因此此处使用递归的方法比较合适。

    每一位从0开始，往下递归，直到到最低位，此时一个n位整数已经写入字符串，将它打印出来后逐层返回并重新循环赋值。

10.删除链表的节点：删除i节点的内容

        思路：将j节点的内容复制到i节点，再将i节点的m_pNext指针指向k节点，再删除j节点。

        好处：不用遍历节点h。

11.删除链表中的重复节点：在已经排序的链表中删除重复的节点。

注意要点：因为头节点可能也是重复的节点，因此删除函数应该声明为void deleteDuplication (ListNode** pHead);

思路：将当前结点与下一节点比较，若为重复的节点，则都可以被删除，使当前节点的前一节点（pPreNode）和后面比当前节点数值更大的节点相连。

12.正则表达式匹配：实现一个函数，模式中的'.'表示任意一个字符,'*'表示前面的字符可以出现任意次数（也包含0次）。

    思路：即'.'单独看就是任意字符；而'*'应该结合前面的一个字符来看，例如：'a*'-->'','a','aa','aaa'...因此在正则表达的规则明确之后，再来分析所有可能情况。

具体实例：字符串："aaa"—>模式："a.a","ab*ac*a"...

先判断下一位是否为'*',则判断模板和字符串当前位置是否相同若相同或该位置的模板是否为‘.’，则可以作三种或判断，一是将模板往后移动两格，字符串往后移动一格（判断是只代换了一个）；二是模板不动，字符串往后移动一格（替换超过一个，继续往下查找直到找到替换结束的位置）；三是字符串不动，模板往后移动两格（替换了0个），此三者存在一种情况是正确的，又因为只需要判断是否为字符串的模板，因此递归函数的返回值应该是bool类型的。而如果第二条判断语句不成立，则直接算作该'*'未替代任何字符，可以省去，因此模板后移两格而字符串不动。在下一位不是'*'的情况下，则可以判断模板该位置内容是否与字符串相等或该位置为'.'。若以上条件都不满足（又不相等又不可替换），则返回false.

13.表示数值的字符串：判断传入的字符串是否表示数值（包含整数，小数和负数）

                        思路：基本结构为A[.[B][e|EC]]或者去掉A的版本。A：整数部分。B：小数部分。C：指数部分。

                        注：一个没有整数部分的数不能没有小数部分。A、C是可以有正负号的数位串。

分无符号扫描和有符号扫描：无符号扫描先判断是否在0~9之间，若是，则向前推进继续判断，遇到非数字则跳出。有符号扫描则是将第一位进行符号判断，之后直接跳至无符号扫描。

14.数组顺序调整：

案例1：让奇数位于偶数前面

        思路：首尾两指针，当前置指针扫描到偶数时停下，当后置指针扫描到奇数时停下，之后交换两数值。继续扫描直到前后两个指针位置重合。

案例2：万金油，即判断标准再变换。

    思路：1.判断数字处于前后部分的标准。2.确定拆分的操作。将标准确定在外部函数当中，该函数作为函数指针传入。

15.链表中倒数第K个节点：尾节点为倒数第一个节点，且此链表不设置父节点的地址。

    思路：倒数第k个节点正序应该是第n-k+1个节点，因此可以设置两个节点，相差k-1个位置，当一个节点在最后一位的时候，后面的节点就在第n-k+1个节点的位置，省去了先扫描一遍再读到n-k+1位这样两次计算的时间浪费。

注意：鲁棒性。1.pListNode的指针不能为空；2.长度不能小于k；3.k的值不能小于1