【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了

安慰自己：