目录

A.统计回文子串

B.构建矩阵

C.找规律填数字

D.复原二叉树

E.子树的后序遍历

F.迷宫问题

A.统计回文子串

#include <iostream>
#include <string>
#include <vector>
  
using namespace std;
  
int countPalindromicSubstring(string s) {
    int n = s.length();
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int count = 0;
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
        count++;
    }
  
    for (int i = 0; i < n - 1; i++) {
        if (s[i] == s[i + 1]) {
            dp[i][i + 1] = true;
            count++;
        }
    }
  
  
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                count++;
            }
        }
    }
  
    return count;
}
  
int main() {
    string s;
    while (cin >> s) {
        cout << countPalindromicSubstring(s) << endl;
    }
    return 0;
}

B.构建矩阵

依据题意遍历即可

#include<bits/stdc++.h>
#define ll long long
 
using namespace std;
int a[10][10];
int main(){
    int n;cin>>n;
    int k;
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            a[i][j]=i*j;
        }
    }
    for(int i=1;i<=n;i++){
        cin>>k;
        for(int x=1;x<=k;x++){
            for(int y=1;y<=k;y++){
                cout<<a[x][y]<<' ';
            }
            cout<<'\n';
        }
    }
     
    return 0;
} 

C.找规律填数字

#include<bits/stdc++.h>
  
int main()
{
    int a,b,c,d,e;
    while(scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)!=EOF)
    { 
        if(a==0&&b==0&&c==0&&d==0&&e==0)
        {
            break;
        }
        if((b-a) == (c-b) && (d-c)==(c-b) &&(d-c)==(e-d))
        {
            int t = b - a;
            for(int i = 1;i<=5;i++)
            {
                printf("%d ",e+i*t);
            }
            printf("\n");
        }
        if((b/a) == (c/b)&&(c/b)==(d/c)&&(d/c)==(e/d)&&(b/a)!=1)
        {
            int t = b/a;
            for(int i = 1;i<=5;i++)
            {
                printf("%d ",e*(int)pow(t,i));
            }
            printf("\n");
        }
        if(a+b==c&&b+c==d&&c+d==e)
        {
            int t1=d,t2=e,s=0;
            for(int i = 6;i<11;i++)
            {
                s=t1+t2;
                t1=t2;
                t2=s;
                printf("%d ",s);
            }
            printf("\n");
        }
    }
    return 0;
}

D.复原二叉树

给前序和中序，求后序。前序是根左右，中序是左根右，可以看出前序的第一个必定是根，中序遍历中，根左边的是左子树，根右边是右子树。这样，又能找出新的前序遍历和中序遍历，不断递推求解即可

#include<bits/stdc++.h>
#define ll long long
 
using namespace std;
void aftord(string beford,string midord){
    if(!beford.size()) return;
    char a = beford[0];
    int k = midord.find(a);
    aftord(beford.substr(1,k),midord.substr(0,k));
    aftord(beford.substr(k+1),midord.substr(k+1));
    cout<<beford[0];
}
string s1,s2;
 
int main(){
    while(cin>>s1>>s2){
        aftord(s1,s2);
        cout<<'\n';
    }
    return 0;
} 

E.子树的后序遍历

直接把后序遍历给出了，那么直接截取右子树即可

#include<bits/stdc++.h>
#define ll long long
 
using namespace std;
string s1,s2;
 
int main(){
    cin>>s1>>s2;
    char a;cin>>a;
    char s = s2[s2.length()-1];
    int k = s1.find(s);
    cout<<(a=='L'  ? s2.substr(0,k) : s2.substr(k,s1.length()-k-1));  
    return 0;
} 

F.迷宫问题

典型的搜索问题。求最优解一般用 bfs ，若用dfs则需判断是否需要更新

#include<bits/stdc++.h>
#define ll long long

using namespace std;
bool a[110][110];
int ans[110][110];
int m,n;
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
pair<int,int>st,en;

void dfs(int x,int y){
    for(int i=1;i<=4;i++){
    	int xx = x+dx[i];
		int yy = y+dy[i]; 
        if(!a[xx][yy]) continue;
        if(ans[xx][yy]==0||ans[xx][yy]>ans[x][y]+1){
        	ans[xx][yy]=ans[x][y]+1;
        	dfs(xx,yy);
		}
    }
}

int main(){
    int k;
    cin>>k;
    while(k--){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
        	char temp;
            cin>>temp;
            
            if(temp=='S')
            {
                st.first=i,st.second=j;
            }
            if(temp=='-'){
            	a[i][j]=1;
			}
			if(temp=='E'){
				a[i][j]=1;
				en.first=i,en.second=j;
				
			}
        }
    }   
    dfs(st.first,st.second);
    cout<<(ans[en.first][en.second]==0? -1 : ans[en.first][en.second])<<'\n';
    memset(a,0,sizeof a );
    memset(ans,0,sizeof ans );
    }
    return 0;
}