Java 磁带平衡 Codility 训练
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19455058/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Tape-Equilibrium Codility Training
提问by CTB
I received a codility test the other day for a job, as such I've been practicing using some of the problems from their training page Link
前几天我收到了一份工作的适应性测试，因此我一直在练习使用他们培训页面链接中的一些问题
Unfortunately, I've only been able to get 83/100 on the Tape-Equilibrium question:
不幸的是，我在 Tape-Equilibrium 问题上只能得到 83/100：
A non-empty zero-indexed array A consisting of N integers is given. Array A represents numbers on a tape.
Any integer P, such that 0 < P < N, splits this tape into two non?empty parts: A[0], A[1], …, A[P ? 1] and A[P], A[P + 1], …, A[N ? 1].
The differencebetween the two parts is the value of: |(A[0] + A[1] + … + A[P ? 1]) ? (A[P] + A[P + 1] + … + A[N ? 1])|
In other words, it is the absolutedifference between the sum of the first part and the sum of the second part.Write a function that, given a non-empty zero-indexed array A of N integers, returns the minimal difference that can be achieved.
Example:
A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3
We can split this tape in four places:P = 1, difference = |3 ? 10| = 7P = 2, difference = |4 ? 9| = 5P = 3, difference = |6 ? 7| = 1P = 4, difference = |10 ? 3| = 7
In this case I would return 1 as it is the smallest difference.N is an int, range [2..100,000]; each element of A is an int, range [?1,000..1,000]. It needs to be O(n) time complexity,
给出了一个由 N 个整数组成的非空零索引数组 A。数组 A 代表磁带上的数字。
任何整数 P，例如 0 < P < N，将磁带分成两个非空部分：A[0], A[1], ..., A[P ? 1] 和 A[P], A[P + 1], ..., A[N ? 1]。两部分
的区别在于：|(A[0] + A[1] + ... + A[P ? 1]) ? (A[P] + A[P + 1] + … + A[N ? 1])|
换句话说，它是第一部分的总和与第二部分的总和之间的绝对差。编写一个函数，在给定 N 个整数的非空零索引数组 A 的情况下，返回可以实现的最小差异。
示例：
A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3
我们可以将此磁带拆分为四个位置：P = 1, difference = |3 ? 10| = 7P = 2，差异 = |4 ？9| = 5P = 3，差异 = |6 ？7| = 1P = 4，差异 = |10 ？3| = 7
在这种情况下，我会返回 1，因为它是最小的差异。N 是一个整数，范围 [2..100,000]；A 的每个元素都是一个整数，范围 [?1,000..1,000]。它需要 O(n) 的时间复杂度，
My code is as follows:
我的代码如下：
import java.math.*;
class Solution {
public int solution(int[] A) {
long sumright = 0;
long sumleft = 0;
long ans;
for (int i =1;i<A.length;i++)
sumright += A[i];
sumleft = A[0];
ans =Math.abs(Math.abs(sumright)+Math.abs(sumleft));
for (int P=1; P<A.length; P++)
{
if (Math.abs(Math.abs(sumleft) - Math.abs(sumright))<ans)
ans = Math.abs(Math.abs(sumleft) - Math.abs(sumright));
sumleft += A[P];
sumright -=A[P];
}
return (int) ans;
}
I went a bit mad with the Math.abs. The two test areas it fails on are "double" (which I think is two values, -1000 and 1000, and "small". http://codility.com/demo/results/demo9DAQ4T-2HS/
我对 Math.abs 有点生气。它失败的两个测试区域是“双倍”（我认为是两个值，-1000 和 1000，以及“小” 。http://codility.com/demo/results/demo9DAQ4T-2HS/
Any help would be appreciated, I want to make sure I'm not making any basic mistakes.
任何帮助将不胜感激，我想确保我没有犯任何基本错误。
采纳答案by Abhishek Bansal
Your solution is already O(N). You need to remove the abs from sumleft and sumright.
您的解决方案已经是 O(N)。您需要从 sumleft 和 sumright 中删除 abs。
if (Math.abs( sumleft - sumright ) < ans)
{
ans = Math.abs( sumleft - sumright );
}
Also before the second for loop,
同样在第二个 for 循环之前，
ans =Math.abs( sumleft - sumright );
It should work.
它应该工作。
回答by PGrejc
I was doing the same task, but couldn't get better than 50 something points. My algorithm was too slow. So, I searched for a hint and found your solution. I've used the idea of summing the elements in the array only once and got 100/100. My solution is in JavaScript, but it can be easily transformed into Java. You can go to my solution by using the link below.
我正在做同样的任务，但无法获得超过 50 分的分数。我的算法太慢了。所以，我搜索了一个提示并找到了您的解决方案。我使用了只对数组中的元素求和一次并得到 100/100 的想法。我的解决方案是在 JavaScript 中，但它可以很容易地转换为 Java。您可以使用下面的链接转到我的解决方案。
http://codility.com/demo/results/demo8CQZY5-RQ2/
http://codility.com/demo/results/demo8CQZY5-RQ2/
Please take a look at my code and let me know if you have some questions. I'd be very happy to help you.
请查看我的代码，如果您有任何问题，请告诉我。我很乐意帮助你。
function solution(A) {
// write your code in JavaScript 1.6
var p = 1;
var sumPartOne = A[p - 1];
var sumPartTwo = sumUpArray(A.slice(p, A.length));
var diff = Math.abs(sumPartOne - sumPartTwo);
for(p; p < A.length - 1; p++) {
sumPartOne += A[p];
sumPartTwo -= A[p];
var tempDiff = Math.abs(sumPartOne - sumPartTwo);
if(tempDiff < diff) {
diff = tempDiff;
}
}
return diff;
}
}
function sumUpArray(A) {
var sum = 0;
for(var i = 0; i < A.length; i++) {
sum += A[i];
}
return sum;
}
}
回答by user3137288
Similar algorithm of CTB posted above: This code get 100% score in JAVA;
上面贴的类似CTB的算法：这段代码在JAVA中得到100%的分数；
class Solution {
public int solution(int[] A) {
int [] diff;
int sum1;
int sum2=0;
int ans, localMin;
diff = new int[A.length-1];
//AT P=1 sum1=A[0]
sum1=A[0];
for (int i =1;i<A.length;i++){
sum2 += A[i];
}
ans = Math.abs(sum1- sum2);
for (int p= 1;p<A.length;p++){
localMin= Math.abs(sum1- sum2);
if( localMin < ans ){
ans = localMin;
}
//advance the sum1, sum2
sum1+= A[p];
sum2-= A[p];
diff[p-1]=localMin;
}
return (getMinVal(diff));
}
public int getMinVal(int[] arr){
int minValue = arr[0];
for(int i=1;i<arr.length;i++){
if(arr[i] < minValue){
minValue = arr[i];
}
}
return minValue;
}
}
}
回答by pietro
this is my 100 score code in Python maybe will help you. You should take a look at if statment its prevent from "double error" if You have N=2 A=[-1,1] when you make sum You get 0 but it should return |-1-1|=|-2|=2
这是我在 Python 中的 100 分代码，也许会对您有所帮助。如果你有 N=2 A=[-1,1] 当你做 sum 你得到 0 但它应该返回 |-1-1|=|-2 |=2
def solution(A):
a=A
tablica=[]
tablica1=[]
suma=0
if len(a) == 2:
return abs(a[0]-a[1])
for x in a:
suma = suma + x
tablica.append(suma)
for i in range(len(tablica)-1):
wynik=(suma-2*tablica[i])
tablica1.append(abs(wynik))
tablica1.sort()
return tablica1[0]
回答by jimi
This is 100 score in ruby
这是红宝石的 100 分
def solution(a)
right = 0
left = a[0]
ar = Array.new
for i in 1...a.count
right += a[i]
end
for i in 1...a.count
check = (left - right).abs
ar[i-1] = check
left += a[i]
right -= a[i]
end
find = ar.min
if a.count == 2
find = (a[0]-a[1]).abs
end
find
end
回答by Alex Fortuna
Consider this 100/100 solution in Ruby:
考虑这个 Ruby 中的 100/100 解决方案：
# Algorithm:
#
# * Compute the sum of all elements.
# * Iterate over elements, maintain left and right weights appropriately.
# * Maintain a minimum of `(left - right).abs`.
def solution(ar)
sum = ar.inject(:+)
left = ar[0]
right = sum - left
min_diff = (right - left).abs
1.upto(ar.size - 2) do |i|
left += ar[i]
right -= ar[i]
diff = (right - left).abs
min_diff = [min_diff, diff].min
end
# Result.
min_diff
end
#--------------------------------------- Tests
def test
sets = []
sets << ["1", 1, [1]]
sets << ["31", 2, [3, 1]]
sets << ["312", 0, [3, 1, 2]]
sets << ["[1]*4", 0, [1]*4]
sets << ["[1]*5", 1, [1]*5]
sets << ["sample", 1, [3, 1, 2, 4, 3]]
sets.each do |name, expected, ar|
out = solution(ar)
raise "FAILURE at test #{name.inspect}: #{out.inspect} != #{expected.inspect}" if out != expected
end
puts "SUCCESS: All tests passed"
end
回答by JPK
Some C# for ya.
一些 C# 给你。
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
class Solution
{
public int solution(int[] A)
{
// write your code in C# with .NET 2.0
int sumRight = 0;
for(int i=0; i<A.Length; i++)
{
sumRight += A[i];
}
int sumLeft = 0;
int min = int.MaxValue;
for(int P=1; P<A.Length; P++)
{
int currentP = A[P-1];
sumLeft += currentP;
sumRight -= currentP;
int diff = Math.Abs(sumLeft - sumRight);
if(diff < min)
{
min = diff;
}
}
return min;
}
}
回答by Nadesri
I was also running into issues getting 83% just like CTB, but for my C++ solution.
我也遇到了像 CTB 一样获得 83% 的问题，但对于我的 C++ 解决方案。
For my code, my tape sum was evaluating AFTER updating rightsum and leftsum, but therein lies the problem. In this case, the second loop should evaluate up until P=A.size()-1. Otherwise, you will end up evaluating a tape pair where everything is added to leftsum, and nothing is added to rightsum (which is not allowed according to the problem description).
对于我的代码，我的磁带总和在更新 rightsum 和 leftsum 后进行评估，但问题就在这里。在这种情况下，第二个循环应该评估直到 P=A.size()-1。否则，您最终将评估一个磁带对，其中所有内容都添加到 leftsum 中，而 rightsum 中没有添加任何内容（根据问题描述这是不允许的）。
One possibly nice aspect about my solution below (now fixed to get 100%) is that it does one less evaluation of the sum, compared to a couple solutions above.
下面我的解决方案的一个可能不错的方面（现在固定为 100%）是，与上面的几个解决方案相比，它对总和的评估少了一次。
#include <stdlib.h>
int solution(vector<int> &A) {
int sumright = 0;
int sumleft;
int result;
for (int i=1; i<A.size(); i++) {
sumright += A[i];
}
sumleft = A[0];
result = abs(sumleft-sumright);
for (int i=1; i<A.size()-1; i++) {
sumleft += A[i];
sumright -= A[i];
if (abs(sumleft-sumright)<result) {
result = abs(sumleft-sumright);
}
}
return result;
}
回答by J.A
this is what I did!!! // write your code in C# with .NET 2.0
这就是我所做的！！！// 使用 .NET 2.0 用 C# 编写代码
using System;
class Solution
{
public int solution(int[] A)
{
int sumRight = 0, sumleft, result;
for(int i=1; i<A.Length; i++)
{
sumRight += A[i];
}
int sumLeft = A[0];
int min = int.MaxValue;
for(int P=1; P<A.Length; P++)
{
int currentP = A[P-1];
sumLeft += currentP;
sumRight -= currentP;
int diff = Math.Abs(sumLeft - sumRight);
if(diff < min)
{
min = diff;
}
}
return min;
}
}
回答by apocalypse
My C# code 100/100:
我的 C# 代码 100/100：
using System;
class Solution
{
public int solution (int[] A)
{
int min = int.MaxValue;
int sumLeft = 0;
int sumRight = ArraySum (A);
for (int i = 1; i < A.Length; i++)
{
int val = A[i - 1];
sumLeft += val;
sumRight -= val;
int diff = Math.Abs (sumLeft - sumRight);
if (min > diff)
{
min = diff;
}
}
return min;
}
private int ArraySum (int[] array)
{
int sum = 0;
for (int i = 0; i < array.Length; i++)
{
sum += array[i];
}
return sum;
}
}
