这个题目虽然说要the set of xxx，但是我觉得并不需要返回一个std::set或者一个set class。只需要确保返回的数里面没有重复就行了。
ddd888的做法，只需要在考虑要不要算上iMin时加上一个判断 if (iMin>=x) 就好了。他自己也说了是顺便写写。相信真要他申请，肯定要跑几遍测试几下的。
我觉得这个东西，想通过你的解答为申请加分，应该不能满足于答案的正确性。要在思路上要些亮点。比如算法上效率高一点。加点其它花俏一点的东西。
我也贴一个：
实在想不到怎么样比较简单地返回一个array，就用了vector。
另外，就着习惯，加了点test。实在没用过cppunit之类的，就弄了个简单的assert。
这次做起来有点像TDD，是先写test，再写实现的。不同的是，我一口气几乎把全部的tests都先写出来了。因为先用来测ddd888的解答。然后才写我自己的。对于调试还是挺有帮助的。一下子就把两个bugs找到。
基本思路在5楼。还是用了一个mod。其实是瞎折腾。真的要投，估计是要用ddd888的那个。
ddd888的我就是改了上面我说的跟x比较，还有就是把开始的值往x靠近一些。
请大家指教。
#include <iostream>
#include <assert.h>
#include <vector>
using namespace std;
vector<int>& multiple(int x, int y) {
vector<int> ret;
if (y>=x) {
int inc[] = { 0, 4, 6, 8 };
int period = 12;
int num_inc = sizeof(inc)/sizeof(int);
ret.reserve(((y-x)/period+1)*num_inc);
int start = x - x % period + period;
int pre = start - period;
for (int i=0; i<num_inc; i++) {
int pre1 = pre+inc;
if (pre1>y) break;
if (pre1>=x) {
ret.push_back(pre1);
}
}
int cur = start;
int stop = y - period;
for (; cur <= stop ; cur+=period) {
for (int i=0; i<num_inc; i++) {
ret.push_back(cur+inc);
}
}
if (y>=start) {
int post = cur;
for (int i=0; i<num_inc; i++) {
int post1 = post+inc;
if (post1>y) break;
if (post1>=x) {
ret.push_back(post1);
}
}
}
}
return ret;
}
vector<int> multiple_ddd888(int x, int y) {
int start = x - 4 * 6;
if (start<0) start = 0;
int sequence1 = start+4;
int sequence2 = start+6;
vector<int> ret;
while (true)
{
int iMin;
if (sequence1 < sequence2)
{
iMin = sequence1;
sequence1 += 4;
}
else if (sequence1 == sequence2)
{
iMin = sequence1;
sequence1 += 4;
sequence2 += 6;
}
else
{
iMin = sequence2;
sequence2 += 6;
}
if (iMin > y) {
break;
}
if (iMin >= x) {
ret.push_back(iMin);
}
}
return ret;
}
int main(int argc, char* argv[])
{
int tests[][2][3] = {
{{13, 12}, {0, -1, -1}},
{{13, 13}, {0, -1, -1}},
{{13, 14}, {0, -1, -1}},
{{13, 15}, {0, -1, -1}},
{{12, 12}, {1, 12, 12}},
{{4, 4}, {1, 4, 4}},
{{6, 6}, {1, 6, 6}},
{{4, 12}, {4, 4, 12}},
{{1, 12}, {4, 4, 12}},
{{1, 11}, {3, 4, 8}},
{{4, 11}, {3, 4, 8}},
{{8, 31}, {8, 8, 30}},
{{7, 30}, {8, 8, 30}},
{{7, 31}, {8, 8, 30}},
};
for (unsigned int i=0; i<sizeof(tests)/sizeof(tests[0]); i++) {
int* input=tests[0];
int* expected=tests[1];
vector<int> actual;
cout << "x:"<<input[0]<<",y:"<<input[1]<<": ";
actual = multiple(input[0], input[1]); // call the function
//cout << actual.size() ;
assert(expected[0]==actual.size());
if (actual.size() > 0) {
assert(expected[1]==actual[0]);
assert(expected[2]==actual[actual.size()-1]);
}
for (int j=0; j<actual.size(); j++) {
assert(actual[j] % 4 == 0 || actual[j] % 6 == 0);
cout << actual[j] << '\t';
}
cout << endl;
}
return 0;
} |
发表于 15-4-2013 00:17:53
收藏
赞
踩
楼主
