华为od机试
第三题：求组合
给定两个正整数a和b，a & b 记为相似值，a ^ b 记为差异值；
输入n个正整数，求满足差异值大于相似值的组合的总数；
输入描述
第一行输入 n 表示 n 个正整数，1 < n < 100000
4
第二行输入 n 个正整数的值
4 3 5 2
输出描述
输出满足差异值大于相似值的组合的总数
4
用的回溯算法超时，只通过35%，求解牛友们怎么优化
let lines = ['4', '4 3 5 2'];
function getResult(lines) {
const n = lines[0] * 1;
let arr = lines[1]
.split(' ')
.map(Number)
.sort((a, b) => a - b);
let count = 0;
console.log(arr);
backtracing(0, 2, n, [], []);
function backtracing(startIdx, k, n, path, used) {
if (path.length === k) {
const [a, b] = path;
if ((a & b) < (a ^ b)) {
console.log(a, b);
count++;
}
return;
}
for (let i = startIdx; i < n - (k - path.length) + 1; i++) {
if (i > 0 && arr[i] === arr[i - 1] && !used[i - 1]) continue;
// if (used[i]) continue;
path.push(arr[i]);
used[i] = false;
backtracing(i + 1, k, n, path, used);
path.pop();
used[i] = true;
}
}
return count;
}
getResult(lines);
#华为od机试#
拼多多集团-PDD公司福利 817人发布