美团4.4笔试题解

早起做了一个小时,除了第二题没得全分(后来发现是没有特殊考虑没有切精度的情况,***了),其他都ac了。

第一题

脑经急转弯,统计出每个字符出现次数,答案就是各个字符出现次数+1的累乘。注意每一步都要取模,且中间过程可能会爆int,最后用long long存,不然需要对中间过程强转一下,代码如下:

#include <iostream>
using namespace std;

const int MOD = 20210101;
int num[26];
int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    string s; cin >> s;
    for(char c: s) num[c - 'a'] ++ ;
    long long res = 1;
    for(int i = 0; i < 26; i ++ ){
        res = res * (num[i] + 1) % MOD;
    }
    cout << res << endl;
    return 0;
}

第二题

没得全分就不贴代码了。。。

第三题

暴力即可,找出每个数的所有约数,这个计算时间复杂度为,总共有20w个数,每个数最大为2w,故最多计算2000w+次,可以过。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    int n, k; cin >> n >> k;
    string t = to_string(k);
    int res = 0;
    for(int i = 0; i < n; i ++ ){
        int a; cin >> a;
        vector<int> f;
        for(int j = 1; j * j <= a; j ++ ){
            if(a % j == 0){
                f.push_back(j);
                if(a / j != j) f.push_back(a / j);
            }
        }
        sort(f.begin(), f.end());
        string s;
        for(int num: f) s += to_string(num);

        int index = s.find(t);
        if(index >= 0 && index < s.size()) res ++ ;
    }
    cout << res << endl;
    return 0;
}

第四题

简单dp,用记忆化搜索写起来更简单,因为数据量只有50,无需优化,写了个的dfs,如下:dfs(x,y)表示从1跳到g[x][y]对应的数字最少花费是多少,显然dfs(x,y)=min(dfs(i,j)+abs(x-i)+abs(y-j)),(i,j)满足(g[i][j]+1=g[x][y])

#include <iostream>
#include <set>
#include <cstring>
using namespace std;

const int N = 55;
int g[N][N];
int dp[N][N];
int n, k; 
void dfs(int x, int y){
    if(dp[x][y] != -1) return;
    if(g[x][y] == 1) {
        dp[x][y] = 0;
        return;
    }
    int t = g[x][y] - 1;
    int ret = 1e9;
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ ){
            if(g[i][j] == t){
                int d = max(x - i, i - x) + max(y - j, j - y);
                dfs(i, j);
                ret = min(ret, dp[i][j] + d);
            }
        }
    dp[x][y] = ret;
}
int main(int argc, char const *argv[])
{
    cin >> n >> k;
    set<int> st;
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ ){
            cin >> g[i][j];
            if(g[i][j] >= 1 && g[i][j] <= k)
                st.insert(g[i][j]);
        }
    if(st.size() != k){
        cout << -1 << endl;
        return 0;
    }
    int res = 1e9;
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ ){
            if(g[i][j] == k) {
                memset(dp, -1, sizeof dp);
                dfs(i, j);
                res = min(res, dp[i][j]);
            }
        }
    cout << res << endl;
    return 0;
}

专项题

这个没啥说的,求一个数组前k项,这k项之和最大,前缀和即可:

#include <iostream>
using namespace std;

const int N = 200001;
int a[N], b[N];
int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    int m, n; cin >> m >> n;
    int res = 0, t1 = 0, t2 = 0;
    for(int i = 0; i < m; i ++ ){
        int x; cin >> x;
        a[i + 1] = a[i] + x;
        t1 = max(t1, a[i + 1]);
    }
    for(int i = 0; i < n; i ++ ){
        int x; cin >> x;
        b[i + 1] = b[i] + x;
        t2 = max(t2, b[i + 1]);
    }
    res = t1 + t2;
    cout << res << endl;
    return 0;
}
#笔试题目##美团#
全部评论
我只a了第二道题.... #include <bits/stdc++.h> using namespace std; int main(){     int n,ans=0,t,x,y=1,z=1;     scanf("%d",&n);     while (n--)     {         scanf("%d%d",&t,&x);         if(t==1){             if(z==1)z+=1;             else z+=2;         }else{             y++;         }     }     printf("%d\n",z*y); }
2 回复
分享
发布于 2021-04-04 15:13
第一题 太难发现了。感觉有点像找规律,一直当子串去找。。。 浪费了太多时间  导致第二第三题都只过了55 第四题没写 第五题ac了
1 回复
分享
发布于 2021-04-04 14:52
英特尔
校招火热招聘中
官网直投
确实,那个切蛋糕真怪异
1 回复
分享
发布于 2021-04-04 19:17
我能说我菜到直接关闭网页吗😭😭😭
1 回复
分享
发布于 2021-04-04 22:29
大佬好强,我就A了第三题~
1 回复
分享
发布于 2021-04-05 12:19
第四题补一个Java版的,返回-1的情况太简单,就暂时忽略掉 https://www.nowcoder.com/discuss/632547
1 回复
分享
发布于 2021-04-05 21:49
怎么样才能像你一样强😥我就第一道和第二道a了9%
点赞 回复
分享
发布于 2021-04-04 12:39
专项题有对应的leetcode吗?
点赞 回复
分享
发布于 2021-04-04 19:31
有没有投测试的,为啥附加题里面代码是写好的,我进去点了下确定直接通过了!
点赞 回复
分享
发布于 2021-04-04 22:40
大佬,求告知算法怎么刷,求点经验
点赞 回复
分享
发布于 2021-04-04 23:51
我的第三题 找约数循环条件设错了不然也A4题了😂 大佬报的什么岗位呀
点赞 回复
分享
发布于 2021-04-07 21:46

相关推荐

25 55 评论
分享
牛客网
牛客企业服务