腾讯8.23笔试 后台

1 删除链表

#include
#include
#include
using namespace std;
int main()
{
    int n,k,m;
    scanf("%d %d",&n,&k);
    scanf("%d",&m);
    if(k != 1)
        printf("%d ",m);
    for(int i=2;i<=n;i++){
        scanf("%d",&m);
        if(i != k)
            printf("%d ",m);
    }
    return 0;
}

2 最小k字符串 ：没写出来
3 两个数的拆分之和

// 思路678  分为99 和剩余的部分的  使得9最多就可以了，这样一定是最大的

#include<iostream>
#include<cstring>
#include<stdio.h>
using namespace std;
long long get_ws(long long n){
    long long k =0;
    while(n>0){
        n /=10;
        k = k*10 + 9;
    }
    return k/10;

}
int main(){
    long long res,k,m,j;
    int n;
    scanf("%d",&n);
    while(n--){
        scanf("%ld",&m);
        if(m < 19){
            printf("%d\n",m);
            continue;
        }
        k = get_ws(m);
        j = m - k;
        res = 0;
        while(k > 0){
            res += k % 10;
            k /= 10;
        }
        while(j > 0){
            res += j % 10;
            j /= 10;
        }

    }
    printf("%ld", res);
    return 0;
}

4 刷木板的问题 DP问题

#include<iostream>
#include<cstring>
#include<stdio.h>
using namespace std;
const int N =5050;
int a[N];
int solve(int l,int r){
    if(l > r)
        return 0;

    int k = l;
    for(int i = l; i <= r;i++){
        if(a[k] > a[i])
            k = i;

    }//找到最短的
    int sum = a[k];
    for(int i = l;i <= r; i++){//所有数都减去这个最小的数
        a[i] -= sum;
    }
    return min(r - l + 1, solve(l,k-1) + solve(k + 1,r) + sum);//在横着涂和竖着涂中取最小值

}

int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0;i < n;i++){
        scanf("%d",&a[i]);
    }
    printf("%d\n",solve(0,n-1));

    return 0;
}

5 回文串问题

/*
f(i,j)表示 i到j 判断是不是会回文串
f(i,j) = min(f(i,j),f(i,k)+f(k+1,j))
*/

#include<iostream>
#include<cstring>

#include<stdio.h>
using namespace std;
int f[505][505];
string s;
bool is_huiwen(int l,int r){
    while(l <= r){
        if(s[l] != s[r]){
            break;

        }
        l++;
        r--;
    }
    if(l >= r){
        return true;
    }
    else{
        return false;
    }
}
int main(){
    int n;
    int l,r;

    cin>>s;
    n = s.size();
    for(int i=0 ;i <n;i++){
        for(int j =0; j<n;j++){
            f[i][j] = j - i + 1;
        }
        f[i][i] = 1;
    }
    for(int i=0 ;i <n;i++){
        for(int j =i+1; j<n;j++){
                if(is_huiwen(i,j))
                    f[i][j] = 1;
        }

    }
    for(int i=0 ;i < n;i++){
        for(int j =i+1; j<n;j++){
            for(int k = i; k<j;k++){
                if(f[i][k] + f[k+1][j] < f[i][j]){
                    f[i][j] = f[i][k] + f[k+1][j];
                }
            }
        }

    }
    scanf("%d",&n);
    while(n--){
        scanf("%d %d",&l,&r);
        l--;
        r--;//数组坐标是0开始，实际上的r和l是1开始
        if(l <= r){
            printf("%d\n",f[l][r]);
        }
        else{
            printf("%d\n",f[r][l]);
        }
    }
    return 0;
}