首页 > 代码库 > TopCoder SRM 625 Incrementing Sequence 题解
TopCoder SRM 625 Incrementing Sequence 题解
本题就是给出一个数k和一个数组,包含N个元素,通过每次添加?数组中的一个数的操作,最后须要得到1 - N的一个序列,不用排序。
能够从暴力法入手,然后优化。
这里利用hash表进行优化,终于得到时间效率是O(n*n)的算法,并且常数项应该非常低,速度还挺快的。
思路:
1 假设数组A[i]在1 -N 范围内,就利用bool B[]记录,这个数已经找到了;
2 假设A[i]的值之前已经找到了,那么就添加?k操作,得到新的值A[i]+k,看这个值是否找到了,假设没找到,就使用B记录,假设之前已经找到了,那么就继续反复添加?k的操作。
3 假设最后A[i]+k大于N了,那么就能够返回IMPOSIBLE了,由于这样不可能得到要求的数列了。
本算法的缺点是须要额外O(n)的bool空间,只是一般算法会通过sort之后处理也须要O(lgn)的int空间了,所以空间效率事实上也差点儿相同。
而本算法的长处是:不须要排序,不须要做模运算,常数项应该低点,执行速度快。
#include <vector> #include <string> using namespace std; class IncrementingSequence { public: string canItBeDone(int k, vector<int> &A) { int N = (int)A.size(); vector<bool> B(N+1); for (int i = 0; i < N; i++) { if (A[i] > N) return "IMPOSSIBLE"; while (A[i] <= 0 || B[A[i]]) { A[i] += k; if (A[i] > N) return "IMPOSSIBLE"; } B[A[i]] = true;//不要错写成B[i] } for (int i = 1; i <= N; i++) //别漏这个循环推断 { if (!B[i]) return "IMPOSSIBLE"; } return "POSSIBLE"; } };
附一道250分的水题,须要找a*b +c = y,给出y找到a,b,c当中a, b, c 不能等于0, 或者1
#include <vector> #include <math.h> using namespace std; class AddMultiply { public: vector<int> makeExpression(int y) { vector<int> vx(3); vx[0] = -1; vx[1] = 2; vx[2] = y - vx[0] * vx[1]; return vx; } };
当然,假设还有额外的限制,那么本算法不是完好的,只是这里不错的思路是先找好难的部分,乘法部分,然后找加数就easy了。
TopCoder SRM 625 Incrementing Sequence 题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。