专栏首页Bingo的深度学习杂货店2019夏令营笔试编程题

2019夏令营笔试编程题

问题1:

给一个数组a,求 a[i] + a[j] - (j - i) 的最大值。

input: 
5  # 数组长度
11 6 5 12 18  # 数组元素
output:
29  # 12 + 18 - (5 - 4)
input: 
5  # 数组长度
6 5 4 4 8  # 数组元素
output:
11  # 4 + 8 - (5 - 4)

解题思路:

1、直接暴力 O(n^2), 只能通过 30% 的 case,pass。 2、时间复杂度为 O(n) 的做法: 做法:因为 ans = a[i] + a[j] - (j - i) = a[i] + a[j] + i - j = (a[i] + i) + (a[j] - j),在遍历一遍数组时,每次更新 ans 和 a[i] + i 的最大值,遍历结束后 ans 就是最终的结果。 注意:之所以这样划分,是因为 a[i] + i 的最大值可以在遍历的过程中更新。

C++实现:

#include <iostream>
#include <cstdio>
using namespace std;
int main() {
    int n, num;
    scanf("%d", &n);
    scanf("%d", &num);  // 第一个数 
    int ans = 0;
    int mymax = num + 1;  // a[i]+i 的初始值 
    for(int i = 2; i <= n; i++) {
        scanf("%d", &num);
        ans = max(ans, num-i+mymax);  // 更新 ans
        mymax = max(mymax, num+i);  // 更新 a[i]+i
    }
    cout << ans;  // 输出结果 
    return 0; 
}

问题2:

给一个 M 行 N 列的 0, 1 数组,求由 1 连通的区块个数 (一个 1 的上下左右或者四条对角线也有 1,则代表相连通)。

input:
3 3  # 数组行,列
0 1 0
1 0 0
1 0 1  # 数组中的元素
output:
2  # 两个区块,右下角一个 1 单独形成一个区块,剩下的 3 个 1形成一个区块。

解题思路:

很经典的回溯法(DFS)求解问题。 1、遍历二维数组,如果数组中的元素为 1,先将区块数 ans 加 1,然后利用回溯法(DFS)求解。 2、在 DFS 中,先把 1 的状态改为 0,然后向它的 8 个方向搜索为 1 的元素,继续调用 DFS 遍历。 3、一个区块找完后,标记为 1 的这些位置会变成 0。返回 1 继续搜索下一个区块。 注意: 数组下标不要越界。

实现技巧:如下,可以用一个 8 行 2 列的数组记录搜索的 8 个方向的偏移位置,然后 for 循环遍历,可以防止写 8 个 if 条件。

向左上,左,左下搜索

向上,下搜索

向右上,右,右下搜索

(-1, -1)

(-1, 0)

(-1, 1)

(0, -1)

1(周围8个方向)

(0, 1)

(1, -1)

(1, 0)

(1, 1)

C++实现:

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

int n, m, ans;
// 记录搜索的8个方向的偏移位置 
int d[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,-1},{1,1},{-1,1},{1,-1}};

void DFS(vector<vector<int> > &array, int i, int j) {
    array[i][j] = 0;  // 状态改为0 
    for(int k=0;k<8;k++)  // 循环搜索8个方向 
        if( i+d[k][0]>=0 && i+d[k][0]<n
            && j+d[k][1]>=0 && j+d[k][1]<m
            && array[i+d[k][0]][j+d[k][1]] == 1) // 搜索的下一个位置元素不越界且为1 
            DFS(array, i+d[k][0], j+d[k][1]);
}

int main() {
    scanf("%d%d", &n, &m);
    vector<vector<int> > array(n);  // vector<vector<int> > 要有一个空格 
    for(int i=0;i<n;i++) {
        array[i].resize(m);  // 定义n行m列数组 
    }
    for(int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            scanf("%d",&array[i][j]);  // 读取元素 
        }
    }
    for(int i=0;i<n;i++)
        for (int j=0;j<m;j++)
            if(array[i][j] == 1) { // 如果为1,区块数加1,然后DFS回溯 
                ans++;
                DFS(array, i, j);
            }
    cout << ans;  // 输出结果 
    return 0; 
}

问题3:

给一个包含数字、字母、% 和 # 的字符串,如 3%acm#2%acm#,将 # 号前面的字母(acm)重复 % 号前面的数字(3、2)次,得到一个新字符串:acmacmacmacmacm。可以允许嵌套,如 3%g2%n##,得到 gnngnngnn(n先重复两次,然后和g组合,再重复3次)。

解题思路:

1、遍历字符串,将字符依次入栈,直到碰到 #; 2、出栈,直到碰到 %,就会得到 # 前面的字符串; 3、再出栈,直到不是数字,就会得到 % 前面的数字; 4、将 2 中得到的字符串重复 3 中得到的次数,重新压入栈。 5、直到遍历结束,栈中的字符串就是最后的答案。 注意:出栈的过程中要判断栈不为空。

按照上述解题思路,对于 3%g2%n##,栈的变化为 3%g2%n -> 3%g2% -> 3%g -> 3%gnn -> 3% -> [] -> gnngnngnn,即得到最终的答案。

C++实现:

#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;

stack<string> sta;  // 栈 

string getstr() {  // 得到 % 后 # 前的字符串 
    string s,t;
    while(sta.empty()==false) {  // 栈不为空 
        t = sta.top();  sta.pop();
        if(t[0] == '%') break;
        s = t + s;
    } 
    return s;
}

int getint() {  // 得到 % 前的数字 
    int num=0,res=1;
    string t;
    while(sta.empty()==false) {  // 栈不为空 
        t = sta.top();
        if(t[0]>='0'&&t[0]<='9') num += (t[0]-'0')*res;
        else break;
        sta.pop();
        res*=10;  // 可能多位数字 
    }
    return num;
}

string print() {  // 出栈就是最后的答案 
    string s,t;
    while(sta.empty()==false) {
        t = sta.top(); sta.pop();
        s = t + s;
    }
    return s;
}

int main() {
    string s;
    cin >> s;
    int len = s.size();
    for(int i=0;i<len;i++) {
        string tmp;
        tmp += s[i];
        if(s[i]>='0'&&s[i]<='9') {  // 不是 # 都入栈 
            sta.push(tmp);
        } else if(s[i]>='a'&&s[i]<='z') {
            sta.push(tmp);
        } else if(s[i]>='A'&&s[i]<='Z') {
            sta.push(tmp);
        } else if(s[i]=='%') {
            sta.push(tmp);
        } else {
            string newstr = getstr();
            int num = getint();
            string t;
            for(int j=0;j<num;j++)  // 一次展开的字符串 
                t += newstr;
            sta.push(t);  // 展开的字符串重新压入栈
        } 
    }
    cout << print();  // 输出结果 
    return 0; 
}

问题4:略(据说是 world final 的题,拉开区分度的,我等渣渣题目都没看)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Wolfram新兴领袖计划中基于项目的生活技能

    在在线学习和远程工作的时代,学生们正在获得宝贵的技能,以帮助他们在教育中航行。随着学生在学习历程中对更大的独立性、更好的时间管理和在意想不到的地方找到社区的新需...

    WolframChina
  • 2018南京大学计算机夏令营机试题

    lipper同学问了我一个算法题,由于时间原因没来得及写,lipper同学就自己动手写了出来,并且顺手写了此篇博文,文笔潇洒,与君共勉。

    ACM算法日常
  • Wolfram 美国高中生夏令营

    WolframChina
  • 只需20小时,让0基础的你掌握小程序云开发!这个暑假,约否?

    "听说五湖四海的小伙伴们对2018年腾讯云高校云人才培养计划项目开展的系列线上线下工坊等活动念念不忘呀~这个暑假项目组又为广大童鞋谋福利啦~为期10天的0基础...

    腾讯高校合作
  • 真正的博士是如何参加AAAI, ICML, ICLR等AI顶会的?

    源于对学术的热爱,让很多人走上了博士这条求索之路,而热爱会让他们勤奋付出,勤奋让他们成为佼佼者。

    AI科技大本营
  • 拉夏贝尔财报:“中国版ZARA”出局

    “全力以赴争取实现2020年度扭亏为盈的目标。”6月29日,拉夏贝尔在姗姗来迟的2019年年度财务报告中如此表示。

    刘旷
  • SAP成都研究院Sunshine: 我的C4C实习感受和保研之路

    今天的文章来自SAP成都一位实习生,曾经和Jerry同在C4C成都开发团队一起工作过。在Sunshine最后一个工作日里,Jerry和Sunshine一起吃饭的...

    Jerry Wang
  • SAP成都研究院Sunshine:我的C4C实习感受和保研之路

    版权声明:本文为博主汪子熙原创文章,未经博主允许不得转载。 https://jerry.blog....

    Jerry Wang
  • 工作 --多时区下时间的加减怎么做?

    国际业务往往比国内业务复杂很多,其中一点就是多时区,洛杉矶时间2019.11.3号,正值夏令时切换时踩了一把坑,该篇文章记录下问题,并给出多时区下时间操作比较合...

    屈定
  • Comcast、ricardo.ch、PingCAP、Prowise和蒙特利尔市通过Kubernetes更上一层楼

    Kubernetes赋能Comcast、ricardo.ch、PingCAP、Prowise和蒙特利尔市,在不增加运营团队的情况下扩张规模,并将生产率提高了15...

    CNCF
  • 鹅厂@你,一起来看腾讯T派夏令营!(下) 内附精彩视频!

    首先呈上彩蛋! 点击观看2018腾讯T派夏令营精彩回顾视频 回顾:鹅厂@你,一起来看腾讯T派夏令营!(上) 回顾完上集内容和精彩视频,我们一起来看看后边几...

    腾讯高校合作
  • 亲历李飞飞的AI4ALL,是一种怎样的体验?

    △ 李飞飞(左)和她的学生、AI4ALL的联合创始人Olga Russakovsky(右)

    量子位
  • “一部手机游武隆”上线试运行 打通智慧旅游服务闭环 ​| 数字文旅周报27期(8.26-9.1)

    ? “一部手机游武隆”上线试运行 打通智慧旅游服务闭环 8月26日,全球关注的国际化、专业性盛会2019中国国际智能产业博览会(简称智博会)正式开幕,期间...

    腾讯文旅
  • 2019腾讯浙江文旅数字营销峰会召开 探讨文旅产业转型升级 | 数字文旅周报09期(3.25-3.31)

    ? 2019腾讯浙江文旅数字营销峰会召开 探讨文旅产业转型升级 3月28日,2019浙江文旅数字营销峰会将在杭州香格里拉酒店举行。 本届峰会将邀请腾讯公司...

    腾讯文旅
  • 经典笔试题-编程题

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明...

    cwl_java
  • 挑战与机遇,RPA人才为何如此抢手?

    RPA(Robotic Process Automation)概念自2015年开始流行起来,在2019年开始“爆发”。全球著名信息技术分析机构Gartner曾在...

    RPA小葵
  • 数据揭示疫情期间电力需求变化,电力企业巧用人工智能应对

    新型冠状病毒的传播,导致COVID-19促使美国各州和地方政府制定了居家隔离的政策,并关闭了一些企业。数百万人居家隔离,这种转变不仅给互联网服务提供商、流媒体平...

    大数据文摘
  • 鹅厂@你,一起来看腾讯T派夏令营!(上)

    沉迷工作.jpg 一个普通的七月炎热下午,小编我正在电脑前苦战一份PPT,突然收到一份邀请邮件,邀请我于7月28日-8月1日去参加腾讯T派夏令营,活动地点深圳...

    腾讯高校合作
  • DeeCamp,(可能是)全球最好的 AI 夏令营

    从7月23日开始至8月23日,5周时间,他们将以2018 DeeCamp人工智能训练营之名,度过一段AI为核心的产、学、研全链条之旅。

    量子位

扫码关注云+社区

领取腾讯云代金券