一道连线面试题

存在行列数未知的二维数组，从上而下连线，一行只可取一个数字，（行-列）为非负数时组合相同数字出现的次数总数最多为 （行-列）+1, 当（行-列）为负数时，一个数字只允许出现一次。
举例说明，如下列数组：

1 2
1 2
1 2

时的组合为：1-2-2, 2-1-1或为1-1-2, 2-2-1,

1 2 3
1 2 3

时，其中一组合为1-2,2-3,3-1,组合不允许出现重复数字。

写出程序。

补充：每行的数字只能出现一次，且行数字出现的总数的差值请保持最小！


有朋友可以写出代码吗？

评论

3 楼 xieboxin 2009-11-12  

无成代码如下:

public static void main(String[] args) {
		int row = 4, cell = 8;
		int gap = (row - cell) < 0 ? 1 : (row - cell + 1);
		array = createArray(row, cell);
		LinkedList<Link> links = new LinkedList<Link>();
		Link link;
		Link rollbackLink = null;
		for (int i = 0; i < array[0].length;) {
			link = new Link();
			if (link.add(array[0][i], gap, rollbackLink)) {
				links.addFirst(link);
				i++;
				rollbackLink = null;
			} else {
				rollbackLink = links.removeFirst();
				link.rollBack(rollbackLink);
				i--;
			}
		}

		for (Link link2 : links) {
			System.out.println(link2);
			System.out.println("-----------------------");
		}

	}

	static Integer[][] array;

	private static Integer[][] createArray(int row, int cell) {
		Integer[][] array = new Integer[row][cell];
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < cell; j++) {
				array[i][j] = j;
			}
		}
		return array;
	}

	static class Link {
		// key:数字，value为出现次数
		Map<Integer, Node> lineMap = new HashMap<Integer, Node>();

		private boolean add(Integer begin, int gap, Link link) {
			lineMap.put(begin, new Node(1, 0));
			array[0][begin] = null;
			Node node;
			Integer mark = null;
			boolean end = false;
			boolean rollback = false;
			for (int i = 1; i < array.length;) {
				end = false;
				for (int j = ((!rollback) ? 0 : (mark + 1)); j < array[i].length; j++) {
					rollback = false;
					if (link != null && link.lineMap.containsKey(array[i][j])) {
						continue;
					}
					if (array[i][j] != null) {
						if (lineMap.containsKey(array[i][j])) {
							if (gap > 1) {
								node = lineMap.get(array[i][j]);
								if (node.count < gap) {
									node.addRow(i);
									array[i][j] = null;
									end = true;
									mark = j;
									i++;
									break;
								}
							}
						} else {
							lineMap.put(array[i][j], new Node(1, i));
							array[i][j] = null;
							end = true;
							mark = j;
							i++;
							break;
						}
					}

				}
				if (!end) {
					if (mark != null && mark < array.length) {
						array[i - 1][mark] = mark;
						lineMap.remove(mark);
						rollback = true;
						i--;
					} else {
						return false;
					}
				}
			}
			return true;
		}

		private void rollBack(Link link) {
			if (link != null) {
				Node node;
				for (Integer key : link.lineMap.keySet()) {
					node = link.lineMap.get(key);
					for (Integer integers : node.row) {
						array[integers][key] = key;
					}
				}
			}
		}

		class Node {
			Integer count = 0;
			List<Integer> row = new ArrayList<Integer>();

			public Node(Integer count, Integer row) {
				super();
				this.count = count;
				this.row.add(row);
			}

			private void addRow(Integer row) {
				count = count + 1;
				this.row.add(row);
			}

		}

		public Link() {
			super();
		}

		@Override
		public String toString() {
			StringBuffer string = new StringBuffer();
			Node node;
			for (Integer integers : lineMap.keySet()) {
				node = lineMap.get(integers);
				for (int i = 0, size = node.row.size(); i < size; i++) {
					string.append(node.row.get(i)).append(" - ").append(integers).append("\n");
				}
			}
			return string.toString();
		}

	}

运行结果：（结果仅为二维数组的下标）

3 - 4
2 - 5
1 - 6
0 - 7

-----------------------
2 - 4
3 - 5
0 - 6
1 - 7

-----------------------
1 - 4
0 - 5
3 - 6
2 - 7

-----------------------
0 - 4
1 - 5
2 - 6
3 - 7

-----------------------
3 - 0
2 - 1
1 - 2
0 - 3

-----------------------
2 - 0
3 - 1
0 - 2
1 - 3

-----------------------
1 - 0
0 - 1
3 - 2
2 - 3

-----------------------
0 - 0
1 - 1
2 - 2
3 - 3

-----------------------

2 楼 zl584521 2009-11-12  

没看懂~~

1 楼 330217445 2009-11-12  

把你的例子和文字对应不起来