菲洛嘉青春动能素135HA FILLMED® NCTF 135HA LED指示灯的常见故障分析 智微智能 Elkhartlake K075终端,零售产业新选择 天空蓝拓客管理系统详细介绍版 muso公链项目 天使计划 是什么?[秘] 独家揭秘最前沿的家装“黑科技”——掌赋 天博体育欧洲杯特辑,东道主法兰西的失意2016 亚马逊的送货侦察员 学习听起来像挡泥板 Google Comics Factory使ML变得容易 笑着说-男性或女性 Amazon Rekognition中更好的人脸检测 关于Spaun的真相-大脑模拟 两个聊天机器人彼此聊天-有趣又怪异 GANPaint:将AI用于艺术 WCF和WF给予社区 从耳朵到脸 所有神经网络的深层缺陷 蠕虫在尾巴上平衡杆子 Kickstarter上的OpenCV AI套件 TensorFlow-Google的开源AI和计算引擎 众包取代新闻工作者 Google的DeepMind学会玩街机游戏 哑机器人V智能机器人 .NET与.NET 5融为一体 Google的深度学习-语音识别 LInQer将.NET LINQ移植到Javascript 机器人TED演讲-新的图灵测试? GAN的发明者加入苹果 您的智能手机会监视您键入的内容 人工智能帮助改善国际象棋 Zalando Flair NLP库已更新 TensorFlow 1.5包含移动版本 AlphaGo输了一场比赛-比分3-1 虚拟机器学习峰会 Microsoft开源AI调试工具 SharePoint走向移动 F#4.0发出文化变革的信号 克里斯蒂拍卖AI艺术品 人工智能如何区分 Facebook在蒙特利尔的新AI实验室 Mozilla想要您的声音 微软使用极深的神经网络赢得ImageNet 建立AI合作伙伴关系 .NET Core 3-Microsoft几乎回到了起点 神经网络-更好的销售商? Google使用AI查找您的住所 虹膜-适用于Android的Siri证明苹果没有优势 TensorFlow 2提供更快的模型训练 深度学习研究人员将为Google工作
您的位置:首页 >程序人生 >

2020阿里笔试题解(9.11)

一个小时两道题,感觉难度也没有传说中的那么大,第二题稍微卡了一会,但是还是做完了

第一题

题意

有一个长度为n的全是小写字母的字符串,有m个要匹配的字符串,问一共能匹配多少次。 例如ababa,2个匹配字符串ab和aba,共能匹配4次。ab2次,aba两次。 数据范围n和m为1e5,匹配字符串长度为[2,10]。

分析

因为匹配字符串长度很短,因此完全可以计算所有的长度为[2,10]的子串的个数,然后用map来存,然后将m个匹配字符串的个数相加即可。

参考代码

#include <cstdio>#include <iostream>#include <string>#include <unordered_map>using namespace std;int n, m;unordered_map<string, int> M;string s, t;int main() {cin >> n >> m;cin >> s;int len = s.length();for (int i=0; i<len; ++i) {for (int j=2; j<=10 && i+j-1<len; ++j) {M[s.substr(i, j)]++;}}int ans = 0;for (int i=0; i<m; ++i) {cin >> t;ans += M[t];}cout << ans << endl;return 0;}

第二题

题意

给一个矩阵,其中值为-1的部分需要替换,如果为-1的部分上下左右相连可以组成连通块,每个连通块中的值都应该被替换成这与这个连通块直接相连的非-1部分的平均值向下取整。 例如:

5 40 8 -1 00 0 8 00 8 8 00 8 0 -10 -1 -1 0

输出:

0 8 5 00 0 8 00 8 8 00 8 0 00 2 2 0

矩阵中有三个连通块: 第一个:{(1,3)},与其直接相连的数有{8, 8, 0},求平均向下取整为5 第二个:{(4,4)},与其直接相连的数有{0, 0, 0},求平均向下取整为0 第三个:{(5,2), {5,3)},与其直接相连的数有{0, 8, 8, 0},求平均向下取整为2

分析

第一步肯定是先求连通块,然后给连通块编号。然后遍历每一个非连通块的值,判断其是否属于某一个连通块,并用sum和num计算每个连通块周围非-1的总和,以及个数。

参考代码

#include <cstdio>#include <iostream>#include <cstring>using namespace std;int n, m;int a[1005][1005];int id[1005][1005];int vis[1005][1005];int num[1000005];int sum[1000005];int dx[4] = {0, 1, 0, -1};int dy[4] = {1, 0, -1, 0};bool judge(int x, int y) {if (1<=x && x<=n && 1<=y && y<=m) return true;return false;}void dfs(int x, int y, int _id) {vis[x][y] = 1;id[x][y] = _id;for (int i=0; i<4; ++i) {int nx = x + dx[i];int ny = y + dy[i];if (judge(nx, ny) && !vis[nx][ny] && a[nx][ny]==-1) {dfs(nx, ny, _id);}}}int main() {scanf("%d%d", &n, &m);memset(sum, 0, sizeof(sum));memset(num, 0, sizeof(num));for (int i=1; i<=n; ++i) {for (int j=1; j<=m; ++j) {id[i][j] = vis[i][j] = 0;scanf("%d", &a[i][j]);}}// 求连通块,并编号int __id = 0;for (int i=1; i<=n; ++i) {for (int j=1; j<=m; ++j) {if (a[i][j]==-1 && !vis[i][j]) {__id++;dfs(i, j, __id);}}}// 计算连通块周围非-1的数量以及总和for (int i=1; i<=n; ++i) {for (int j=1; j<=m; ++j) {if (a[i][j] != -1) {int idd[4];idd[0] = idd[1] = idd[2] = idd[3] = -1;// 判断是否属于上下左右的连通块,如果属于则累加和以及个数// 注意有可能出现上下左右其中几个是同一个连通块,需要去重for (int k=0; k<4; ++k) {int nx = i + dx[k];int ny = j + dy[k];if (judge(nx, ny) && a[nx][ny]==-1) {bool flag = true;for (int l=0; l<k; ++l) {if (idd[l]!=-1 && idd[l]==id[nx][ny]) {flag = false;break;}}if (!flag) continue;idd[k] = id[nx][ny];sum[id[nx][ny]] += a[i][j];num[id[nx][ny]]++;}}}}}for (int i=1; i<=n; ++i) {for (int j=1; j<=m; ++j) {if (a[i][j] == -1) {if (num[id[i][j]] == 0)printf("0 ");else printf("%d ", sum[id[i][j]] / num[id[i][j]]);} else {printf("%d ", a[i][j]);}}printf("\n");}return 0;}

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。