美文网首页笔试&&面试经验程序员
Microsoft在线编程测试热身题(hiho密码)

Microsoft在线编程测试热身题(hiho密码)

作者: CopyYoung | 来源:发表于2017-03-29 20:39 被阅读0次

hiho密码

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述
小Ho根据最近在密码学课上学习到的知识,开发出了一款hiho密码,这款密码的秘钥是这样生成的:对于一种有N个字母的语言,选择一个长度为M的单词;将组成这个单词的所有字母按照顺序不重复的写出(即遇到相同字母时跳过);然后将字母表剩下的没有使用过的字母按照顺序在其后进行排列。
如对于有5个字母的hiho语,选择单词1, 2, 2, 4, 3(此处数字表示字母在字母表中的顺序),则秘钥为1,2,4,3,5。
但是有一天小Ho在计算出了秘钥之后,却发现他弄丢了一开始选择的单词,于是他找到了你,希望你能够帮他找到能够生成这个秘钥的最短的单词。
输入
每个输入文件包含单组测试数据。
每组测试数据的第一行为一个正整数N,意义如前文所述。
每组测试数据的第二行为N个正整数,用来描述一个秘钥,其中第i个正整数Ai表示秘钥的第i个字符在字母表中的顺序。
对于100%的数据,满足N<=1000,1<=Ai<=N。
对于100%的数据,满足对于任意1<=i, j<=N,若i≠j,则Ai≠Aj。
输出
对于每组测试数据,输出能够生成输入给出的秘钥的最短的单词(空串不认为是单词)。由于字母表没有给出,所以对于每个字母,输出其在字母表中的顺序即可(用空格隔开)。
样例输入
5
1 2 4 3 5
样例输出
1 2 4

解题思路:

这道题题干很长,对于题目的理解可能需要一定的时间。但是一旦静下心来理解透了的话,还是很容易做的。不过这毕竟只是微软用来让在线编程测试的人热身的一道题,真正的考试题还是会有一定难度的,会选拔出来真正优秀的程序员的,有志于此的朋友们还是要打好基础,不可掉以轻心。
在看懂这道题之后,算法还是很容易想出来的,只要想通以下几点:

  1. 最短的单词肯定是不会有重复字母的。
  2. 原单词里可以出现逆序,但是字母表剩下的未使用过的字母一定是顺序排列的,且字母表剩下的字母排列在密钥的后面。
  3. 原单词至少也有一个字母,不会为空。

想通了以上三点,我们就很容易得到算法了,我的做法是,密钥从后往前遍历,直到发现了逆序对才停止,从停止的位置到密钥的起始端都必须是原单词里的字母了。然后最后输出的时候注意一下(1.原单词不能为空 2.N==1的情况)就好了。
C++代码如下:

#include <iostream>
using namespace std;

int main(){
    int N;
    int array[1010];
    cin >> N;
    for (int i=0; i<N; ++i)
        cin >> array[i];
        
    int j;
    if (N == 1)
        cout << array[0];
    else{
        for (j=N-2; j>=0; --j)
            if (array[j] > array[j+1])
                break;
        if (j == -1)
            cout << array[0];
        else{
            for (int i=0; i<=j; ++i)
                cout << array[i] << ' ';
        }
    }
    return 0;
}

最后,关于时间复杂度的问题,这道题也很容易看出来时间复杂度为O(N)。

相关文章

  • Microsoft在线编程测试热身题(hiho密码)

    hiho密码 时间限制:10000ms单点时限:1000ms内存限制:256MB 描述小Ho根据最近在密码学课上学...

  • Hiho 1289 403 Forbidden(微软编程题)

    题意 输入 ip 按顺序匹配规则,优先匹配前面的规则,如果没有规则可以匹配则视为合法。注意:掩码为 0 的时候表示...

  • reademe

    一直想把hiho从头理一遍。也算救过我一命。hiho week1的第一题,是网研2016年的机试第二题。(第一题逆...

  • 常见的兼容性问题总结

    微软提供的测试工具,但是只能抓取截图,不能在线调试,比较鸡肋https://developer.microsoft...

  • 编程题测试

    给定以下8*8的0/1比特矩阵M, 请编程实现Mx(矩阵乘向量),x是8比特的0/1向量。即,输入x,输出Mx的值...

  • Letter G song of Lucas

    The girl in the farm , the girl in the farm, Hiho hiho th...

  • 编程笔试题(一)冒泡排序

    很多测试同学在面试做笔试题的时候都会遇到编程题,总的看来测试同学的编程题都不是很困难,主要在考察大家的代码基本功,...

  • 第七周

    这周我学了一点编程题还有密码题,自从上学期课程有上过C语言以后,很久没接触过编程了。 先看第一道题 这道题我用了三...

  • 简单测试面试题

    软性热身题 自我介绍介绍下你负责的公司项目你有什么优点和缺点?测试计划,测试流程,如何bug,你做过哪些测试请描述...

  • LeetCode 刷题指南(一):为什么要刷题

    虽然刷题一直饱受诟病,不过不可否认刷题确实能锻炼我们的编程能力,相信每个认真刷题的人都会有体会。现在提供在线编程评...

网友评论

    本文标题:Microsoft在线编程测试热身题(hiho密码)

    本文链接:https://www.haomeiwen.com/subject/kfyyottx.html