◆◆关于算法(急)◆◆

曾经面试遇到的问题:
1. 色子(6个面),N个色子,把所有组合输出来,去掉重复的(如:3个色子: 1,2,3的组合 和 3,2,1的组合 或者 2,3,1 的组合 都示为重复的 )
2. 画TABLE,所有单元格相临的颜色都不能有重复的.

这2个问题说明:

当时去了一家公司面试,环境挺好,也挺不错.
面试很简单.也很到位.

就给了我3个题. 并且只要做出其中2个题就可以.时间是5小时. 我看了下题.选的是其中的2个. 还有一个忘记了.

------重点希望有朋友可以解答第1题. 因为我只做了第1题. 5小时.还没做出来.-------

小弟是新人.第一次发帖.希望大家指点.

13个回答

来个完全正确的。

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);
}

}

共13条数据 1 尾页
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问