1.字符串
（1）字符串转化为整数
int StrToInt(string str) {
int size=str.size();
if(size==0)
return 0;
int i=0,sign=1,result=0;
while(str[i]==' ')
i++;
if(str[i]=='+')
i++;
if(str[i]=='-'){
i++;
sign=-1;
}
while(i<size){
if(str[i]>='0'&&str[i]<='9')
result=result*10+(str[i]-'0');//重点！！
else
return 0;
i++;
}
return result*sign;
}（2）字符串排列：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
string result;
vector<string> allresult;
vector<string> Permutation(string str){
if(str.size()==0)
return allresult;
PermutationCore(str,0);
sort(allresult.begin(),allresult.end());//注意sort的用法
return allresult;
}
void PermutationCore(string str,int n){//确定第n个数
int size=str.size();
if(n==size-1){
allresult.push_back(str);
return;
}
for(int i=n;i<size;i++){
if(i==n||str[n]!=str[i]){//一定要记住第一个也得进去
char temp=str[n];
str[n]=str[i];
str[i]=temp;
PermutationCore(str,n+1);
}
}（3）第一个只出现一次的字符
int FirstNotRepeatingChar(string str) {
if(str.length()==0)
return -1;
const int tableSize=256;
unsigned int hashTable[tableSize];
for(unsigned int i=0;i<tableSize;++i)
hashTable[i]=0;
int pHashKey=0;
while(str[pHashKey]!='\0')
hashTable[str[pHashKey++]]++;
pHashKey=0;
while(str[pHashKey]!='\0'){
if(hashTable[str[pHashKey]]==1)
return pHashKey;
pHashKey++;
}
return -1;
}2.数组
（1）排序
//快速排序
//平均时间复杂度：O(NlogN)
//最坏情况复杂度：O(N^2)
//不稳定排序
void quiksort(vector<int> &numbers,int start,int end){
if(start>=end)
return;
int povit=numbers[start];
int p1=start,p2=end;
while(p1<p2){
while(p1<p2&&numbers[p2]>=povit)
p2--;
if(numbers[p2]<povit)
numbers[p1++]=numbers[p2];
while(p1<p2&&numbers[p1]<=povit)
p1++;
if(numbers[p1]>povit)
numbers[p2--]=numbers[p1];
}
numbers[p1]=povit;
quiksort(numbers,start,p1-1);
quiksort(numbers,p1+1,end);
}
//冒泡排序
//平均时间复杂度:O(N^2)
//最坏情况复杂度:O(N^2)
//空间复杂度:O(1)
//稳定排序
void bubblesort(vector<int>& a)
{
int n = a.size();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n - 1 - i; j++)
{
if (a[j] > a[j+1])
swap(a[j], a[j+1]);
}
}
}
//插入排序
//平均时间复杂度:O(N^2)
//最坏情况复杂度:O(N^2)
//最好情况复杂度:O(N)
//空间复杂度:O(1)
//最多需要n(n−1)/2次比较
//最少需要n−1次比较
//稳定排序
void insertsort(vector<int>& a)
{
int n = a.size();
for (int i = 1; i < n; i++)
{
int insert_num = a[i], j;
for (j = i - 1; j >= 0; j--)
{
if (a[j] > insert_num)
a[j + 1] = a[j];
else
break;
}
a[j + 1] = insert_num;
}
}
//选择排序
//平均时间复杂度 O(n^2)
//最坏时间复杂度 O(n^2)
//最好时间复杂度 O(n^2)
//空间复杂度 O(1)
//我这个写法 是稳定排序
void select_sort(vector<int>& vt)
{
for (int i = 0; i < vt.size() - 1; i ++)
{
int swap_pos = i;
for (int j = i + 1; j < vt.size(); j++)
{
if (vt[swap_pos] > vt[j])
{
swap_pos = j;
}
}
if (swap_pos != i)
{
swap(vt[swap_pos], vt[i]);
}
}
}
//希尔排序
//最坏情况复杂度:O(N^2)
//不稳定排序
void shellsort(vector<int>& a)
{
int n = a.size();
for (int increment = n / 2; increment > 0; increment /= 2)
{
for (int i = increment; i < n; i++)
{
int insert_num = a[i], j;
for (j = i - increment; j >= 0; j -= increment)
{
if (a[j] > insert_num)
a[j + increment] = a[j];
else
break;
}
a[j + increment] = insert_num;
}
}
}
//堆排序
//建堆的平均时间是：O(N)
//建堆的最坏情况是：O(NlogN)
//删除元素的时间是：O(logN)
//整个排序平均时间复杂度：O(N+NlogN)=O(NlogN)
//最坏情况复杂度：O(NlogN)
//不稳定排序
//建立一个大顶堆O(n),要求就是 把最大的元素 移动到堆顶 也就是a[0]
void make_heap(vector<int>& a, int size) //size的当前堆的大小，也就是数组的前size个数
{
for (int i = size - 1; i > 0; i--)
{
if (i % 2 && a[i] > a[(i - 1) / 2])//奇数
swap(a[i], a[(i - 1) / 2]);
else if (i % 2 == 0 && a[i] > a[(i - 2) / 2])//偶数
swap(a[i], a[(i - 2) / 2]);
}
}
void heapsort(vector<int>& a)
{
int n = a.size();
while (n)
{
make_heap(a, n); //每次把新的最大元素移到堆顶，也就是a[0]
n--;
swap(a[0], a[n]); //然后把当前最大移动到后面来作为排好序的元素
}
}
//归并排序
//平均时间复杂度：O(NlogN)
//稳定排序
vector<int> mergeHelper(vector<int> &a, int left, int right)
{
if (left == right) return vector<int> (1, a[left]);
int mid = (right - left) / 2 + left;
vector<int> l = mergeHelper(a, left, mid);
vector<int> r = mergeHelper(a, mid + 1, right);
//merge
vector<int> ret;
int ll = 0, rr = 0;
while (ll < l.size() && rr < r.size())
{
if (l[ll] <= r[rr]) ret.push_back(l[ll++]);
else ret.push_back(r[rr++]);
}
while (ll < l.size()) ret.push_back(l[ll++]);
while (rr < r.size()) ret.push_back(r[rr++]);
return ret;
}
void mergesort(vector<int>& a)
{
a = mergeHelper(a, 0, a.size() - 1);
}（2）二维数组中的查找：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
bool Find(int target, vector<vector<int> > array)
{
int rows=array.size()-1,cols=array[0].size()-1;
int i=0,j=cols;
while(i<=rows&&j>=0){//行最大、列最小
if(array[i][j]==target)
return true;
else if(array[i][j]<target)//小于他，向下移
i++;
else if(array[i][j]>target)//大于他，向左移
j--;
}
return false;
} （3）连续子数组的最大和
int FindGreatestSumOfSubArray(vector<int> array) {
if(array.size()==0)
return 0;
int result=array[0],addvalue=array[0];
for(int i=1;i<array.size();i++){
if(addvalue>=0)
addvalue+=array[i];
else
addvalue=array[i];
if(addvalue>result)
result=addvalue;
}
return result;
}（4）数组中只出现一次的数字
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
if(data.size()<2)
return;//直接return就行哦
int temp=0;
for(int i=0;i<data.size();++i)
temp^=data[i];
int indexof1=0;
//(temp&1)==0中（）必须加，&优先级更低
while(((temp&1)==0)&&(indexof1<8*sizeof(int))){
//sizeof(int)可以知道电脑的int占多少个字节，一个字节有8位
temp=temp>>1;//一定要用temp=一下！不可以直接temp>>1
++indexof1;
}
*num1=0;*num2=0;
for(int i=0;i<data.size();++i){
if(IsBit1(data[i],indexof1))
*num1^=data[i];
else
*num2^=data[i];
}
}
bool IsBit1(int num,int index){
num=num>>index;
return (num&1);
}3.链表
（1）从尾到头打印链表
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> Arraylist;
if(head==nullptr)
return Arraylist;
stack<int> temp;
ListNode* p=head;
while(p!=nullptr){
temp.push(p->val);
p=p->next;
}
while(!temp.empty()){
Arraylist.push_back(temp.top());
temp.pop();
}
return Arraylist;
}（2）反转链表
ListNode* ReverseList(ListNode* pHead)
{
if(pHead==nullptr)
return nullptr;
ListNode* p=pHead;
ListNode* pre=nullptr;
while(p!=nullptr){
ListNode* pnext=p->next;
p->next=pre;
pre=p;
p=pnext;
}
return pre;
}（3）复杂链表的复制：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
RandomListNode* Clone(RandomListNode* pHead)
{
if(pHead==nullptr)
return nullptr;
clonenodes(pHead);
conectrandom(pHead);
return reconect(pHead);
}
void clonenodes(RandomListNode* pHead){
RandomListNode* p=pHead;
while(p!=nullptr){
RandomListNode* pClone=new RandomListNode(p->label);
pClone->next=p->next;
pClone->random=nullptr;
p->next=pClone;
p=pClone->next;
}
}
void conectrandom(RandomListNode* pHead){
RandomListNode* p=pHead;
RandomListNode* pClone=nullptr;
while(p!=nullptr){
pClone=p->next;
if(p->random!=nullptr)
pClone->random=p->random->next;
p=pClone->next;
}
}
RandomListNode* reconect(RandomListNode* pHead){
if(pHead==nullptr)
return nullptr;
RandomListNode* p=pHead;
RandomListNode* pCloneHead=p->next;
RandomListNode* pClone=pCloneHead;
p->next=pClone->next;
p=p->next;
while(p!=nullptr){
pClone->next=p->next;
pClone=pClone->next;
p->next=pClone->next;
p=p->next;//一定要注意顺序，指针变化的先后
}
return pCloneHead;
}4.树
（1）重建二叉树
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin)
{
if(pre.empty()||vin.empty())
return nullptr;
TreeNode* root=new TreeNode(pre[0]);//注意new的用法
vector<int> leftpre,rightpre,leftvin,rightvin;
int rootcount=0;
while(vin[rootcount]!=pre[0]){
rootcount++;
}
for(int i=0;i<vin.size();i++){
if(i<=rootcount){
if(i!=0)
leftpre.push_back(pre[i]);
if(i!=rootcount)
leftvin.push_back(vin[i]);
}
if(i>rootcount){
rightpre.push_back(pre[i]);
rightvin.push_back(vin[i]);
}
}
root->left=reConstructBinaryTree(leftpre,leftvin);
root->right=reConstructBinaryTree(rightpre,rightvin);
return root;
}（2）从上到下打印二叉树
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> result;
if(root==nullptr)
return result;
deque<TreeNode*> temp;
temp.push_back(root);
while(!temp.empty()){
result.push_back(temp.front()->val);
if(temp.front()->left!=nullptr)
temp.push_back(temp.front()->left);
if(temp.front()->right!=nullptr)
temp.push_back(temp.front()->right);
temp.pop_front();
}
return result;
}（3）三种递归遍历
//前序遍历
void preorder(TreeNode *root, vector<int> &path)
{
if(root != NULL)
{
path.push_back(root->val);
preorder(root->left, path);
preorder(root->right, path);
}
}
//中序遍历
void inorder(TreeNode *root, vector<int> &path)
{
if(root != NULL)
{
inorder(root->left, path);
path.push_back(root->val);
inorder(root->right, path);
}
}
//后续遍历
void postorder(TreeNode *root, vector<int> &path)
{
if(root != NULL)
{
postorder(root->left, path);
postorder(root->right, path);
path.push_back(root->val);
}
}（4）按之字形顺序打印二叉树
vector<vector<int> > Print(TreeNode* pRoot) {
if(pRoot==nullptr)
return allresult;
queue<TreeNode*> temp;
temp.push(pRoot);
int line=1,linecount=1,nextlinecount=0;
while(!temp.empty()){
while(linecount>0){
result.push_back(temp.front()->val);
if(temp.front()->left!=nullptr){
++nextlinecount;
temp.push(temp.front()->left);
}
if(temp.front()->right!=nullptr){
++nextlinecount;
temp.push(temp.front()->right);
}
temp.pop();
--linecount;
}
allresult.push_back(result);
result.clear();
linecount=nextlinecount;
nextlinecount=0;
}
int sizeofall=allresult.size();
for(int i=0;i<sizeofall;++i){
if(i&1==1){
int p2=allresult[i].size()-1,p1=0,temp=0;
while(p1<p2){
temp=allresult[i][p1];
allresult[i][p1]=allresult[i][p2];
allresult[i][p2]=temp;
++p1;
--p2;
}
}
}
return allresult;
}
private:
vector<vector<int> > allresult;
vector<int> result;（5）二叉搜索树的第k个节点
TreeNode* KthNode(TreeNode* pRoot, int k)
{
if(pRoot==nullptr||k<1)
return nullptr;
vector<TreeNode*> mid;
midfind(pRoot,mid);
if(k>mid.size())
return nullptr;
return mid[k-1];
}
void midfind(TreeNode* pRoot,vector<TreeNode*> &mid){
if(pRoot!=nullptr){
midfind(pRoot->left,mid);
mid.push_back(pRoot);
midfind(pRoot->right,mid);
}
}
};（6）和为某一值的路径
public:
vector<vector<int> > FindPath(TreeNode* root,int expectNumber){
if(root==nullptr)
return allresult;
result.push_back(root->val);
if((root->val==expectNumber)&&(root->left==nullptr)&&(root->right==nullptr))
allresult.push_back(result);
FindPath(root->left,expectNumber-(root->val));
FindPath(root->right,expectNumber-(root->val));
result.pop_back();//这一步必须加！！
return allresult;
}
private:
vector<vector<int> > allresult;
vector<int> result;（7）二叉搜索树与双向链表
TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree==nullptr)
return nullptr;
TreeNode* pHead=pRootOfTree;
while(pHead->left!=nullptr)
pHead=pHead->left;
FindLeftAndRight(pRootOfTree);
return pHead;
}
void FindLeftAndRight(TreeNode* pRootOfTree){
if(pRootOfTree->left!=nullptr){
FindLeftAndRight(pRootOfTree->left);
TreeNode* p=pRootOfTree->left;
while(p->right!=nullptr)
p=p->right;
p->right=pRootOfTree;
pRootOfTree->left=p;
}
if(pRootOfTree->right!=nullptr){
TreeNode* p=pRootOfTree->right;
FindLeftAndRight(pRootOfTree->right);//注意递归的位置，一定要在前面！
while(p->left!=nullptr)
p=p->left;
p->left=pRootOfTree;
pRootOfTree->right=p;
}
}5.栈
（1）用两个栈来实现一个队列
public:
void push(int num){
stack1.push(num);
}
int pop(){
int result;
if(!stack2.empty()){
result=stack2.top();
stack2.pop();
}
else{
while(!stack1.empty()){
stack2.push(stack1.top());
stack1.pop();
}
result=stack2.top();
stack2.pop();
}
return result;
}
private:
stack<int> stack1;
stack<int> stack2;（2）包含min函数的栈
public:
void push(int value){
st.push(value);
if(smin.empty()||value<smin.top())
smin.push(value);
}
void pop() {
if(st.top()==smin.top())
smin.pop();
st.pop();
}
int top() {
return st.top();
}
int min() {
return smin.top();
}
private:
stack<int> st;//正常记录
stack<int> smin;//小的压栈（3）栈的压入、弹出序列
bool IsPopOrder(vector<int> pushV,vector<int> popV)
{
int pushcount=pushV.size(),popcount=popV.size();
if(pushcount!=popcount)
return false;
stack<int> temp;
int pi=0;
for(int i=0;i<popcount;++i)
{
while(temp.empty()||temp.top()!=popV[i])
{
temp.push(pushV[pi++]);
if(pi>pushcount)
return false;
}
temp.pop();
}
return true;
}
6.队列
（1）从上往下打印二叉树</int></int></int>
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> result;
if(root==nullptr)
return result;
deque<TreeNode*> temp;
temp.push_back(root);
while(!temp.empty()){
result.push_back(temp.front()->val);
if(temp.front()->left!=nullptr)
temp.push_back(temp.front()->left);
if(temp.front()->right!=nullptr)
temp.push_back(temp.front()->right);
temp.pop_front();
}
return result;
}////////////////////会根据我的学习进展不断更新哦////////////////////////////欢迎一起努力的小伙伴们点赞收藏呀///////////////////////////////////////////////////
参考链接：https://blog.csdn.net/liqinzhe11/article/details/78743743
参考资料：剑指offer
京公网安备 11010502036488号