目录

1. 数组中重复的数字2. 二维数组中的查找3. 替换空格4. 从尾到头打印链表5. 重建二叉树6. 二叉树的下一个结点7. 用两个栈实现队列8. 斐波那契数列9.矩形覆盖10. 跳台阶11. 变态跳台阶动态规划数学推倒 12.旋转数组的最小数字13.矩阵中的路径14.机器人的运动范围15.剪绳子动态规划贪心 16.数值的整数次方17.删除链表中重复的结点18. 正则表达式匹配19. 表示数值的字符串20. 调整数组顺序使奇数位于偶数前面21. 链表中倒数第k个结点22.链表中环的入口结点23. 顺时针打印矩阵24包含min函数的栈25.栈的压入、弹出序列26.从上往下打印二叉树27. 把二叉树打印成多行28.按之字形顺序打印二叉树29.二叉搜索树的后序遍历序列30.二叉树中和为某一值的路径31.复杂链表的复制32.二叉搜索树与双向链表33.序列化二叉树34.数组中出现次数超过一半的数字35.字符串的排列36.最小的K个数排序partition最小堆

1. 数组中重复的数字

数组中重复的数字

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(numbers==NULL||length<=0) return false; for(int i=0;i<length;++i){ while(numbers[i]!=i){ if(numbers[i]==numbers[numbers[i]]){ *duplication=numbers[i]; return true; } swap(numbers,i,numbers[i]); } } return false; } void swap(int nums[],int i,int j){ int temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; } };

2. 二维数组中的查找

二维数组中的查找

class Solution { public: bool Find(int target, vector<vector<int> > array) { if(array.size()!=0){ int row=0,col=array[0].size()-1; while(row<int(array.size())&&col>=0){ if(array[row][col]==target) return true; else if(array[row][col]>target) --col; else ++row; } } return false; } };

3. 替换空格

替换空格

class Solution { public: void replaceSpace(char *str,int length) { if(str==NULL) return; int iCountofblanks=0; int iOriginalLengths=0; for(int i=0;str[i]!='\0';++i){ ++iOriginalLengths; if(str[i]==' ') ++iCountofblanks; } int iLen=iOriginalLengths+2*iCountofblanks; if(iLen+1>length) return; int iP1=iOriginalLengths,iP2=iLen; while(iP1<iP2){ if(str[iP1]==' '){ str[iP2--]='0'; str[iP2--]='2'; str[iP2--]='%'; } else{ str[iP2--]=str[iP1]; } --iP1; } } };

4. 从尾到头打印链表

从尾到头打印链表

class Solution { public: void replaceSpace(char *str,int length) { if(str==NULL) return; int iCountofblanks=0; int iOriginalLengths=0; for(int i=0;str[i]!='\0';++i){ ++iOriginalLengths; if(str[i]==' ') ++iCountofblanks; } int iLen=iOriginalLengths+2*iCountofblanks; if(iLen+1>length) return; int iP1=iOriginalLengths,iP2=iLen; while(iP1<iP2){ if(str[iP1]==' '){ str[iP2--]='0'; str[iP2--]='2'; str[iP2--]='%'; } else{ str[iP2--]=str[iP1]; } --iP1; } } };

5. 重建二叉树

重建二叉树

/** * 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()) return NULL; vector<int> leftpre,leftvin,rightpre,rightvin; auto iterator_p1=pre.begin(); auto iterator_p2=vin.begin(); TreeNode* head(new TreeNode(*iterator_p1++)); while(*iterator_p2!=head->val){ leftpre.push_back(*iterator_p1++); leftvin.push_back(*iterator_p2++); } iterator_p2++; while(iterator_p2!=vin.end()){ rightpre.push_back(*iterator_p1++); rightvin.push_back(*iterator_p2++); } head->left=reConstructBinaryTree(leftpre,leftvin); head->right=reConstructBinaryTree(rightpre,rightvin); return head; } };

6. 二叉树的下一个结点

二叉树的下一个结点

/* struct TreeLinkNode { int val; struct TreeLinkNode *left; struct TreeLinkNode *right; struct TreeLinkNode *next; TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) { } }; */ class Solution { public: TreeLinkNode* GetNext(TreeLinkNode* pNode) { if(pNode->right!=NULL){ TreeLinkNode* next=pNode->right; if(next->left!=NULL){ next=next->left; } return next; } else{ while(pNode->next!=NULL){ TreeLinkNode* parent=pNode->next; if(parent->left==pNode) return parent; pNode=parent; } } return NULL; } };

7. 用两个栈实现队列

用两个栈实现队列

class Solution { public: void push(int node) { while(!stack2.empty()){ stack1.push(stack2.top()); stack2.pop(); } stack1.push(node); } int pop() { while(!stack1.empty()){ stack2.push(stack1.top()); stack1.pop(); } int a=stack2.top(); stack2.pop(); return a; } private: stack<int> stack1; stack<int> stack2; };

8. 斐波那契数列

斐波那契数列

class Solution { public: Solution(){ fib[0]=0; fib[1]=1; for(int i=2;i<len;++i){ fib[i]=fib[i-2]+fib[i-1]; } } int Fibonacci(int n) { return fib[n]; } private: int len=40; int *fib=new int[len]; };

9.矩形覆盖

矩形覆盖

class Solution { public: int rectCover(int number) { if(number<3) return number; int pre1=2,pre2=1,result=0; for(int i=3;i<=number;++i){ result=pre2+pre1; pre2=pre1; pre1=result; } return result; } };

10. 跳台阶

跳台阶

class Solution { public: int jumpFloor(int number) { if(number<3) return number; int pre1=2,pre2=1,result=0; for(int i=3;i<=number;++i){ result=pre2+pre1; pre2=pre1; pre1=result; } return result; } };

11. 变态跳台阶

变态跳台阶

动态规划

class Solution { public: int jumpFloorII(int number) { int* temp=new int[number](); for(int i=0;i<number;++i){ temp[i]=1; for(int j=0;j<i;++j){ temp[i]+=temp[j]; } } return temp[number-1]; } };

数学推倒

class Solution { public: int jumpFloorII(int number) { return pow(2,number-1); } };

12.旋转数组的最小数字

旋转数组的最小数字

class Solution { public: int minNumberInRotateArray(vector<int> rotateArray) { if(rotateArray.empty()) return 0; int l=0,h=rotateArray.size()-1; while(l<h){ int m=(l+h)/2; if(rotateArray[m]<rotateArray[h]) h=m; else l=m+1; } return rotateArray[l]; } };

矩阵中的路径

13.矩阵中的路径

矩阵中的路径

class Solution { int next[4][2]={{0,-1},{0,1},{-1,0},{1,0}}; int trows; int tcols; bool backcompare(char* matrix,bool* marked,char* str,int num,int i,int j){ if(str[num]=='\0') return true; if(i<0||i>=trows||j<0||j>=tcols||marked[i*tcols+j]||matrix[i*tcols+j]!=str[num]) return false; marked[i*tcols+j]=true; for(int* a:next){ if(backcompare(matrix,marked,str,num+1,i+a[0],j+a[1])) return true; } marked[i*tcols+j]=false; return false; } public: bool hasPath(char* matrix, int rows, int cols, char* str) { if(rows==0||cols==0) return false; trows=rows; tcols=cols; bool* marked=new bool[trows*tcols]{false}; for(int r=0;r<trows;++r){ for(int c=0;c<tcols;++c){ if(backcompare(matrix,marked,str,0,r,c)) return true; } } delete[] marked; return false; } };

14.机器人的运动范围

机器人的运动范围

class Solution { public: int next[4][2]={{0,-1},{0,1},{-1,0},{1,0}}; int trows; int tcols; int tthreshold; int *sum_array; int cnt=0; public: int movingCount(int threshold, int rows, int cols) { trows=rows; tthreshold=threshold; tcols=cols; form_sum_array(); //建立一个rows*cols大小的数组，初始化为false bool *marked=new bool[rows*cols]{false}; DFS(marked,0,0); return cnt; } void form_sum_array(){ sum_array=new int[std::max(trows,tcols)+1]; for(int i=0;i<std::max(trows,tcols);++i){ int n=i; while(n>0){ sum_array[i]+=n%10; n=n/10; } } } void DFS(bool *marked,int r,int c){ if(r<0||r>=trows||c<0||c>=tcols||marked[r*tcols+c]) return; marked[r*tcols+c]=true; if(sum_array[r]+sum_array[c]>tthreshold) return; cnt++; for(auto i : next){ DFS(marked,r+i[0],c+i[1]); } } };

15.剪绳子

剪绳子

动态规划

class Solution { int *maxinteger; public: int integerBreak(int n) { maxinteger=new int[n+1]{0}; maxinteger[1]=1; for(int i=2;i<=n;++i){ for(int j=1;j<i;++j){ maxinteger[i]=std::max(maxinteger[i],std::max(j*(i-j),maxinteger[i]*((i-j)))); } } return maxinteger[n]; } };

贪心

class Solution { public: int integerBreak(int n) { if(n<2) return 0; if(n==2) return 1; if(n==3) return 2; int timesof3=n/3; if(n%3==1) timesof3--; int timesof2=(n-timesof3*3)/2; return pow(3,timesof3)*pow(2,timesof2); } };

16.数值的整数次方

数值的整数次方

class Solution { public: double Power(double base, int exponent) { if(exponent==0) return 1; if(exponent==1) return base; bool negative=false; if(exponent<0){ negative=true; exponent=-exponent; } double pow=Power(base*base,exponent/2); if(exponent%2!=0) pow=base*pow; return negative?1/pow:pow; } };

17.删除链表中重复的结点

链接

class Solution { public: ListNode* deleteDuplication(ListNode* pHead) { if(pHead==NULL||pHead->next==NULL) return pHead; ListNode *nex=pHead->next; if(pHead->val==nex->val){ while(nex!=NULL&&pHead->val==nex->val) nex=nex->next; return deleteDuplication(nex); }else{ pHead->next=deleteDuplication(nex); return pHead; } return pHead; } };

18. 正则表达式匹配

链接

class Solution { public: bool match(char* str, char* pattern) { if(str==NULL||pattern==NULL) return false; int stridx=0,patidx=0; patlen=countsize(pattern); strglen=countsize(str); return matchcore(str,stridx,pattern,patidx); } bool matchcore(char* str,int stridx,char* pattern,int patidx){ if(stridx==strglen&&patidx==patlen) return true; if(patidx==patlen&&stridx<strglen) return false; if(patidx+1<patlen&&pattern[patidx+1]=='*'){ if(stridx!=strglen&&(str[stridx]==pattern[patidx]||pattern[patidx]=='.')){ return matchcore(str,stridx,pattern,patidx+2)||matchcore(str,stridx+1,pattern,patidx+2)|| matchcore(str,stridx+1,pattern,patidx); }else{ return matchcore(str,stridx,pattern,patidx+2); } } if(stridx!=strglen&&(str[stridx]==pattern[patidx]||pattern[patidx]=='.')){ return matchcore(str,stridx+1,pattern,patidx+1); }else{ return false; } return false; } int countsize(char* a){ int i=0; while(a[i]) i++; return i; } int strglen=0,patlen=0; };

19. 表示数值的字符串

链接

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

链接

class Solution { public: void reOrderArray(vector<int> &array) { int cntodd=0; for(int& i: array){ if(i%2==1) cntodd++; } vector<int> copyarr(array); int i=0,j=cntodd; for(int&inum: copyarr){ if(inum%2==0) array[j++]=inum; else array[i++]=inum; } } };

21. 链表中倒数第k个结点

链接

class Solution { public: ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { ListNode* fastp=pListHead; int i=k; while(fastp!=NULL&&i!=0){ fastp=fastp->next; i--; } if(i!=0) return NULL; ListNode* slowp=pListHead; while(fastp!=NULL){ fastp=fastp->next; slowp=slowp->next; } return slowp; } };

22.链表中环的入口结点

链接

class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { if(pHead==NULL||pHead->next==NULL) return NULL; ListNode *fastp=pHead,*slowp=pHead; do{ fastp=fastp->next->next; slowp=slowp->next; }while(fastp!=NULL&&slowp!=fastp); if(fastp==NULL) return NULL; fastp=pHead; while(slowp!=fastp){ fastp=fastp->next; slowp=slowp->next; } return fastp; } };

23. 顺时针打印矩阵

链接

class Solution { public: vector<int> printMatrix(vector<vector<int> > matrix) { vector<int> vReturn; int r1=0,r2=matrix.size()-1,c1=0,c2=matrix[0].size()-1; while(r1<=r2&&c1<=c2){ if(r1<=r2&&c1<=c2){ for(int i=c1;i<=c2;i++) vReturn.push_back(matrix[r1][i]); r1++; } if(r1<=r2&&c1<=c2){ for(int i=r1;i<=r2;i++) vReturn.push_back(matrix[i][c2]); c2--; } if(r1<=r2&&c1<=c2){ for(int i=c2;i>=c1;i--) vReturn.push_back(matrix[r2][i]); r2--; } if(r1<=r2&&c1<=c2){ for(int i=r2;i>=r1;i--) vReturn.push_back(matrix[i][c1]); c1++; } } return vReturn; } };

24包含min函数的栈

链接

class Solution { stack<int> minstack,originstack; public: void push(int value) { originstack.push(value); minstack.push(minstack.empty()?value:std::min(minstack.top(),value)); } void pop() { originstack.pop(); minstack.pop(); } int top() { return originstack.top(); } int min() { return minstack.top(); } };

25.栈的压入、弹出序列

链接

class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { stack<int> temstack; for(int pushnum=0,popnum=0;pushnum<pushV.size();pushnum++){ temstack.push(pushV[pushnum]); while(popnum<pushV.size()&&!temstack.empty()&&temstack.top()==popV[popnum]){ temstack.pop(); popnum++; } } return temstack.empty(); } };

26.从上往下打印二叉树

链接

class Solution { public: vector<int> PrintFromTopToBottom(TreeNode* root) { vector<int> vResult; if(root==NULL) return vResult; deque<TreeNode*> vTemp; vTemp.push_back(root); while(!vTemp.empty()){ TreeNode* each=vTemp.front(); vTemp.pop_front(); vResult.push_back(each->val); if(each->left!=NULL) vTemp.push_back(each->left); if(each->right!=NULL) vTemp.push_back(each->right); } return vResult; } };

27. 把二叉树打印成多行

链接

class Solution { public: vector<vector<int> > Print(TreeNode* pRoot) { vector<vector<int> > vResult; if(pRoot==NULL) return vResult; deque<TreeNode*> vTemp; vTemp.push_back(pRoot); while(!vTemp.empty()){ int num_l=vTemp.size(); vector<int> vResult1; while(num_l-->0){ TreeNode* each=vTemp.front(); vTemp.pop_front(); vResult1.push_back(each->val); if(each->left!=NULL) vTemp.push_back(each->left); if(each->right!=NULL) vTemp.push_back(each->right); } vResult.push_back(vResult1); } return vResult; } };

28.按之字形顺序打印二叉树

链接

class Solution { public: vector<vector<int> > Print(TreeNode* pRoot) { vector<vector<int> > vResult; if(pRoot==NULL) return vResult; deque<TreeNode*> vTemp; vTemp.push_back(pRoot); bool printFromLeft=false; while(!vTemp.empty()){ int num_l=vTemp.size(); vector<int> vResult1; printFromLeft=!printFromLeft; while(num_l-->0){ if(printFromLeft){ TreeNode* each=vTemp.front(); vTemp.pop_front(); vResult1.push_back(each->val); if(each->left!=NULL) vTemp.push_back(each->left); if(each->right!=NULL) vTemp.push_back(each->right); }else{ TreeNode* each=vTemp.back(); vTemp.pop_back(); vResult1.push_back(each->val); if(each->right!=NULL) vTemp.push_front(each->right); if(each->left!=NULL) vTemp.push_front(each->left); } } vResult.push_back(vResult1); } return vResult; } };

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

链接

class Solution { public: bool VerifySquenceOfBST(vector<int> sequence) { if(sequence.empty()) return false; if(sequence.size()==1) return true; int sizeSequence=sequence.size(); int val=sequence[sizeSequence-1]; int loc=0,searchnum=0; while(sequence[searchnum]<val) searchnum++; loc=searchnum; while(sequence[searchnum]>val) searchnum++; if(searchnum!=sizeSequence-1) return false; vector<int> a(sequence.begin(),sequence.begin()+loc),b(sequence.begin()+loc,sequence.begin()+searchnum); if(loc==0) return VerifySquenceOfBST(b); if(loc==sizeSequence-1) return VerifySquenceOfBST(a); else return VerifySquenceOfBST(a)&&VerifySquenceOfBST(b); } };

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

链接

class Solution { public: vector<vector<int> > vvResult; vector<vector<int> > FindPath(TreeNode* root,int expectNumber) { vector<int> vPath; FindPath1(root,expectNumber,vPath); return vvResult; } void FindPath1(TreeNode* root,int expectNumber,vector<int> vPath) { if(root==NULL) return; expectNumber-=root->val; vPath.push_back(root->val); if(expectNumber==0&&root->left==NULL&&root->right==NULL){ vvResult.push_back(vPath); }else{ FindPath1(root->left,expectNumber,vPath); FindPath1(root->right,expectNumber,vPath); } return; } };

31.复杂链表的复制

链接

class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { if(pHead==NULL) return NULL; RandomListNode* pCur=pHead; //插入 while(pCur!=NULL){ RandomListNode* pTemp=new RandomListNode(pCur->label); pTemp->next=pCur->next; pCur->next=pTemp; pCur=pTemp->next; } pCur=pHead; RandomListNode* pClone; while(pCur!=NULL){ pClone=pCur->next; if(pCur->random!=NULL){ pClone->random=pCur->random->next; } pCur=pClone->next; } pCur=pHead; RandomListNode* pCloneHead=pHead->next; while(pCur->next!=NULL){ RandomListNode* pnext=pCur->next; pCur->next=pnext->next; pCur=pnext; } return pCloneHead; } };

32.二叉搜索树与双向链表

链接

class Solution { public: TreeNode* head=NULL; TreeNode* pre=NULL; TreeNode* Convert(TreeNode* pRootOfTree) { reorder(pRootOfTree); return head; } void reorder(TreeNode* root){ if(root==NULL) return; reorder(root->left); root->left=pre; if(pre!=NULL){ pre->right=root; } pre=root; if(head==NULL){ head=root; } reorder(root->right); } };

33.序列化二叉树

链接

class Solution { public: vector<int> vStr; char* Serialize(TreeNode *root) { vStr.clear(); dfs1(root); int v_size=vStr.size(); int *res=new int[v_size]; for(int i=0;i<v_size;i++) res[i]=vStr[i]; return (char*)res; } void dfs1(TreeNode * root){ if(!root) vStr.push_back(0xFFFFFFFF); else{ vStr.push_back(root->val); dfs1(root->left); dfs1(root->right); } return; } TreeNode* dfs2(int* &root){ if(*root==0xFFFFFFFF){ root++; return NULL; } TreeNode* t=new TreeNode(*root); root++; t->left=dfs2(root); t->right=dfs2(root); return t; } TreeNode* Deserialize(char *str) { int *p=(int *)str; return dfs2(p); } };

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

链接

class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { int numSize=int(numbers.size()); int majority=numbers[0]; for(int i=1,cnt=1;i<numSize;i++){ cnt=numbers[i]==majority?cnt+1:cnt-1; if(cnt==0){ majority=numbers[i]; cnt=1; } } int cnt=0; for(int& i :numbers){ if(i==majority) cnt++; } return cnt>numSize/2?majority:0; } };

35.字符串的排列

链接

class Solution { public: vector<string> Permutation(string str) { vector<string> result; if(str.length()==0) return result; Permutation1(str,result,0); sort(result.begin(),result.end()); return result; } void Permutation1(string str,vector<string>& result,int begin){ if(begin==str.length()-1){ if(find(result.begin(),result.end(),str)==result.end()) result.push_back(str); } else{ for(int i=begin;i<str.length();i++){ swap(str[i],str[begin]); Permutation1(str,result,begin+1); swap(str[i],str[begin]); } } } void swap(char& i,char&j){ char temp=i; i=j; j=temp; } };

36.最小的K个数

链接

排序

class Solution { public: vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { vector<int> result; if(input.size()==0||k>input.size()) return result; sort(input.begin(),input.end()); for(int i=0;i<k;i++){ result.push_back(input[i]); } return result; } };

partition

class Solution { public: vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { vector<int> result; if(input.size()==0||k>input.size()) return result; int l=0,h=input.size()-1; int index; while(l<h){ index=partition(input,l,h); if(index==k) break; else if(index>k) h=index-1; else l=index+1; } for(int i=0;i<index;i++){ result.push_back(input[i]); } return result; } int partition(vector<int>& input,int l,int h){ int p=input[l]; int i=l,j=h; while(i<j){ while(i<j&&input[i]<p) i++; while(i<j&&input[j]>p) j--; swap(input[i],input[j]); } return i; }; void swap(int& a,int&b){ int temp=a; a=b; b=temp; } };

最小堆

class Solution { public: vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { vector<int> result; if(input.size()==0||k>input.size()) return result; for(int i=0;i<k;i++) result.push_back(input[i]); make_heap(result.begin(),result.end()); for(int i=k;i<input.size();i++){ if(input[i]<result.front()){ pop_heap(result.begin(),result.end()); result.pop_back(); result.push_back(input[i]); push_heap(result.begin(),result.end()); } } sort_heap(result.begin(),result.end()); return result; } };

链接

链接

链接

链接

链接