数组中重复的数字
题目描述
在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
思路：
数组大小为n，数字范围为0~n-1,也就是说如果数组不重复，则排序后每个数组i上的元素就应该是i
为此，我们可以模拟这个排序的过程，如果i位置上的元素不为i，则把它与nums[i]位置的元素进行交换，这相当于把nums[i]放到他该去的地方。如果nums[i]位置的元素已经是i了，则这刚好就是重复的数字；否则将交换到i位置上的数字继续这个过程，如果交换过来的数等于i，则说明这个数放在了他应该放的地方，继续处理i+1上的数，如果仍然不等，则将这个换来的数放到他应该放的地方....最后，对于i位置来说，要么找到了值为i的元素，要么找到了重复的元素，是不可能出现无限循环的，因为无限循环要求换来的数字与i位置的数字相等，但这时候已经判定重复并跳出返回了。
class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int numbers[], int length, int* duplication) {
if(length<=1)
return false;
int p1=0;
while(p1<length)
{
if(numbers[p1]!=p1)
{
while(numbers[p1]!=p1)
{
int right=numbers[numbers[p1]];
if(numbers[p1]==right)
{
*duplication=right;
return true;
}
swap(numbers[numbers[p1]],numbers[p1]);
}
}
p1++;
}
return false;
}
void swap(int& a,int& b)
{
int tmp=a;
a=b;
b=tmp;
}
};
二维数组中的查找
题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：
一开始想用两次二分，这实际上是不可行的
比如:
7
[1,2,8,9]
[2,4,9,12]
[4,7,10,13]
[6,8,11,15]
实际上7并不是出现在第四行
问题出现在不能保证比数组头元素大的元素一定出现在这一行，不能保证上一行的某个元素一定会大于这一行的头元素，因为只能保证头元素大于上一行的头元素。对上一行的头元素来说相当于有两个递增方向。只有每行的头都大于上一行的尾，也就是严格单调递增时，可以这样写
实际上只要找到只有一个方向递增，一个方向递减的方向，从这个位置开始搜索，即相当于遍历一个有序数组。这个位置在左下角或右上角。左下角向右递增，向上递减；右上角向左递减，向下递增。
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
auto& nums=array;
if(nums.empty()||nums[0].empty())
return false;
int row=nums.size()-1;
int col=0;
while(row>=0&&col<nums[row].size())
{
if(nums[row][col]==target)
return true;
else if(nums[row][col]<target)
col++;
else
row--;
}
return false;
}
};
替换空格
题目描述
请实现一个函数，将一个字符串中的每个空格替换成“ ”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We Are Happy。
思路：
最优解当然是不适用空间复杂度
首先计算拓展后的空间大小，然后用2个指针指向2个尾，逐个进行复制。
唯一值得注意的是，由于传进来的是str,因此尾部要取'\0'的位置，因为也要把'\0'也拷进去。
因此2个尾部分别是：
int pLast=len+count*2; int pCur=len;
而不是
int pLast=len+count*2-1; int pCur=len-1;
虽然这一种也能实现，但少了个'\0',需要自己在补一个。
class Solution {
public:
void replaceSpace(char *str,int length) {
int len=length;
int count=0;
for(int i=0;i<len;i++)
{
if(str[i]==' ')
count++;
}
int pLast=len+count*2;
int pCur=len;
while(pCur>=0&&pLast>pCur)
{
if(str[pCur]!=' ')
{
str[pLast]=str[pCur];
pLast--;
}
else
{
str[pLast--]='0';
str[pLast--]='2';
str[pLast--]='%';
}
pCur--;
}
return ;
}
};
从尾到头打印链表
题目描述
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
思路：
最简单的就是push进vector后reverse,如果不用这种方式，递归也可以
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> ans;
if(!head)
return ans;
Core(ans,head);
return ans;
}
void Core(vector<int>& in,ListNode* head)
{
if(!head)
return;
Core(in,head->next);
in.push_back(head->val);
}
};
重建二叉树★★★
思路很清晰的题，但容易出错，多写几次注意下细节，特别是传参长度的处理。
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
要唯一的确定一个二叉树，必须知道两种遍历方式，且其中必须要有一个中序遍历，因为前序与后序只能分割出父与子的关系，而无法分割出左右子树的关系。
思路：
根据前序的第一个数，找到中序中的那个数的位置，然后将其分割为左右子树，相当于说前序提供父子关系，中序提供左右子树关系。
然后递归这个过程。
值得注意的是Core中的传参，其实只要前序的起点，中序的起点与长度就可以了，因为前序与中序的长度必须一致。如果每次传入前序的起点与终点，中序的起点与终点，则太复杂，也太麻烦。
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.empty()||pre.size()!=vin.size())
return NULL;
return reConstructCore(pre,vin,0,0,pre.size());
}
TreeNode* reConstructCore(vector<int>& pre,vector<int>& vin,int pstart,int vstart,int len)
{
if(len<=0)
return NULL;
int tmp=pre[pstart];
int pos=0;
for(;pos<len&&vin[pos+vstart]!=tmp;pos++);
pos+=vstart;
int left=pos-vstart;
int right=len-left-1;
TreeNode* root=new TreeNode(tmp);
root->left=reConstructCore(pre,vin,pstart+1,vstart,left);
root->right=reConstructCore(pre,vin,pstart+left+1,pos+1,right);
return root;
}
};
二叉树的下一个结点★★★
要考虑的情况很多，值得好好看看，体味下二叉树的结构
题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路：
其实就是分为多种情况：
1).当前节点是父亲节点的左子树时：
此时要遍历该节点的右子树：
如果右子树存在，则找到右子树根节点的最左边的一个节点
如果右子树不存在，以此点为根的树已经遍历完了，此时由于它是父节点的左子树，因此下一个应该遍历父节点
2).当前节点时父亲节点的右子树时：
此时要遍历该节点的右子树：
如果右子树存在，则找到右子树根节点的最左边的一个节点
如果右子树不存在，则不仅以此节点为根的的子树已经遍历完了，由于是父节点的右子树，相当于父节点也遍历完了；如果父节点是祖父节点的右子树，则相当于祖父节点也已经遍历完了。。。。。
因此要找到祖先节点中的某一个节点，该节点要么父亲节点时空，要么父亲节点的左子树的根就是这个节点。
当为选中的祖先节点的父节点为空，相当于已经遍历完了所有节点，返回NULL
如果非空，则相当于已经遍历完了该祖先节点父节点的左子树，此时应该返回该祖先的父亲节点。
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(!pNode)
return NULL;
return GetNextCore(pNode);
}
TreeLinkNode* GetNextCore(TreeLinkNode* node)
{
if(!node->next)
{
auto it=node->right;
if(!it)
return NULL;
while(it->left)
it=it->left;
return it;
}
auto pLast=node->next;
if(pLast->left==node)
{
if(node->right)
{
auto right=node->right;
while(right->left)
right=right->left;
return right;
}
else
return pLast;
}
else if(pLast->right==node)
{
if(node->right)
{
auto right=node->right;
while(right->left)
right=right->left;
return right;
}
else
{
while(pLast->next&&pLast->next->right==pLast)
pLast=pLast->next;
if(pLast->next==NULL)
return NULL;
else
return pLast->next;
}
}
else
return NULL;
}
};
这个分类讨论太多了，其实完全可以简化：
1).如果该节点存在右子树，则应该遍历右子树中的最左节点
2).如果不存在，则要找到某个节点，该节点是其父的左子节点（包括目前的这个节点）
这样就简化很多了
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(!pNode)
return NULL;
auto right=pNode->right;
if(right)
{
while(right->left)
right=right->left;
return right;
}
else
{
while(pNode->next&&pNode->next->right==pNode)
pNode=pNode->next;
if(pNode->next)
return pNode->next;
else
return NULL;
}
}
};
用两个栈实现队列
题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思路：
栈的特点是先入后出，队列的特点是先入先出
现在给了两个栈，其实可以想象成这样一个情景：
Tail和Head相当于两个水管，水从tail中流入，从Head中流出，这样实际上就相当于实现了队列
我们在Tail中灌水，就相当于push进数，然后pop提出最先灌进去的数，则从Head中读出。
如果Head现在是空，也就是说没有元素，则把Tail里的数全部转到Head中，当然顺序要变化，这也就相当于上图里用个管子把两个容器相连，然后把Tail底部的水抽到Head中
每次push都push到Tail中。
class Solution
{
public:
void push(int node) {
stack2.push(node);
}
int pop() {
if(!stack1.empty())
{
auto ans=stack1.top();
stack1.pop();
return ans;
}
else
{
if(stack2.empty())
return INT_MIN;
while(!stack2.empty())
{
stack1.push(stack2.top());
stack2.pop();
}
auto ans=stack1.top();
stack1.pop();
return ans;
}
}
private:
stack<int> stack1;//head
stack<int> stack2;//tail
};
用两个队列实现栈
两个队列：
某个队列pop到只剩一个元素，其他的元素PUSH到另一个队列。
一个队列：
push进后，将新元素前面的元素重新pop并push进队列。
矩形覆盖
题目描述我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，总共有多少种方法？
思路：
矩形可以横着摆与竖着摆，竖着摆时只能组成2x1;而横着摆可以用2个组成一个2X2
因此2*n的矩形可以来自于：2*(n-1)的矩形加一个2X1,或来自于2*(n-2)的矩形加两个横着摆的2x1
class Solution {
public:
int rectCover(int number) {
if(number<=0)
return 0;
if(number<2)
return number;
vector<int> dp(number,0);
dp[0]=1;
dp[1]=2;
for(int i=2;i<dp.size();i++)
dp[i]=dp[i-1]+dp[i-2];
return dp.back();
}
};
旋转数组的最小数字★★★★★
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
思路：
将数组分为两部分，左部分为旋转点右侧的所有元素，右部分为包括旋转点在内的旋转点前的所有元素。
使用二分查找的方法，当mid位于左部分时，l=mid+1;当位于右部分时，h=mid（
不减1是因为如果mid刚好指向旋转点，则减1则使h调到了左部分）
现在还有一个问题是如何判定mid位于左部分还是右部分，如果nums[mid]>nums[h]，则一定位于左部分;如果nums[mid]<nums[h]，则一定位于右部分.如果nums[mid]=nums[h]，则说不好。
因为如果是11101111，当0左与右都有1则无法判定到底是哪个部分
此时对h--，因为h--相当于缩减l与h的窗口，使重新计算的mid向左部分偏移，这个过程持续到直到nums[mid]>nums[h]或l=h（此时相当于l与h间都是同一种数字）
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
auto& nums=rotateArray;
if(nums.size()==0)
return 0;
int l=0;int h=nums.size()-1;
int mid=(l+h)/2;
while(l<h)
{
mid=(l+h)/2;
if(nums[mid]>nums[h])
l=mid+1;
else if(nums[mid]<nums[h])
h=mid;
else
h--;
}
return nums[h];
}
};
剪绳子★★★
题目描述把一根绳子剪成多段，并且使得每段的长度乘积最大。
思路：
切割绳子时，可以将它看做切成两半，然后每半部分再决定切不切
比如10，可以先切成4,6，由于已经切了一次了，因此4和6均可以选择继续切或者不切，这样就有四种情况，取其中最大值即可
class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n+1,0);
dp[0]=1;
dp[1]=1;
for(int i=2;i<dp.size();i++)
{
for(int j=1;j<=i-j;j++)
dp[i]=max(dp[i],max(dp[j],j)*max((i-j),dp[i-j]));
}
return dp.back();
}
};
二进制中 1 的个数
题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
思路：
1).用flag循环左移
由于负数的原因，用n右移会出现问题，因此对1个初值为1的数不断左移相与
class Solution {
public:
int NumberOf1(int n) {
int num=sizeof(n)*8;
int flag=1;
int count=0;
while(flag)
{
if((flag&n)==flag)
count++;
flag=flag<<1;
}
return count;
}
};
2).n&(n-1)会使n最右边一个1变为0
这是因为,当n最右边的数为1时，与n-1相与可以让n的最后一位从1变为0
如果n最右边一位为0,则n-1会使n最优边1个1变为0，而是这个1右侧的0全变为1，再与n相与，则那个1及它右侧全变为0.
这样n&(n-1)将不断使右边的1变为0，直到n==0;
class Solution {
public:
int NumberOf1(int n) {
int count=0;
while(n)
{
count++;
n&=n-1;
}
return count;
}
};
数值的整数次方★★★
题目描述给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent，求 base 的 exponent 次方。
思路：
如果每次只乘base则速度太慢，因此考虑每次进行平方，如果剩余的指数不足以平方，则递归剩余的指数，重复这个过程。
注意exponent为负数的情况，要先判断，最后用1.0去除
class Solution {
public:
double Power(double base, int exponent) {
if(!base)
return 0;
if(!exponent)
return 1;
bool flag=false;
if(exponent<0)
flag=true;//判断exponent为负数的情况
exponent=abs(exponent);
auto ans=PowerCore(base,exponent,base);
if(flag)
ans=1.0/ans;
return ans;
}
double PowerCore(double num,int exponent,double base)
{
if(!exponent)
return 1;
if(exponent==1)
return exponent*base;
int count=2;
while(count<=exponent)
{
num*=num;
exponent-=count;
count*=2;
}
return num*PowerCore(num,exponent,base);
}
};
打印从 1 到最大的 n 位数
题目描述输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数即999。
思路：
模拟加法过程，当最低位满足10进1时，通过while一直进位。
pCur用于跟踪最高位。
class Solution
{
public:
void display(int n)
{
if(!n)
return;
if(n==1)
{
for(int i=0;i<10;i++)
cout<<i<<endl;
return;
}
string str(n+1,'0');
int pCur=str.size()-1;
while(str[0]!='1')
{
cout<<str.data()+pCur<<endl;
if(str.back()=='9')
{
int p=str.size()-1;
while(str[p]=='9')
{
str[p]='0';
p--;
}
if(pCur-p==1)
pCur=p;
str[p]+=1;
}
else
str.back()+=1;
}
return;
}
};
删除链表中重复的结点★★★
题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
思路：
pCur指向的是无重复链表的最后一个节点，pre为pCur后一个节点，通过next找到第一个不与pre相等的节点，如果pre与next相邻，则说明无重复，否则令pCur指向next.
注意第一个元素就开始重复的情况，因此创建一个头节点。
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead)
{
if(!pHead)
return NULL;
if(!pHead->next)
return pHead;
ListNode* head=new ListNode(100);
head->next=pHead;
ListNode* pCur=head;
ListNode* pre=head->next;
while(pre)
{
ListNode* next=pre->next;
while(next&&next->val==pre->val)
next=next->next;
if(pre->next==next)
{
pCur=pre;
pre=next;
}
else
{
pCur->next=next;
pre=next;
}
}
return head->next;
}
};
正则表达式匹配★★★★★
题目描述请实现一个函数用来匹配包括 '.' 和 '*' 的正则表达式。模式中的字符 '.' 表示任意一个字符，而 '*' 表示它前面的字符可以出现任意次（包含 0 次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串 "aaa" 与模式 "a.a" 和 "ab*ac*a" 匹配，但是与"aa.a" 和 "ab*a" 均不匹配。
思路：
dp[i][j]表示主串0~i与模式串0~j是否匹配。
状态转移方程为：
1).s[i]==p[j]||[j]=='.':dp[i][j]=dp[i-1][j-1],即只要前i-1与前j-1相等，则匹配
2).s[i]!=p[j]:
a).p[j]!='*':此时p[j]与s[i]完全不等，则dp[i][j]=false;
b).p[j]='*':此时*可以使前面的字母为0个，1个或多个
当p[j-1]!=s[i]时，此时只能使他为0:dp[i][j]=dp[i][j-1];
当p[j-1]==s[i]时，此时可以使前面的字母为0个，1个或多个
为0个时：dp[i][j]=dp[i][j-1]
为1个时:dp[i][j]=dp[i-1][j-1]
为多个时：此时拿出一个前面的字母与s[i]匹配，因此主串还剩i-1个，但由于p[j]='*'且此时是会产生多个前面字母的情况，因此即使已经分出一个了，但还可能分出很多个，因此还是拿s的前i-1个与p的前j个来匹配，因为p[j]='*'，相当于他可以无限的拿出来。
举个例子：
s:###bbb
p:###b*
现在*与b不等，我们令*产生多个b的情况，此时先产生一个b与s的b消除：
s:###bb
p:###b*
而此时p串仍然为###b*,这时在令*产生一个b:
s:###b
p:###b*
此时再令*使前面的b为0个：
s:###
p:###
这样就匹配了
相当于说*产生多个p让他分步一步步来，而不是一下生产2个b
因此此时dp[i][j]=dp[i-1][j]
也就是说先拿出一个b与主串的消掉，然后将问题转换为dp[i-1][j]，如果剩下的i-1还有b，但这已经是dp[i-1][j]的问题了。
另外注意初始状态：
dp[0][i]，当p[i]='*'时，此时应该与dp[0][i-2]一致，也就是隐去i前面的一个
比如
s:""
p".*"
此时*将.隐去，而相当于dp[0][0]=true
class Solution {
public:
bool match(char* str, char* pattern)
{
string str1(str);
string str2(pattern);
vector<vector<bool>> dp(str1.size()+1,vector<bool>(str2.size()+1,false));
dp[0][0]=true;
if(str2[0]=='*')
return false;
for(int i=0;i<str2.size();i++)
{
if(str2[i]=='*')
dp[0][i+1]=dp[0][i-1];
}
for(int i=1;i<dp.size();i++)
{
for(int j=1;j<dp[i].size();j++)
{
if((str1[i-1]==str2[j-1])||(str2[j-1]=='.'))
dp[i][j]=dp[i-1][j-1];
else if(str2[j-1]=='*')
{
if(j==1)
return false;
if(str2[j-2]==str1[i-1]||str2[j-2]=='.')
dp[i][j]=dp[i][j-2]||dp[i-1][j-1]||dp[i-1][j];
else
dp[i][j]=dp[i][j-2];
}
}
}
return dp.back().back();
}
};
表示数值的字符串
题目描述
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
思路：
以e/E为分界线将整个数分为两部分：
左部分的数字部分可以为整数或者小数，+-只能出现在0,只能有一个'.'
右部分的数字部分只能是整数，+-只能出现在e后面一个位置，不能有'.'
class Solution {
public:
bool isNumeric(char* string)
{
char * str=string;
int p1=0;
while(p1<strlen(str)&&str[p1]!='e'&&str[p1]!='E')
p1++;
return isLeft(str,p1-1)&&isRight(str,p1+1);
}
bool isLeft(char* str,int end)
{
if(end<0)
return false;
int pointnum=0;
for(int i=0;i<=end;i++)
{
if((str[i]=='+'||str[i]=='-'))
{
if(i!=0)
return false;
continue;
}
if(str[i]=='.')
{
pointnum++;
if(pointnum==2)
return false;
continue;
}
if(str[i]<'0'||str[i]>'9')
return false;
}
return true;
}
bool isRight(char* str,int start)
{
if(start==strlen(str))
return false;
if(start>strlen(str))
return true;
int len=strlen(str);
for(int i=start;i<len;i++)
{
if((str[i]=='+'||str[i]=='-'))
{
if(i!=start)
return false;
continue;
}
if(str[i]<'0'||str[i]>'9')
return false;
}
return true;
}
};
调整数组顺序使奇数位于偶数前面★★★
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
思路：
每当找到一个奇数，就使用类似于冒泡的思想，将它放到前面。
while来找到一个位置j，这个位置的前面j-1是奇数，此时这个j就是插入位置.
class Solution {
public:
void reOrderArray(vector<int> &array) {
if(array.empty())
return;
vector<int>& nums=array;
for(int i=0;i<nums.size();i++)
{
int target=nums[i];
if(target&0x1)
{
int j=i;
while(j>0&&!(array[j-1]&0x1))//当j==0或j前面是奇数时停止
{
array[j]=array[j-1];
j--;
}
array[j]=target;
}
}
return;
}
};
链表中倒数第k个结点
题目描述
输入一个链表，输出该链表中倒数第k个结点
思路：
倒数第k个节点，比如倒数第一个节点，也就是最后一个节点，其领先NULL一个身位；倒数第二个领先2个身位。。。因此实际上只要先找到一个节点，其领先起点k个身位，则当这个节点走到NULL时，起点的那个指针也走到了倒数第k个节点的位置
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
ListNode* pNext=pListHead;
if(k<=0||!pListHead)
return NULL;
while(pNext&&k)
{
pNext=pNext->next;
k--;
}
if(k!=0)
return NULL;
ListNode* pCur=pListHead;
while(pNext)
{
pCur=pCur->next;
pNext=pNext->next;
}
return pCur;
}
};
链表中环的入口结点
题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
思路：
首先找到一个环内的节点，如果找不到，return NULL;
其次如果找到环内的节点了：假设这个链表由两部分组成，一部分为环，另一部分为一个链。
设环的周长为r,链的长为l，由于环会回到起点，也就是有l=l+r。因此如果让一个节点先走r的长度，则当他们相遇时，先走的节点走了l+r,而后走的节点走了l，这个l刚好就是环的入口
此外注意下slow-fast指针的写法。
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if(!pHead)
return NULL;
ListNode* p1=pHead;
ListNode* p2=pHead;
while(p2&&p2->next)
{
p1=p1->next;
p2=p2->next->next;
if(p1==p2)
break;
}
if(!p2||!p2->next)
return NULL;
p1=pHead;
auto tmp=p2;
do{
tmp=tmp->next;
p1=p1->next;
}while(tmp!=p2);
auto pCur=pHead;
while(pCur!=p1)
{
pCur=pCur->next;
p1=p1->next;
}
return pCur;
}
};
反转链表
题目描述
输入一个链表，反转链表后，输出新链表的表头。
思路：
两种方法：
最简单的：
头插法，不多说了。
其次：
使用三个指针pre,pCur,pNext;pre保存上一个节点，pCur保存当前节点，pNext保存下一个节点。
每次循环让pCur的next指向pre,然后更新pre为pCur,更新pCur为pNext;
头插法：
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if(!pHead)
return NULL;
ListNode* pCur=new ListNode(250);
while(pHead)
{
auto tmp=pHead->next;
pHead->next=pCur->next;
pCur->next=pHead;
pHead=tmp;
}
return pCur->next;
}
};
三指针：
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if(!pHead)
return NULL;
if(!pHead->next)
return pHead;
ListNode* pre=NULL;
ListNode* pCur=pHead;
ListNode* pNext=pHead->next;
while(pNext)
{
pNext=pCur->next;
pCur->next=pre;
pre=pCur;
pCur=pNext;
}
return pre;
}
};
合并两个排序的链表
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路：
小的加入新链表。
最后如果有链表还有剩则补进新链表
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if(!pHead1)
return pHead2;
if(!pHead2)
return pHead1;
ListNode* pHead=new ListNode(-1);
ListNode* pCur=pHead;
while(pHead1&&pHead2)
{
if(pHead1->val<pHead2->val)
{
auto tmp=pHead1->next;
pCur->next=pHead1;
pHead1->next=NULL;
pHead1=tmp;
}
else
{
auto tmp=pHead2->next;
pCur->next=pHead2;
pHead2->next=NULL;
pHead2=tmp;
}
pCur=pCur->next;
}
if(pHead1)
pCur->next=pHead1;
if(pHead2)
pCur->next=pHead2;
return pHead->next;
}
};
树的子结构★★★
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路：
递归
class Solution {
public:
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(!pRoot2||!pRoot1)
return false;
return HasSubtreeCore(pRoot1,pRoot2);
}
bool HasSubtreeCore(TreeNode* p1,TreeNode* p2)
{
if(!p1&&p2)
return false;
if(!p2)
return true;
if(p1->val==p2->val
&&HasSubtreeCore(p1->left,p2->left)//根相等且左右子树都是子结构
&&HasSubtreeCore(p1->right,p2->right))
return true;
return HasSubtreeCore(p1->left,p2)||HasSubtreeCore(p1->right,p2);
}
};
二叉树的镜像
题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。
思路：
。。。。
class Solution {
public:
void Mirror(TreeNode *pRoot) {
if(!pRoot)
return;
MirrorCore(pRoot);
}
void MirrorCore(TreeNode* root)
{
if(!root)
return;
MirrorCore(root->left);
MirrorCore(root->right);
auto tmp=root->right;
root->right=root->left;
root->left=tmp;
return;
}
};
对称的二叉树★★★
题目描述
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
思路：
isSymCore用来判断两个树是否对称相等，我们用这个来递归判断根的左子树与右子树。
递归中首先判断根是否相等，如果相等则判断这两个树的左与右和右与左的对称情况
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
if(!pRoot)
return true;
return isSymCore(pRoot->left,pRoot->right);
}
bool isSymCore(TreeNode* p1,TreeNode* p2)
{
if(!p1&&!p2)
return true;
if(p1&&!p2||p2&&!p1)
return false;
if(p1->val!=p2->val)
return false;
return isSymCore(p1->left,p2->right)&&isSymCore(p1->right,p2->left);
}
};
顺时针打印矩阵★★★★★
题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字
思路：
一开始想的太贪，想用一下模拟所有情况，实际上只剩一行或只剩一列的情况是要特殊考虑的。
r_num为当前轮次的行数，c_num为当前轮次的列数
class Solution {
public:
vector<int> printMatrix(vector<vector<int> > matrix) {
if(matrix.empty()||matrix[0].empty())
return vector<int> ();
int circle=0;
int r_num=matrix.size();
int c_num=matrix[0].size();
vector<int> ans;
while(r_num>0&&c_num>0)
{
if(r_num==1)
{
for(int i=0;i<c_num;i++)
ans.push_back(matrix[circle][circle+i]);
}
else if(c_num==1)
{
for(int i=0;i<r_num;i++)
ans.push_back(matrix[circle+i][circle]);
}
else
{
for(int i=0;i<c_num-1;i++)
ans.push_back(matrix[circle][circle+i]);
for(int i=0;i<r_num-1;i++)
ans.push_back(matrix[circle+i][circle+c_num-1]);
for(int i=0;i<c_num-1;i++)
ans.push_back(matrix[circle+r_num-1][circle+c_num-1-i]);
for(int i=0;i<r_num-1;i++)
ans.push_back(matrix[circle+r_num-1-i][circle]);
}
circle++;
r_num-=2;
c_num-=2;
}
return ans;
}
};
包含min函数的栈★★★
题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
思路：
由于栈会push与pop,这都会导致栈内元素出现变化：push可能push进一个更小的数，pop可能pop出最小的数。
因此不能只存当前最小的数，因为他可能被pop出去。
准备一个栈aux用于存放可能成为最小的数的数，当当前push进来的数小于aux栈顶元素时，这个元素将成为最小元素，因此要将他存进aux；而原来的栈顶元素，由于对新元素pop后原来的栈顶元素又将成为最小，因此要留下。
如果大于栈顶元素，则它不可能成为当前栈内的最小元素，且即使pop出去也不会影响最小元素，因此不入aux.
由于aux与min栈不是完全相等的，因此如果要判断min pop出去的元素是不是aux的栈顶元素，只能在aux中存放索引而不是值。
class Solution {
public:
void push(int value) {
nums.push_back(value);
if(nums.size()==1)
{
aux.push(0);
return;
}
auto tmp=aux.top();
if(value<nums[tmp])
aux.push(nums.size()-1);
}
void pop() {
if(nums.empty())
return;
auto idx=nums.size()-1;
nums.pop_back();
if(idx==aux.top())
aux.pop();
}
int top() {
if(nums.empty())
return INT_MIN;
return nums.back();
}
int min() {
if(nums.empty())
return INT_MIN;
return nums[aux.top()];
}
private:
vector<int> nums;
stack<int> aux;
};
栈的压入、弹出序列★★
题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。
思路：
模拟压入与弹出的过程，用一个栈aux,push到栈顶等于popV中的某个元素。如果无法达到则return false。
然后aux.pop;p2++。相当于找下一个出栈的元素。
如果最后栈内空，说明可以实行，return true.
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
if(pushV.size()!=popV.size())
return false;
if(pushV.empty())
return true;
int p1=0;int p2=0;
stack<int> aux;
while(p2<popV.size())
{
while(p1<popV.size()&&(aux.empty()||aux.top()!=popV[p2]))//1 2 3 4 5 ;4 5 3 2 1
{
aux.push(pushV[p1]);
p1++;
}
if(p1>=pushV.size()&&aux.top()!=popV[p2])
{
return false;
}
aux.pop();
p2++;
}
if(aux.empty())
return true;
else
return false;
}
};
从上往下打印二叉树
题目描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
思路：
层次遍历。。。
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
if(!root)
return vector<int>();
queue<TreeNode*> aux;
aux.push(root);
vector<int> ans;
while(!aux.empty())
{
ans.push_back(aux.front()->val);
auto tmp=aux.front();
aux.pop();
if(tmp->left)
aux.push(tmp->left);
if(tmp->right)
aux.push(tmp->right);
}
return ans;
}
};
把二叉树打印成多行
题目描述
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
思路：
count记录每一层的节点个数。tmp记录下一层的节点个数，当这一层的pop完毕后，count=tmp,即进入下一层。
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
if(!pRoot)
return vector<vector<int>>();
queue<TreeNode*> aux;
int count=1;
aux.push(pRoot);
vector<vector<int>> ans;
while(!aux.empty())
{
int tmp=0;
vector<int> in;
while(count)
{
in.push_back(aux.front()->val);
if(aux.front()->left)
{
aux.push(aux.front()->left);
tmp++;
}
if(aux.front()->right)
{
aux.push(aux.front()->right);
tmp++;
}
aux.pop();
count--;
}
count=tmp;
ans.push_back(in);
}
return ans;
}
};
按之字形顺序打印二叉树★★★★
题目描述
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
思路：
分解成多个问题：
1.层次遍历
2.要记录每一层的个数
3.要求之字形打印
首先层次遍历想到用队列，其次要分层打印，因此还要一个count记录当前层数量。
最后由于要之字型打印：
也就是说如果这一层从左到右，则下一层则要从右到左，此时可以考虑，在push子节点时，先push进一个栈，这样再从栈里push进队列时，就是从右到左了
当要求下一层从右到左时，应该先push左，在push右，这样栈里才会是右->左
而当要求下一层从左到右时，应该先push右，在push左，这样栈里才会是左->右
因此还要加入一个flag,用于不同情况下的左右的顺序
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>> ans;
if(!pRoot)
return ans;
int count=1;
queue<TreeNode*> aux;
stack<TreeNode*> carry;
aux.push(pRoot);
int flag=1;
while(!aux.empty())
{
int tmp=0;
vector<int> val;
while(count)
{
val.push_back(aux.front()->val);
auto first=(flag==1)?aux.front()->left:aux.front()->right;
auto second=(flag==1)?aux.front()->right:aux.front()->left;
if(first)
{
carry.push(first);
tmp++;
}
if(second)
{
carry.push(second);
tmp++;
}
count--;
aux.pop();
}
while(!carry.empty())
{
aux.push(carry.top());
carry.pop();
}
flag=-flag;
count=tmp;
ans.push_back(val);
}
return ans;
}
};
二叉搜索树的后序遍历序列★★★★
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路：
首先，后序遍历代表根节点在尾部。
其次，二叉搜索树代表左右子树可以根据根节点的大小分开。
要确定是否为后序遍历，有两个地方:
1.两个子树也要是二叉搜索树
2.尾部的节点要比左子树中所有树大，比右子树中所有树小。
因此：
首先找到尾部节点，根据尾部节点的值把左子树分割出来，然后看看剩余的数里有没有比根节点小的，如果有则说明不是二叉搜索树。
然后递归左子树与右子树，如果都是二叉搜索树的后序遍历，则return true.
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if(sequence.empty())
return false;
return VerifyBSTCore(sequence,0,sequence.size());
}
bool VerifyBSTCore(vector<int>& nums,int start,int len)
{
if(len<=1)
return true;
int val=nums[start+len-1];
int i=0;
for(;i<len&&nums[start+i]<val;i++);
int left=i;
for(;i<len&&nums[start+i]>=val;i++);
if(i!=len)
return false;
return VerifyBSTCore(nums,start,left)&&VerifyBSTCore(nums,left,len-left-1);
}
};
转载于:https://www.cnblogs.com/lxy-xf/p/11516404.html
