2019字节跳动笔试

4道算法题，2个小时。

第1题

有面额1，4，16，64四种面额的硬币，面额1024的纸币，小明拿一张面额1024的纸币去买价格为 N (0<N<=1024)的商品，求需要找给小明的最少零钱数。
我的解答：这是一道典型的动态规划算法题，思路就是，如果我第一次找的零钱是硬币A，那么总的零钱数就是 1+ coinChange(amount-valueOfA)，最少的零钱数就是 min(1+coinChange(amount-coin_1_value, 1+coinChange(amount-coin_2_value,...)) ，递归进行。（coinChange是求最少零钱数的函数，amount代表找零金额。）
代码如下：

const coinChange=function (N) {
        let amountMap=new Map();
        const helper=function (coinsArr, amount) {
            if(amount===0){
                return 0;
            }
            if(amountMap.has(amount)){
                return amountMap.get(amount);
            }
            let n=amount+1;
            for(let coin of coinsArr){
                let curCoinNum=0;
                if(amount>=coin){
                    let nextCoinNum=arguments.callee(coinsArr,amount-coin);
                    if(nextCoinNum>=0){
                        curCoinNum=nextCoinNum+1;
                    }
                }
                if(curCoinNum>0){
                    n=Math.min(curCoinNum,n);
                }
            }
            let result=(n===amount+1)? -1:n;
            amountMap.set(amount,result);
            return result;
        }
        const coins=[1,4,16,64];
        return helper(coins,1024-N);
    }

由于在递归求解过程中，会出现对同一找零金额的多次求解，故将已求解的找零金额所需最小零钱数存到一个散列表（amountMap）中，以减小时间复杂度。

第2题

字符串校对，原题目还包装了下，主人公是王大锤。。。
（1）三个同样的字母连在一起，则删除一个，如"AAA"=>"AA"；
（2）两对一样的字母（AABB）连在一起，则去掉第二对的一个字母，AABB=>AAB；
（3）按照“从左到右”的优先规则，如AABBCC，虽然AABB和BBCC都是错误拼写，应该先修复AABB，结果为AABCC。
我的解答：我的答案通过率才15%，等我想好了再补上。