首页 > 2020.08.23腾讯秋招第一场笔试(2h 5题)
头像
joshua0509
编辑于 2020-08-24 06:27
+ 关注

2020.08.23腾讯秋招第一场笔试(2h 5题)

第一题:打印链表,有一个元素删除了。
代码:
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define ios ios::sync_with_stdio(false),cin.tie(0);

template <typename T>
inline void read(T &x) {char ch=getchar(); int f=1; x=0; while(!isdigit(ch)){if(ch=='-')f *= -1; ch=getchar();} while(isdigit(ch)) {x = (x<<1) + (x<<3) + (ch^48); ch=getchar();} x*=f;}
ll qpow(ll x, ll y) { ll a=1, b=x; while(y){if(y&0x1) a*=b; b*=b; y>>=1;} return a;}

const int maxn = 1000005;
int a[maxn];

int main(void)
{
#ifndef ONLINE_JUDGE
    freopen("a.txt", "r", stdin);
#endif

    int n, k;
    while(cin >> n >> k) {
        for(int i = 1; i <= n; ++i) cin >> a[i];
        for(int i = k+1; i <= n; ++i) a[i-1] = a[i];
        n--;
        for(int i = 1; i <= n; ++i) {
            if(i == 1) cout << a[i];
            else cout << " " << a[i];
        }
        cout << endl;
    }
    return 0;
}

第二题:找到第k小的子符串,1 <= k <= 5, 理论上最长只需要5个字符的长度就好了。
代码:
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define ios ios::sync_with_stdio(false),cin.tie(0);

template <typename T>
inline void read(T &x) {char ch=getchar(); int f=1; x=0; while(!isdigit(ch)){if(ch=='-')f *= -1; ch=getchar();} while(isdigit(ch)) {x = (x<<1) + (x<<3) + (ch^48); ch=getchar();} x*=f;}
ll qpow(ll x, ll y) { ll a=1, b=x; while(y){if(y&0x1) a*=b; b*=b; y>>=1;} return a;}

int main(void)
{
#ifndef ONLINE_JUDGE
    freopen("b.txt", "r", stdin);
#endif

    int k;
    string s;
    while(cin >> s >> k) {
        set<string> heap;
        int n = s.size();

        for(int len = 1; len <= min(n, k); ++len) {
            for(int i = 0; i+len <= n; ++i) {
                heap.insert(s.substr(i, len));
                if(heap.size() > k) heap.erase(next(heap.begin(), k));
            }
        }
        cout << *heap.rbegin() << endl;
    }   
    return 0;
}

第三题:数字被拆解后,能构成的最大的数位值是多少?例子:35,最大被拆为16 + 19: 1 + 6 + 1 + 9 = 17,17就是最大值
代码:
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define ios ios::sync_with_stdio(false),cin.tie(0);

template <typename T>
inline void read(T &x) {char ch=getchar(); int f=1; x=0; while(!isdigit(ch)){if(ch=='-')f *= -1; ch=getchar();} while(isdigit(ch)) {x = (x<<1) + (x<<3) + (ch^48); ch=getchar();} x*=f;}
ll qpow(ll x, ll y) { ll a=1, b=x; while(y){if(y&0x1) a*=b; b*=b; y>>=1;} return a;}

int getVal(int x) {
    int s = 0;
    while(x > 0) {
        s += x%10;
        x /= 10;
    }
    return s;
}

int main(void)
{
#ifndef ONLINE_JUDGE
    freopen("c.txt", "r", stdin);
#endif

    int t, n;
    cin >> t;
    while(t--) {
        cin >> n;
        if(n == 1) {cout << 1 << endl; continue;}

        int x = 0;
        while(x <= n) x = x*10 + 9;
        x /= 10;

        cout << getVal(x) + getVal(n - x) << endl;
    }
    return 0;
}

第四题:用刷子刷板子,每个板子高度不一样,可以横刷或者竖着刷,算一次,最少刷几次?
代码:

第五题:给一个字符串,并且给出一个区间[l, r],问该区间进行拆分成所有的子串都是回文的最少数量是多少?
代码:
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define ios ios::sync_with_stdio(false),cin.tie(0);

template <typename T>
inline void read(T &x) {char ch=getchar(); int f=1; x=0; while(!isdigit(ch)){if(ch=='-')f *= -1; ch=getchar();} while(isdigit(ch)) {x = (x<<1) + (x<<3) + (ch^48); ch=getchar();} x*=f;}
ll qpow(ll x, ll y) { ll a=1, b=x; while(y){if(y&0x1) a*=b; b*=b; y>>=1;} return a;}

const int maxn = 500;
bool f[maxn][maxn];
int dp[maxn][maxn];

int dfs(int l, int r) {
    if(l == r || f[l][r]) return 1;
    if(dp[l][r]) return dp[l][r];

    int t = maxn;
    for(int i = l; i < r; ++i) {
        t = min(t, dfs(l, i) + dfs(i+1, r));
    }
    return dp[l][r] = t;
}

int main(void)
{
#ifndef ONLINE_JUDGE
    freopen("e.txt", "r", stdin);
#endif

    int n;
    string s;
    while(cin >> s) {
        memset(f, 0, sizeof(f));
        memset(dp, 0, sizeof(dp));
        int n = s.size();

        for(int i = n-1; i >= 0; --i) {
            f[i][i] = true;
            for(int j = i+1; j < n; ++j) {
                if(s[i] == s[j] && (j-i == 1 || f[i+1][j-1])) {
                    f[i][j] = true;
                }
            }
        }

        int q;
        cin >> q;
        while(q--) {
            int l, r;
            cin >> l >> r;
            l--;
            r--;
            if(f[l][r]) {
                cout << 1 << endl;
                continue;
            }
            int ans = r - l + 1;
            cout << dfs(l, r) << endl;
        }
    }
    return 0;
}


全部评论

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

推荐话题

相关热帖

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

近期精华帖

热门推荐