关于javascript:JS-教练我想做习题17

???? 前言

大家好呀，我是毛小悠，能够叫我二毛，在家中排行老二，是一名前端开发工程师。

本系列文章旨在通过练习来进步 JavaScript 的能力，一起欢快的做题吧。????????????

以下每道题，二毛我都有尝试做一遍。倡议限时训练，比方限定为半小时，如果半小时内想不进去，能够联合文章开端的参考答案来思考。

求关注求点赞????\~~~????????????

???? 题目 1：受约束的 GCD

将为您提供两个数字 n 和 k，您的工作将是返回总和为 n 且具备最大可能 GCD 的 k 位数组。

例如，假如 n = 12，k = 3，则有许多可能的 3 位数组之和等于 12，例如[1,2,9]，[2,3,7]，[2,4，6]，… 等。在所有可能性中，具备最高 GCD 的可能性为[2,4,6]。因而，solve（12,3）= [2,4,6]。

还要留神，数字不能在子数组内反复，因而 [1,1,10] 是不可能的。最初，如果没有这样的数组，则返回一个空数组。

习题代码：

function solve(n,k){//..};

???? 题目 2：排列

您将取得 N 个 k 位整数。您必须重新排列整数中的数字，以便最大和最小数字之间的差别最小。所有整数均应依照雷同的规定重新排列。

输出：
输出蕴含 N 个 k 位正整数（写为字符串）的数组。初始整数和数字重新排列后的整数都容许前导零。

输入：
返回一个数字：依照雷同规定将所有整数重新排列后，最大和最小数字之间的最小差值。

例子：

['5237', 
 '2753', 
 '7523', 
 '5723',     =>  2700 
 '5327', 
 '2537']

['010',
 '909',      =>  3
 '012]

['00',
 '57',       =>  75
 '76']

留神：
在第一个样本中，如果咱们将数字重新排列为（3,1,4,2），则第二个和第四个数字将别离等于 5237 和 2537（对于这样的数字程序）。
在第二个示例中，如果咱们替换第二个数字和第一个数字，咱们将失去整数 100、99 和 102。

习题代码：

function permutations(s) {}

答案

???? 题目 1 的答案

参考答案 1：

function solve(n, k) {let minMult = k * (k + 1) / 2
  let maxGCD = n / minMult | 0
  if (!maxGCD) return []
  
  while (n % maxGCD) maxGCD--
  let result = Array.from({length: k-1}, (_,i) => maxGCD * (i+1))
  result.push(n - k * (k-1) * maxGCD / 2)
  return result
}

参考答案 2：

const solve=(n,k)=>(r=>r?Array.from({length:k-1},(_,i)=>(i+1)*r).concat(n-(k-1)*k*r/2):[])((m=>Array.from({length: m},(_,i)=>m-i).filter(e=>(n-(k-1)*k*e/2)%e==0)[0])(Math.floor(n/(k*(k+1)/2))));

参考答案 3：

function solve(n,k){for (var i = n; i > 0; i--) {if (n % i === 0 && i * k * (k+1) / 2 <= n) {return [...[...Array(k-1)].map((_, j) => i * (j+1)), n - (i * k * (k-1) / 2)];
    }
  }
  return [];}

参考答案 4：

function solve(n,k){
  let gcd = n;
  let results = [];

  function factorial(interval, count = k){
    let increment = interval;
    let acc = 0;
    while (count > 0) {
      acc += increment;
      increment += interval;
      count--;
    }
    return acc;
  }

  if (factorial(1) > n) return [];

  while (true) {if (factorial(gcd) <= n){let diff = n - factorial(gcd, k-1);
  
      if (diff%gcd === 0) {
        let temp = gcd;
        for (let i = 0; i < k-1; i++) {results.push(temp);
          temp += gcd;
        }
        results.push(diff);
      }
  
      else {
        let temp = gcd;
        for (let i = 0; i < k; i++) {results.push(temp);
        }
      }

      if (results.reduce((a,c)=> a+c) === n) break;
      results = [];}
    gcd--;
  }

  return results;
}

参考答案 5：

function solve(n,k){
   var sol = null;
   for (var i = 1; i < n; ++i) {if ( n == i || n % i == 0) {var sum = k*(k+1)/2*i;
         if (sum > n) {break;} else {sol = i;}
      }
   }
   
   var retval = [];
   if (sol === null) {return retval;}
   
   var rest = n;
   var count = sol;
   for (var i = 0; i < k-1; ++i) {retval.push(count);
      rest -= count;
      count += sol;
   }
   retval.push(rest);

   return retval;
}

???? 题目 2 的答案

参考答案 1：

// https://github.com/gkucmierz/algorithms/blob/master/js/generate_permutations.js
const genPermutations = size => {const perms = [];
  const gen = (res, used, shift) => {if (used === size) {perms.push(res);
    }
    for (let i = 0; i < (size-used); ++i) {gen([...res, shift[i]], used + 1, [...shift.slice(0, i), ...shift.slice(i + 1)]);
    }
  };
  gen([], 0, new Array(size).fill(0).map((_, i) => i));
  return perms;
};

function permutations(s) {const perms = genPermutations(s[0].length);
  return perms.reduce((smallest, perm) => {let [min, max] = [Infinity, 0];
    s.map(str => {const val = +perm.map(i => str[i]).join``;
      if (val < min) min = val;
      if (val > max) max = val;
    });
    return Math.min(smallest, max - min);
  }, Infinity);
}

参考答案 2：

function* permute(array, currArr=[], skip=[]){for( let itr=0; itr<array.length; itr++){if( skip.includes(itr) ) continue
    yield* permute(array, [...currArr, array[itr]], [...skip, itr])
  }
  if(currArr.length == array.length) yield currArr;
}

function* baz(start, stop, step=1){for( let itr=start; itr<stop; itr+=step){yield itr}
}

function permutations(array){let noLen = array[0].length
  let orders = permute([...baz(0, noLen)])
  let rtn = Infinity;
  for(let order of orders){let re_order = array.map(noStr => parseInt(order.map(val => noStr[val]).join('')) );
    let x = Math.max(...re_order) - Math.min(...re_order);
    rtn = rtn < x ? rtn : x;
  }
  return rtn
}

参考答案 3：

Array.prototype.concatMap = function(fn) {return [].concat(...this.map(fn)); };
Array.prototype.without = function(i) {return [].concat(this.slice(0,i),this.slice(i+1)); };
Array.prototype.permutations = function(n) {return n ? this.concatMap( (v,i) => this.without(i).permutations(n-1).map(w => [v,...w] ) ) : [[]] ; };

const permutations = a => Math.min(...Array.from( a[0], (_,i) => i ).permutations(a[0].length).map(perm => a.map( v => Number( perm.map( i => v[i] ).join("") ) ) ).map(a => Math.max(...a) - Math.min(...a) )) ;

参考答案 4：

function permutations(s) {var perms = [], len = s[0].length;
  (function f(lst,elems=[]){if(elems.length===len) {perms.push(elems); return;}
    for(let i=0; i<lst.length; i++) {let t=lst.slice(), e=t.splice(i,1);
      f(t,elems.concat(e));
    }
  })([...Array(len)].map((_,i)=>i));
  return Math.min(...perms.map(r=>s.map(n=>+r.map(i=>n[i]).join(''))).map(r=>Math.max(...r)-Math.min(...r)));
}

参考答案 5：

function permutations(arr) {
  let best=Infinity;
  for(let idx of genPermIdx(arr[0])){let x=arr.map(s=>+idx.map(i=>s[i]).join(''));
    let a=Math.min(...x), b=Math.max(...x);
    best=best>b-a?b-a:best;
  }
  return best;
}

function* genPermIdx(s){const dfs=function*(arr,perm=[]){if(!arr.length) yield perm;
    else{
      let i=-1;
      for(let v of arr){ i++;
        perm.push(v);
        yield* dfs(arr.slice(0,i).concat(arr.slice(i+1)),perm);
        perm.pop();}
    }
  }
  let arr=Array.from(s,(_,i)=>i);
  yield* dfs(arr);
}

???? 后序

本系列会定期更新的，题目会由浅到深的逐步提高。

求关注求点赞 ????~~????????????

能够关注我的公众号：前端毛小悠。欢送浏览