【2017-07-29】CVTE在线笔试题编程题
我参加的是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了
安慰自己:
没有上去说明能力还不够,等能力达到要求了,自然就会往上走,所以还是努力修炼吧!骚年!
- Pingback: C++技术岗位-笔试面试题总结【持续更新…】 - Veaxen's