数据结构

数组和串

找出字符串中第一次出现子串的位置：KMP算法
力扣例题

class Solution {
public:
    vector<int> countpi(string str){
        vector<int> pi (str.length(),0);
        int i = 1,j = 0;
        while(i<str.length()){
            if(str[i]==str[j]){
                i++;
                j++;
                if(i>=str.length()) break;
                pi[i]=j;
            }
            else if(j==0) i++;
            else j=pi[j];
        }
        return pi;
    }


    int strStr(string haystack, string needle) {
        vector<int> pi= countpi(needle);
        int i = 0 ,j = 0;
        while(i<haystack.length()){
            if(haystack[i]==needle[j]){
                i++;
                j++;
                if(j==needle.length()) return i-needle.length();
            }
            else if(j==0) i++;
            else j=pi[j];
        }

        return -1;

    }
};

链表

基本操作

  • 定义链表结点
struct node {
    int data;
    struct node *next;
};

  • 为链表结点分配与释放内存
//C
#include <stdlib.h>
node* newNode = (node*)malloc(sizeof(node));
free(newNode);
newNode = NULL; 
//C++
node* newNode=new node;
delete newNode;

  • 删除链表中所有值在[x, y]范围内的元素
void deleteByRange(int x, int y) {
    node *p = head;
    node *q = head->next;
    while(q){
        if(q->data<=y&&q->data>=x) {p->next=q->next;q=q->next;}
        else {q=q->next;p=p->next;}   
    }
}
  • 去除链表中的重复元素，保留第一次出现的元素
void eliminateRepeat() {
    node *p = head->next;
    while (p != NULL) {
       node* q=p->next;
       while(q->next){
        if(q->next->data==p->data) q->next=q->next->next;
        q=q->next;
       }
       p=p->next;
    }
}

栈

FILO应用

  • 数制转换：
void conv_k(int N,int k){//把十进制N转化为k进制
    stack<int> s;
    while(N){
        s.push(N%k);
        N/=k；
    }
    while(!s.empty()){
        cout<<s.top();
        s.pop();
    }
}
  • 括号匹配：
bool isValid(const string& s) {
    stack<char> left;
    for (int i = 0;i<s.length();i++>) {
        c=s[i];
        if (c == '(' || c == '[' || c == '{') {
            left.push(c);
        } else {
            if (left.empty()) return false;
            if ((c == ')' && left.top!= '(') || (c == ']' && left.top!= '[') || (c == '}' && left.top!= '{')) {
                return false;
            }
            left.pop();
        }
    }
    return left.empty();
}
  • Hanoi塔
void hanoi(int n, char source, char auxiliary, char target) {
    if (n == 1) {
        std::cout << "将圆盘1从 " << source << " 移动到 " << target << std::endl;
        return;
    }
    hanoi(n - 1, source, target, auxiliary);
    std::cout << "将圆盘" << n << "从 " << source << " 移动到 " << target << std::endl;
    hanoi(n - 1, auxiliary, source, target);
}
  • graham-scan算法找到点的闭包
  1. 选最低点。
  2. 按角度排序
  3. 扫描(scan)
    1）先把p[0]、p[1]入栈
    2）（S[k]-S[k-1]） x （p[i]-S[k-1]）>0: p[i]入栈,即p[i]在(S[k]-S[k-1])左侧（夹角小于180°），否则：p[i]出栈
  1. 重复2）遍历所有点

队列

FIFO

  • 循环队列
//入队
queue[rear]=c;
rear=(rear+1)%m;
//出队
front=(front+1)%m;
打印队列
if (front != rear) {
        int i = front;
        while (i != rear) {
            cout<<queue[i];
            i = (i + 1) % m; 
        }
    }

二叉树

基本性质
如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i，有：
(1) 如果i=1，则结点i是二叉树的根，无父亲；否则其父亲是 ⌊i2⌋\left\lfloor\frac i2\right\rfloor
(2) 如果2i>n，则结点i无左孩子；否则则其左孩子是2i
(3) 如果2i+1>n，则结点i无右孩子；否则其右孩子是2i+1

先序遍历

void preorder(tree* T){
    if(T){
        cout<<T->val;
        preorder(T->lchild);
        preorder(T->rchild);
    }
}


中序遍历

void inorder(tree* T) {
	if(T){
        inorder(T->lchild);
        cout<<T->val;
        inorder(T->rchild);
    }
	    
}

后序遍历

void postorder(tree* T) {
	if(T){
        postorder(T->lchild);
        postorder(T->rchild);
        cout<<T->val;
    }
	    
}

多叉树转二叉树

void buildTree()
{
  cin >> n;
  for (int i = 1; i <= n; i++)
    cin >> nodes[i].data >> nodes[i].parent;
  for (int i = 2; i <= n; i++)
  {
    int f = nodes[i].parent;
    if (lastchild[f] == 0)
      nodes[f].lchild = lastchild[f] = i;
    else
    {
      nodes[lastchild[f]].rchild=i;//兄弟变成右孩子
    }
    lastchild[f]=i;
  }
}

堆

最小堆的基本操作

int heap[MAX_SIZE]; // 用数组存储堆
int heapSize = 0;   // 当前堆的大小

// 向上调整
void siftUp(int index) {
    while (index > 1 && heap[index] < heap[index / 2]) { // 当前节点小于父节点
        // 交换当前节点和父节点
        swap(heap[index],heap[index/2]);
        index = index / 2; // 更新当前节点为父节点
    }
}

// 向下调整
void siftDown(int index) {
    while (2 * index <= heapSize) { // 当有左子节点时
        int j = 2 * index; // 左子节点的索引
        if (j + 1 <= heapSize && heap[j + 1] < heap[j]) {
            j = j + 1; // 如果右子节点更小，选择右子节点
        }
        if (heap[index] <= heap[j]) break; // 如果当前节点小于等于子节点，调整结束
        swap(heap[index],heap[j]);
        index = j; // 更新当前节点为子节点
    }
}

// 插入元素
void insert(int x) {
    if (heapSize >= MAX_SIZE - 1) {
        printf("Heap overflow\n");
        return;
    }
    heapSize++;         
    heap[heapSize] = x; 
    siftUp(heapSize);   // 向上调整堆
}

// 删除堆顶元素
void deleteTop() {
    if (heapSize == 0) {
        printf("Heap is empty\n");
        return;
    }
    heap[1] = heap[heapSize]; // 用最后一个元素替换堆顶
    heapSize--;               // 减少堆的大小
    siftDown(1);              // 从堆顶向下调整
}

并查集

int find_parent(int i){
    if(i!=parent[i]){
        parent[i]=find_parent(parent[i]);//路径压缩
    }
    return parent[i];
    
}
void connect(int u,int v){
    int u_root=find_parent(u);
    int v_root=find_parent(v);
    if(u_root!=v_root){
    if(Rank[u_root]<Rank[v_root]) parent[u_root]=v_root;//按秩合并
    else if(Rank[u_root]>Rank[v_root]) parent[v_root]=u_root;
    else {
        parent[u_root]=v_root;
        Rank[v_root]++;
    }
    }
}

算法

排序问题

  1. 快速排序：
    选择固定位快排平均时间复杂度为 O(nlog⁡n)O(n\log n) ，最差时间复杂度（已是顺序排列）：O(n2)O(n^2)
    随机快排平均及最差时间复杂度均为 O(nlog⁡n)O(n\log n)
int partition(int arr[], int low, int high)
{   
    int random=low+rand()%(high-low+1);
    swap(arr[random],arr[high]);
    int i = low,j=low;//开始index=low
    while(j<high){
        if(arr[j]<arr[high]) swap(arr[i++],arr[j]);
        j++;
    }
    swap(arr[high],arr[i]);
    return i;
    
  // Insert your code here
}

void quickSort(int arr[], int low, int high)
{
    if(low<high){
        int key=partition(arr,low,high);
        quickSort(arr,low,key);
        quickSort(arr,key+1,high);
    }
}


2.分治排序：平均及最差时间复杂度均为 O(nlog⁡n)O(n\log n)
力扣例题

class Solution {
public:
    vector<int> order(vector<int> a,vector<int> b){//治
        vector<int> sum;
        int i=0,j=0;
        while(i<a.size()&&j<b.size()){
            if(a[i]<b[j]) sum.push_back(a[i++]);
            else sum.push_back(b[j++]);
        }
        while(i<=a.size()-1){
            sum.push_back(a[i++]);
        }
        while(j<=b.size()-1){
            sum.push_back(b[j++]);
        }
        return sum;
    }
    void part(vector<int>& nums,vector<int>& a,vector<int>& b){//分
        int i = 0,j=nums.size()/2;
        while(i<j){
            a.push_back(nums[i++]);
        }
        while(j<nums.size()){
            b.push_back(nums[j++]);
        }
    }
    vector<int> sortArray(vector<int>& nums) {
        if(nums.size()==1) return nums;
        vector<int> a,b;
        part(nums,a,b);
        a=sortArray(a);
        b=sortArray(b);
        return order(a,b);
    }
};

动态规划

思想：创建数组，数组中每个数都由递推公式得到

  • 矩阵相乘最小运算量
void MatrixChainOrder(int n)
{
    
    for (int i = 1; i <= n; i++)//先初始化对角线的
    {
        m[i][i] = 0;
    }
    
    for(int L=1;L<n;L++){//L要从1开始
        for(int i = 1;i+L<=n;i++){    
                int j=i+L;//j要在循环条件外定义 
                long long int min=100000000;
                for(int k = i;k<j;k++){
                    long long int mul=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                    min=min<mul?min:mul;
                }
                m[i][j]=min;
            
        }
    }

    printf("%lld", m[1][n]);
}

最大1的矩形面积

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        vector<vector<int>> wid(matrix.size(),vector<int>(matrix[0].size(),0));
        for(int i = 0;i<matrix.size();i++)
         for(int j = 0;j<matrix[0].size();j++){
            if(matrix[i][j]=='1'){
            wid[i][j]=(j==0?0:wid[i][j-1])+1;//矩形的宽度数组用动态规划确定
            }
         }
         int reg=0;
        for(int i = 0;i<matrix.size();i++){
            for(int j = 0;j<matrix[0].size();j++){
                if(matrix[i][j]=='0') continue;
                int w=wid[i][j],l=1,area=w*l;
                for(int k = i-1;k>=0;k--){
                	w=min(wid[k][j],w);
                	if(w==0) break;
                    l++;
                    area=max(area,w*l);
                    }
				
	            reg=max(reg,area);
                
            }
            
        }
        
        return reg;
        
    }
};

贪婪算法

  • 任务最早结束时间
int taskProcess()
{
	int cnt = 0, t = 0, tasknum = n;
	while (tasknum)
	{
		int min=1000000,j=0;//j定位p[i]最小处index
        for(int i = 1;i<=n;i++){
            if(r[i]<=t&&p[i]>0&&p[i]<min){
                
                min=p[i];
                j=i;
            }
        }
        p[j]--;
        t++;
        if(p[j]==0) {tasknum--; cnt+=t;}       
	}
	return cnt;
}

课件习题：给数列分组，使得长度最小组元素个数尽可能多
给定整数a1~an, 可能有重复元素。
1.要将它们分成若干组， 每组是一些连续的整数（每组不能有重复元素）
2.你需要使元素个数最少的一组的元素数量最多。
举例
输入4 5 2 3 -4 -3 -5。
输出3。 {-5,-4,-3}一组，{2,3,4,5}一组。
tips:尽量少开新组，且优先填满未填满的组

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
bool satisfy(vector<vector<int>>& a,int m){//a前记得加引用
	for(int i = 0;i<a.size();i++){
		if(!a[i].empty() &&a[i].back()==m-1) {
			return 1;
		}
	}
	return 0;
	
}
vector<int>& satisfied_shortest(vector<vector<int>>& a,int m){
	sort(a.begin(), a.end(), [](const vector<int>& v1, const vector<int>& v2) {
        return v1.size() < v2.size();  // 按照s数组大小升序排序
    });
	for(int i = 0;i<a.size();i++){
		if(!a[i].empty()&&a[i].back()==m-1)
			return a[i];
	}
	return a[0];
	
}
vector<int> min_vector(vector<vector<int>>& a){
	int Min=10000,key=0;
	for(int i = 0;i<a.size();i++){
		if(a[i].size()<Min){
			Min=a[i].size();
			key=i;
		}
	}
	return a[key];
}
vector<int> find_the_min_vector(vector<int>& in){
	sort(in.begin(),in.end(),[](int t,int k){return t<k;});
	vector<vector<int>> a;
	vector<int> n;
	n.push_back(in[0]);
	a.push_back(n);
	for(int i = 1;i<in.size();i++){
			if(satisfy(a,in[i])){
			satisfied_shortest(a,in[i]).push_back(in[i]);//优先填满满足条件的长度最小组
		    }
			else
			{
				vector<int> m={in[i]};
				a.push_back(m);
			}		
    }
    return min_vector(a);
}
int main(){
	vector<int> in;
	int x;
	cout << "Enter numbers (end input with Ctrl+Z): ";
	while(cin>>x){
		in.push_back(x);
	}
	cout<<"The min vector's max size:"<<find_the_min_vector(in).size()<<endl;
	return 0;	
}

丰富的函数库

iomanip

  • cout<<setprecision(n)<<a: 控制a显示n个有效数字位数（不显示末尾的零）
  • cout<<showpoint<<setprecision(n)<<a: 控制a显示n个有效数字位数（强制显示末尾的0）
  • cout<<fixed<<setprecision(n)<<a: 控制a小数点后保留n位小数（强制显示末尾的0）
  • cout<<scientific<<setprecision(n)<<a: 将a转化为保留n位小数（精度为n）的科学计数法
  • cout<<oct<<a: 将a转化为八进制形式
  • cout<<hex<<a: 将a转化为十六进制形式
  • cout<<left<<a: 控制a为左对齐输出
  • cout<<setw(n)<<a: 设定a占n个数字的宽度

vector

  • arr.push_back(i): 将整数i加入到数组末尾

string

  • s.length(): 计算s字符串的长度（含空格）
  • s.substr(index,num): 从s下标为index处开始，提取含num个字符的子串，若无第二个参数，则一直提取到结尾
  • s.find(str): 在s中寻找str字符串
  • s.find(str,index): 在s中从index处开始查找子串str
  • s.find(c): 在s中找c字符
  • s.rfind(str): 倒着找str
  • s.append(str): 在s末尾添加str字符串
  • s.append(num,c): 在s末尾添加num个c字符
  • s.insert(index,str): 在s的index处插入str字符串
  • s.insert(index,num,c): 在s的index处插入num个c字符
  • s.erase(index,num): 从s的index开始，删除num个字符
  • s.clear: 清空s
  • s.copy(&str[i],num,index): 从s的index处开始，复制num个字符替换从str[i]开始的字符串，不会完全替换掉str串，只会替换指定位置的指定字符个数
  • s.compare(str): 将s与str按照ascll码表进行对比，返回负数，0，正数
  • s.compare(index,num,str): 从s的index处开始选取长度为num的子串与str进行对比，返回负数，0，正数
  • s.swap(str): 交换s与str内容
  • s.pop_back(): 删除s的最后一个字符

algorithm

  • sort(s.begin(),s.end(),less<int>()): 升序排列数组
  • sort(s.begin(),s.end(),greater<int>()): 降序排列数组

cctype

  • islower(c): 判断字符是否为小写
  • toupper(c): 将小写字符变为大写

cstdlib

  • atoi(str): 将字符串str转化为整数
  • stof(str): 将字符串str转化为小数

math.h

  • hypot(a,b): 计算 a2+b2\sqrt{a^2+b^2}