Codility平衡指数样本测试 - 我的刺吧 [英] Codility equilibrium index sample test - my stab at it
问题描述
我做下面的测试Codility磨练自己的技能，或缺乏他们。
这是一个演示任务。你可以阅读有关该任务及其在这篇博客文章的解决方案。由N个整数的零索引数组A中给出。此阵的平衡指数为任何整数p 0≤P＆LT; N和较低的指数的元素的总和等于较高指数，即元素的总和A [0] + A [1] + ... + A [P-1] = A [P + 1] + ... + A [N-2] + A [N-1]。
零元素的总和被假定为等于0。这可能发生，如果P = 0，或者如果P = N-1。例如，考虑由N = 7元以下数组A：
A [0] = -7 A [1] = 1 A [2] = 5
A [3] = 2 A [4] = -4 A [5] = 3
A [6] = 0
P = 3是该数组的平衡指数，这是因为：•A [0] + A [1] + A [2] = A [4] + A [5] + A [6]P = 6也是一个均衡指数，这是因为：•A [0] + A [1] + A [2] + A [3] + A [4] + A [5] = 0并有与指数大于6没有元素。P = 7不是平衡索引，因为它不符合条件0≤P＆下; N.
.............................. ...........................................
我的code如下。我拿到18满分100，但我的code经过样品阵列和一个简单的数组，以及其他一些测试。然而，code，因为它没有一些复杂的阵列，并不能很好地扩展失败。谁能给我任何指针，不管是用集合或提高我的code原样。如果我的code就是垃圾，我可以采取看跌起伏。
类解决方案{
公众诠释溶液（INT [] A）{
中期业绩= -1; 的for（int i = 0; I＆LT;则为a.length;我++）{
/ *获取数组的当前索引* /
INT currIndex = I;
长sumdleft = 0;
长sumdright = 0; 为（中间体J = currIndex; J + 1＆下;则为a.length ++ j）条{ / *金额目前指数*权/ sumdright = sumdright + A [I]
} 对于（INT K = currIndex;的K - 1＆gt;一种[0]; --k）{ / *离开目前的指数总和* / sumdleft = sumdleft + A [I]
} 如果（sumdright == || sumdleft（sumdright == 0安培;＆安培; sumdleft == A [i]））{ / *将结果* /
RES = I;
}
} 返回水库;
}
}
您的解决方案可能是某些输入正确的，但效率不高，因为它可以。在您的解决方案，您从头开始一遍遍重新添加左，右总数，导致为O（n ^ 2）解决方案。
的最佳解决方案是左边和为零和右总和初始化为整个阵列的总和。然后，通过每个元件以便步骤：如果左和等于右总和，然后返回当前索引作为结果。否则，当前元素添加到左和，从右侧总和减去它，并移动到下一个元素。这是一个O（n）的解决方案：
公共类解决方案
{
///＆LT;总结＆gt;
///返回找到了一个数组的第一个平衡
///＆LT; /总结＆gt;
///＆LT; PARAM NAME =A＆gt;在问题＆LT数组; /参数＆GT;
///＆LT;返回＆gt;在阵列的平衡，如果它存在，否则-1 LT; /回报＆GT;
公众诠释溶液（INT [] A）
{
//默认功能结果
INT平衡= -1; //检查参数
若（a == NULL）
{
抛出新的ArgumentNullException（A）;
}
否则，如果（则为a.length == 0）
{
抛出新的ArgumentException（A不能有0个元素，A）;
}
其他
{
//策略：考虑输入阵列提供两个独立的子阵列，一到
//左边的元件被考虑，其它的权利。我们一步
//通过阵列依次直到子阵列的总和相等。 //获取初始左右的款项
长sumLeft = 0;
长sumRight = 0;
的for（int i = 0; I＆LT;则为a.length;我++）
{
sumRight + = A [I]
} //遍历数组，寻找第一个均衡
的for（int i = 0; I＆LT;则为a.length;我++）
{
VAR tempRight = sumRight - A [I];
如果（sumLeft == tempRight）
{
//我们已经发现在第i个元素的溶液
平衡= I;
打破;
}
其他
{
// prepare明年对比
sumLeft + = A [I]
sumRight = tempRight;
}
}
} //返回结果
回到均衡;
}
}
希望这有助于...
I am doing the following Codility Test to hone my skills, or lack of them.
This is a demo task. You can read about this task and its solutions in this blog post.
A zero-indexed array A consisting of N integers is given. An equilibrium index of this array is any integer P such that 0 ≤ P < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e.
A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].
Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N−1.
For example, consider the following array A consisting of N = 7 elements:
A[0] = -7 A[1] = 1 A[2] = 5
A[3] = 2 A[4] = -4 A[5] = 3
A[6] = 0
P = 3 is an equilibrium index of this array, because:
•A[0] + A[1] + A[2] = A[4] + A[5] + A[6]
P = 6 is also an equilibrium index, because:
•A[0] + A[1] + A[2] + A[3] + A[4] + A[5] = 0
and there are no elements with indices greater than 6.
P = 7 is not an equilibrium index, because it does not fulfill the condition 0 ≤ P < N.
..........................................................................................
My code is as follows. I get 18 out of 100 but my code passes the sample array and a simple array, as well as a few other tests. However the code fails because it fails a few complex arrays and does not scale well. Can anyone give me any pointers, whether that be using collections or improving my code as is. If my code is just rubbish I can take that the put downs.
class Solution {
public int solution(int[] A) {
int res = -1;
for(int i=0; i < A.length; i++) {
/* gets the current index of the array */
int currIndex = i;
long sumdleft = 0;
long sumdright = 0;
for(int j = currIndex ; j + 1 < A.length; ++j) {
/* sums right of the current index */
sumdright = sumdright + A[i];
}
for(int k = currIndex ; k - 1 > A[0]; --k) {
/* sums left of the current index */
sumdleft = sumdleft + A[i];
}
if (sumdright == sumdleft || (sumdright == 0 && sumdleft == A[i]) ) {
/* sets the result */
res = i;
}
}
return res;
}
}
Your solution may be correct on some inputs, but it is not as efficient as it could be. In your solution, you re-add the left and right totals from scratch over and over again, leading to an O(n ^ 2) solution.
The optimal solution is to initialize your left sum to zero and the right sum to the sum of the entire array. Then, step through each element in order: If the left sum equals the right sum, then return the current index as the result. Otherwise, add the current element to the left sum, subtract it from the right sum, and move to the next element. This is an O(n) solution:
public class Solution
{
/// <summary>
/// Returns the first equilibrium found of an array
/// </summary>
/// <param name="A">The array in question</param>
/// <returns>The equilibrium of the array, if it exists, otherwise -1</returns>
public int solution(int[] A)
{
// Default function result
int equilibrium = -1;
// Check arguments
if (A == null)
{
throw new ArgumentNullException("A");
}
else if (A.Length == 0)
{
throw new ArgumentException("A cannot have 0 elements", "A");
}
else
{
// Strategy: Consider the input array two separate sub-arrays, one to the
// left of the element being considered, the other to the right. We step
// through the array sequentially until the sums of the sub-arrays are equal.
// Get initial left and right sums
long sumLeft = 0;
long sumRight = 0;
for (int i = 0; i < A.Length; i++)
{
sumRight += A[i];
}
// Traverse the array, looking for the first equilibrium
for (int i = 0; i < A.Length; i++)
{
var tempRight = sumRight - A[i];
if (sumLeft == tempRight)
{
// We have found a solution at the i-th element
equilibrium = i;
break;
}
else
{
// Prepare for next comparison
sumLeft += A[i];
sumRight = tempRight;
}
}
}
// Return the result
return equilibrium;
}
}
Hope this helps...
这篇关于Codility平衡指数样本测试 - 我的刺吧的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
