答复: 上个星期去腾讯面试一位主考官出的动脑题，当时被难住了

如果是智商题，根本就不应该想算法这回事。我看以后大家如果遇到这样的问题，问问是在考算法还是考智商。

hanjiangit 写道

你这方法还是不行 用得还是穷举法  而且你预设了数组值为0 完全是掌握结果后再来写的 不能用数学方法解释

我也写了个算法实现，是用穷举，但是运算过程中逐步向正确结果收敛，有效降低了循环次数。从数学方法上完全可以解释(穷举)。运算大概18ms。没有上面WonderfulCounter快。

不过可读性还好，有人能够帮忙再优化一下么？

算法实现如下：

/*
 一共有上下两排数，上排的十个数是【0，1，2，3，4，5，6，7，8，9】
针对上排的每个数，在其对应的下面位置填写一个数，该数表示上面的数在下面出现的次数。

####################
数值:0,1,2,3,4,5,6,7,8,9
分配:6,2,1,0,0,0,1,0,0,0
比如说，
0的下面我填写6，就表示在下面一共有6个0.
1的下面我填写2，表示下面下面一共有2个1
2的下面我填写1，表示下面下面一共有1个2
这回能看明白？ 
 */

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 */
public class NumberRowCaculator {

	public static void main(String[] args) throws Exception {
		int[] row1 = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

		long start = System.currentTimeMillis();

		NumberRowCaculator r = new NumberRowCaculator(row1);
		r.caculate();
		for (NumberRow number : r.getNumbers())
			System.out.println(number);

		System.out.println(System.currentTimeMillis() - start);
	}

	List<NumberRow> numbers = new ArrayList<NumberRow>();
	final int[] firstRow;

	public NumberRowCaculator(int[] firstRow) {

		this.firstRow = firstRow;

		for (int i = 0; i < firstRow.length; i++) {
			NumberRow n = new NumberRow(firstRow.length);
			n.setBit(0, i);
			numbers.add(n);
		}
	}
	
	public void caculate() throws Exception {
		this.calculator();
		this.clearErrorRows();
	}

	public List<NumberRow> getNumbers() {
		return numbers;
	}

	/**
	 * 计算出所有满足与原始列的各个对应数字乘积之和不大于最大数字个数的行
	 * @throws CloneNotSupportedException
	 */
	private void calculator() throws CloneNotSupportedException {

		for (int bitposition = 1; bitposition < this.firstRow.length; bitposition++) {

			List<NumberRow> temp = new LinkedList<NumberRow>();
			Iterator<NumberRow> it = numbers.iterator();
			while (it.hasNext()) {
				NumberRow n = it.next();
				for (int value = 0; value < firstRow.length; value++) 
					if (n.check(bitposition, value, firstRow)) {
						NumberRow added = (NumberRow) n.clone();
						added.setBit(bitposition, value);
						temp.add(added);
					}
			}
			numbers = temp;
		}
	}

	/**
	 * 清理不完全满足条件的行
	 */
	private void clearErrorRows() {
		List<NumberRow> temp = new LinkedList<NumberRow>();
		for (NumberRow number : numbers) {
			boolean v = true;
			for (int i = 0; i < firstRow.length && v; i++) {
				if (!number.validate(i, firstRow[i])) {
					v = false;
					break;
				}
			}
			if (v)
				temp.add(number);
		}
		this.numbers = temp;
	}

}

/**
 * 具体某一行对象
 *
 */
class NumberRow {

	private final int[] rows;

	public NumberRow(int length) {
		super();
		this.rows = new int[length];
	}

	/**
	 * 检查设置新数字后是否满足与原始行对应数字乘积之和不大于最大长度
	 * @param index 要插入的位置
	 * @param value 要插入的数字的值
	 * @param firstRow 原始行
	 */
	public boolean check(int index, int value, int[] firstRow) {
		int c = 0;
		for (int i = 0; i < rows.length; i++) {
			c += (firstRow[i] * rows[i]);
		}
		c += firstRow[index] * value;

		return c <= firstRow.length;
	}

	public void setBit(int index, int value) {
		this.rows[index] = value;
	}

	public boolean validate(int index, int value) {
		int c = 0;
		for (int i = 0; i < rows.length; i++)
			if (rows[i] == value)
				c++;

		return c == rows[index];
	}

	protected Object clone() throws CloneNotSupportedException {
		NumberRow n = new NumberRow(this.rows.length);
		for (int i = 0; i < rows.length; i++)
			n.rows[i] = rows[i];
		return n;
	}

	@Override
	public String toString() {
		StringBuilder s = new StringBuilder();
		for (int i = 0; i < rows.length; i++)
			s.append(rows[i]).append(",");
		return s.toString();
	}

}