Codility 算法测验

>> 欢迎您客人: 登录 | 注册 | 在线 | 搜索 | 风格 | 帮助 | 统计 | 文章

返回首页

>>分享数据结构和算法相关的知识和技术

书籍支持

卫琴直播

品书摘要

在线测试

资源下载

联系我们

Java技术网站 → 『 Java开发技术』 → 『数据结构和算法专题』 → Codility 算法测验

您是本文章第 19646 个阅读者

* 贴子主题: Codility 算法测验

点赞(0) 收藏

作者:flybird 发表时间：2020-03-15 19:13:11

消息

查看

搜索

好友

邮件

复制

引用

这个题目第一次做得到90分，大大提高了信心。

给定一个非空的从零起始的数组A，包含N个整数。(P, Q) 满足 0<=P<=Q<N, 被称作A的一个slice。(P, Q) 的sum表示 A[P]+A[P+1]+...+A[Q].

min abs slice 表示一个slice，其sum的绝对值是最小的。

举例来说，数组A

A[0] = 2 A[1] = -4 A[2] = 6 A[3] = -3 A[4] = 9

包含以下slice（不仅这些）

(0, 1), whose absolute sum = |2 + (4)| = 2
(0, 2), whose absolute sum = |2 + (4) + 6| = 4
(0, 3), whose absolute sum = |2 + (4) + 6 + (3)| = 1
(1, 3), whose absolute sum = |(4) + 6 + (3)| = 1
(1, 4), whose absolute sum = |(4) + 6 + (3) + 9| = 8
(4, 4), whose absolute sum = |9| = 9

slices (0, 3) 和 (1, 3) 都是min abs slice, 他们的绝对值和等于1.

算法要求如下：

给定非空，索引从0开始的数组A，包含N个整数，寻求 min abs slice，返回其sum的绝对值。

假定：

N的取值范围为[1..100,000];
A中元素取值范围为[10,000..10,000].

复杂度要求：

时间复杂度为 O(N*log(N));
空间复杂度为 O(N)

原文如下：

A non-empty zero-indexed array A of N integers is given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].

A min abs slice is a slice whose absolute sum is minimal.

For example, array A such that:

<tt> A[0] = 2 A[1] = -4 A[2] = 6 A[3] = -3 A[4] = 9</tt>

contains the following slices, among others:

  (0, 1), whose absolute sum = |2 + (4)| = 2
  (0, 2), whose absolute sum = |2 + (4) + 6| = 4
  (0, 3), whose absolute sum = |2 + (4) + 6 + (3)| = 1
  (1, 3), whose absolute sum = |(4) + 6 + (3)| = 1
  (1, 4), whose absolute sum = |(4) + 6 + (3) + 9| = 8
  (4, 4), whose absolute sum = |9| = 9

Both slices (0, 3) and (1, 3) are min abs slices and their absolute sum equals 1.

Write a function:

<tt>class Solution { public int solution(int[] A); }</tt>

that, given a non-empty zero-indexed array A consisting of N integers, returns the absolute sum of min abs slice.

For example, given:

<tt> A[0] = 2 A[1] = -4 A[2] = 6 A[3] = -3 A[4] = 9</tt>

the function should return 1, as explained above.

Assume that:

N is an integer within the range [1..100,000];
each element of array A is an integer within the range [10,000..10,000].

Complexity:

expected worst-case time complexity is O(N*log(N));
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

实现：

public int solution(int[] A) {
        int sum = 0;
        int n = A.length;
        int[] sums = new int[n];
        for (int i=0; i<n; i++) {
            sum += A[i];
            if (sum == 0) return 0;
            sums[i] = sum;
        }
        // 问题转换为数组sums[], 寻找两个元素之差的绝对值最小 min(|S[P] - S[Q]|), 即点之间的最小距离
        Arrays.sort(sums);
        int ans = Math.abs(sums[0]);
        for (int i=0; i<n-1; i++) {
            ans = Math.min(ans, Math.abs(sums[i+1] - sums[i]));
        }
        return ans;
    }

----------------------------
原文链接:https://blog.51cto.com/fushan/1673955

程序猿的技术大观园：www.javathinker.net

[这个贴子最后由 flybird 在 2020-03-15 19:13:11 重新编辑]

Java精品书籍推荐