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%，等我想好了再补上。
