首页 > 8.23腾讯后台笔试解法分享(全AC,C++)
头像
js8544
编辑于 2020-08-23 22:25
+ 关注

8.23腾讯后台笔试解法分享(全AC,C++)

1. 除了第K个数全部打出来即可
int n;
int k;
void solve() {
    cin>>n>>k;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        if(i!=k-1) cout<<x<<" ";
    }
    cout<<endl;
}
2. 把所有长度小于等于K的子串排序找第K个即可。这样保证前K个字串一定被选择同时不会超时。
string s;
int k;
int n;
void solve() {
    cin>>s>>k;
    set<string> ss;
    n = s.size();
    for(int i=0;i<n;i++){
        for(int j=1;j<=k&&i+j<=n;j++){
            ss.insert(s.substr(i,j));
        }
    } 
    for(int i=1;i<k;i++){
        ss.erase(ss.begin());
    }
    cout<<*ss.begin()<<endl;
}
3. 找到小于N的最大的99……9然后拆分即可(我模板用宏#define int long long,没贴进来)
int n;

void solve() {
    cin>>n;
    int x = n;
    int d = 0;
    int ans = 0;
    while(x>=10){
        d *= 10;
        d += 9;
        x /= 10;
        ans += 9;
    }
    int y = n-d;
    while(y){
        ans += y % 10;
        y /= 10;
    }
    cout<<ans<<endl;
    
}
4. Top-down dp,dp[l][r]代表解决l到r区间的最小次数。按区间长度遍历,dp[l][r]初始化成(r-l+1),因为可以对每个木板竖着刷一次。如果横着刷,我们刷arr[l]...arr[r]中最小的次,然后分割成小区间,求和。然后取两者最小值。
int n;
int arr[5001];

int dfs(int l, int r){
    if(l==r){
        if(arr[l]==0) return 0;
        else return 1;
    }

    int ans = r-l+1;
    int minl = INT_MAX;
    for(int i=l;i<=r;i++){
        minl = min(minl, arr[i]);
    }
    int ans1 = minl;
    int curl = -1;
    for(int i=l;i<=r;i++){
        arr[i] -= minl;
        if(arr[i] > 0){
            if(i==0 || arr[i-1]==0){
                curl = i;
            }
            if(i==r){
                ans1 += dfs(curl, i);
            }
        }else{
            if(i>0 && arr[i-1] > 0){
                ans1 += dfs(curl, i-1);
            }
        }
    }
    return min(ans, ans1);
}

void solve() {
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    cout<<dfs(0,n-1)<<endl;
}
5. 二维DP。dp[i][j]代表区间i到j的答案。首先检查i到j是否是回文,如果是的话答案是1,如果不是的话遍历所有分割区间方法求和取最小值。
int n;
string s;
int dp[401][401];
int q;
bool check(int i, int j){
    for(int k=0;k<(j-i+1)/2;k++){
        if(s[i+k] != s[j-k]) return false;
    }
    return true;
}
void solve() {
    cin>>s;
    n = s.size();
    memset(dp,0x3f,sizeof(dp));
    for(int l=0;l<n;l++){
        for(int i=0;i+l<n;i++){
            int j = i+l;
            if(check(i,j)) dp[i][j] = 1;
            else{
                for(int k=i+1;k<=j;k++){
                    dp[i][j] = min(dp[i][j], dp[i][k-1]+dp[k][j]);
                }
            }
        }
    }
    cin>>q;
    for(int i=0;i<q;i++){
        int a,b;
        cin>>a>>b;
        cout<<dp[a-1][b-1]<<endl;
    }
}




全部评论

(13) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐