#include<iostream> #include<queue> using namespace std; const int N=2e5+6; int arr[N]; int n; bool vis[N]; // 下标是否被访问过 queue<int> que; // 存下标 int main(){ ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); cin>>n; for(int i=0;i<n;i++){ ...

dp[i][j]：str[i , j]的最长回文子序列长度1、str[i]==str[j]：dp[i][j] = dp[i+1][j-1] + 2;2、str[i]!=str[j]：dp[i][j] = max(dp[i+1][j] , dp[i][j-1] )由于dp[i][j]依赖于dp[i+1][j-1]、dp[i+1][j]、dp[i][j-1]，所以i要先遍历i较大的，即i从大到小遍历根据dp定义，j>=i，注意初始化dp[i][i]=1string str;for(int i=0;i<str.size();i++){        dp[i][i]=1;    }   ...

状态方程：st，st[i][j]：存储矩阵[i][j]开始的最长严格递减长度int dfs(int i,int j){    if(st[i][j]!=0) return st[i][j];    int ma=0;    for(int k=0;k<4;k++){        int ni=i+dir[k][0],nj=j+dir[k][1];        if(ni>=0 && ni<n && nj>=0 && nj<m && g[ni][nj]<g[i][j]){           ...

struct node{    long long x;    node(long long x){        this->x=x;        } friend bool operator < (const node &a,const node &b){ return a.x>b.x; // 按x降序排列，与sort比较重写相反 }};priority_queue<node> pq;

struct node{    long long x;    node *l=nullptr;    node *r=nullptr;    node(long long x){        this->x=x;        }};struct compare{    bool operator () (const node *a,const node *b){        return a->x > b->x;        // 按x降序排列，与sort比较重写相反    }};priority_queue<node*,vector<node*&...

const int N=1e5+6;int pile[N],data[N];int idx=1,n;for(int i=1;i    pile[idx]=data[i], idx++;}int ind=idx-1;while(2*ind>=idx) ind--;       // 找到最后一个非叶子节点的下标void down_adjust(int pa){    if(2*pa if(pile[2*pa]>pile[2*pa+1]){ if(pile[2*pa]>pile[pa]){                exchange(pa,2*pa);                down_adjust(2*pa);            }        }        else{ if(pile[2*pa+1]>pile[pa]){                exchange(pa,2*pa+1);                down_adjust(2*pa+1);            }        }    }    if(2*pa=idx){ if(pile[2*pa]>pile[pa]){            exchange(pa,2*pa);            down_adjust(2*pa);        }    }}// 遍历调整for(int i=ind;i>=1;i--){    int p=pile[i],l,r;    if(2*i+1    else l=pile[2*i], r=pile[i]-1; if(l>p && l>r){        exchange(i,2*i);        down_adjust(2*i);    } if(r>p && r>l){        exchange(i,2*i+1);        down_adjust(2*i+1);    }}

int pile[N];int idx=1; // 下一个节点的位置void exchange(int a,int b){    int temp=pile[a];    pile[a]=pile[b];    pile[b]=temp;}堆插入，以大根堆为例，完全二叉树，用数组存储1、插入节点成为最后一个叶子节点，从该节点开始向上调整，每次只需要比较当前节点与父节点，看是否需要交换。因为大根堆的性质，父节点比左、右儿子节点都大，若当前节点比父节点大，则子树中当前节点最大。递归调整，代码如下。void up_adjust(int a){    if(a>=2){        i...

时间复杂度O(n)，空间复杂度O(1)。需要3个指针，t指向上一个节点，tt指向当前节点，当前节点的next改变指向，ttt记录下一个节点if(head==nullptr || head->next==nullptr) return head; // 链表为空或者只有一个节点        ListNode *t=head,*tt=head->next;        bool sign=true; // 标记第一次改变指向时，尾巴节点的next设为nullptr        while(tt!=nullptr){            ListN...

链表插入，删除，链表有头节点。在第一个值为a前插入b。void insert_node(node *head,int a,int b){         node *t=head; while(t->next!=nullptr){ if(t->next->x==a){            break;        } t=t->next;    } if(t->next==nullptr){        node *tt=new node(); tt->x=b; t->next=tt;    }    else{        node *tt=new node(); tt->x=b; tt->next=t->next; t->next=tt;    }}删除第一个值为b的节点。void delete_node(node *head,int b){    node *t=head; while(t->next!=nullptr){ if(t->next->x==b){            break;        } t=t->next;    } if(t->next!=nullptr){ node *tt=t->next; if(tt->next==nullptr){ t->next=nullptr;            free(tt);        }        else{ t->next=tt->next;            free(tt);        }    }}