一些算法题

alg,js

//Q：两个玻璃珠，n层楼，确定会摔碎的临界层所需的最少次数
//缓存递归过程中的结果
var cache = [];
function find(n) {
//确定递归的结束条件
  if(n == 1){
    return 1;
  }
  if(n == 0){
    return 0;
  }
  
//有缓存返回缓存
  if(cache[n]){
    return cache[n];
  }
  
//先假定一个最大的最小值（即从第一层逐层试到第n层）
  var min = n;
  //第一次挑第i层扔的最坏结果
  for(var i = 1; i < n; i++){
  //动态规划，摔碎则i次，没碎则缩小为为-i层的问题
    var result = Math.max(i, find(n-i)+1);
    //记录最优解
    if(min > result){
      min = result;
    }
  }
  //缓存结果
  cache[n] = min;
  
  return min;
}

console.log(find(39));//结果是9，即从第9层开始扔，最坏结果为扔9次
//QEND

//Q：从1到n中含有多少个k
function find(n, k) {
  var count = 0;
  for(var i = 1; i <= n; i*=10){
    //以个位，十位，百位分割数字
    //假设n=21313,k=2
    //以i=100为例,a=213,b=13
    var a = Math.floor(n/i);
    var b = n % i;
    var resultA;
    //当a的最低位大于等于k+1=3时,有a/10+1=22(0~21)个百位
    //且每个百位都有100个k
    if(a % 10 >= k+1){
      resultA = (Math.floor(a/10) + 1) * i;
    }else if (a % 10 == k){
    //当a最低位等于k时，有a/10 个百位满足每个百位有100个k，
    //剩余b+1个数百位是k
      resultA = (Math.floor(a/10)) * i + b + 1;
    }else{
    //当a最低位小于k时，只有a/10个百位满足条件
    //（如21113，只有前两位为（0~20）时满足百位为k）
      resultA = Math.floor(a/10) * i;
    }
    count += resultA;
  }
  return count;
}


var n = 22;
console.log(find(n,2));
console.log([...Array(23).keys()])
//QEND

//最小的K个数（类似题目：找出数组中出现次数超过一半的数：pivotIndex == middle时停止）
//解法一：用partition，pivotIndex == k-1时停止。O(n)算法。
//优点：快；缺点：改变原数据、无法处理海量数据
//解法二：用容器装这K个数据，未满则入，满则找最大比较，小于最大则增删。O(nlogk)算法。
//可用最大堆/红黑树作容器（其增删操作耗时O(logk)）。
//优点：不改变原数据，可以处理海量数据；缺点：稍慢