求成功率计算代码,详细见描述

发版效率提升计划
详细描述
随着Shopee业务的不断扩张,项目数量越来越多。为了做到有序发版,小李需要先统计出当前发版的成功率,再做针对性的优化。
首先,在不考虑依赖的情况下,项目有两个数据:总发版次数total、发版失败的次数fail。我们认为(total-fail)/total100%就是这个项目“自身的成功率”。
其次如果一个项目依赖了多个项目,那么这个项目的成功率应当是:该项目的自身成功率
所有依赖项都成功的概率。
整个系统发版的成功率就是:所有最下游(不依赖任何项目)的项目都成功的概率。
小李想选择一个项目做优化,把项目的自身成功率增加到1。他想知道,这最多可以让系统的发版成功率增加到多少。返回的结果请使用xxx%的格式,四舍五入保留6位小数(注意JavaScript 中的 toFixed 不是四舍五入,请自行使用 Math.round 来处理)
PS.我们认为整个系统有N个项目,编号分别是0~N-1。
【数据规模】
对于10%的数据,项目的依赖关系是一条链。对于30%的数据,项目不超过10个。
对于全部数据,项目不超过50个,其余数字均小于10000。
示例1
输入[1,1,1,1,1][10,10,10,10,10],[[],[0],[1],[2],[3]]
输出65.610000%"
说明
每个项目的发版成功率都是90%,依赖关系是一条链,因此随意选一个项目将成功率优化成100%,最终结果都是10.90.90.90.9=0.6561,所以答案是65.610000%。

以下是一个可能的JavaScript代码实现,可以用来计算整个系统的发版成功率增加的最大值:


function successRate(total, fail) {
  return (total - fail) / total;
}

function calcSuccessRate(project, rates, dependencies) {
  if (dependencies[project].length === 0) {
    return rates[project];
  } else {
    let successProb = 1;
    for (let i = 0; i < dependencies[project].length; i++) {
      let dep = dependencies[project][i];
      successProb *= calcSuccessRate(dep, rates, dependencies);
    }
    return successProb * rates[project];
  }
}

function calcMaxSuccessRateIncrease(total, fail, dependencies) {
  let successRates = [];
  for (let i = 0; i < total; i++) {
    successRates.push(successRate(total[i], fail[i]));
  }
  let maxIncrease = 0;
  for (let i = 0; i < total; i++) {
    let oldSuccessRate = successRates[i];
    let newSuccessRate = 1;
    let deps = dependencies.slice();
    deps[i] = [];
    for (let j = 0; j < total; j++) {
      if (deps[j].indexOf(i) !== -1) {
        deps[j] = deps[j].filter(dep => dep !== i);
      }
    }
    for (let j = 0; j < total; j++) {
      if (deps[j].length === 0) {
        newSuccessRate *= successRates[j];
      }
    }
    let increase = newSuccessRate - oldSuccessRate;
    if (increase > maxIncrease) {
      maxIncrease = increase;
    }
  }
  return (Math.round(maxIncrease * 1000000) / 10000).toFixed(6) + "%";
}

  • 其中,successRate(total, fail)函数用来计算一个项目的自身成功率;calcSuccessRate(project, rates, dependencies)函数用来计算一个项目的成功率,包括依赖项的成功率;calcMaxSuccessRateIncrease(total, fail, dependencies)函数用来计算整个系统的发版成功率增加的最大值。
  • 具体使用方法是,给定项目的总发版次数数组total、发版失败的次数数组fail、以及项目之间的依赖关系数组dependencies,调用calcMaxSuccessRateIncrease(total, fail, dependencies)函数即可得到最大的成功率增加值。
  • 注意,在实现中为了避免修改原始的dependencies数组,我们使用了slice()方法复制了一份副本。如果对原始数组没有修改的要求,可以不进行复制。
/**
 * @param {number[]} total
 * @param {number[]} fail
 * @param {number[][]} dependencies
 * @return {string}
 */
var maxSuccessProbability = function(total, fail, dependencies) {
    const n = total.length;  // 项目数
    const dp = Array(n).fill(0);  // 记录每个项目的成功率
    const graph = Array(n).fill().map(() => []);  // 邻接表表示项目依赖关系
    const outDegree = Array(n).fill(0);  // 记录每个项目的出度
    for (let i = 0; i < n; i++) {
        dp[i] = (total[i] - fail[i]) / total[i];  // 计算自身成功率
        for (let j of dependencies[i]) {
            graph[j].push(i);  // 记录依赖关系
            outDegree[i]++;  // 统计出度
        }
    }

    // 递归计算项目的成功率
    const calcSuccessProbability = function(i) {
        if (dp[i]) {  // 如果已经计算过,直接返回结果
            return dp[i];
        }
        let prob = dp[i] = 0;
        for (let j of graph[i]) {
            prob += calcSuccessProbability(j) / total[j];  // 计算依赖项的成功概率之和
        }
        dp[i] = dp[i] * prob;  // 乘以自身成功率
        return dp[i];
    };

    // 计算整个系统的成功率
    let prob = 1;
    for (let i = 0; i < n; i++) {
        if (outDegree[i] === 0) {  // 如果是最下游的项目
            prob *= calcSuccessProbability(i);
        }
    }

    // 格式化输出结果
    return (prob * 100).toFixed(6) + '%';
};

希望对你有帮助