# 剑指offer-刷题总结

## 01.二维数组中的查找

```class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
if(0==array.size())
return false;
int raw=array.size();
int col=array[0].size();
for(int i=0;i<raw;++i){
if(array[i][col-1]>=target){
for(int j=0;j<col;++j){
if(array[i][j]==target)
return true;
}
}
}
return false;
}
};```

## 02.替换空格

```class Solution {
public:
void replaceSpace(char *str,int length) {
if(length<=0)
return;
int origin_length=0,new_length=0,space_num=0;
for(int i=0;str[i]!='\0';++i){
origin_length++;
if(str[i]==' ')
space_num++;
}
new_length=origin_length+2*space_num;
if(new_length>length)
return;
str[new_length]='\0';
while(origin_length>0){
--origin_length;
if(str[origin_length]==' '){
str[--new_length]='0';
str[--new_length]='2';
str[--new_length]='%';
}
else{
str[--new_length]=str[origin_length];
}
}
}
};```

## 03.从尾到头打印链表

```/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
vector<int> res;
return res;
stack<int> istack;
}
while(!istack.empty()){
res.push_back(istack.top());
istack.pop();
}
return res;
}
};```

## 04.重建二叉树

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.empty() || pre.size()!=vin.size())
return nullptr;
vector<int> pre1,pre2,vin1,vin2;
TreeNode* root=new TreeNode(pre[0]);
int i=0;
for(;i<vin.size();++i){
if(pre[0]==vin[i])
break;
}
//不需要判断i ==0 或者i==vin.size()-1的情况
for(int j=0;j<i;++j){
pre1.push_back(pre[1+j]);
vin1.push_back(vin[j]);
}
for(int j=i+1;j<pre.size();++j){
pre2.push_back(pre[j]);
vin2.push_back(vin[j]);
}
root->left=reConstructBinaryTree(pre1,vin1);
root->right=reConstructBinaryTree(pre2,vin2);
return root;
}
};```

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* recurse(vector<int>& pre,int begin1,int end1,vector<int >& vin,int begin2,int end2){
if(begin1>end1 || begin2>end2)  //退出条件
return nullptr;
TreeNode* root=new TreeNode(pre[begin1]);
for(int i=begin2;i<=end2;++i){
if(pre[begin1]==vin[i]){
root->left=recurse(pre,begin1+1,begin1+i-begin2,vin,begin2,i-1);  //递归的重点，这个要考虑清楚
root->right=recurse(pre,begin1+1+i-begin2,end1,vin,1+i,end2);
break;
}
}
return root;
}
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.empty() || pre.size()!=vin.size())
return nullptr;
return recurse(pre,0,pre.size()-1,vin,0,vin.size()-1);
}
};```

## 05.用两个栈实现队列

```class Solution
{
public:
void push(int node) {
stack1.push(node);
}

int pop() {
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.top());
stack1.pop();
}
}
int top=stack2.top();
stack2.pop();
}

private:
stack<int> stack1;
stack<int> stack2;
};```

## 06.旋转数组的最小数字

```class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if(0==rotateArray.size()){
return 0;
}
int begin=0,end=rotateArray.size()-1;
while(begin<end-1){
int mid=begin+(end-begin)/2;
if(rotateArray[begin]<rotateArray[mid])
begin=mid;
else if(rotateArray[begin]>rotateArray[mid])
end=mid;
else{
int res=begin;
for(size_t i=1;i<rotateArray.size();++i){
res=(res<rotateArray[i]?res:rotateArray[i]);
}
return res;
}
}
return rotateArray[end];
}
};```

## 07.斐波那契数列

```class Solution {
public:
int Fibonacci(int n) {
if(n==0)
return 0;
if(n==1||n==2)
return 1;
int first=1,second=1,res=0;
while(--n>1){
res=first+second;
first=second;
second=res;
}
return res;
}
};```

## 08.跳台阶

```class Solution {
public:
int jumpFloor(int number) {
if(number<=2)
return number;
int first=1,second=2,res=0;
while(--number>1){
res=first+second;
first=second;
second=res;
}
return res;
}
};```

## 09.变态跳台阶

```f(n)=f(1)+f(2)+...+f(n-1)
f(n+1)=f(1)+f(2)+...+f(n-1)+f(n)=2f(n)
//代码如下：
class Solution {
public:
int jumpFloorII(int number) {
if(number<=2)
return number;
int res=2;
while(--number>=2){
res*=2;
}
return res;
}
};```

## 11.二进制中1的个数

```class Solution {
public:
int  NumberOf1(int n) {
int count=0;
while(n){
count++;
n=n&(n-1);
}
return count;
}
};```

## 12.数值的整数次方

```class Solution {
public:
double Power(double base, int exponent) {
bool flag=true;
if(exponent<0){
flag=false;
exponent*=-1;
}
double res=1;
while(exponent){
if(exponent&1){
res*=base;
exponent--;
}
else{
exponent=exponent/2;
res*=res;
}
}
return flag?res:(1/res);
}
};```

## 13.调整数组顺序使奇数位于偶数前面

```class Solution {
public:
void reOrderArray(vector<int> &array) {
if(array.empty())
return;
int begin=0,end=array.size();
int even=-1;

while(begin<end){
while((array[begin]&1) && (begin<end)){
begin++;
}
even=begin;
while((!(array[begin]&1))){
begin++;
}
if(begin>=end)
return;
int temp=array[begin];
while(even<begin){
array[begin]=array[begin-1];
begin--;
}
array[even]=temp;
}
}
};```

## 14.链表中倒数第k个结点

```/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
for(int i=0;i<k;++i){
if(!p1)
return nullptr;
p1=p1->next;
}
while(p1){
p1=p1->next;
}
}
};```

## 15.反转链表

```/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
//最开始的一版代码，采用的是栈，看起来比较复杂。
class Solution {
public:
stack<ListNode*> list_stack;
}
while(!list_stack.empty()){
list_stack.pop();
}
}
};

//采用在链表中的穿针引线。涉及到链表的断开与重连，维护三个指针，分别为：pre,cur,next
class Solution {
public:
ListNode* pre=nullptr;
while(cur){
ListNode* next=cur->next;
cur->next=pre;
pre=cur;
cur=next;
}
return pre;
}
};

//采用递归实现
class Solution {
public:

}
};```

## 16.合并两个排序的链表

```/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
{
//当一个链表为空时，直接返回另一个链表
}
else{
}
}
//另一个链表不为空时，加在后面
else
}
};
//采用递归实现
class Solution {
public:
{
}
else{
}
}
};```

## 17.树的子结构

```class Solution {
public:
bool dfs(TreeNode* pRoot1,TreeNode* pRoot2){
if(!pRoot2)    //注意不能先判断pRoot1再判断pRoot2，因为，只要pRoot2为空的时候，都是true了，而不管这时候pRoot1是不是为空。
return true;
if(!pRoot1)
return false;
if(pRoot1->val!=pRoot2->val)
return false;
return dfs(pRoot1->left,pRoot2->left)&&dfs(pRoot1->right,pRoot2->right);

}
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
if((!pRoot2)||(!pRoot1))
return false;
return (dfs(pRoot1,pRoot2)||HasSubtree(pRoot1->left,pRoot2)||HasSubtree(pRoot1->right,pRoot2));
}
};```

## 18.二叉树的镜像

```/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
void Mirror(TreeNode *pRoot) {
if(pRoot==nullptr)
return;
Mirror(pRoot->left);
Mirror(pRoot->right);
swap(pRoot->left,pRoot->right);
}
};```

## 20.包含min函数的栈

```class Solution {
public:
void push(int value) {
stk.push(value);
if(!stk_min.empty()){
if(value<stk_min.top())
stk_min.push(value);
else{
int temp=stk_min.top();
stk_min.push(temp);
}
}
else
stk_min.push(value);
}
void pop() {
stk_min.pop();
stk.pop();
}
int top() {
return stk.top();
}
int min() {
return stk_min.top();
}
private:
stack<int> stk;
stack<int> stk_min;
};```

## 21.栈的压入、弹出序列

```class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
stack<int> istack;
int i=0,j=0;
while(i<pushV.size()){
istack.push(pushV[i++]);
while(j<popV.size() && istack.top()==popV[j]){
istack.pop();
++j;
}
}
return istack.empty();
}
};```

## 22.从上往下打印二叉树

```/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> res;
if(root==nullptr)
return res;
queue<TreeNode*> ique;
ique.push(root);
while(!ique.empty()){
TreeNode* temp=ique.front();
res.push_back(temp->val);
ique.pop();

if(temp->left)
ique.push(temp->left);
if(temp->right)
ique.push(temp->right);
}
return res;
}
};```

## 23.二叉搜索树的后序遍历序列

```class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
return Verify(sequence,0,sequence.size());
}
bool Verify(vector<int> sequence,int start,int end){
int i=start;
if(start==end)
return false;
for(;i<end-1;++i){
if(sequence[i]>sequence[end-1]){
break;
}
}
for(int j=i;j!=end;++j){
if(sequence[j]<sequence[end-1]){
return false;
}
}
bool left=true;
if(i>start)
left=Verify(sequence,start,i);

bool right=true;
if(i<end-1)
right=Verify(sequence,i,end-1);
return left&&right;
}
};```

## 24.二叉树中和为某一值的路径

```class Solution {
public:
vector<vector<int>> res;
vector<int> temp;
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
if(!root)
return res;
temp.push_back(root->val);
if(expectNumber-root->val==0 && root->left==nullptr && root->right==nullptr)
res.push_back(temp);
FindPath(root->left,expectNumber-root->val);
FindPath(root->right,expectNumber-root->val);
if(!temp.empty())
temp.pop_back();
return res;
}
};```

## 25.复杂链表的复制

```        while(pHead->next){
cout<<pTemp->next->label<<endl;
}

//拆分
RandomListNode* pTemp=pNode->next;
while(pNode){
pNode->next=pTemp->next;
pNode=pNode->next;
pTemp->next=pNode?pNode->next:NULL;
//pTemp->next=pNode->next;
//cout<<"pTemp: "<<pTemp->label<<endl;
pTemp=pTemp->next;
//cout<<"text"<<endl;
}```
```class Solution {
public:
{

while(pNode){
RandomListNode* pClone=new RandomListNode(pNode->label);
pClone->next=pNode->next;
pNode->next=pClone;
pNode=pClone->next;
}

while(pNode){
RandomListNode* pClone=pNode->next;
if(pNode->random)
pClone->random=pNode->random->next;
pNode=pClone->next;
}

while(pNode->next){
RandomListNode* pTemp=pNode->next;
pNode->next=pTemp->next;
pNode=pTemp;
//			pNode=pNode->next;                  //这种不行，搞得我折腾了很久
//			pTemp->next=pNode->next;
}

}
};```

## 28.数组中出现次数超过一半的数字

```class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
if(numbers.empty())
return 0;
int count=1;
int num=numbers[0];
for(int i=1;i<numbers.size();++i){
if(numbers[i]==num)
count++;
else{
if((--count)<=0){
num=numbers[i];
count=1;
}
}
}
//判断结果是否符合条件
count=0;
for(int i=0;i<numbers.size();++i){
if(num==numbers[i]){
count++;
}
}
return count*2>numbers.size()?num:0;
}
};```

## 29.最小的K个数

```class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> min_stack;
if(input.empty()||(k<=0)||(k>input.size()))  //边界条件的判断
return min_stack;
for(int i=0;i<input.size();++i){
sort(min_stack.begin(),min_stack.end());
if(min_stack.size()<k){
min_stack.push_back(input[i]);

}
else{
//cout<<"min_stack[min_stack.size()-1]: "<<min_stack[min_stack.size()-1]<<endl;
if(input[i]<min_stack[min_stack.size()-1]){
min_stack.pop_back();
min_stack.push_back(input[i]);
}
}
}
return min_stack;
}
};```

## 30.连续子数组的最大和

```class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
int  res=array[0];
int cur=array[0];
for(int i=1;i<array.size();++i){
cur+=array[i];
if(cur<array[i])
cur=array[i];
res=(res>cur?res:cur);
}
return res;
}
};```

## 31.整数中1出现的次数（从1到n整数中1出现的次数）

```class Solution {
public:
int NumberOf1Between1AndN_Solution(int n)
{
int count=0;
//n=1的情况
if(n==1)
return 1;
//考虑的边界情况，n=10,100,1000之类的，同时循环中没有考虑n=0的情况
if(n>1&&n%10==0)
count++;
//没有考虑n=1的情况
for(int i=1;i<n;i*=10){
int a=n/i,b=n%i;
count+=(a+8)/10*i+(a%10==1)*(b+1);

}
return count;
}
};```

## 32.把数组排成最小的数

```class Solution
{
public:
static bool equal(int a,int b){
string str1=to_string(a)+to_string(b);
string str2=to_string(b)+to_string(a);
return str1<str2;
}
string PrintMinNumber(vector<int> numbers)
{
string result;
sort(numbers.begin(),numbers.end(),equal);
for(int i=0;i<numbers.size();++i){
result+=to_string(numbers[i]);
}
return result;
}
};```

## 33.丑数

```class Solution {
public:
int GetUglyNumber_Solution(int index) {
if(index<=0)
return 0;
vector<int > res(index);
res[0]=1;
int x=0,y=0,z=0;
for(int i=1;i<index;++i){
res[i]=min(2*res[x],min(3*res[y],5*res[z]));
if(res[i]==2*res[x])
x++;
if(res[i]==3*res[y])
y++;
if(res[i]==5*res[z])
z++;
}
return res[index-1];
}
};```

## 34.第一个只出现一次的字符位置

```class Solution
{
public:
int FirstNotRepeatingChar(string str)
{
if(str.size()<=0)
return -1;
int array[256]={0};
for(int i=0;i<str.size();++i){
array[int(str[i])]++;
}
for(int i=0;i<str.size();++i){
if(array[int(str[i])]==1)
return i;
}
return str.size();
}
};```

## 36.两个链表的第一个公共结点

```class Solution {
public:
while(p1!=p2){
}
return p1;
}
};```

## 37.数字在排序数组中出现的次数

1234567891011121314151617181920212223242526272829303132

class Solution {public: int GetNumberOfK(vector<int> data ,int k) { if(data.empty()) return 0; int begin=0,end=data.size()-1; int count=0; int mid; while(begin<=end){ mid=(begin+end)/2;// cout<<"dsdasads"<<endl; if(data[mid]==k) break; else if(data[mid]<k){ begin=mid+1; continue; } else if(data[mid]>k){ end=mid-1; continue; } } begin=end=mid; while(data[begin]==k) --begin; while(data[end]==k) ++end; count=(end-begin-1)>0?(end-begin-1):0; return count; }};

## 38.二叉树的深度

```class Solution {
public:
int TreeDepth(TreeNode* pRoot)
{
if(!pRoot)
return 0;
return max(1+TreeDepth(pRoot->left),1+TreeDepth(pRoot->right));
}
};```

## 40.数组中只出现一次的数字

```class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
if(data.empty())
return;
//第一次遍历一遍，求两个数字最后的异或
int res=data[0];
for(int i=1;i<data.size();++i){
res=res^data[i];
}
if(res==0)
return;
//由于存在两个只出现一次的数字，所以res的值为这两个数字的异或，因此肯定不为0，肯定不为0意味着肯定有一位是1.找出这一位是1的
int index=0;
while((res&1)==0){
res=res>>1;
index++;
}
*num1=*num2=0;
//根据index位为不为1，将数组分为两部分。
int x;
for(int i=0;i<data.size();++i){
if((x=data[i]>>index)&1)
*num1^=data[i];
else
{
*num2^=data[i];
}

}
}
};```

## 41.和为S的连续正数序列

```class Solution {
public:
vector<vector<int> > FindContinuousSequence(int sum) {
vector<vector<int>> res;
vector<int> temp;
//边界条件的判断
if(sum<0)
return res;

int end=0;
int tempSum=0;
//遍历数组
while(end<sum){
if(tempSum==sum){
res.push_back(temp);
end=temp[0];  //这一句其实很重要,因为要考虑将end从最开始重新开始计算，不然可能会有所遗漏,eg:9=2+3+4=4+5，其中4会重复
temp.erase(temp.begin(),temp.end());
tempSum=0;
continue;
}
if(tempSum>sum){
tempSum-=temp[0];
temp.erase(temp.begin());
continue;
}
temp.push_back(++end);
tempSum+=end;
}
return res;
}
};```

## 42.和为S的两个数字

```class Solution
{
public:
vector<int> FindNumbersWithSum(vector<int> array, int sum)
{
vector<int > res;
if(array.empty())
return res;

int i=0,j=array.size()-1;
while(i<j){
int temp=array[i]+array[j];
if(temp>sum)
--j;
if(temp<sum)
++i;

if(temp==sum)
{
res.push_back(array[i]);
res.push_back(array[j]);
return res;
}
}
return res;
}
};```

## 43.左旋转字符串

```//第一次通过代码
class Solution {
public:
string LeftRotateString(string str, int n) {
int len=str.size();
if(n>=len)
return str;
int i=0,j=0;
for(i=0,j=n-1;i<j;++i,--j){swap(str[i],str[j]);}
for(i=n,j=len-1;i<j;++i,--j){swap(str[i],str[j]);}
for(i=0,j=len-1;i<j;++i,--j){swap(str[i],str[j]);}
return str;
}
};```

## 44.翻转单词顺序列

```//以前买的
class Solution {
public:
void ReverseSentence(string &str,int begin,int end){
while(begin<end){
char tmp=str[begin];
str[begin]=str[end];
str[end]=tmp;
begin++;
end--;
}
}
string ReverseSentence(string str) {
if(str.size()<=1)
return str;
int begin=0;
int end=0;
//这里需要注意，考虑只有一个单词的情况
while(end!=str.size()){
if(str[end]==' '){
ReverseSentence(str,0,str.size()-1);
break;
}
else if(end==str.size()-1)
return str;
else
++end;
}
end=0;
//开始遍历，旋转每个单词
while(begin!=str.size()){
if(str[begin]==' '){
++end;
++begin;
}
else if(str[end]==' '||end==str.size()){
ReverseSentence(str,begin,--end);
begin=++end;
}
else
++end;
}
return str;
}
};```

## 45.扑克牌顺子

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何。为了方便起见,你可以认为大小王是0。

```class Solution
{
public:
bool IsContinuous(vector<int> numbers)
{
if (numbers.empty())
return false;
sort(numbers.begin(), numbers.end());
int sum = 0, zero_num = 0;
for (int i = 0; i < numbers.size() - 1; ++i)
{
if (numbers[i] == 0)
{
zero_num++;
continue;
}
//考虑数字重复的情况
if (numbers[i + 1] == numbers[i])
return false;
sum += numbers[i + 1] - numbers[i] - 1;
}
return sum <= zero_num; //注意这里要大于等于就可以，不一定等于
}
};```

## 46.孩子们的游戏(圆圈中最后剩下的数)

```class Solution {
public:
int LastRemaining_Solution(int n, int m)
{
if(n<=0)
return -1;
int last=0;
for(int i=2;i<=n;++i){
last=(last+m)%i;
}
return last;
}
};```

## 47.求1+2+3+…+n

```class Solution {
public:
int Sum_Solution(int n) {
int sum=n;
sum&&(sum+=Sum_Solution(n-1));
return sum;
}
};```

## 48.不用加减乘除做加法

```class Solution
{
public:
{
int res = num1 ^ num2, temp = num1 & num2;
while (temp != 0)
{
temp = temp << 1;
int t = res;  //暂存res,以避免res的值被改变
res ^= temp;
temp = temp & t;
}
return res;
}
};```

## 49.把字符串转换成整数

```class Solution
{
public:
int StrToInt(string str)
{
if (str.size() == 0)
return 0;
int flag = 1;
int size = str.size(), res = 0;
int i = 0;
if (str[0] == '-')
{
flag = -1;
i++;
}
else if (str[0] == '+')
{
i++;
}
for (; i < size; ++i)
{
if (str[i] <= '0' || str[i] >= '9')
{
return 0;
}
else
res = res * 10 + (str[i] - '0');
}
return flag * res;
}
};```

## 50.数组中重复的数字

```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)
{
for(int i=0;i<length;++i){
int index=numbers[i];
if(index>=length)
index=index-length;
if(numbers[index]>=length){
*duplication=index;
return true;
}
numbers[index]+=length;
}
return false;
}
};```

## 51.构建乘积数组

```class Solution {
public:
vector<int> multiply(const vector<int>& A) {
vector<int> res(A.size());
if(A.empty())
return res;
res[0]=1;
//计算下三角
for(int i=1;i<A.size();++i){
res[i]=res[i-1]*A[i-1];
}
int temp=1;
for(int i=A.size()-2;i>=0;--i){
temp*=A[i+1];
res[i]*=temp;
}
return res;
}
};```

## 53.表示数值的字符串

```/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
{

}
else
}
else{
prev=prev->next;
}

}
}
};```

## 54.字符流中第一个不重复的字符

```class Solution
{
public:
//Insert one char from stringstream
void Insert(char ch)
{
if(!array[ch])
ique.push(ch);
array[ch]++;
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
while(!ique.empty() && array[ique.front()]>1){
ique.pop();
}
if(!ique.empty())
return ique.front();
return '#';
}
private:
int array[256]={0};
queue<char> ique;
};```

## 55.链表中环的入口结点

```class Solution {
public:
{
return nullptr;
while(fast->next && slow){
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
break;
}
if(fast!=slow)
return nullptr;
while(fast!=slow){
fast=fast->next;
slow=slow->next;
}
return fast;
}
};```

## 56.删除链表中重复的结点

```//一个不通过的代码
class Solution {
public:
{
int temp;
while(cur && cur->next){
ListNode* next=cur->next;
if(cur->val==next->val){   //原因是这个相等的处理有问题，没有考虑一直是同一个值的处理
temp=cur->val;
cur=next->next;
pre->next=cur;
}
else if(next->val==temp){
cur->next=next->next;
pre->next=cur;
}
else{
if(next->next){
pre=cur;
cur=next;
//  next=next->next;
}
else
}
}
}
};
//一个通过了的代码
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
{
while(cur && cur->next){
ListNode* next=cur->next;
if(cur->val==next->val){
int val=cur->val;
while(cur && cur->val==val)  //一直遍历到不为当前值为止
cur=cur->next;
pre->next=cur;
cur=pre->next;
}
else{
pre=pre->next;
cur=cur->next;
}
}
}
};
//递归解决
class Solution {
public:
{
current=current->next;
return deleteDuplication(current);
}

else{
}
}
};```

70 篇文章14 人订阅

0 条评论

## 相关文章

18940

34720

14720

24820

### HashMap源码解析（JDK1.8）

1 package java.util; 2 3 import sun.misc.SharedSecrets; 4 5 imp...

37270

8920

21320

37780

29450

35590