前端算法面试题，求解

Question

如图，写一个方法，传入一个给定的数字，如 60，使用1，2，5这三个数组成60，求大佬解惑

Answer 1

这个题是一个经典的组合问题

分析

1. 要组合的数N和可能币值(数组C，各个元素为c0，c1..cn)的关系，可以生成一个数组B，各元素值为bi=N/ci (i=0,1,...n)
2. 经过1就把问题转换成了有限搜索啦，变成分别有bi 个ci面值的钱币，是否能凑出N值，这样就可以开始组合遍历啦

3. 一些短路条件

   • 如果币值中有1，直接返回true
   • 如果在计算bi时，可以同步判断bi*ci ==N ，即存在整除无余数的情况，就表示可以凑出，返回true退出
   • 在遍历中任何 组合 凑出 c0bt0+c1bt1+..cn*btn == N 则返回true退出，其中bt0,bt1...btn 中的t表示第t次尝试，且分别<= B中各个对应元素值。
   • 如果 c0bt0+c1bt1+..cn*btn > N, 则进行下次尝试
4. 遍历完无结果就返回false

这个策略是单纯的遍历无需递归

这个算法不需要递归，可以转换成常规遍历问题。比如可以根据B中各个值对应bi情况，把bi转换成n位二进制数表示位cbi（表示bi可以有cbi来表示，cbi最大值>=bi）,这样整个搜索空间就映射到一个整数上，整数的位数是所有cbi的和，比如cb0=2，cb1=5，则整数的位数就是2+5=7，其中前2位对应于cb0的表达，后5位对应于cb1的表达。就可以很快构造出遍历循环的条件，结合下面的优化处理，过滤掉不符合的情况，可以很快遍历出来。

一些优化处理

1. 先对C进行降序排列
2. 遍历按bt递减进行
3. 对单个bt调整时判断趋势，如果已经小于N,则开始调整另外的bt。
4. 因为是对有限空间遍历，其实步进时可以同时判断空间对应补数是否符合条件来减少步进总数（这个不影响总的判断数，只是单纯的加快步进）。

另外一些考虑

因为有些语言不支持无限长度的整数（python是支持的），所以可能直接位表达会出现问题，需要做一些特殊处理。

javascript实现

var coins = [3, 77];
var coins1 = [3, 7];
var N = 100;

function getCoin( N, coins ){
    let SortCoins=coins.sort((a,b)=>{return (b-a);}); // 降序排序
    let SortCoinsNum=[];
    let CoinsLength = coins.length;
    for(let i=0;i<CoinsLength;i++){
        if( N % SortCoins[i]){
            SortCoinsNum.push( (N - (N% SortCoins[i]) ) / SortCoins[i] );
        }else{
            return true; // 有能整除的，直接返回true
        }
    }
    let SortCoinsBit=SortCoinsNum.map(a=>{ // 产生各个数据位段长度
        let i=2;
        let c=1;
        for(;i<a;i=i*2){
            c++;
        }
        return c;
    });

    let bitAll=SortCoinsBit.reduce((p,c)=>{return p+c},0); // 总的数据位长度
    let BigAll= (1 << bitAll) -1 ;  // 最大的数（搜索空间，也是数据mark值）
    let HalfBitAll = (bitAll%2)?((bitAll+1)/2):(bitAll/2);
    let HalfAll = (1 << HalfBitAll) -1; // 降序搜索空间大阀值。
    function getNum( Num ){ // 根据一个数，返回对应的各个Coins的数,注意这里Num中低位存储SortCoins前面元素信息。
        let out=[];
        let a=0;
        for(let i=0;i<CoinsLength;i++){
            out.push( ( Num>>a ) & ( ( 1<<SortCoinsBit[ i ] ) - 1) );
            a = a + SortCoinsBit[ i ];
        }
        return out;
    }

    for(let i= BigAll; i>HalfAll ; i--){
        let B1=getNum( i );
        let fi = (~i) & BigAll
        let B2=getNum( fi ); // 取补数的情况
        let sum1=0;
        let sum2=0;
        for(let j=0;j<CoinsLength;j++){
            sum1=sum1 + B1[j] * SortCoins[ j ];
            sum2=sum2 + B2[j] * SortCoins[ j ];
        }
        if( sum1 == N || sum2 == N) { // 判断是否凑出
            return true;
        }
    }
    return false
}


console.log(  getCoin( N, coins ) );
console.log(  getCoin( N, coins1 ) );

Answer 2

以下是己一丝拙见，在此抛砖引玉了

1、传入面额无需全部使用（请注意以下方法对入参未进行校验）

let cions = [3,77], N = 101;
const fn = (cions, N) => {
    if(cions.indexOf(1) >= 0 || cions.filter(item => N % item === 0).length > 0) {
        return true;
    }
    let total = cions.reduce((total, current) => (total+current), 0);
    let q = cions.filter(item => {
        if((N-total) % item === 0) {
            return true;
        }
        let result = false;
        let diff = N - 2*total;
        while(diff > total) {
            if(diff % item === 0) {
                result = true;
                break;
            }
            diff -= total;
        }
        return result;
    });
    if(q.length > 0) {
        return true;
    }
    return false;
}
console.log(fn(coins, N); //output: true

2、全用上的情况也和未全用上的情况是一样的，就是判断条件仅有一种便可

let cions = [3,77], N = 101;
const fn = (cions, N) => {
    let total = cions.reduce((total, current) => (total+current), 0);
    let q = cions.filter(item => {
        if((N-total) % item === 0) {
            return true;
        }
        let result = false;
        let diff = N - 2*total;
        while(diff > total) {
            if(diff % item === 0) {
                result = true;
                break;
            }
            diff -= total;
        }
        return result;
    });
    if(q.length > 0) {
        return true;
    }
    return false;
}
console.log(fn(coins, N); //output: true

Answer 3

没有考虑使用 数组中的每个元素

function fun(num, arr) {
    // 先对数组从小到大排序
    let list = arr.sort((a, b) => { return a - b; }),
        residual = null;
    // 对数字 num 与数组从往前一次求余数，余数为 0 则返回 true
    for (let index = list.length - 1; index >= 0; index--) {
        const item = list[index];
-       //residual = num % item;
+       residual = num %= item; // 直接将余数复制给 num
        if (residual === 0) {
-       //    break;
+           return true; // 此处直接返回结果
        }
-       //else {
-       //    let d = parseInt(num / item);
-       //    num -= item * d;
-       //}
    }
    if (residual !== 0) {
        return false;
    }
-   //if (residual === 0) {
-   //    return true;
-   //} else {
-   //    return false;
-   //}
}

console.log(fun(60, [1, 2, 5])); // true
console.log(fun(100, [3, 77])); // false

Answer 4

function getCoin(N, coins) {
      if (typeof N == 'string' && /\D(?=>\.)/.test(N)) {
        console.warn('请传入整数');
        return;
      }
      N = Math.floor(Number(N));
      coins.sort((a, b) => b - a);
      let index = 0;
      function _temp(money) {
        money = money % coins[index]
        if (index >= coins.length) return false;
        if (money > 0) {
          return _temp(money, coins, ++index);
        } else {
          return true;
        }
      }
      return _temp(N)
    }
    console.log(getCoin("11.01", [1, 5, 2]))
    console.log(getCoin(100, [3, 77]))

Answer 5

/*
    判断组合[c1,, c2, ...]能够凑够N
*/
function calcBase(coins, N){
    // coins中没有内容了
    if(!coins.length) return false;
    // 只有一种硬币,判断是否能整除N
    if(coins.length == 1){
        return N % coins[0] == 0;
    }
    
    // 依次按大硬币从少到多递归
    for(var i=coins.length-1; i>=0; i--){
        // 判断是否能够整除
        if(N % coins[i] == 0){
            return true; 
        }
        // 不能整除时，如果能够使用最大硬币，则最大硬币从1到n
        while(N >= coins[i]){
            N -= coins[i];
            // 递归查询
            if(calcBase(coins.slice(0, i), N)){
                return true;
            }
        }
    }
    return false;
}

/*
    思路： 
        1、将硬币按照面额大小从小到大排序
        2、从最小的硬币开始试探能否凑成N
        3、如果硬币c1不能凑成N，则使用组合[c1,c2],直到所有硬币用完
*/
function calc(coins, N){
    // 如果硬币中包含1，则返回true
    if(coins.includes(1)) return true;
    // 硬币排序
    coins = coins.sort();
    // 从最小硬币开始
    for(let i=1, len=coins.length; i<=len; i++){
        if( calcBase(coins.slice(0, i), N) ){
            return true; 
        }
    }
    return false;
}

console.time();
console.log(calc([6, 7, 26, 12, 45], 14));
console.timeEnd()

Answer 6

Subset sum problem

Answer 7

多谢各位大神，小弟对算法不是很了解，有这么多大神都用自己的方法帮助我，感谢！

Answer 8

function fn (cion, N) {
    let cionArr = cion.sort((a, b) => {return b - a;});
    for(var i = 0; i < cionArr.length; i++) {
        if(N % cionArr[i] > 0) {
            N = N % cionArr[i];
            console.log(N);
        }else { return true; }
    }
    if(i == cionArr.length){return false}
}

fn([3,77], 100) // false
fn([1,2,5], 11) // true

这样有什么漏洞么？

Answer 9

搜一下背包问题

Answer 10

错误的示例，各位绕过

function count (coins = [], sum = 0) {
  for (let coin of coins) {
    let remainder = sum % coin;
    // console.log('----> ', sum, coin, remainder);
    if (remainder === 0) {
      return true;
    } else {
      // 取余算，如果有这种组合，可最快算出
      let result = count(
        coins.filter(_coin => (coin !== _coin)),
        remainder
      );

      // 递减算
      let result1 = (sum - coin > 0) && count(
        coins.filter(_coin => (coin !== _coin)),
        sum - coin
      );

      if (result || result1) {
        return true;
      }
    }
  }
  return false;
}