[mock]10月4日

第一次mock，CollabEdit开一个页面，开始做题。
题目是，有方法pow(m,n)，m和n都大于1，给出N，有顺序的打印出前N个pow(m,n)的结果。前一个是：4,8,9,16，...

然后在CollabEdit上写写画画，想思路，不得，开始紧张。拿起笔在纸上画，有些想法，但又觉得复杂度太高，不敢。
先想的是，2^2之后，m和n都可以往+1的方向变。然后取其小的，但这样的话递归太多，而且有很多重复计算。
经提示有重复计算后，第一反应DP，被否。后来提示得知是4,8,9之类的已经算过的就可以去掉了。（一开始我以为只要质数，马上遇上6^2==36的反例）
所以用一个boolean数组记录是否可以去掉。此时灵光一现，用int[]数组，比如A[i]来表示i这个数下一个要取的幂是A[i]。
然后从0到L+1遍历（L为sqrt(N)），取pow(m,n)的最小值，并更新。这里有两个问题，一是不能从0开始，因为最小是2,而是上限不止sqrt(N)，N倒是保险一点。
让优化，一是pow(m,n)不用一直结算，记录上一次的结果下次直接乘以m就可。二是数组长度，其实不用一开始分配N，因为只有到m^2被取了以后，才有必要遍历到m后面去，所以可以动态增长的。三是，很多数字到后来都valid为false了（比如，4,8,16），可以从动态数组中去掉。
再让我用数据结构优化，我想到堆，但又不觉得可以。结束后被告知，维持一个最小堆，把算过的结果都放进去，然后从堆顶取并把新的加入更新即可。

被指出，代码风格最好写成{后换行，+前后空格，以及++i。

一个经验是现场先努力有个代码，再优化比完全没有要好得多。

下为现场写的核心代码：

int k = 0;

while (k < n)

{

	int min = Integer.MAX_VALUE;

	int pos = -1;

	for (int i = 2; i <= L+1; i++)

	{

		if (valid[i])

		{

			int value = pow(i, arr[i]);

			if (arr[i] ==2 && value > min) break;

			if (value < min)

			{

				int pos = i;

				min = value;

			}

		}

	}

	valid[min] = false;

	System.out.println(min);

	arr[pos] =arr[pos]+1;

	k++;

}

/以上

巴特西

[mock]10月4日

最新文章

热门文章