【2017-07-29】CVTE在线笔试题编程题

作者: veaxen 分类: 笔试面试 发布时间: 2017-07-31 16:16

我参加的是C/C++岗位的,编程题第一的题目大概是:
有一个无序整数数组,要求找到第n小未出现的正偶数,实现函数
unsigned int getMinEven(int *a,int len,int n)
示例:
{4,-1,1,3},4,1 输出:2
{3,1,2,10,5,8},6,2 输出:6

笔试时这里我给出的代码如下:

unsigned int getMinEven(int *a,int len,int n)
{
    if(a == NULL) return 0;

    unsigned int target = n*2;

    for(int i=0;i<len;i++){
        if(a[i]>0 && a[i]%2==0){
            int k = a[i]/2;
            if(k<=n){
                target = (++n)*2;
            }
        }
    }
    return target;
} 

思路:
我们先假设最终输出的正偶数是target,则这个target的值为n*2,然后开始遍历数组a,当遇到比target小的正偶数时,我们需要把target向后移动一个正偶数,当遇到比target大的正偶数时,对target没有影响。

但是这里有个问题,我在笔试的时候没有考虑到的(现在看来这次笔试又GG了 :sob: :sob: :sob: ),就是当数组中有重复出现偶数时的情况,这种情况下,我们应该把重复是正偶数剔除掉,防止n重复增加。然而,我想了一下,我第一个想法之上(时间复杂度为O(n)),我找不到可以使空间复杂度为O(1)的改进方法了,可能是我愚钝了;但是利用排序算法还是可以的,先进行一次排序,然后在进行遍历,只是这样的时间复杂度为O(nlog n)。我就不写出演示代码了。

第二道编程题的题目大概是:
判读给定了两个字符串的结构是否相同,比如:

“bool”和”pool”输出true;
“book”和”feed”输出true;
“paper”和”title”输出true;
“for”和”abc”输出true;
“abcd”和”abc”输出false;

实现函数bool func(const string& s,const string& t)

这里我写的代码为:

bool func(const string& s,const string& t)
{
    if(s.empty() && t.empty()) return true;
    if(s.size() != t.size()) return false;

    int s_cnt[256];
    int t_cnt[256];

    for(int i=0;i<256;i++){
        s_cnt[i] = t_cnt[i] = -1; 
    }

    for(int i=0;i<s.size();i++){
        if(s_cnt[s[i]] != t_cnt[t[i]]){
            return false;
        }
        s_cnt[s[i]] = t_cnt[t[i]] = i;
    }
    return true;
}

思路
首先初始化两个数组s_cnt[256]和t_cnt[256],用这两个数组记录遍历时,上一次出现该字母出现的位置(初始化为-1,表示还没有出现过),如果s_cnt[s[i]] == t_cnt[t[i]]时,说明这一次循环找到两个字符串中的字母上次出现的位置也相同,说明结构相同,当遇到不同时,就说明结构不同了,直接返回。

说到这里我又要哭了 :weary: :weary: :weary: 我笔试虽然总体思路还是这样,不过记录错该记的了,总之这次也是GG了


安慰自己:

没有上去说明能力还不够,等能力达到要求了,自然就会往上走,所以还是努力修炼吧!骚年!

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

一条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.