leetcode本地c++11开发组件

/* * auther: jlusuoya * mail: jlusuoya@foxmailc.om * date: 2017-06-29 */ #include "leetcode.h" //use class Q1 : public Solution<RetType, ParamList> class Q3 : public Solution<vector<int>, vector<int>, int> { public: Q3(int id, bool debug = true) { SetConf(id, debug); } //一次随机测试 void RandomTest(uniform_int_distribution<int>& u, default_random_engine& e) override { Test(RandomVector(u, e, 2), u(e)); } //输出输入信息 void DumpInput(vector<int> nums, int target) override { cout << "sum: " << target << " | " << VecToStr(nums, ' ') << endl; } //输出字符串化以比较 r0是标准函数返回结果, r1是自定义函数结果 bool CheckRst(vector<int>& r0, vector<int>& r1, vector<int> nums, int target) const override { cout << r0[0] << "," << r0[1] << endl << r1[0] << "," << r1[1] << endl; return nums[r1[0]] + nums[r1[1]] == nums[r0[0]] + nums[r0[1]]; //1和2结果对比 //return (nums[r1[0]] + nums[r1[1]] == target) && (nums[r0[0]] + nums[r0[1]] == target) //全量校验以避免参考答案有误 } //算法1，普通算法，a+b=target，遍历一次数组，每个数，即可能是a，也可能是b，将a起来。如果找到了当前数的a，则成功 //9ms 54.37, 再提交2次，6ms和12ms vector<int> FUN_NAME_0(vector<int> nums, int target) override { unordered_map<int, int> subs; const int max = nums.size(); for(int i = 0; i < max; i++) { auto it = subs.find(target-nums[i]); if(it != subs.end()) return vector<int> {it->second, i}; subs[nums[i]] = i; } return vector<int> {-1, -1}; } //算法2，改进最佳答案，用map同时实现排序和反查，降低反查代价，损耗一些排序性能（相对快速排序） //18ms， 41.35%, 并没有成功，原因是数据量小的情况下，得不偿失 vector<int> FUN_NAME_1(vector<int> nums, int target) override { multimap<int, int> org_pos; for(size_t i = 0; i < nums.size(); i++) org_pos.insert(pair<int,int>(nums[i], i)); auto it_beg = org_pos.begin(); auto it_end = --org_pos.end(); while(it_beg != it_end) { int val = it_beg->first + it_end->first; if(val == target) { if(it_beg->second < it_end->second) return vector<int> {it_beg->second, it_end->second}; else return vector<int> {it_end->second, it_beg->second}; } if(val > target) it_end--; else if(val < target) it_beg++; } return vector<int> {-1, -1}; } }; Interface* GetObj(int argc, char* argv[], char* env[]) { Q3* s = new Q3(1, false); //指定使用1号算法 //返回之前可以进行一些内部测试 //s.Test(vector<int> {3,3}, 6); //指定的固定测试数据 //s.Test(vector<int> {2,7,11,15}, 9); return s; }