发版效率提升计划
详细描述
随着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) + "%";
}
/**
* @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) + '%';
};
希望对你有帮助