2020-05-19 4 kyu How many number

My answer / NAC

function findAll(n, k) {
    var res = [];
    for(let i=Math.pow(10, k-1); i<Math.pow(10, k); i++){
      if(i.toString() == i.toString().split("").sort().join`` && i.toString().split("").reduce((a,b)=>Number(a)+Number(b), 0) == n) res.push(i);
    }
    return res.length ? [res.length, res[0].toString(), res[res.length-1].toString()] : [];
}

问题出在哪？

• 直接穷举法对计算机的计算量太大，耗时超过12000ms了
• 需要优化（递归），这里的递归学问就大了。递归本质上就是循环（能取代一些循环的操作），却胜过循环，简称“套娃”。

My answer / AC

function findAll(n, k, min=1) {
    // 判断结束条件
    if(n<k*min || n>k*9) return [];
    if(k==1) return [1, String(n), String(n)];
    // 两种情况会返回，要么要求的sum不可能达到要求（太小了我后面全取最小的都表示不了）
    // 要么太大了，后面全取9都表示不了，这两种都直接返回[]。
    // 而能够表示的，并且只要求一位数字的，直接返回一位所对应的结果。
    
    var count = 0;
    var maximum = "0".repeat(k);
    var minimum = "9".repeat(k);
    for(var i=min; i<=9; i++){
      var cur = findAll(n-i, k-1, min=i);
      if(cur.length>0){
        count += cur[0];
        // （站在最高层想）将弟弟们递归完出来的最大/最小值加上当前字符变成一个新的字符串，
        // 在这些新的字符串里面找到当前的最大值
        // （站在倒数第二层想）将下一个递归完出来并且不为[]的findAll(n-i, 1, i)之结果[1, n-i, n-i]的最大/最小值加上当前字符变成一个新的字符串，
        // 在这些新的字符串里面找到当前的最大值
        minimum = minimum<(i+cur[1])?minimum:i+cur[1];
        maximum = maximum>(i+cur[2])?maximum:i+cur[2];
      }
      
    }
    console.log(count+","+minimum+","+maximum);
    return [count, minimum, maximum];
}

• 这里findAll(n, k, min)和它的返回值[count, minimum, maximum]是真的得好好看懂的。
• n是当前轮的总和值，k是当前轮的总位数，min是新加的，表示当前轮能取到最小的数字，方便递归操作，也能够保证我们的数字是从小到大走的。（我本来思路是循环，没想这里使用递归来将位数不断逼小，直到k为1，而循环是没有这种路越走越窄最后变成if(k===1)这种单独判断的，这也是为什么说递归胜过循环了）

递归的上下文（stack frame）会切换，循环不会切换（位于相同的 stack frame）

from hoodlum1980

• count是当前轮递归满足要求的总个数，minimum和maximum分别是当前轮最小值和当前轮最大值

Best answer

function findAll(n,k,min=1) {
  if(n<min*k || n>9*k)
    return [];
  if(k===1)
    return [1,String(n),String(n)];
  var counter=0;
  var minimum="9".repeat(k);
  var maximum="0".repeat(k);
  for(var i=min;i<=9;i++){
    var current=findAll(n-i,k-1,i);
    if(current.length>0){
      counter+=current[0];
      if(i+current[1]<minimum)
        minimum=i+current[1];
      if(i+current[2]>maximum)
        maximum=i+current[2];
    }
  }
  return [counter,minimum,maximum];
}

好在哪？

• 用了递归，加了新参数。优化了性能，避免爆服务器。

Recap

• 多做点递归，熟悉递归的上下文相关的写代码方式