>>分享数据结构和算法相关的知识和技术 书籍支持  卫琴直播  品书摘要  在线测试  资源下载  联系我们
发表一个新主题 开启一个新投票 回复文章 您是本文章第 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面向对象编程-->接口
  JavaWeb开发-->Servlet技术详解(Ⅲ)
  JSP与Hibernate开发-->立即检索和延迟检索策略
  Java网络编程-->基于MVC和RMI的分布式应用
  精通Spring-->Vue Router路由管理器
  Vue3开发-->Vue组件开发基础
  64匹马,8个赛道,找出跑得最快的4匹马
  算法学习与收集:一些有用的算法网站和网页
  无向图的最短路径求解算法之——Dijkstra算法
  常见的调度算法
  haproxy调度算法
  分布式一致Hash算法-存储之道
  AES算法,DES算法,RSA算法JAVA实现
  Haproxy支持的调度算法
  Citrix Netscaler负载均衡算法
  全排列的六种算法
  Binary Search二分查找算法
  字节跳动面试官这样问消息队列:分布式事务、重复消费、顺序...
  RSA 非对称加密原理(小白也能看懂哦~)
  谷歌面试算法题:两个排序数组的中位数
  分析递归和迭代的区别、优缺点及实例对比
  更多...
 IPIP: 已设置保密
树形列表:   
1页 0条记录 当前第1
发表一个新主题 开启一个新投票 回复文章


中文版权所有: JavaThinker技术网站 Copyright 2016-2026 沪ICP备16029593号-2
荟萃Java程序员智慧的结晶,分享交流Java前沿技术。  联系我们
如有技术文章涉及侵权,请与本站管理员联系。