一著名软件公司的java笔试算法题 数字排序

缘起

1
2
3
4
该公司笔试题就1个，要求在10分钟内作完。

题目如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：
512234、 412345等，要求："4"不能在第三位，"3"与"5"不能相连。

分析

dfs 秒解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include "stdafx.h"
#include <stdio.h>
#define LOCAL

int ans[10],v[10],cnt; // v[i]表示i用过的次数
bool book[600000]; // true表示已经打印过了

bool ok(int step, int i) // ans[step]能不能选择i? true表示可以选择, false表示不能选择
{
	if (step==2 && i==4) // 4不能在第三位
	{
		return false;
	}
	if ((step&&ans[step-1]==3&&i==5) || (step&&ans[step-1]==5&&i==3)) // 3、5不能相邻
	{
		return false;
	}
	if (i!=2 && v[i]) // 次数不够用了
	{
		return false;
	}
	if (i==2&&v[i]>1) // 次数不够用了
	{
		return false;
	}
	return true;
}

void dfs(int step) // 目前是决定ans[step]
{
	if (step==6)
	{
		int ret = 0;
		for (int i = 0; i<step; i++) // 洪特规则
		{
			ret = ret*10+ans[i];
		}
		if (!book[ret]) // 如果没打印过
		{
			printf("%d\n", ret);
			cnt++;
			book[ret] = true;
		}
		return;
	}
	for (int i = 1; i<=5; i++)
	{
		if (ok(step, i))
		{
			ans[step] = i; // 选择i
			v[i]++;
			dfs(step+1);
			v[i]--;
		}
	}
}

int main()
{	
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	dfs(0);
	printf("%d\n",cnt); // 198
	return 0;
}

但是唯一令我不爽的是，上面为了判定到底有没有打印过，开了一个60w的布尔数组——太浪费空间啦（而且还额外导致了洪特规则的使用，白白浪费了时间）~

就单单为了防止两个2导致的重复打印. 解决之道是将两个2区别开来. 例如叫甲2和乙2. 规定甲2必须在乙2前面, 那么就只会打印1个了. 而不会重复打印. 怎么实现这个甲2和乙2呢? 就是不再是5个数，而是6个数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include "stdafx.h"
#include <stdio.h>
#define LOCAL

int ans[10],cnt;
bool v[6]; // true表示i这个数字(i=6时表示乙2,i=2表示甲2)

bool ok(int step, int i)
{
	if (step==2 && i==4)
	{
		return false;
	}
	if ((step&&ans[step-1]==3&&i==5) || (step&&ans[step-1]==5&&i==3))
	{
		return false;
	}
	if (v[i]) // 如果已经用过了, 就不能用
	{
		return false;
	}
	if (i==6)
	{
		return v[2]; // 甲2尚没用, 就不可以用乙2, 否则可以用 
	}
	return true;
}

void dfs(int step)
{
	if (step==6)
	{
		for (int i = 0; i<6;i++)
		{
			printf("%d ", ans[i]);
		}
		cnt++;
		puts("");
		return;
	}
	for (int i = 1; i<=6; i++) // 第6个数字是2（乙2），第2个数字也是2, 是甲2
	{
		if (ok(step, i))
		{
			ans[step] = (i==6?2:i);  // 如果是6的话, 实际塞入的是2而不是6哦~
			v[i] = true;
			dfs(step+1);
			v[i] = false;
		}
	}
}

int main()
{	
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	dfs(0);
	printf("%d\n",cnt); // 198
	return 0;
}