数组中重复的数字（一维数组）
问题：在一个长度为长度为n的数组里的所有数字都在0-n-1之间。找出任意一个重复的数字，或者找出全部重复的数字。
这个题目的限制性非常大，一定要知道他想给答题人什么信息，这道题给答题人的信息是：如果没有重复的数字，那么排序后每个数字都在其本身下标的位置。
当使用哈希表的时候，每遍历一个数字，存进哈希表，key就是这个数字，在遍历下一个数字的时候，只用O(1)的时间复杂度就可以判断出来哈希表中有没有这个数。但是，整体的空间复杂度却是O(n)，我们应该尽量使空间复杂度变为O(1).（其实使用普通数组也没什么差别）。
解题思路：不用排序，从前往后遍历，当前数字如果和其下标数字是相等的，那么当前数字就是在正确的位置。否则，当前数字挪到正确的位置（a[a[i]]），在交换之前，先比较正确位置的这两个数字，如果相等，那就是重 复的，不相等，交换位置。
问题：在一个长度为n+1的数组里的所有数字都在1-n之间,所以至少有一个数字是重复的，在不破坏数组顺序的前提下，找出任意一个重复的数字，或者找出全部重复的数字。
像上边一样牺牲O(n)的空间复杂度。
解题思路：把1-n的数字从中间数字m分为两部分，前面一半为1m，后边一半为m+1n。如果1~m的数字个数超过m（整个数组中），那么一定有重复的数字，若不超过，另一半一定有重复的。然后继续把包含重复数字的区间一分为二，直到找到重复的数字。（类似于二分法查找，但是二分法查找是在有序前提下的）。
（2 3 5 4 3 2 6 7）这个序列首先找到重复的数字是3。
先是1-4,5-7这个范围，发现1-4范围有5个数，再分1-2,3-4,这个范围，发现1-2有两个数，虽然都是2，但是没问题。然后是3-4范围，有三个数，再看3-3这个范围，有两个，那么就确定3了。
int findDuplicate(vector<int>& nums) {
int len = nums.size();
if(len <= 1)
return 0;
int low = 0,high = len-1;
while(low <= high)
{
int count = 0;
int mid = (high+low)/2;
for(int i = 0;i < len;++i)
if(nums[i] <= mid)
count++;
if(low == high)//返回条件
return mid;
if(count > mid)
high = mid;
else
low = mid+1;
}
return 0;
}
在二维数组中查找
问题：在一个二维数组中，每一行按照从左到右递增的顺序排序，每一列按照从上到下递增的顺序排序。给定一个数字，判断数组中有没有这个数字。
1 2 7 8 9
2 4 8 12 13
4 7 10 13 15
6 8 11 15 20（可以试试找6）
我们平时做这道题，首先想的就是从左上角往右下角来确定区域，但是这种做法会求得两个区域，增加了题目的复杂性。
我们换个思路，从右上角开始查找，若比右上角数字大，那么一定在这一列的下边（排除这一行），若比右上角数字小，排除这一列。这样每次判断之后都只剩下一个区域。
bool find_num(int a[][],int m,int n,int num)//在这里，这种二维数组作为参数传递的方法是不正确的。
bool find_num(int （a)[5],int num)//平时是这样传的，定义一个指针数组（一个指针指向有五个整形元素的数组），int （a)[5]仅仅表示传进来的是一个地址，二维数组的地址还是连续的。二维数组的行数可以不知道，但是列必须知道。但是这还不满足本题要求。
void testshuzu(int (*a)[3],int m)
{
cout<<**(++a)<<endl;//4，表示a一下子移了3位。
cout<<a[1][2]<<endl;//6
cout<<a[0][1]<<endl;//2
}
int main()
{
int a[2][3] = {1,2,3,4,5,6};
testshuzu(a,3);
}
int a[4][3]={1,2,3,4,5,6,7,8,9,10,11,12};
cout<<*(*a+3)<<endl;//加1，指向2，加2，指向3，加3，指向4（换行了）
cout<<**(a+1)<<endl;//加1,指向4（第二行），加2，指向7（第三行）
cout<<*(*(a+1)+2)<<endl;//指向第二行的第三列
bool find_num(int *a,int m,int n,int num)//我们用指针来表示。m表示行数，n表示列数
{
int p = 0,q = n-1;//p是行，q是列（这个是从0开始的）
while(p < m && q >= 0)
{
if(num < a[p*n+q])
q = q-1;
else if(num > a[p*n+q])
{
p = p+1;
}
else
return true;
}
return false;
}
合并字符串
问题：请实现一个函数，把字符串中的每个空格替换成“%20”。例如：“we are happy.”，结果为“we%20are%20happy.”
最初我们想从前往后遍历这个字符串，当遇到空格，后边的统统后移两位，把当前位置和移出来的两位分别用“%20”代替。这样做虽然思路很简单，但是时间复杂度太高，如果都是空格，时间复杂度将是O(n^2)。
我们可以这样，首先计算出来字符串中有多少空格，一个空格需要增加两个空间。然后定义两个指针，一个指向增加空间后的末尾p2，一个指向原字符串的末尾p1（‘\0’处）。然后把p1值赋值给p2.遇到空格的话，p1往前移动一位，p2依次插入0 2 %之后也往前移动一位。直到二者汇合。
[图片上传失败...(image-ee70e0-1560665997322)]
有两个排序后的数组A1和A2，内存在A1末尾有足够多的空余空间容纳A2.请实现一个函数，把A2中的所有数字插入A1中，并且所有的数字都是排序的。
正常思维是在A1中从头到尾复制数字，这样需要移动多次，我们可以从后往前去复制。
在合并两个数组时，如果从前往后复制每个数字（字符），则需要重复移动数字（字符）多次，那么我们可以考虑从后往前复制，这样就能够减少移动次数，从而提高效率。
两个栈实现一个队列（有细节）
class Solution
{
public:
void push(int node) {
stack1.push(node);
return;
}
int pop() {
if(stack2.empty())//必须要做这个判断。
{
while(!stack1.empty())
{
stack2.push(stack1.top());
stack1.pop();
}
}
int num = stack2.top();
stack2.pop();
return num;
}
private:
stack<int> stack1;
stack<int> stack2;
};
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
使用递归。
void push(vector<int> &a,ListNode* head)
{
if(head == NULL)
return;
push(a,head->next);
a.push_back(head->val);
return;
}
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> result;
if(head == NULL)
return result;
push(result,head);
return result;
}
重建二叉树（知道先序和中序）（递归）
问题：先序：1 2 4 7 3 5 6 8.中序：4 7 2 1 5 3 8 6，重建二叉树。
[图片上传失败...(image-63d7f4-1560665997322)]
在先序遍历中，第一个数字总是树的根结点的值。由此在中序遍历中找到根结点，左边就是这个根结点的左子树，右边是这个根结点的右子树。
在左子树与右子树中，同样以这个方式来寻找根结点。（递归）
递归的边界条件就是：先序的开始结点与结束结点是同一个值。
TreeNode* CreateTree(int startpre,int endpre,int startvin,int endvin,const vector<int> &pre,const vector<int> &vin)
{
TreeNode *root = new TreeNode(0);
root->val = pre[startpre];
root->left = root->right = NULL;
int now = root->val;
if(startpre == endpre)//递归结束条件，先序的开始结点与结束结点是同一个值。
return root;
int i;
for(i = startvin;i <= endvin;++i)//寻找中序序列中的当前结点（先序第一个结点）
if(vin[i] == now)
break;
//计算根结点左边各个结点的位置。
int startvin_l = startvin;
int endvin_l = i-1;
int leftlen = endvin_l-startvin+1;
int startpre_l = startpre+1;
int endpre_l = startpre_l + leftlen-1;
//计算根结点右边各个结点的位置。
int rightlen = endvin - i;
int startpre_r = endpre_l+1;
int endpre_r = startpre_r + rightlen - 1;
int startvin_r = i +1;
int endvin_r = startvin_r + rightlen - 1;
if(startpre_l <= endpre_l && startvin_l<=endvin_l)//必不可少的条件，防止上边计算越界。
root->left = CreateTree(startpre_l,endpre_l,startvin_l,endvin_l,pre,vin);
if(startpre_r <= endpre_r && startvin_r<=endvin_r)//必不可少的条件，防止上边计算越界。
root->right = CreateTree(startpre_r,endpre_r,startvin_r,endvin_r,pre,vin);
return root;
}
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
int len1 = pre.size();
int len2 = vin.size();
if(len1 <= 0 || len2 <= 0 || len1 != len2)
return NULL;
return CreateTree(0,len1-1,0,len2-1,pre,vin);
}
二叉树的序列化（面试题37）
问题：给定二叉树，得到其结点序列，然后通过这个序列再把二叉树构造出来。
分析：如果使用上一题的方法，那么二叉树中所有的结点都互不相同才可以。所以我们可以遍历二叉树，如果遇到NULL结点就用特殊字符表示，然后根据这个序列再构建二叉树。
void getSer(TreeNode* root,vector<int> &result)
{
if(!root)
{
result.push_back('$');//碰到NULL用这个
return;
}
result.push_back(root->val);
getSer(root->left,result);
getSer(root->right,result);
return;
}
char* Serialize(TreeNode *root) {//返回char* 的方法。
vector<int> result;
getSer(root,result);
int len = result.size();
int* a = new int[len];
for(int i = 0;i < len;++i)
a[i] = result[i];
return (char*)a;
}
TreeNode* dfs2(int* &p) {//注意传引用
if(*p=='$') {
p++;
return NULL;
}
TreeNode* res=new TreeNode(*p);
p++;
res->left=dfs2(p);
res->right=dfs2(p);
return res;
}
TreeNode* Deserialize(char *str) {
int *p=(int*)str;
return dfs2(p);
}
二叉树下一个结点
问题：给定一颗二叉树和其中一个结点，如何找到中序遍历的下一个结点？这棵树除了有指向左右子树的指针外，还有指向父结点的指针。
平时思考：进行中序遍历然后找到下一个结点，这样做时间复杂度较高，而且会做很多无用功。
我们针对于这个结点来看，分两种情况：
有右子树：下一个结点就是右子树最左边结点。
没有右子树：再分两种情况讨论：
这个结点是其父结点的左子树：下一个结点就是其父结点。
这个结点是其父结点的右子树：往上找根，直到这个根是其父结点的左子结点，那么下一个结点就是这个根的父结点。
其实上边这两个条件在判断的时候可以归结为1个，即从当前开始（包括当前结点），求含有左子结点的结点。
BinaryTreeNode* Getnext(BinaryTreeNode* pNode)
{
if(pNode == NULL)
return NULL;
BinaryTreeNode *result = NULL;
if(pNode->right != NULL)//有右子树
{
result = pNode->right;
while(result->left != NULL)
{
result = result->left;
}
return result;
}
else if(pNode->parent != NULL)//没有右子树但是有父结点
{
BinaryTreeNode* pCurrent = pNode;//注意，此时pCurrent与pNode完全一样
BinaryTreeNode* pParent = pNode->parent;
while(pParent != NULL && pCurrent == pParent->right)//当前结点有父结点而且当前结点是父结点的右子结点，合并了上述所说的条件，减少编程。
{
pCurrent = pParent;
pParent = pParent->parent;
}
result = pParent;
return result;
}
else//没有右子树没有父结点
return NULL;
}
斐波那契数列
写一个函数，输入n，求斐波那契数列第n项。（也可以是上楼梯的问题、或者小矩形覆盖大矩形的问题）
斐波那契数列：n == 0时，f(n) = 0，n == 1时，f(n) = 1,n > 1时，f(n) = f(n-1) + f(n-2).
提到斐波那契数列，我们往往会想到使用递归：
long long Fibonacci(unsigned int n)
{
if(n <= 0)
return 0;
if(n == 1)
return 1;
return Fibonacci(n-1) + Fibonacci(n-2);//思考与上边的递归不同之处。
}
但是这样做时间复杂度并不是最小的。所以说递归是一种简单但是时间复杂度较高的一种方法。下边是时间复杂度更少的方法：
long long Fibonacciii(unsigned int n)
{
if(n <= 0)
return 0;
if(n == 1)
return 1;
int a = 0,b = 1,result;
for(int i = 2;i <= n;++i)
{
result = a+b;
a = b;
b = result;
}
return result;
}
把数字翻译成字符串有几种不同的翻译方法
问题：例如，12258有5种不同的翻译，bccfi,bwfi,bczi,mcfi,mzi。
分析：可以使用斐波那契数列，但是是有条件的斐波那契数列。
int GetTranslationCounttt(int num)
{
string num_str = to_string(num);
int len = num_str.length();
if(len <= 0)
return 0;
if(len == 1)
return 1;
string temp;
int result[len];
result[0] = 1;
//temp += num_str[0];temp += num_str[1];
temp = num_str.substr(0,2);
if(stoi(temp) < 26)//有条件的斐波那契
result[1] = 2;
else
result[1] = 1;
temp.clear();
if(len == 2)
return result[1];
for(int i = 2;i < len;++i)
{
//temp += num_str[i-1];temp += num_str[i];
temp = num_str.substr(i-1,2);
if(stoi(temp) < 26)
result[i] = result[i-1] + result[i-2];
else
result[i] = result[i-1];
temp.clear();
//cout<<result[i]<<endl;
}
return result[len-1];
}
旋转数组的最小数字
问题：有一个递增序列，把前边的一段移到后边，求这个序列中最小的数字。比如1 2 3 4 5 ----- 3 4 5 1 2
一般情况下我们会遍历一遍数组，找到最小数字，但是我们还可以使用更少的时间去寻找。
提及有序序列的查找，我们应该想到折半查找的方法。折半查找时间复杂度是O(logn)。这个问题中我们可以将数组看成两个递增序列。
1.low = 0，high = n-1.if(a[mid] >= a[low])，mid位于前边的的递增序列，此时low = mid;
if(a[mid] <= a[high])，mid位于后边的递增序列。此时high = mid;
最终，low和high将相邻，而且最小数字为high。
2.还有一种情况是把排序数组的前边0个元素移到后边，即还是原来那个数组，上述情况将不再适用，我们可以更改判断条件为：
a[mid] >= a[low] && a[mid] <= a[high]，这是上边两个条件同时出现的情况。
3.还有一种情况没有被考虑到，即a[low] == a[high] == a[mid]。比如说 1 0 1 1 1和1 1 1 0 1情况。无法判断mid位于前边还是后边递增序列的情况，我们只好使用顺序查找方法。
int Binary_Search(int *a,int n)
{
if(n == 0)
return NULL;
if(n == 1)
return a[0];
int low = 0,high = n-1,mid = (low + high) / 2;
if(a[low] == a[high] && a[low] == a[mid])//无法判断mid位于前边还是后边递增序列的情况，我们只好使用顺序查找方法。
{
mid = a[0];
for(int i = 0;i < n;++i)
if(a[i] < mid)
mid = a[i];
return mid;
}
if(a[mid] >= a[low] && a[mid] <= a[high])//把排序数组前边的0个元素搬到最后面，即排序数组本身情况。（下边的方法不适合）
return a[0];
while(low < high && high-low > 1)
{
mid = (low + high) / 2;
if(a[mid] >= a[low])//mid位于前边的的递增序列
low = mid;
if(a[mid] <= a[high])//mid位于后边的递增序列
high = mid;
}
return a[high];
}
回溯法
问题：三行四列的矩阵，是否包含一条“bfce”这样一个字符串的路径。求可以从矩阵中任意一格开始，每一步可以往上下左右四个方向移动。
a b t g
c f c s
j d e h
回溯法一般都是使用递归实现的。注意一点，如果找c的时候先移动到了f左边那个，那么将找不到e，还得回到f。就这样一个过程。
bool hasPathCore(const char* a,int rows,int cols,int row,int col,const char* str,int& pathLength,bool* visited)
{
if(str[pathLength] == '\0')
return true;
bool hasPath = false;
if(row >= 0 && row < rows && col >= 0 && col < cols && a[row*cols+col] == str[pathLength] && !visited[row*cols+col])
{
++pathLength;
visited[row*cols+col] = true;//将这一格标记位true
hasPath = hasPathCore(a,rows,cols,row,col-1,str,pathLength,visited) || //如果是需要的字符，那么递归下去。如果不是，返回false，上一层接着进行众多或运算中的下一个 hasPathCore(a,rows,cols,row-1,col,str,pathLength,visited) ||
hasPathCore(a,rows,cols,row,col+1,str,pathLength,visited) ||
hasPathCore(a,rows,cols,row+1,col,str,pathLength,visited);
if(hasPath == false) //如果四个方向的字符都不是需要的，那么返回false，进行上一层的另一个方向。返回false 使得上一层的或操作不会被停止。
{
--pathLength;
visited[row*cols+col] = false;
}
}
return hasPath;
}
bool hasPath(char* a,int rows,int cols,char* str)
{
if(a == NULL || rows < 1 || cols < 1 || str == NULL)
return false;
bool *visited = new bool[rows*cols];//定义这个标记位是因为路径不能重复进入矩阵的格子。（比如从b到f后，不能再回到b）
memset(visited,0,rows*cols);
int pathLength = 0;
for(int row = 0;row < rows;++row)
for(int col = 0;col < cols;++col)
if(hasPathCore(a,rows,cols,row,col,str,pathLength,visited))//使用这样一个循环是因为有可能有多个str[0]这个字符，而第一个可能走不通。
return true;
delete[] visited;
return false;
}
问题：有m行n列的方格，一个机器人从坐标（0,0）的格子开始移动，每次可以向上下左右四个方向移动一格，但是不能进入行坐标和列坐标数位之和大于k的格子。求这个机器人能够到达多少个格子。
这个题目我没有用回溯法，定义一个标记数组，如果能进入到这个位置，相应标记数组置为true，然后试从某一点开始能达到的所有的位置。
int getDigitSum(int num)
{
int sum = 0;
while(num)
{
sum += num % 10;
num /= 10;
}
return sum;
}
bool check(int threashold,int rows,int row,int cols,int col,bool* visited)
{
if(row >= 0 && row < rows && col >= 0 && col < cols && getDigitSum(row)+getDigitSum(col) <= threshold && !visited[row*cols+col])
return true;
return false;
}
void countNum(int threshold, int rows, int cols,int row,int col,bool* visited)
{
if(!check(threshold,rows,row,cols,col,visited))
return;
visited[row*cols+col] = true;
countNum(threshold,rows,cols,row+1,col,visited);
countNum(threshold,rows,cols,row-1,col,visited);
countNum(threshold,rows,cols,row,col+1,visited);
countNum(threshold,rows,cols,row,col-1,visited);
return;
}
int movingCount(int threshold, int rows, int cols)
{
if(threshold < 0)
return 0;
int count = 0;
bool *visited = new bool[rows*cols];
memset(visited,0,rows*cols);
countNum(threshold,rows,cols,0,0,visited);
for(int i = 0;i < rows*cols;++i)
if(visited(i))
count++;
delete[] visited;
return count;
}
位运算
右移：当原先的数为正数，则右移n位后在最左边补上n个0
当原先的数为负数，则右移n位后在最左边补上n个1
左移：不管原先的数为正数还是负数，左移n位后右边补上n个0.
问题：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。比如9，输出2.
初见这个题目会想到将其转换成二进制再计算，但是这样比下面这种方法还low
int findNumOf1(int n)
{
bool flag = false;
if(n < 0)
{
n = -n;
flag = true;
}
int result = 0;
while(n)
{
if(n % 2 == 1)
result++;
n /= 2;
}
return result+(flag?1:0);
}
上边这种方法做了/和%运算，这种运算的效率要远远低于位运算。所以我们更改为
while(n)
{
if(n & 1)//（一个数与1与运算能够判断其为奇数还是偶数）但是注意，n为偶数的时候，n&1 == 0不成立
result++;
n = n >> 1;
}
但是在n<0情况下，n>>2会使得前边两位补上1，这样会进入死循环（我们上边先判断是否为负的方法效率太低）。
所以我们考虑不对n进行移位，而对要与n进行与运算的数进行移位来判断n的位是不是1
unsigned int flag = 1;//32位
while(flag)//利用这种方法，不管n是几，循环都要进行32次。flag到 1000 0000 0000 0000 0000 0000 0000 0000之后再左移，就会变成0（32位下）
{
if(n & flag)
result++;
flag = flag << 1;
}
我们还需要注意一点，例如-4，其二进制为 1111 1111 1111 1111 1111 1111 1111 1100，即有30个1
在计算机中，负数是以原码的补码形式存在的。
正数：原码 = 反码 = 补码
负数：补码 = 反码+1.
4的原码：0000 0000 0000 0000 0000 0000 0000 0100
-4原码： 1000 0000 0000 0000 0000 0000 0000 0100（正数的原码改变符号位）
-4反码： 1111 1111 1111 1111 1111 1111 1111 1011（除符号位之外，其他都取反）
-4补码： 1111 1111 1111 1111 1111 1111 1111 1100（反码+1）
上述方法还存在弊端，我们可以对“始终进行32次循环”进行优化。
有这样一种说法：把一个整数减去1，再和原整数进行与运算，会把原整数最右边的1变成0。（解决二进制多数问题的思路）
int findNumOf1(int n)
{
int result = 0;
while(n)
{
n = n&(n-1);
result++;
}
return result;
}
^是异或运算 2^3 = 1；
数值的整数次方
问题：实现函数double Power(double base,int exponent),求base的exponent次方。
这个题目主要考察我们对问题考虑的全面性。exponent为负的情况、base == 0而且exponent为负的情况（无意义）、0的0次方情况（不存在）。
const float EPSINON =1e-6;
double Power(double base,int exponent)
{
if(base >= -EPSINON && base <= EPSINON && exponent < 0)//base == 0而且exponent为负的情况（无意义）
{
cout<<"wrong input"<<endl;
return 0;
}
if(exponent == 0)
return 1;
bool negative = false;
double result = 1.0;
if(exponent < 0)//exponent为负的情况
{
negative = true;
exponent = -exponent;
}
while(exponent)
{
result = result * base;
exponent--;
}
return(negative?(1.0/result):result);
}
当指数确定为正数或者0的时候，可以使用递归来优化算法。
如果输入的指数为32，我们可以求指数为16情况，进而求指数为8情况，然后是4、2、1；减少计算量。
double Power(double base,unsigned int exponent)
{
if(exponent == 0)
return 1;
if(exponent == 1)
return base;
double result = Power(base,exponent>>1);
result = result * result;
if(exponent&1 == 1)//指数为奇数的情况，多乘一个base
result = result*base;
return result;
}
打印从1到最大的n位数
问题：输入数字n，按顺序打印出从1到最大的n位十进制数。比如输入3，打印出1.2.3....999
分析：重点是要知道个位数是一直在加的。
void print_func(string s)//比如000034，只输出34
{
int m = s.length();
int i,j;
for(i = 0;i < m;++i)
{
if(s[i] != '0')
break;
}
for(j = i;j < m;++j)
cout<<s[j];
cout<<endl;
}
void Add1(int n)
{
if(n == 0)
return;
if(n == 1)
{
for(int i = 1;i < 10;++i)
cout<<i<<endl;
return;
}
string s;
for (int i = 0; i < n; ++i)
s += '0';
bool overflow = false;//判断第一位数有没有被进位（超过范围）
int len = n;
while (true)
{
if (s[len - 1] < '9')//最后一位一直在加
{
s[len - 1]++;
print_func(s);//防止前边的0输出来
}
else
{
s[len - 1] = '0';
for (int i = len - 2; i >= 0; --i)//从倒数第二个往前判断哪一位应该被加上1
{
if (s[i] < '9')//不用继续往前进位了
{
s[i]++;
break;
}
if (s[i] == '9')
{
if (i == 0)//如果第一位是9，就可以退出了
{
overflow = true;
break;
}
s[i] = '0';
continue;
}
}
if (!overflow)
print_func(s);//输出10、20、30。。。100.。。1000。。。
}
if (overflow)//跳出整个while循环
break;
}
}
删除链表中的结点（o(1)的空间复杂度，给定头结点指针和要删除结点指针）
我们知道，要删除一个结点，必须知道这个结点的前一个结点。要以o(1)的时间复杂度删除结点，可以将后一个结点的值复制给要删除的结点，然后删除要删除的结点的后一个结点。
除此之外还要考虑要删除的结点是尾结点和链表只有一个结点的情况。
1.当链表只有一个结点的时候，需要把指向这个结点的指针delete之后然后置空（任何情况下删除都是这样），头结点指针也需要置空。
2.当要删除的链表是尾结点的时候，没有办法复制后一个结点的值，所以只能从头开始遍历。（若直接使其等于NULL，则没有办法delet要删除的结点）。
删除链表中重复的结点
例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
分析：题目中是不包含头结点的链表，但是当第一个结点也是重复结点的时候，我们需要知道第一个结点的前驱结点，这个时候可以新建一个结点作为头结点，然后循环去删除重复的结点。
ListNode* deleteDuplication(ListNode* pHead)
{
if(pHead == NULL || pHead->next == NULL)
return pHead;
ListNode* pre = new ListNode(0);//新建一个结点作为头结点
pre->next = pHead;
ListNode* p = pHead;
ListNode* q = pHead->next;
ListNode* start_dele = NULL;
ListNode* temp;//指向要删除的结点
ListNode* result = pre;
bool flag = false;
while(p!= NULL && q != NULL)//遍历整个链表
{
flag = false;
while (q != NULL && (p->val == q->val))//如果存在相同值的结点，我们进行标记并删除
{
flag = true;
q = q->next;
}
if(flag)
{
start_dele = p;
p = q;
if(q != NULL)
q = q->next;
pre->next = p;
while(start_dele != p)//删除相同结点
{
temp = start_dele;
start_dele = start_dele->next;
delete temp;
}
}
if(!flag)//没有相同结点，pre、p、q指针后移
{
p = p->next;
q = q->next;
pre = pre->next;
}
}
ListNode* ret_result;
ret_result = result->next;
delete result;
return ret_result;
}
};
正则表达式
问题：请实现一个函数用来匹配包含‘.’和‘’的正则表达式。模式中的‘.’表示可以匹配任何字符，而‘’表示它前面的字符可以出现任意次（包括0次），匹配是指字符串所有字符匹配整个模式。
例如 aaa与a.a和abaca匹配，与aa.a和ab*a不匹配。
分析：当模式中的第二个字符不是*的时候，情况很简单，遍历就可以。
当模式中的第二个字符是*的时候，如果当前str与当前pattern匹配，我们有三种选择：*前字符只使用一次||*前字符使用多次||*前字符不使用
如果当前str与当前pattern不匹配，只有一种选择：*前字符不使用
用递归更清晰，且必须使用递归：（简单递归） 递归返回值中使用||意味着从前往后试一次，直到试出返回值为true的
bool matchCore(char* str,char* pattern)
{
if(*str == '\0' && *pattern == '\0')
return true;
if(*str != '\0' && *pattern == '\0')
return false;
if(*(pattern+1) == '*')//必须先判断下一个字符是不是*的情况，不满足再判断下边if
{
if(*pattern == *str || (*pattern == '.' && *str != '\0'))//下一个是*且当前匹配
return matchCore(str+1,pattern+2) || matchCore(str+1,pattern) || matchCore(str,pattern+2);
//*前字符只使用一次||*前字符使用多次||*前字符不使用
else//下一个是*且当前不匹配
return matchCore(str,pattern+2);//*前字符不使用
}
if(*str == *pattern || (*pattern == '.'&& *str != '\0'))
return matchCore(str+1,pattern+1);
return false;
}
bool match(char* str,char* pattern)
{
if(str == NULL || pattern == NULL)
return false;
return matchCore(str,pattern);
}
判断字符串能否表示数值
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。小数点前边后边都可以没有数字。
分析：初见这道题，我们可能想到从前往后遍历，但是这样过于复杂。要知道，表示数值的字符串包括整数部分、小数部分、指数部分，我们可以将一个字符串分成这三部分，然后分别对其判断是否符合条件。
整数部分：以‘+’或者‘-’或者数字开头而且其余都是数字
小数部分：以‘.’开头，其余都是数字
指数部分：以‘E’或者‘e’开头。其余都是整数部分（可以以‘+’或者‘-’或者数字开头而且其余都是数字）。
bool scanUnsignedInteger(const char** str)//必须使用指向指针的指针，否则这个函数执行后，isNumeric函数中string指针不会后移
{
const char* before = *str;
while(**str != '\0' && **str >= '0' && **str <= '9')
++(*str);
return *str > before;
}
//判断整数部分
bool scanInteger(const char** str)//必须使用指向指针的指针，否则这个函数执行后，isNumeric函数中string指针不会后移
{
if(**str == '+' || **str == '-')
++(*str);
return scanUnsignedInteger(str);
}
bool isNumeric(const char* string)
{
if(string == NULL)
return false;
bool numeric = scanInteger(&string);//判断小数点前边的整数部分
if(*string == '.')
{
++string;
numeric = scanUnsignedInteger(&string) || numeric;// || numeric是因为小数点后边且e前边可以没有数字
}
if(*string == 'E' || *string == 'e')//判断e后边的整数部分
{
++string;
numeric = numeric&&scanInteger(&string);
}
return numeric && *string == '\0';
}
调整数组顺序使奇数位于偶数前边
问题：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
分析：如果没有红色字体的要求，我们可以定义两个指针一个指向开始一个指向最后，若开始指针指的是偶数而且最后指针指向的是奇数，交换位置。直到最后指针位于开始指针前边。
当有红色要求时，我们按照常规解法：遍历数组，遇到偶数，后边元素前移一位，最后一位放遍历到的偶数元素。
但是这样有两点需要特别注意：1.当前移后，还得从当前位置遍历，因为前移后当前位置没有被遍历。2.遍历次数为奇数个数次，不然会掉入无限循环，因为到最后剩下的都是偶数。
void reOrderArray(vector<int> &array) {
int len = array.size();
int temp,num = 0;
for(int i = 0;i < len;++i)
if(array[i]&1)
num++;
for(int i = 0;i < num;++i)//只遍历奇数个数次
{
if(!(array[i]&1))
{
temp = array[i];
for(int j = i;j < len-1;++j)
array[j] = array[j+1];
array[len-1] = temp;
i--;//还得从当前位置开始便利
}
else
continue;
}
return;
}
链表中倒数第k个结点
问题：输入一个链表，输出该链表中倒数第k个结点。
分析：若想只遍历一次链表，可以定义两个指针，只一个指针先指向正数第k个结点，然后第二个指针从头开始，当第一个指针指向最后一个非空结点的时候，第二个指针指向的就是要求的结点。但是，我们还要注意一些细节：k的取值问题，如果k等于0或者k大于链表长度，都需要返回NULL（代码的鲁棒性），否则在运行测试用例的时候会掉入无限循环。
扩展：如果想求链表中间节点，还可以设置两个指针，一个一次走两位，一个一次走一位。
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if(pListHead == NULL || k == 0)
return pListHead;
ListNode* p = pListHead;
for(int i = 1;i < k;++i)
{
if(p->next != NULL)//防止k大于链表长度从而掉入无限循环
p = p->next;
else
return NULL;
}
ListNode* q = pListHead;
while(p->next)
{
p = p->next;
q = q->next;
}
return q;
}
链表中环的入口结点
问题：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
分析：如果有环，我们利用快慢指针，如果指针相遇，说明存在环，两个指针相遇的结点一定在环中。然后计算这个环包含多少个结点（假设n个），重新让两个指针指向头结点，其中一个前进n位，然后两个指针一起走（一次走一个），相遇结点就是入口结点。如果没有环，在利用快慢指针的时候就不可能结束循环，这时候我们在快慢指针走后判断是否指向空（为空就是有环）。
ListNode* EntryNodeOfLoop(ListNode* pHead){
if(pHead == NULL || pHead->next == NULL)
return NULL;
ListNode* p = pHead;
ListNode* q = p;
if(p->next->next)
q = p->next->next;
else
return NULL;
while(p != q){
p = p->next;
q = q->next;
if(p == NULL || q == NULL)
return NULL;
}
int circle_num = 1;
p = p->next;
while(p != q){
circle_num++;
p = p->next;
}
p = q = pHead;
while(circle_num){
q = q->next;
circle_num--;
}
while(p != q){
p = p->next;
q = q->next;
}
return p;
}
两个链表的第一个公共节点
问题：输入两个链表，找出它们的第一个公共结点。
分析，先计算两个链表的长度n1和n2，然后定义两个指针分别指向两个链表的表头，长度长的那个链表先走abs(n1-n2),然后一起走，相等的那个结点就是公共结点。
在求二叉树两个结点的最近公共结点时，如果有指向父结点的指针存在，那么就可以转化成这个问题。
反转单链表
定义前驱结点（记住指向），当前结点，以及下一个结点（改变当前结点指向后还能够知道下一个结点是谁）。
ListNode* ReverseList(ListNode* pHead) {
if(pHead == NULL || pHead->next == NULL)
return pHead;
ListNode* pre = NULL;
ListNode* now = pHead;
ListNode* next = now->next;
while(now)
{
now->next = pre;
pre = now;
now = next;
next = next->next;
if(next == NULL)//防止当next为空时，又一次next->next
{
now->next = pre;
break;
}
}
return now;
递归写法：
ListNode* reverse(ListNode* current,ListNode* pre)
{
if(current == NULL)
return pre;
ListNode* next = current->next;
current->next = pre;
return reverse(next,current);
}
ListNode* reverseList(ListNode* head) {
return reverse(head,NULL);
}
合并两个有序的链表
问题：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == NULL)
return l2;
if(l2 == NULL)
return l1;
ListNode* head;
if(l1->val < l2->val)
{
head = l1;
head->next = mergeTwoLists(l1->next,l2);
}
else
{
head = l2;
head->next = mergeTwoLists(l1,l2->next);
}
return head;
}
判断两个二叉树是否相同
问题：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
分析：我们可以先通过遍历算法从A中寻找与B根结点值一样的结点，存入一个vector，然后从这个vector中依次拿出一个结点作为根结点与B进行比较。问题的核心是如何比较两个二叉树。下边这个算法是比较二叉树p中是否包含二叉树q。
bool FST_TWO(TreeNode* p,TreeNode* q)
{
if(p == NULL && q != NULL)
return false;
if(q == NULL)//q为null，不管p是不是空都为真
return true;
if(p->val != q->val)
return false;
else
return(FST_TWO(p->left,q->left)&&FST_TWO(p->right,q->right));
}
或者：
bool FST_TWO(TreeNode* p,TreeNode* q)
{
if(p == NULL && q != NULL)
return false;
if(q == NULL)//q为null，不管p是不是空都为真
return true;
if(p->val != q->val)
return false;
bool a = FST_TWO(p->left,q->left);
bool b = FST_TWO(p->right,q->right);
return a&&b;
}
所以，当问题转化为判断两个二叉树是否相等的时候：
bool FST_TWO(TreeNode* p,TreeNode* q)
{
if(p == NULL && q == NULL)
return true;
if(p == NULL && q != NULL)
return false;
if(q == NULL && p != NULL)
return false;
if(p->val != q->val)
return false;
else
return(FST_TWO(p->left,q->left)&&FST_TWO(p->right,q->right));
}
二叉搜索树的后序遍历序列
问题：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
分析：后序遍历的二叉树中，最后一个结点一定是头结点。前边比头结点小的是左子树，比头结点大的是右子树。遍历前边结点，若发现比头结点大的，作为分界点，从这个分界点开始向后遍历（一直到头结点前），一旦发现比头结点小的，一定不是二叉搜索树的后序遍历。
bool check(vector<int> s,int m,int n){
int root = a[n];
int i,j;
for(i = m;i <= n-1;++i){
if(s[i] > root)
break;
}
for(j = i;j <= n-1;++j){
if(s[j] < root)
return false;
}
return true;
bool left = true,right = true;//必须先初始化，因为有可能只有左子树或者只有右子树。当没有左（右）子树的时候，不能判定为false。
if(i > m)
left = check(s,m,i-1);
if(i < n)
right = check(s,i,n-1);
return (left && right);
}
bool VerifySquenceOfBST(vector<int> sequence) {
int len = sequence.size();
if(len == 0)
return false;
if(len == 1 || len == 2)
return true;
return (check(sequence,0,len-1));
}
二叉树的镜像
[图片上传失败...(image-726f06-1560665997323)]
分析：要求二叉树的镜像，需要交换二叉树的左右子树，可以用遍历的方法交换。
void Mirror(TreeNode *pRoot) {
if(pRoot == NULL)
return;
TreeNode* temp;
temp = pRoot->left;
pRoot->left = pRoot->right;
pRoot->right = temp;
Mirror(pRoot->left);
Mirror(pRoot->right);
}
对称的二叉树（联系上上上题）
问题：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
分析：如果二叉树的每一位结点值都是不相同的，那么我们可以使用中序遍历，中序遍历结果是对称的，那么二叉树就是对称的，但是这种方法又不适合用于所有结点值都是相同的情况。需要知道：对称二叉树的根左右与根右左序列是完全一样的，而且还需要吧null值一起比较（针对结点值全部相同的情况）。
bool check(TreeNode* p,TreeNode* q)
{
if(p == NULL && q == NULL)//对null也进行比较
return true;
if(p == NULL && q != NULL)//对null也进行比较
return false;
if(p != NULL && q == NULL)//对null也进行比较
return false;
if(p->val != q->val)
return false;
bool a = check(p->left,q->right);//联系上上题。
bool b = check(p->right,q->left);
return a&&b;
}
bool isSymmetrical(TreeNode* pRoot)
{
if(pRoot == NULL || (pRoot->left == NULL && pRoot->right == NULL))
return true;
if((pRoot->left == NULL && pRoot->right != NULL) || (pRoot->left != NULL && pRoot->right == NULL))
return false;
return(check(pRoot,pRoot));
}
二叉树中和为某一值的路径
问题：输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
注意，temp传引用与不传引用都一样。
void findPathCore(TreeNode* root,int expectNumber,vector<int> temp,vector<vector<int>> &result)
{
if(root == NULL)
return;
temp.push_back(root->val);
if(expectNumber == root->val && root->left == NULL && root->right == NULL)
{
result.push_back(temp);
}
if(expectNumber < 0)
return;
findPathCore(root->left,expectNumber-root->val,temp,result);
findPathCore(root->right,expectNumber-root->val,temp,result);
temp.pop_back();
}
vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
vector<vector<int>> result;
vector<int> temp;
findPathCore(root,expectNumber,temp,result);
return result;
}
二叉搜索树转为双向链表
问题：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
分析：中序遍历为从小到大的数。树中指向左子结点的指针调整为链表中指向前一个结点的指针，指向右子结点的指针调整为链表中指向后一个结点的指针。最后寻找头结点。注意中间传递的是引用，特别是pre结点（因为每次pre结点的指向是要改变的）。
void trans(TreeNode **p,TreeNode **pre)
{
if(*p == nullptr)
return;
TreeNode *p_cur = *p;
trans(&p_cur->left,pre);
p_cur->left = *pre;//当前结点左指针指向上一个结点，最开始为传进来的pre，为nullptr
if(*pre != nullptr)
(*pre)->right = p_cur;//上一个结点右指针指向当前结点
*pre = p_cur;//在遍历右子树之前，更新上一个结点
trans(&p_cur->right,pre);
}
TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree == nullptr || (pRootOfTree->left == nullptr && pRootOfTree->right == nullptr))
return pRootOfTree;
TreeNode* p = pRootOfTree;
TreeNode* pre = nullptr;
trans(&p,&pre);
p = pre;
while(p != nullptr && p->left != nullptr)//令p指向链表开头
p = p->left;
return p;
}
之字形打印二叉树
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
分析：将每次进入队列的元素逆置，但是不是在队列中逆置，而是在读出队列后的vector中逆置。和普通层次遍历二叉树不同的是多了一个for循环，这个for循环将每一行的元素装入vector。
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>> result;
if(pRoot == NULL)
return result;
deque<TreeNode *> q;
q.push_back(pRoot);
bool rever = false;
vector<int> temp;
while(!q.empty())
{
int size = q.size();
for(int i = 0;i < size;++i)//和普通层次遍历二叉树不同的是多了一个for循环
{
TreeNode* out = q.front();
q.pop_front();
temp.push_back(out->val);
if(out->left)
q.push_back(out->left);
if(out->right)
q.push_back(out->right);
}
if(rever)
reverse(temp.begin(),temp.end());
rever = !rever;
result.push_back(temp);
temp.clear();
}
return result;
}
