Massive Algorithms: 2016 campus recruitment of baidu programming problem resolution software development

2016 campus recruitment of baidu programming problem resolution software development

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

以下称第x个全排列是都是指由小到大的顺序。

X=a_n(n-1)!+a_{n-1}(n-2)!+\cdots+a_1\cdot0!

其中,

a_i

为整数,并且

0\leq a_i<i,1\leq i\leq n

。

a_i

的意义参见举例中的解释部分

例如，3 5 7 4 1 2 9 6 8 展开为 98884。因为X=2*8!+3*7!+4*6!+2*5!+0*4!+0*3!+2*2!+0*1!+0*0!=98884.

解释：

排列的第一位是3，比3小的数有两个，以这样的数开始的排列有8!个，因此第一项为2*8!

排列的第二位是5，比5小的数有1、2、3、4，由于3已经出现，因此共有3个比5小的数，这样的排列有7!个，因此第二项为3*7!

以此类推，直至0*0!

显然，n位（0~n-1）全排列后，其康托展开唯一且最大约为n!，因此可以由更小的空间来储存这些排列。由公式可将X逆推出唯一的一个排列。

既然康托展开是一个双射，那么一定可以通过康托展开值求出原排列，即可以求出n的全排列中第x大排列。

如n=5,x=96时：

首先用96-1得到95，说明x之前有95个排列.(将此数本身减去！)
用95去除4! 得到3余23，说明有3个数比第1位小，所以第一位是4.
用23去除3! 得到3余5，说明有3个数比第2位小，所以是4，但是4已出现过，因此是5.
用5去除2!得到2余1，类似地，这一位是3.
用1去除1!得到1余0，这一位是2.
最后一位只能是1.
所以这个数是45321.

康托展开

例如：有一个数组S=["a","b","c","d"]，它的其中之一个排列是S1=["b","c","d","a"]，现在欲把S1映射成X，需要怎么做呢？按如下步骤走起

X = a 4 * 3! + a 3 * 2! + a 2 * 1! + a 1 * 0!

首先计算n，n等于数组S的长度，n=4
再来计算a4=”b”这个元素在数组["b","c","d","a"]中是第几大的元素。”a”是第0大的元素，”b”是第1大的元素，”c”是第2大的元素，”d”是第3大的元素，所以a4=1
同样a3=”c”这个元素在数组["c","d","a"]中是第几大的元素。”a”是第0大的元素，”c”是第1大的元素，”d”是第2大的元素，所以a3=1
a2=”d”这个元素在数组["d","a"]中是第几大的元素。”a”是第0大的元素，”d”是第1大的元素，所以a2=1
a1=”a”这个元素在数组["a"]中是第几大的元素。”a”是第0大的元素，所以a1=0
所以X(S1)=1\*3!+1\*2!+1\*1!+0\*0!=9
注意所有的计算都是按照从0开始的，如果[“a”,”b”,”c”,”d”]算为第1个的话，那么将X(S1)+1即为最后的结果

    static int charLength = 12;//定义字符序列的长度

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int n = scanner.nextInt();
            String lines[] = new String[n];
            int res[] = new int[n];//存储结果的数组
            for (int i = 0; i < n; i++) {
                lines[i] = scanner.next();
                res[i] = calculate(lines[i]);
            }
            for (int s : res) {
                System.out.println(s);
            }

        }
    }

    //计算某个字符序列的位次
    private static int calculate(String line) {
        Set<Character> s = new TreeSet<Character>();
        for (char c : line.toCharArray()) {
            s.add(c);
        }
        //存储每一个字符在该序列中是第几大的元素，然后将其值存储到counts数组中
        int counts[] = new int[s.size()];
        char[] chars = line.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            Iterator<Character> iterator = s.iterator();
            int temp = 0;
            Character next;
            while (iterator.hasNext()) {
                next = iterator.next();
                if (next == chars[i]) {
                    counts[i] = temp;
                    s.remove(next);
                    break;
                } else {
                    temp++;
                }
            }
        }
        int sum = 1;
        for (int i = 0; i < counts.length; i++) {
            sum = sum + counts[i] * factorial(charLength - i - 1);
        }
        return sum;
    }

    //计算阶乘的函数
    private static int factorial(int n) {
        if (n > 1) {
            return n * factorial(n - 1);
        } else {
            return 1;
        }
    }

判断字符串是否出现

将字符串a存储在一个map集合中，以每个字符的ASCII码作为key，以其出现的次数作为value，记为aMap
遍历字符串b，对于b中的每一个字符，如果aMap的key中含有该字符的ASCII码，如果该key对应的value>1，那么将value值减1
否则value=1的话，那么将该键值对从aMap中移除
在判断aMap的key是否包含b中的某个字符的时候，只要有一次不包含，那么就说明没有都出现
否则的话，表示b中的字符在a中都出现过

    public static void main(String[] args) {
        //以某个字符的ASCII码作为key，以其出现的次数作为value
        Map<Integer, Integer> aMap = new HashMap<Integer, Integer>();

        Scanner input = new Scanner(System.in);
        while (input.hasNextLine()) {
            String a = input.nextLine();
            String b = input.nextLine();
            char[] chars = a.toCharArray();
            for (char c : chars) {
                if (aMap.keySet().contains((int) c)) {
                    int temp = aMap.get((int) c);
                    aMap.put((int) c, (temp + 1));
                } else {
                    aMap.put((int) c, 1);
                }
            }

            char[] chars1 = b.toCharArray();
            boolean flag = true;
            for (char c : chars1) {
                if (aMap.keySet().contains((int) c)) {
                    int temp = aMap.get((int) c);
                    if (temp == 1) {
                        //说明只有一个
                        aMap.remove((int) c);
                    } else {
                        //说明多过于一个
                        aMap.put((int) c, (temp - 1));
                    }

                } else {
                    flag = false;
                    break;
                }

            }

            if (flag) {
                System.out.println(1);
            } else {
                System.out.println(0);
            }
            aMap.clear();
        }
    }

组合概率

需要递推公式，然后用动态规划求解。
https://segmentfault.com/a/1190000005060870

以样例为例：
n = 2, a = 1, b = 3, x = 4，
则从[1, 3]中取出2个数的组合共有六对：
(1, 1), (1, 2), (1, 3),
(2, 2), (2, 3),
(3, 3)
其中，能组合成4，即相加为4的只有(1, 3), (2, 2)。

假设n=2, x=4的概率表示为rate(4, 2)，其概率计算公式为
取两个数和为4概率 = 取一个数为1的概率取一个数为3的概率 + 取一个数为2的概率取一个数为2的概率 + 取一个数为3的概率*取一个数为1的概率
rate(4, 2) = rate(1, 1)*rate(3, 1) + rate(2,1)*rate(2,1) + rate(3,1)*rate(1,1)
可以进一步归纳为
rate(4,2) = rate(1,1)*rate((4-1),1) + rate(2,1)*rate(4-2,1) + rate(3,1)*rate((4-3),1)
我们现在将数字替换为字母
rate(x,n) = rate(1,n-1)*rate(x-1,n-1) + rate(2,n-1)*rate(x-2,n-1) + rate(3,n-1)*rate(x-3,n-1)

现在，我们将[1, 3]区间替换成字母[a,b]，公式可以进一步归纳为
rate(x,n) = rate(a,1)*rate(x-a,n-1) + rate(a+1,1)*rate(x-(a+1),n-1) + ... + rate(b,1)*rate(x-b,n-1)
其中x-b>=a

至此，我们已可以确定，在区间[a,b]内取n个数其和为x的概率即为rate(x,n)，这可以处理为一个递归函数，当n=1时，即可确定其值。

$区间下限 = a;
$区间上限 = b;
$区间数字个数 = $区间上限 - $区间下限 + 1;
function rate($x, $n) {
    // 当只取一个数时，其概率可以确定下来了
    if($n == 1) {
        if($x > $区间上限 || $x < $区间下限) {
            return 0;
        } else {
            return 1/$区间数字个数;
        }
    }

    $概率 = 0;
    for($i = $区间上限; $i < $区间下限; $i ++) {
        if($x-$i < $区间下限) break;

        $概率 += rate($i,1)*rate($x-$i, $n-1);
    }
    return $概率;
}

    static DecimalFormat dec = new DecimalFormat("0.0000");
    static double v[][];//表示取i个数时和为j的概率

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (input.hasNextInt()) {
            int n = input.nextInt();
            int a = input.nextInt();
            int b = input.nextInt();
            int x = input.nextInt();
            v = new double[n + 1][x + 1];
            double sum = b - a + 1;
            for (int i = a; i <= b; i++) {
                v[1][i] = 1.0 / sum;//取1个数和为i的概率
            }
            for (int i = 1; i <= n; i++) {//对n个数进行迭代
                for (int j = a; j <= b; j++) {//
                    for (int k = 1; k <= x; k++) {
                        if (k >= j) {
//                            print(v);
//                            System.out.println();
                            v[i][k] = v[i][k] + v[i - 1][k - j] / sum;
                        }
                    }
                }
            }
            //输出取n个数和为x的概率
            System.out.println(dec.format(v[n][x]));

        }
    }
    }

2016 campus recruitment of baidu programming problem resolution software development

Labels

Popular Posts