javascript - 找到最小切片的绝对和 - 可编码性
问题描述
嗨,我参加了 Codility 测试两次,得分为 0。请帮助我使用 JavaScript 解决问题。
给定一个由 N 个整数组成的非空数组 A。一对整数 (P, Q),使得 0 ≤ P ≤ Q < N,称为数组 A 的切片。切片 (P, Q) 的总和是 A[P] + A[P +1] + ... + A[Q]。
最小绝对切片是其绝对和最小的。
例如,数组 A 使得:
A[0] = 2
A[1] = -4
A[2] = 6
A[3] = -3
A[4] = 9
其中包含以下切片:
- (0,1),其绝对和为 = |2 + (-4)| = 2
- (0,2),其绝对和为 = |2 + (-4) + 6| = 4
- (0,3),其绝对和为 = |2 + (-4) + 6 + (-3)| = 1
- (1,3),其绝对和为 = |(-4) + 6 + (-3)| = 1
- (1,4),其绝对和为 = |(-4) + 6 + (-3) + 9| = 8
- (4,4),其绝对和为 = |9| = 9
切片 (0,3) 和 (1,3) 都是最小绝对切片,它们的绝对和等于 1。
写一个函数:
function solution(A);
即,给定一个由 N 个整数组成的非空数组 A,返回 min abs slice 的绝对和。
为以下假设编写一个有效的算法:
- N 是 [1..1,000,000] 范围内的整数;
- 数组 A 的每个元素都是 [−10,000..10,000] 范围内的整数;
这是我的解决方案:
function solution(A, i = 0, sum = 0) {
const N = A.length;
if (N === 0) {
return 0;
}
if (N == 1) {
return Math.abs(A[0]);
}
A.sort();
// All positives
if (A[0] >= 0 && A[N - 1] >= 0) {
return Math.abs(A[0]);
}
// All Negatives
if (A[0] <= 0 && A[N - 1] <= 0) {
return Math.abs(A[N - 1]);
}
let currAbsSum = 0;
let minAbsSum = Number.MAX_SAFE_INTEGER;
for (var i = 0; i < N; i++) {
let j = N - 1;
while (j >= i) {
currAbsSum = Math.abs(A[i] + A[j]);
if (currAbsSum === 0) {
return 0;
}
minAbsSum = Math.min(currAbsSum, minAbsSum);
if (Math.abs(A[i]) > Math.abs(A[j])) {
i++;
} else {
j--;
}
}
if (A[i] > 0) break;
}
return minAbsSum;
}
解决方案
这是取自此处的 O(n log n) 答案的 javascript 版本:
function solution(A) {
if (1 == A.length) return Math.abs(A[0]);
let sums = new Array(A.length + 1);
let minAbsSum = Number.MAX_SAFE_INTEGER;
sums[0] = 0;
for (var i = 0; i < A.length; i++) {
sums[i + 1] = A[i] + sums[i];
}
sums.sort();
for (var i = 1; i < sums.length; i++) {
minAbsSum = Math.min(minAbsSum, Math.abs(sums[i] - sums[i - 1]));
}
return minAbsSum;
}
console.log(solution([2, -4, 6, -3, 9]))
console.log(solution([10, 10, 10, 10, 10, -50]))
推荐阅读
- react-native - 我想从另一个移动应用程序打开 Qliksense 移动应用程序
- ios - AdMob 刷新请求
- python - Tensorflow 在构建和训练 RNN 时使用了太多内存
- python-3.x - 处理夏令时
- terraform - 在 Terraform 中引用由“for_each”创建的资源实例
- python - 使用 PyTest 进行测试时如何在后台启动 Uvicorn + FastAPI
- sql-server - SQL OLEDB 使用 TLS 1.2 失败
- laravel - 在 Auth::check() 之前,我可以在哪里以及如何设置用户对某些功能或页面的访问权限
- oracle-apex - Oracle Apex 19.1 类图表 100% 区域宽度
- mysql - 无法使用 AWSAuthenticationPlugin 和 terraform 创建 mysql 用户