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

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

——dansen

1. Count number of binary strings without consecutive 1's

Given a positive integer n(3≤n≤90), count all possible distinct binary strings of length n such that there are no consecutive 1's .

Examples:

Input:  2 
Output: 3 // The 3 strings are 00, 01, 10 

Input: 3 
Output: 5 // The 5 strings are 000, 001, 010, 100, 101

中文题意:给定一个正整数n(3≤n≤90),数出长度为n的所有可能的不同二进制串的个数,使得串中没有连续的1出现。

解题思路:考试时第一想法是用回溯法,因为长度为n的所有二进制串形成一棵子集树,所以可以用DFS遍历子集树,遍历过程中检查是否有连续的1出现,作为约束函数用于剪枝,时间复杂度为O(2n)。然而用代码实现以后发现10个测点只通过了5个,还有5个测点超时了,毕竟时间复杂度O(2n)实在是太高了。

思考了一会儿,忽然想起来以前学习数理逻辑与图论这门课的时候在递推那一章做过这道题,于是恍然大悟,可以用动态规划求解!令a[i]为长度为i的不含连续1的二进制串的个数,考虑长度为i的不含连续1的任意一个二进制串:若第i位(末位)为0,则第i-1位可以为0也可以为1,这种情况的二进制串有a[i-1]个;若第i位为1,则第i-1位只能为0(否则最后两位为连续两个1,不符题意),进一步考虑第i-2位,由第i-1位为0可知第i-2位可以为0也可以为1,这种情况的二进制串有a[i-2]个。综上可以写出递推式 a[i]=a[i-1]+a[i-2], i≥3,边界条件为a[1]=1,a[2]=3。本题动态规划的时间复杂度为O(n),所以得到一个教训——能用动态规划做的就尽量不要用回溯法,回溯法实在太容易超时了。。。

这道题有个坑就是当n比较大的时候使用int会溢出,导致第一次用动态规划提交时只通过了5个测点,后来把数组a的元素类型改为long long就AC了。本题动态规划的代码实现如下:

#include<iostream>
using namespace std;
int main() {
    int n;
    cin>>n;
    long long *a = new long long[n+1]{0,2,3};
    for(int i=3;i<=n;i++) {
        a[i]=a[i-1]+a[i-2];
    }
    cout<<a[n]<<endl;
    return 0;
}

2. Missing number

Given a positive integer n(n≤40), pick n-1 numbers randomly from 1 to n and concatenate them in random order as a string s, which means there is a missing number between 1 and n. Can you find the missing number?(Notice that in some cases the answer will not be unique, and in these cases you only need to find one valid answer.)

Examples:

Input:  20 
        81971112205101569183132414117
Output: 16

中文题意:给定正整数n(n≤40),从1到n中随机选择n-1个数,并将它们以随机顺序连接为字符串s,这意味着在1和n之间有一个缺失的数字。你能找到那个缺失的数字吗?(请注意在某些情况下答案不唯一,此时你只需要找到一个有效的答案。)

解题思路:这题乍一看似乎和LeetCode 268 Missing Number十分相似,但实则大相径庭,因为LeetCode的Missing Number是把选中的n-1个数字以int数组的形式直接告诉我们了,而这题n-1个数字是以随机顺序连接在一起形成的字符串,没有告诉我们是如何划分的,要找出缺失的数字也没那么简单了。

注意到题中限制了n≤40,为什么n的上界取这么小呢?我觉得这就是在暗示这题解法的时间复杂度比较高,所以自然应该想到回溯法。分析本题特点,只要能找到字符串s的合理划分方法,从s中提取出n-1个数字,缺失的那个数字自然就找出来了,所以本题的关键就在于字符串s的划分。具体怎么划分呢?不妨这样考虑,设字符串s的长度为n,则对于s中的第i(1≤i≤n-1)个字符,它要么与第i+1个字符结合成一个数字,要么自己单独作为一个数字,对于第n个字符则只能单独作为一个数字。可能有人要问了,第i个字符不是还可以向前和第i-1个字符结合吗?当然可以,但是这种情况就和第i-1个字符向后与第i个字符结合的情况重叠了,所以对这种情况不做考虑。如此一来就是n个字符,除第n个字符外每个字符有两种选择,这是不是和背包问题很像呢?所以用回溯法应该是没问题的。向下一层左子树搜索的约束条件就是由第i个字符与第i+1个字符结合得到的数字落在1到n的范围内且之前未被划分出来,向下一层右子树搜索的约束条件就是由第i个字符单独形成的数字落在1到n的范围内且之前未被划分出来。如若当前字符为'0',说明之前的划分有误(因为'0'既不能和后一个字符结合,也不能单独成数),应该直接返回上一层。如何知道已经找到了正确的划分呢?只需要在搜索到叶子结点时检验是不是已经划分出n-1个数字即可。

这题需要注意的是对于某些测点可能会有两个答案,比如n=27,s="37258161810262717111420212324131912956152241212345678910" ,s有两种可能的划分,一种是“3 7 25 8 16 18 10 26 27 17 11 14 20 2 1 23 24 13 19 12 9 5 6 15 22 4”,另一种是“3 7 25 8 16 18 10 26 27 17 11 14 20 21 23 24 13 19 1 2 9 5 6 15 22 4”,前者得到的答案是21,后者得到的答案是12,两个答案都是合理答案,至于导致答案不唯一的原因请读者自己揣摩。

有一点我要坦白:很遗憾考试时我并没有做出这题,由于当时第一题用回溯法超时了,这题又被LeetCode上的Missing Number带偏了思路,所以考试时压根就没往回溯法去想,只靠一点骗分技巧骗了点分。考完以后才想到这题也可以用回溯法,然后自己试着实现了一下。为了便于调试,本题的测点全部随机产生,经检验在100000个测点的情况下依然是可以AC的,调试的时候测了下时间,当n接近40的时候回溯部分的耗时也在10-5~10-4 s量级,应该不用担心TLE。回溯法的实现代码如下:

#include<iostream>
#include<vector>
#include<set>
#include<string>
#include<sstream>
#include<ctime>
#include<algorithm>
using namespace std;

const int total=100000;    //测点总数
int n;
string s;
void createSample(int& ans,vector<int>& split);
void backtrack(int index,int cnt,vector<bool>& existed,set<int>& myAns);

int main() {
    srand((unsigned int)time(NULL));
    int num=0;  //通过的测点数
    for(int i=0;i<total;i++) {
        int ans;    //缺失的数字,即本题答案
        vector<int> split;  //测点字符串产生时的划分方法
        n=rand()%40+1;
        s.clear();
        createSample(ans,split);
        set<int> myAns;     //使用回溯法得到的答案
        vector<bool> existed(n+1,false);    //标记已划分出来的数字,existed[i]=true表示数字i已划分出来
        backtrack(0,0,existed,myAns);
        set<int>::iterator it;
        it=myAns.find(ans);
        if(it!=myAns.end()) {
            num++;
        }
        else {
            cout<<n<<endl<<s<<endl;
            cout<<"Split:";
            for(auto n : split) {
                cout<<n<<' ';
            }
            cout<<endl;
            cout<<"Your answer:";
            for(set<int>::iterator it=myAns.begin();it!=myAns.end();it++ ) {
                cout<<*it<<' ';
            }
            cout<<endl;
            cout<<"Expected answer:"<<ans<<endl;
            cout<<"Passed/Total: "<<num<<'/'<<total<<endl;
            cout<<"Wrong answer"<<endl;
            break;
        }
    }
    if(num==total) {
        cout<<"Passed/Total: "<<num<<'/'<<total<<endl;
        cout<<"Accepted"<<endl;
    }
    return 0;
}

//随机产生测点字符串s,缺失的数字存放在ans中,字符串的划分方法存放在split中
void createSample(int& ans,vector<int>& split) {
    int m,num=0;
    vector<bool> existed(n+1,false);
    while(num < n-1) {  //每一轮随机产生一个数字m,直至产生n-1个数字为止
        m=rand()%n+1;
        //检查数字m之前是否已经产生过,只有未产生过的数字才能加入到字符串中
        if(existed[m]==false) {
            //将int转换为string,加入到字符串s中,并将数字m保存到split中
            stringstream ss;
            string tmp;
            ss<<m;
            ss>>tmp;
            s+=tmp;
            existed[m]=true;
            split.push_back(m);
            num++;
        }
    }
    vector<bool>::iterator it;
    it=find(existed.begin()+1,existed.end(),false);
    ans=it-existed.begin();
}

//回溯法求解字符串s的划分,index为字符串s的下标,cnt为已经划分出的数字个数,existed标记已经划分出了的数字,myAns为求解出的缺失的数字
void backtrack(int index,int cnt,vector<bool>& existed,set<int>& myAns) {
    if(index >= s.length()) {
        //已经划分出n-1个数字,existed中未被标记的就是缺失的数字
        if(cnt==n-1) {
            vector<bool>::iterator it;
            it=find(existed.begin()+1,existed.end(),false);
            myAns.insert(it-existed.begin());
        }
        return;
    }
    if(s[index]=='0')   return;  //用于剪枝
    //下标为index的字符与下标为index+1的字符组合成一个数字
    if(index < s.length()-1) {
        int tmp1=(s[index]-'0')*10+s[index+1]-'0';
        if(tmp1 >= 1&&tmp1 <= n&&existed[tmp1]==false) {
            existed[tmp1]=true;
            cnt++;
            backtrack(index+2,cnt,existed,myAns);
            cnt--;
            existed[tmp1]=false;
        }
    }
    //下标为index的字符单独作为一个数字
    int tmp2=s[index]-'0';
    if(tmp2 >= 1&&tmp2 <= n&&existed[tmp2]==false) {
        existed[tmp2]=true;
        cnt++;
        backtrack(index+1,cnt,existed,myAns);
        cnt--;
        existed[tmp2]=false;
    }
}

机试还有一道题,但是题目我记不太清了,考试的时候就粗略看了下题目,觉得没啥想法,直接放弃了。考完google了一下题目里的一些关键词,并没有搜到原题,连相似的题目都没找到,所以这里也就不介绍了。

总体来说南大的机试题还是不算难的,考察的都是比较基本的算法,从近几年的机试题来看,如果是三道题的话,一般第一题是动态规划,第二题是回溯法(DFS),第三题就不好说了。考试按测点给分,三道题每题十个测点,一个测点10分,满分300分。然而往年也有四道题选做两道,按ACM形式排名的,就是提交没有AC的话要罚时,按AC的题数和总用时排名,那种就比较坑了,不知道以后会不会又采用那种形式。

第一次发表文章,希望能帮助到大家,文章里有错误的话欢迎大家帮忙修订哦。感谢您的阅读!

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-08-21

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java系列博客

UML类图

33130
来自专栏SimpleAI

Python高级特性——为什么都说Python高效

本微教程根据廖雪峰python教程中的部分内容,配合我个人的学习经历进行总结整理。

13540
来自专栏web编程技术分享

来谈谈JAVA面向对象 - 继续说多态~

30550
来自专栏牛客网

头条实习面经

【每日一语】真实人生中,我们往往在大势底定无可更改时才迟迟进场,却又在胜败未分的浑沌中提早离席。——翁贝托·埃科《开头与结尾》

14020
来自专栏Petrichor的专栏

numpy库 简介

  NumPy 是一个 Python 包。 它代表 “Numeric Python”。 它是一个由多维数组对象和用于处理数组的例程集合组成的库。

24420
来自专栏androidBlog

快速排序的相关算法题(java)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

25210
来自专栏量化投资与机器学习

【精心解读】用pandas处理大数据——节省90%内存消耗的小贴士

本文我们讨论 pandas 的内存使用,展示怎样简单地为数据列选择合适的数据类型,就能够减少 dataframe 近 90% 的内存占用。

1.8K50
来自专栏小詹同学

Leetcode打卡 | No.012 整数转罗马数字

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

13410
来自专栏拭心的安卓进阶之路

重温数据结构:哈希 哈希函数 哈希表

在学习 HashMap 前,我们先来温习下 Hash(哈希) 的概念。 什么是 Hash Hash(哈希),又称“散列”。 散列(hash)英文原意是“混杂”...

32550
来自专栏从零开始学自动化测试

python笔记1-用python解决小学生数学题

前几天有人在群里给小编出了个数学题: 假设你有无限数量的邮票,面值分别为6角,7角,8角,请问你最大的不可支付邮资是多少元? 小编掰着手指头和脚趾头算了下,答案...

37090

扫码关注云+社区

领取腾讯云代金券