个人中心
gpt4 book ai didi

javascript - 找到最小切片的绝对和 - codility

转载 作者：塔克拉玛干 更新时间：2023-11-03 04:38:09 25 4
gpt4 key购买 nike

<分区>

您好，我参加了两次 Codility 测试，得分为 0。请帮助我使用 JavaScript 解决问题。

给定一个由N个整数组成的非空数组A。一对整数 (P, Q) 满足 0 ≤ P ≤ Q < N，称为数组 A 的切片。切片 (P, Q) 的总和是 A[P] + A[P +1] + ... + A[Q].

min abs slice 的绝对和是最小的。

例如，数组 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;
}

25 4 0
文章推荐： arrays - 给定 4 个数组，未排序，找到所有可能的四元组，其总和
文章推荐： arrays - 统计至多 k 个奇数的子数组
文章推荐： algorithm - 给定2D点列表和正方形网格大小，返回最接近最多点的坐标
文章推荐： java - Mac + Selenium + Chrome = 找不到 Chrome 二进制文件
塔克拉玛干
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com