本題就是給出一個(gè)數(shù)k和一個(gè)數(shù)組，包含N個(gè)元素，通過每次添加?數(shù)組中的一個(gè)數(shù)的操作，最后須要得到1 - N的一個(gè)序列，不用排序。

能夠從暴力法入手，然后優(yōu)化。

這里利用hash表進(jìn)行優(yōu)化，終于得到時(shí)間效率是O(n*n)的算法，并且常數(shù)項(xiàng)應(yīng)該非常低，速度還挺快的。

思路：

1 假設(shè)數(shù)組A[i]在1 -N 范圍內(nèi)，就利用bool B[]記錄，這個(gè)數(shù)已經(jīng)找到了；

2 假設(shè)A[i]的值之前已經(jīng)找到了，那么就添加?k操作，得到新的值A(chǔ)[i]+k，看這個(gè)值是否找到了，假設(shè)沒找到，就使用B記錄，假設(shè)之前已經(jīng)找到了，那么就繼續(xù)反復(fù)添加?k的操作。

3 假設(shè)最后A[i]+k大于N了，那么就能夠返回IMPOSIBLE了，由于這樣不可能得到要求的數(shù)列了。

本算法的缺點(diǎn)是須要額外O(n)的bool空間，只是一般算法會通過sort之后處理也須要O(lgn)的int空間了，所以空間效率事實(shí)上也差點(diǎn)兒相同。

而本算法的長處是：不須要排序，不須要做模運(yùn)算，常數(shù)項(xiàng)應(yīng)該低點(diǎn)，執(zhí)行速度快。

      #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;//不要錯(cuò)寫成B[i]
		}
		for (int i = 1; i <= N; i++)	//別漏這個(gè)循環(huán)推斷
		{
			if (!B[i]) return "IMPOSSIBLE";
		}
		return "POSSIBLE";
	}
};
    

附一道250分的水題，須要找a*b +c = y，給出y找到a,b,c當(dāng)中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;
	}
};
    

當(dāng)然，假設(shè)還有額外的限制，那么本算法不是完好的，只是這里不錯(cuò)的思路是先找好難的部分，乘法部分，然后找加數(shù)就easy了。