首页 > 2020.08.26阿里巴巴笔试(1h 2题!!!)
头像
joshua0509
编辑于 2020-08-26 10:51
+ 关注

2020.08.26阿里巴巴笔试(1h 2题!!!)

第一题:给出两个长度均为n的字符串A, B(只包含小写字母),求字典序介于这两个字符串之间的且长度为n的字符串有多少个, 即满足 A < X < B;
思路:直接把字符串看出是一个26进制的数据,然后相减的结果 - 1 就是答案了!
注意:26^10 超过了int的范围,所以用long long, 最后5min通过,卡崩溃了...
代码:AC
#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("a.txt", "r", stdin);
#endif

    int t, n;
    string stra, strb;

    cin >> t;
    while(t--) {
        cin >> n >> stra >> strb;
        if(stra >= strb) {
            cout << 0 << endl;
            continue;
        }

        int a[16] = {0};
        int b[16] = {0};
        for(int i = 0; i < n; ++i) {
            a[i] = stra[i] - 'a' + 1;
            b[i] = strb[i] - 'a' + 1;
        }

        int pos = 0;
        for(int i = 0; i < n; ++i) if(a[i] != b[i]) {pos = i; break;}
        
        ll suma = 0, sumb = 0, t = 1;
        for(int i = pos+1; i < n; ++i) {
            suma = suma * 26 + (ll)a[i];
            sumb = sumb * 26 + (ll)b[i];
            t *= 26;
        }
        printf("%lld\n", sumb + 1LL * t * (b[pos] - a[pos]) - suma - 1LL);
    }
    return 0;
}

第二题:题目刚刚读完,最后2分钟交卷了,我也太菜了!
我感觉第二题不是那么难,有点01背包的味道,耗费忍耐值,得到对应的数量的怪!可能与阿里无缘了,不用惦记了!

全部评论

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

推荐话题

相关热帖

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

近期精华帖

热门推荐