腾讯算法逻辑题

浏览数：30 / 时间：2015年06月08日

前几天小生去了一趟腾讯，接受前端大大的虐待。

整个过程充斥着各种血与泪，特别是他们的算法逻辑题，让我甚是上心。遂mark下，以求甚解...

经过一番思考以及和小伙伴们的共同探索，总算代码的运行结果是符合题目要求了，不过也不确定是否是最佳答案...

且不管了，如果知道有更好的答案再更新便是..

有人也许会说，骚年，你这样把题目发出来真的好吗？这样不担心是个人都有种去企鹅面前装13吗？

那么我可以很负责任的说，这几道题只是餐前小菜。真正的风浪在后头，假如谁天真的以为有了这几道题就稳了，小心被人当猴看。

OK，下面上正文...

    /*---- 52张牌，通过洗牌使每张牌的位置都不在原来的位置上，要求尽量让牌洗得均匀 ----*/
    var poker = [‘a1‘,‘a2‘,‘a3‘,‘a4‘,‘b1‘,‘b2‘,‘b3‘,‘b4‘]; //这里应该有52张，但为了不让小手受虐，只模拟了8张...

    function wash(poker) {
        var xFlag = [];

        for (var i = 0,len = poker.length; i < len; i++) {
            xFlag.push(i);
        }

        function exchange () {
            var flag_a = randomFlag(),
                flag_b = randomFlag(),
                p_a = poker[flag_a],
                p_b = poker[flag_b];

            poker.splice(flag_a, 1, p_b);
            poker.splice(flag_b, 1, p_a);

            while (xFlag.length != 0) {
                exchange();
            }
        }

        var randomFlag = function () {
            var n = Math.floor(Math.random() * xFlag.length),
                curFlag = xFlag.splice(n, 1)[0];
            return curFlag;
        }

        exchange();

        return poker;
    }

    /*---- 现在有一个函数Rand5()可以等概率生成[0,5)的随机整数，先要求在仅依赖此函数的基础下，写一个Rand3()函数，等概率生成[0,3)的随机整数 ----*/
    function rand5 () {
        return Math.floor(Math.random() * 5);
    }

    function rand3 () {
        var i;

        do {
            i = rand5();
        } while (i >= 3)

        return i;
    }

    /*---- 数组a[N]，存放了数字1至N-1，其中某个数字重复出现了一次，要求写一函数find(arr)，找出该数字，时间复杂度必须为O(N)，空间复杂度不能是O[N] ----*/
    var arr = [1,5,8,9,4,6,2,3,7,9]; //这里模拟了一个题目中描述的数组

    function find (arr) {
        var len = arr.length,
            sum_a = (1 + len) * (len / 2),
            sum_b = 0;

        for (var i = 0; i < len; i++) {
            sum_b += arr[i];
        }

        return len - (sum_a - sum_b);
    }

    /*---- 判断正整数是否是对称数，不能把整数转成字符串做判断 ----*/
    function countNunLength (num) {
        var result = 0;
        while (num > 1) {
            num = num / 10;
            result++;
        }
        return result;
    }

    function isSimNum (num) {
        if (countNunLength(num) == 1) return true;

        while (countNunLength(num) > 1) {
            var len = countNunLength(num),
                num_l = Math.floor(num / Math.pow(10, len - 1)),
                num_r = num % 10;

            if (num_l != num_r) {
                return false;
            }

            num = Math.floor((num - num_l * Math.pow(10, len - 1)) / 10);
        }

        return true;
    }

    /*---- 给定一个整数，按10进制来看，计算里面包含多少个0，不能将数字转成字符串 ----*/
    function count_O (num) {
        var result = 0;
        while (num > 10) {
            if (num % 10 == 0) {
                result++;
            }
            num = Math.floor(num / 10);
        }
        return result;
    }

    /*---- 有一个二叉树，每个节点的值是一个整数。写一个函数，判断这棵树中是否存在从根到叶子节点的一个路径，这个路径上所有的节点的值之和为某一个值。存在则返回1，否则返回0 ----*/
    //要做题，先造树...
    var tree = {
        value : 10,
        nodes : [
            {
                value : 10,
                nodes : []
            },
            {
                value : 10,
                nodes : [
                    {
                        value : 10,
                        nodes : [
                            {
                                value : 40,
                                nodes : []
                            },
                            {
                                value : 50,
                                nodes : []
                            }
                        ]
                    },
                    {
                        value : 20,
                        nodes : []
                    }
                ]
            }
        ]
    }

    function checkTree (treeNode, compareNum) {
        var result = false;

        var checkNode = function (treeNode, compareNum, lastSumNum) {
            if (treeNode.nodes.length > 0) {
                for (var i = 0, len = treeNode.nodes.length; i < len; i++) {
                    checkNode(treeNode.nodes[i], compareNum, lastSumNum + treeNode.value);
                }
            } else {
                if (lastSumNum + treeNode.value == compareNum) {
                    result = true;
                }
            }
        }

        checkNode(treeNode, compareNum, 0);

        return result;
    }