我正在做一个需要二进制断层扫描算法的测试。提供了一组 38 个测试值来测试正确性，但完成所有测试也有 1 个 CPU 秒的时间限制。问题如下：
如果存在 m×n 矩阵 A，则输出“Yes”，每个元素为 0 或 1，使得
否则输出“否”。
对于每个测试，提供 2 个数组：
- r（矩阵中每一行的总和）
- c（矩阵中每一列的总和）
在等式中：
- m是r数组的长度，其中1 <= m
- n是c数组的长度，其中n <= 1000
- ri是r的一个元素，其中0 <= ri <= n
- cj是c的一个元素，其中0 <= cj <= m
一个“是”的例子
米 = 3; n = 4; r = [2, 3, 2]; c = [1, 1, 3, 2];
一个“不”的例子
米 = 3; n = 3; r = [0, 0, 3]; c = [0, 0, 3];
我有一个似乎可以给出正确答案的解决方案，但是在超过 1 秒的 CPU 时间之前它只管理 12 / 38 次测试。
我最初在 ES5 中编写代码，然后返回并转换为 ES3 以尝试从中获得更多性能。（最初作为 ES5 管理 9 个测试）。我可以对当前算法做很多事情来提高性能（除非我弄错了）。这使我相信我的算法有问题，并且必须有更快的算法来执行此操作。我读了很多书试图找到一个，结果头疼:)
所以我转向社区，看看是否有人可以提出比我目前使用的更快的算法。
'use strict';
const ZEROS = (function (seed) {
let string = seed;
for (let i = 0; i < 19; i += 1) {
string += seed;
}
return string;
}('00000000000000000000000000000000000000000000000000'));
const ZEROSLEN = ZEROS.length;
const permutate = function (n, ri) {
const result = [];
const memoize = {};
let count = 0;
do {
const bin = count.toString(2);
if (ZEROSLEN + bin.length > ZEROSLEN + n) {
break;
}
if (!memoize[bin] && (bin.split('1').length - 1) === ri) {
const string = (ZEROS + bin).slice(-n);
const sLen = string.length;
const perm = new Array(sLen);
for (let i = sLen - 1; i >= 0; i -= 1) {
perm[i] = +string[i];
}
memoize[bin] = result.push(perm);
}
count += 1;
} while (count);
return result;
};
const getMatrixSum = function (n, matrix) {
const mLength = matrix.length;
const rows = new Array(mLength);
const a = new Array(n);
const last = mLength - 1;
for (let x = n - 1; x >= 0; x -= 1) {
for (let y = last; y >= 0; y -= 1) {
rows[y] = matrix[y][x];
}
let sum = 0;
for (let i = rows.length - 1; i >= 0; i -= 1) {
sum += rows[i];
}
a[x] = sum;
}
return a;
};
const isEqual = function (a, b) {
const length = a.length;
if (length !== b.length) {
return false;
}
for (let i = length - 1; i >= 0; i -= 1) {
if (a[i] !== b[i]) {
return false;
}
}
return true;
};
const addRow = function (i, prev, r, c, result) {
if (result) {
return result;
}
const n = c.length;
const ri = r[i];
if (ri < 0 || ri > n) {
throw new RangeError('ri out of range');
}
const p = permutate(n, ri);
const m = r.length;
const rsLast = m - 1;
const nextI = i + 1;
for (let x = p.length - 1; x >= 0; x -= 1) {
const permutation = p[x];
const next = prev.slice();
next.push(permutation);
const sums = getMatrixSum(n, next);
if (i < rsLast) {
let memo = 0;
for (let j = sums.length - 1; j >= 0; j -= 1) {
if (sums[j] > c[j]) {
memo += 1;
}
}
if (!memo && addRow(nextI, next, r, c, result)) {
return true;
}
} else if (isEqual(sums, c)) {
return true;
}
}
return false;
};
const isSolvable = function (r, c) {
const m = r.length;
const n = c.length;
if (m < 1 || n > 1000) {
throw new Error('Bad data');
}
for (let j = n; j >= 0; j -= 1) {
const cj = c[j];
if (cj < 0 || cj > m) {
throw new RangeError('cj out of range');
}
}
return addRow(0, [], r, c, false) ? 'Yes' : 'No';
};
console.log(isSolvable([2, 3, 2], [1, 1, 3, 2]));
console.log(isSolvable([0, 0, 3], [0, 0, 3]));值得注意的是，测试是在 SpiderMonkey 版本 JavaScript-C24.2.0 上运行的
参考：
