校友能详细讲讲二面吗

相关推荐

09-07 18:49
南昌大学 Java
## 选择题略## 编程题### T1 最大美观度(100%)三种情况,一个格子、两个格子、三个或以上格子,时间复杂度O(1)### T2 字符消除(100%)考虑记忆化搜索代替dp,先是挨着删除,比如abcdef,删除ab,求cdef,删除cd,求abef。这样过27%,因为重复太多,比如ab删除了,后面求cdef又删除cd,和第一次循环删除cd效果相同。考虑不可逆的记忆化,删除第一个字符和其他(1+2i)位置的字符,保证子串是偶数,AC。#pragma GCC optimize(3)#include<iostream>#include<bits/stdc++.h>using namespace std;typedef long long ll;unordered_map<string, ll> mp;int a[27][27];int n, k;string s;ll dfs(string str){    string key = str;    if(str == "") return 0;    if(mp.find(key) != mp.end()) return mp[key];    ll res = 0;    for(int i = 1; i < str.size()-1; i+=2) res = max(res, dfs(str.substr(1, i) + str.substr(i + 1)) + a[(str[0] - 'a')][(str[i] - 'a')]);    return mp[key] = res;}int main(){    cin >> n >> k;    for(int i = 0; i < k; i++) for(int j = 0; j < k; j++) cin >> a[i][j];    cin >> s;    dfs(s);    cout << mp[s];    return 0;}
查看2道真题和解析 投递滴滴等公司10个岗位
点赞 评论 收藏
分享
牛客网
牛客企业服务