大目录
一、数组问题
1.数组中重复的数字
题目一：在一个长度为n的数组里的所有数字都在0~n-1的范围内。数字中某些数字是重复的，但是不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如：如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3.
解题思路：我们使用数组下标的特点来解出这道题。以数组{2,3,1,0,2,5,3}为例。我们可以将数组的下标和数组中的数据进行匹配，让相等的下标和元素匹配起来。数组的第一个，也就是0这个下标的数据是2，那么，0和2不相等，就让第0个数据和第2个数据进行交换。得到：{1,3,2,0,2,5,3}。
继续，第0位置的数据是1，不相等，就让第0个位置的数据和第1个位置的数据交换，得到：{3,1,2,0,2,,5,3}；第0个位置的数据是3，与0不相等，那么让第0个位置和第3个位置的数据交换，得到：{0,1,2,3，2,5,3}；此时，第0、1、2、3的位置都与其数据相等。那么到第4个位置，发现数据是2，而第2个位置已经匹配成功了，因此，这个重复的数字之一就是2。
根据这个思路，可以写出这道题的代码：
int dupliccate(int* nums,int numsSize) { int i = 0; //如果传入的数组是空的，或者数组长度不正常，那么就直接返回-1. if(nums==nullptr||numsSize<=0) return -1; //如果数组中的元素不在0~numsSize-1这个范围内，那么就直接返回-1； for(i = 0;i<numsSize;i++) { if(nums[i]<0||nums[i]>numsSize-1) return -1; } //开始寻找 for(i = 0;i<numsSize;i++) { if(nums[i]!=i)//当下标与其元素不相等，则往下走 { if(nums[i]==nums[nums[i]]//如果当要交换的时候，发现已经交换过，这个数就是重复的 return nums[i]; } //还没找到的时候，交换 int temp = nums[i]; nums[i] = nums[nums[i]]; nums[nums[i]] = temp; } return -1; }
这道题的总结：
复杂度：虽然这个代码有两个循环，但是每个数字最多只要交换两次就能找到属于它自己的位置，因此，总的时间复杂度是O(N)。另外，不需要额外开辟内存，因此空间复杂度是O(1)。
学到的思想：利用数组的特点：下标。通过下标查找数字。以后遇到有关数组的问题，可以往这方面想想。
题目二：不修改数组找出重复的数字。
题目：在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字的重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如：如果输入长度为8的数组{2,3,5,4,3,2,6,7}，那么对应的输出是重复的数字2或者3.
解题思路：这道题跟上面那道题类似。我嫩可以创建一个长度为n+1的数组，然后逐一将原数组中的元素复制过去。剩下的解法与上道题一样。但是这就需要O(N)的空间复杂度了。
因此，我们可以尝试着不开辟新空间。我们先从题目开始分析，因为数组里的元素，范围只有1~n，而数组长度是n+1，那么，就一定存在着重复的数字。于是，可以借助二分查找的思路，去找出这个数字。怎么找？统计个数！
我们可以把1~n个数字从中间的数字m分成两部分，前面部分为1~m，后面部分为m+1~n。然后开始统计1~m部分的数字在数组中出现的次数，如果大于m，那么重复的数字就在1~m中，否则在m+1~n中。
假如是在1~m中，那么我们继续将1~m分开两部分，继续查找，知道找出这个数字。这里就是运用了二分查找，就是多加了一步统计次数。
用{2,3,5,4,3,2,6,7}为例。取4为中间数，分割成1~4,5~7。然后统计1~4在数组中出现的次数，是5次。所以，重复的数字是在1~4里面。
然后，将1~4分割成1~2和3~4，统计1~2，发现出现了2次。然后统计3~4，发现出现了3次，大于2个，因此重复的数字是在3~4.
最后，将3~4分成3和4，发现3在数组中出现了2次，那么，3就是重复的数字了。
根据这个思路：
int getDuplication(const int* nums,int numsSize) { if(nums==nullptr||numsSize<=0) return -1; int start = 1; int end = numsSize-1; while(start<=end) { int middle = ((end-start)>>1)+start;//取中间数字 int count = countRange(nums,numsSize,start,middle);//统计次数 if(end==start)//当只剩下一个数的时候，不是这个数就是另外一个数，判断这个数的次数 { if(count>1)//大于1，就是它了 return start; else break; } if(count>(middle-start+1))//选择部分 end==middle; else start = middle+1; } return -1; } int countRange(const int* nums,int numsSize,int start,int end) { if(nums==nullptr) return 0; int count = 0; int i = 0; for(i = 0;i<numsSize;i++) { if(nums[i]>=start&&nums[i]<=end) count++; } return count; }
这道题的总结：
复杂度：因为是根据二分查找的方法，因此，函数countRange被调用O(logn)次，每次需要O(N)的时间，所以，时间复杂度是O(N*logN).空间复杂度为O(1)。
思想：数组不仅能往下标的方向去想，还能使用二分查找。
2.二维数组中的查找
题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
例如：有二维数组：
，要查找7这个数字，找到返回true，没找到就返回false。
解题思路：首先选取数组右上角的数字9，由于9大于7，那么说明，9所在的列，也就是第4列，全都大于7，那么7不可能出现在第四列。于是把这一列剔除。我们只需看剩下的。
剔除第四列后，右上角的数字变成了8，由于8也比7大，同理，剔除第3列。
此时右上角的数字变成了2。因为2比7小，因此，7可能位于2的下边，和2的右边。但是右边已经被剔除，因此，7一定在2的下边。
所以，剔除掉2的这一行，此时右上角变成了4.同理，剔除4这一行。最终找到了7.返回true
根据这个思路：
bool Find(int* maxtrix,int rows,int columns,int number) { if(maxtrix!=nullptr&&rows>0&&columns>0) { int row = 0; int column = columns-1; while(row<rows&&column>=0) { if(matrix[row*columns+column]==number) { return true; } else if(matrix[row*columns+column]>number) --column; else ++row; } } return false; }
二、字符串问题
题目：替换空格。
请实现一个函数，把字符串中的每个空格替换成"%20"。例如：输入"We are happy.",则输出"We%20are%20happy."
由于在网络编程当中，如果URL参数中含有特殊字符，如空格、'#'等，则可能导致服务器端无法获得正确的参数值，因此需要这些特殊符号转换成服务器可以识别的字符。
转换的规则是在'%'的后面跟上ASCll码的两位十六进制的表示。比如空格的是32，即十六进制的0x20，因此空格被替换成"%20"。
在遇到这个问题时，首先想到的是要把一个空格变成"%20"，那么就要将把字符串的长度扩大。在替换的时候，要把空格后面的字符往后挪，挪出两个字节用来存放'2'和'0'。但是这样的话，时间复杂度就是O(N^2)。
因此，我们需要想一个问题，如果输入的字符串后面有足够多的空余内存，那么，我们是否可以用另外一种思路去使用这些内存？比如，从尾往头走。
所以，这道题的解题思路就是，先遍历一次字符串，统计出空格的数量。然后，替换后的字符串长度就是原来字符串长度+空格数量*2.
我们准备两个指针p1和p2，p1指向原字符串的末尾，也就是'\0'，p2指向替换后的字符串的末尾。
![XAY2JAZ]}8R%6J@K%]3U61P.png](https://ucc.alicdn.com/pic/developer-ecology/ipajprmaanvwy_4f9973e018d24fa0bd91133dfaafbaf5.png?x-oss-process=image/resize,w_1400/format,webp "XAY2JAZ]}8R%6J@K%]3U61P.png")
然后从p1开始，逐个将它指向的字符复制到p2指向的位置，直到碰到空格为止。![$~Q(732KRA`QO]2XQ$10M41.png](https://ucc.alicdn.com/pic/developer-ecology/ipajprmaanvwy_71cf5f188b9e45de823d0fe4fcac1595.png?x-oss-process=image/resize,w_1400/format,webp "$~Q(732KRA`QO]2XQ$10M41.png")
碰到空格后，p1向前挪动一格，然后在p2开始插入字符串"%20"。
接着继续复制非空格字符。
重复上面的操作，最后把所有空格字符替换掉。
根据这个思路，我们可以写出代码：
void ReplaceBlank(char string[],int length)//length为字符数组string的总长度 { if(string==nullptr||length<=0) return; //知道总长度length还不够，还需要得到字符串的长度和空格的数量，替换后，字符串的长度三个变量 int originallLength = 0;//字符串的长度 int numberBlank = 0;//空格的个数 int i = 0; while(string[i]!='\0') { ++originallLength; if(string[i]==' ') ++numberBlank; ++i; } int newlength = 0;//替换后的字符串长度 newlength = originallLength + numberBlank*2; if(newlength>length)//如果替换后的字符串长度比字符数组string的总长度还长。那就是错误的。 return; int indexOfOriginal = originalLength;//也就是我们画图中的p1 int indexOfNew = newlength;//p2 while(indexOfOriginal>=0 && indexOfNew>indexOfOriginal)//p1走到头，并且p2要一直大于p1 { if(string[indexOfOriginal]==' ') { string[indexOfNew--] ='0'; string[indexOfNew--] ='2'; string[indexOfNew--] ='%'; } else { string[indexOfNew--] = string[indexOfOriginal]; } ++indexOfOriginal; } }
根据分析，所有的 字符都只需要复制一遍，所有时间复杂度就是O(N);
三、链表问题
从尾到头打印链表。
题目描述：输入一个链表的头结点，从尾到头反过来打印每个节点的值。链表节点定义如下：
struct ListNode { int m_nKey; ListNode* m_pNext; };
解决这道题有两个思路，一个是用递归，另外一个是用栈来实现。
如果是用递归，那么每访问一个节点的时候，先去访问它的下一个节点，再输出自身节点。
void PrinListReversingly_Recursively(ListNode* pHead) { if(pHead!=NULL) { if(pHead->m_pNext!=NULL) PrinListReversingly_Recursively(pHead->m_pNext); printf("%d ",pHead->m_nValue); } }
如果是用栈结构，那么我们利用栈的先进后出，就可以实现从尾到头打印了。
void PrintListReversingly_Iteratively(ListNode* pHead) { std::stack<ListNode*>nodes; ListNode* pNode = phead; while(pNode!=NULL)//入栈,是节点入栈 { nodes.push(pNode); pNode = pNode->m-pNext; } while(!nodes.empty())//出栈 { pNode = nodes.top(); printf("%d ",pNode->m-nValue); nodes.pop(); } }
如果链表非常长的时候，使用递归的话，函数调用的栈帧会非常长，导致栈溢出。因此，使用数据结构的栈结构的鲁棒性会好一些！
四、二叉树问题
二叉树的下一个节点
题目描述：给定一颗二叉树和其中的一个节点，如何找出中序遍历的下一个节点？树中的节点除了还有两个分别指向左右子节点的指针，还有一个指向父节点的指针。
如图：![6NLL)AIHTF[R0P]H_VEW7{B.png](https://ucc.alicdn.com/pic/developer-ecology/ipajprmaanvwy_fbba5ebc40944bfb98ec2c855f6b644e.png?x-oss-process=image/resize,w_1400/format,webp "6NLL)AIHTF[R0P]H_VEW7{B.png")
对于中序遍历，我们需要找这一个节点的下一个节点，有三种情况：
①这个节点有右子树，那么它的下一个节点是它的右子树的最左子节点。如上图，a的下一个节点就是f，b的下一个节点就是h。
②这个节点是它父节点的左子节点，并且它没有右子树，那么它的下一个节点就是它的父节点。如果它有右子树，那么就是第一种情况。如d的下一个节点就是b。
③这个节点没有右子树（如果有，那么就是第一种情况），并且是它父节点是右子节点。那么，它的下一个节点，就是一直沿着父节点的指针向上遍历，直到遇到一个是它父节点的左子节点是节点。如果这个节点存在，那么这个节点的父节点就是下一个节点。如：i的下一个节点就是a。由于a是根节点，所以g没有下一个节点。
因此，根据这个思路和这三种情况，我们可以用C++写出代码
BinaryTreeNode* GetNext(BinaryTreeNode* pNode) { if(pNode==NULL) return NULL; BinaryTreeNode* pNext = NULL; //第一种 if(pNode->m-pRight!=NULL) { BinaryTreeNode* Right = pNode->m_pRight; while(Right->m_pLeft!=NULL) Right = Right->m_pLfet; pNext = Right; } else if(pNode->m_pParent!=NULL)//第二种和第三种 { BinaryTreeNode* pCurrent = pNode; BinaryTreeNode* pParent = pNode->m_pParent; while(pParent->m_pRight==pCurrent && pParent!=NULL)//当不是父节点的右节点，退出循环 { pCurrent = pParent; pParent = pParent->m_pParent; } pNext = pParent; } }
五、栈和队列问题
题目描述：用两个栈实现队列。
本题使用两个栈来实现队列，因为栈是后进先出的，通过画图，就可以发现，只要把一条栈上的元素放到另外一条栈上，那么元素都会颠倒过来，然后对这一条栈进行出栈，就是出队的顺序了
![]A_L%_V3T)JW8G}[H%IK2)P.png](https://ucc.alicdn.com/pic/developer-ecology/ipajprmaanvwy_8f07902ca5064d2cbf3f53f5aebe2c56.png?x-oss-process=image/resize,w_1400/format,webp "]A_L%_V3T)JW8G}[H%IK2)P.png")
注意，必须让用来入栈的那个栈将所有元素出栈后，才能将新的元素进栈。用来出栈的也应如此。
思路简单，代码也不难实现：这里是使用c语言实现，复习一下栈结构
![4EPFYFV]O_BV](`R2R}L67A.png](https://ucc.alicdn.com/pic/developer-ecology/ipajprmaanvwy_4c15a64c219c44ea8c66ef1dc54d8bf4.png?x-oss-process=image/resize,w_1400/format,webp "4EPFYFV]O_BV](`R2R}L67A.png")
六、递归与循环问题
题目描述：斐波那契数列
写一个函数，输入n，求斐波那契数列的第n项。
我们第一次入手这道题的时候，大多数用的都是递归！
long long Fibonacci(unsigned int n) { if(n<=0) return 0; if(n==1) return 1; return Fibonacci(n-1) + Fibonacci(n-2); }
我们先用f(10)来分析一下，如果要求f(10)，那么就要求f(9)和f(8)。如果要求f(9)，要求f(8)和f(7)......不难发现，在使用递归的时候，会出现很多重复项，若是n非常大，那么就需要非常恐怖的时间。
因此，我们可以考虑不用递归。并且，我们从f(0)和f(1)开始，从小往大算。
这样的复杂度就是O(N)了。
long long Fibonacci(unsigned n) { int result[2] = {0,1}; if(n<2) return result[n]; long long fibNMinusOne = 1; long long fibNMinusTwo = 0; long long fibN = 0; for(unsigned int i = 2;i<=n;i++) { fibN = fibNMinusOne + fibNMinusTwo; fibNMinusTwo = fibNMinusOne; fibNMinusOne = fibN; } return fibN; }
七、查找与排序问题
题目描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小的元素。
如：数组{3,4,5,1,2}为{1,2,3,4,5}的旋转数组。最小的元素的1.
其实这道题的解放很简单，只需要遍历一遍数组，就能找到最小的元素了，但是，这样肯定达不到训练查找和排序的能力。
通过分析，可以知道，旋转数组划分成了两个排序的子数组，都是递增。而且，最小的元素恰好是这两个子数组的分界点。因此，我们可以利用二分查找的思路，用两个指针分别指向数组的尾和头。
接着，我们始终让p1指向指向第一个子数组的元素，p2始终指向第二个子数组的元素。这样中间元素是位于第一个子数组的时候，它应该是大于等于第一个指针指向的元素，而这个数组最小的元素就是这个元素的下一个元素。
当中间元素是位于第二个子数组，它应该小于等于第二个指针指向的元素，那么它就是最小的元素了。
当然，前提是p1和p2的下标相差1，否则，继续二分查找。每一次查找，判断中间元素是哪个数组里面的，然后就让这个数组的p指向它，知道p2和p1相差1.
当p1和p2还有中间元素相等的时候，这里就没办法使用二分查找了，只能使用顺序查找。
int Mid(int* numbers,int length) { if(numbers==NULL||length<=0) exit(-1); int start = 0; int end = length-1; int mid = start;//如果旋转的元素个数为0，也是旋转数组，那么第一个就是最小的。 while(numbers[start]>=numbers[end]) { if(end-start==1) { mid = end; break; } mid = ((end-start)>>1) + start; if(numbers[start]==numbers[end]&&numbers[start]==numbers[mid]) return MidInOrder(numbers,start,end);//使用顺序查找 if(numbers[mid]>=numbers[start]) start = mid; else if(numbers[mid]<=numbers[end]) end = mid; } return numbers[end]; } int MidInOrder(int* numbers,int start,int end) { int mini = numbers[start]; for(int i = start;i<=end;i++) { if(mini>numbers[i]) mini = numbers[i]; } return mini; }
八、位运算问题
二进制中1的个数
题目描述：请实现一个函数，输入一个整数，输出该数二进制表示中的1的个数。例如：9的二进制是1001，由2个1.
解题思路：优解：我们可以先分析一下，把一个数减1，那么它的二进制数就会以它的第一个1为分界点，1变成0，然后1的前面保持不变，而1的后面的全部的数都变成了1。比如：9的二进制数是1001，那么，减去1后，变成了1000.
如果我们将还没减1的数按位与减1之后的数，那么就能统计出1的个数了，往后循环，直到变为0.
int NumberOf(int n) { int count = 0; while(n) { n = n&(n-1); count++; } return count; }
