曾经面试遇到的问题：
1. 色子(6个面),N个色子,把所有组合输出来,去掉重复的(如:3个色子: 1,2,3的组合 和 3,2,1的组合 或者 2,3,1 的组合 都示为重复的 )
2. 画TABLE,所有单元格相临的颜色都不能有重复的.
这2个问题说明:
当时去了一家公司面试,环境挺好,也挺不错.
面试很简单.也很到位.
就给了我3个题. 并且只要做出其中2个题就可以.时间是5小时. 我看了下题.选的是其中的2个. 还有一个忘记了.
------重点希望有朋友可以解答第1题. 因为我只做了第1题. 5小时.还没做出来.-------
小弟是新人.第一次发帖.希望大家指点.
来个完全正确的。
public class DiceArith {
/**
* 数组转字符
*
* @return
*/
public static String arraysToString(String[] s) {
String t = "";
for (int i = 0; i < s.length; i++)
t += s[i];
return t;
}
/**
* 方法一
*
* @param N
*/
public static void method1(int N) {
TreeSet<String> tree = new TreeSet<String>();
long start = 1, end = 6;
for (int i = 1; i < N; i++) {
start += 1 * convert(10, i);
end += 6 * convert(10, i);
}
String[] data;
for (long j = start; j <= end; j++) {
if (expValid(j + "")) {
data = String.valueOf(j).split("");
Arrays.sort(data);
tree.add(arraysToString(data));
}
}
for (Iterator<String> t = tree.iterator(); t.hasNext();) {
String d = t.next();
System.out.println(d);
}
}
public static void main(String[] args) {
method1(3);
}
/**
* 计算平方根
*
* @param data
* @param n
* @return
*/
public static long convert(int data, int n) {
long result = 1l;
for (int i = 1; i <= n; i++)
result *= data;
return result;
}
/**
* 正则验证色子数在【1-6】范围内
*
* @param s
* @return
*/
public static boolean expValid(String s) {
Pattern p4 = Pattern.compile("^[1-6]+$");
Matcher m4 = p4.matcher(s + "");
if (m4.find())
return true;
else
return false;
}
}
第一个问题:
N 个色子, 每个取值 1~6, 要求没有重复的组合, 则组合为这样的
11111111111...1 (N 个 1),
12345612345...6 (N 个数),
...
将每个组合产生的数字按升序排序, 如 123432 得到 122334,
则所有组合其实就是 111111...1 (N个1) 到 666666...6 (N个6).
第二个问题:
四色定理?
[quote]能不能给出具体的代码。关于理论的想法我也想过很多。
但就是困于代码实现这一步[/quote]
第一题的代码...不就是输出这些数字么
int start = 1, end = 6;
for (int i = 1; i < N; i++) {
start += 1* 10 * i;
end += 6*10*i;
}
for (int i = start; i <=end; i++)
System.out.println(i);
第一题，上位朋友的代码改进。
public class DiceArith {
public static long convert(int data, int n) {
long result = 1l;
for (int i = 1; i <= n; i++)
result *= data;
return result;
}
public static void main(String[] args) {
long start = 1, end = 6;
long N = 4;
for (int i = 1; i < N; i++) {
start += 1 * convert(10, i);
end += 6 * convert(10, i);
}
for (long j = start; j <= end; j++)
System.out.println(j);
}
}
[quote]for (int i = start; i <=end; i++)
System.out.println(i);[/quote]
这样的话，如果start=11,end=66。你这样的输出不就包含有
17..27..37..47..57.了吗，请问色子有7吗？
所以我觉得应该这样：
[code="java"]for (int i = start; i <=end; i++) {
Pattern p4=Pattern.compile("[1-6]+");
Matcher m4=p4.matcher(i+"");
if(m4)
System.out.println(i);
}[/code]
但我觉得你们这样做循环，效率都不高，我觉得让一个组合作成六进制的数，只要加到6就进1，那样会省去很多多余的组合。估计效率会高点
的确的确, 没有考虑到 start - end 之间的其他数字. 悲剧悲剧.
不过, 在此基础上, 作出改进是可以得到正确结果的
比如简单判断:
for (int i = start; i <=end; i++) {
if (i.toString().indexOf(55) != -1 || i.toString().indexOf(56) != -1 || i.toString().indexOf(57) != -1 || i.toString().indexOf(48) != -1)
continue;
System.out.println(i);
}
[quote]但我觉得你们这样做循环，效率都不高，我觉得让一个组合作成六进制的数，只要加到6就进1，那样会省去很多多余的组合。估计效率会高点[/quote]
算法复杂度不变. 当然如果能做你这样的改进, 还是不错的.
给你个运行通过的！你自己在试试了，其实只要对大家的代码进行优化和改进就ok了，思路都蛮好的。
public class DiceArith {
/**
* 数组转字符
*
* @return
*/
public static String arraysToString(String[] s) {
String t = "";
for (int i = 0; i < s.length; i++)
t += s[i];
return t;
}
/**
* 方法一
*
* @param N
*/
public static void method1(int N) {
String data = "", temp = "";
TreeSet<String> tree = new TreeSet<String>();
for (int i = 1; i <= N; i++) {
for (int k = 1; k <= 6; k++) {
data = i + "" + k;
String[] arr = data.split("");
Arrays.sort(arr);
temp = arraysToString(arr);
tree.add(temp);
}
}
for (Iterator<String> t = tree.iterator(); t.hasNext();) {
String d = t.next();
System.out.println(d);
}
}
public static void main(String[] args) {
method1(4);
}
}
我觉得还有一个问题，就是你们产生所有排列的时候，并没有对每个组合进行每个数字的降序排序噢，还是有出现16,61这样的重复组合，不符合LZ的要求，虽然你最先的想法是完全正确的
上面代码好像还有问题，只是给个思路，在把上面的代码集成进去就ok了！
[code="java"]public class test4 {
/**
* @param args
*/
public static void main(String[] args) {
//六进制
int n[]={1,1,1};//可自己设定
Set set=new HashSet();
while(true){
System.out.println(n[2]+""+n[1]+""+n[0]);
//排序
for(int i=0;i<n.length;i++){
//for(j=1;j<n...){
//忘记怎么写冒泡了，郁闷~~
//}
//最终是把n数组排成升序排列的数组
}
set.add(n);//每得一个结果就用加进set里面，根据set的特性得到唯一的组合
add(n,0);
if(n[n.length-1]==6)
break;
}
//输出set
for(int k=0;k<set.size();k++){
//这个我就省略了，下班回家吃饭咯~~~
}
}
public static void add(int a[], int i) {
if (i < a.length) {
a[i]++;
if (a[i] == 7) {
a[i] = 1;
add(a, i + 1);
}
}
}
}[/code]