Извините, если я написал слишком много.Я старался быть очень подробным, чтобы найти собственный ответ при описании проблемы (решение и как я туда попал), и все же, если я этого не сделал, не оставлял сомнений читателю.Я не хочу, чтобы проблема была решена кем-то другим, просто получите несколько советов и где я должен искать, чтобы улучшить свое решение, если это возможно.Я открыт, чтобы отказаться от подхода, если он неправильный, но мне также нравится, чтобы этот подход прошел 100%, если это возможно, и если он имеет смысл и подходит в отношениях качества и усилий.Если моя идея плохая, я не против того, чтобы мне сказали, и следуйте другой, но опять же, пожалуйста, не показывайте мне код или «правильный ответ», я могу сам прогуглить или найти его здесь в SO.
Упражнение выглядит так:
Дан непустой массив A, состоящий из N целых чисел.Массив A представляет числа на ленте.
Любое целое число P, такое, что 0
A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].
Разница между двумя частями - это значение:
|(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|
Другими словами, это абсолютная разница между суммой первой части и суммойвторая часть.
Например, рассмотрим массив A такой, что:
A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3
Мы можем разделить этолента в четырех местах:
P = 1, разница = | 3 - 10 |= 7
P = 2, разница = | 4 - 9 |= 5
P = 3, разница = | 6 - 7 |= 1
P = 4, разница = | 10 - 3 |= 7
Напишите функцию:
class Solution { public int solution(int[] A); }
, которая при непустом массиве A из N целых чисел возвращает минимальную разницу, которая может быть достигнута.
Например, с учетом:
A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3
функция должна возвращать 1, как описано выше.
Напишите эффективный алгоритм для следующих предположений:
N - целое число в диапазоне [2..100,000];каждый элемент массива A является целым числом в диапазоне [−1,000..1,000].
Как указано в заголовке, мое решение не так уж велико (производительность 66%; 85% в правильности; 76% как общий балл).
Этот подход я использовал вчера:
накапливается с левой и правой стороны полученного массива и проверяет, какая сторона будет меньше после добавления следующей справа отлевая сторона или ближайшая слева от правой стороны массива.
Графически идея заключалась в том, чтобы сделать два поезда: сначала локомотивы (соответственно, голову и хвост массива) каждой стороны, а затем добавить к каждому локомотиву вагоны поезда (если они есть, и если они соответствуют)и сделать оба поезда крушения .Я вроде как «добавлял вагоны в поезд, только если другой поезд был больше, чем тот, который я добавил в вагон».
Код, который я написал, работал не очень хорошо, потому что мне нужно было найти наименьшее различие , которое я мог бы между двумя разделами массива.
но я получил несколько ошибок: с отрицательными числами, смешанными с неотрицательными, массивами из двух элементов и т. Д., И еще худшими результатами (например, 65% общего балла).
Идея аналогична той, которой я придерживался сегодня:
Накапливайтесь с левой и правой стороны и проверяйте разницу между левой и правой поездами был меньше после добавления вагона слева или справа.В этом подходе я сконцентрировался на «разнице между двумя поездами , а не в добавлении вагона, если другой был больше и нашел равновесие».
В любом случае, яполучил ошибки в:
- small_random: random small, length = 100: WRONG ANSWER, получил 269 ожидаемых 39
- large_ones: большая последовательность, числа от -1 до 1, длина = ~ 100 000: НЕПРАВИЛЬНЫЙ ОТВЕТ, получено 228 ожидаемых 0;НЕПРАВИЛЬНЫЙ ОТВЕТ, получено 147 ожидаемых 1. (возможное переполнение?)
- large_random random large, длина = ~ 100 000: НЕПРАВИЛЬНЫЙ ОТВЕТ, получено 202635 ожидаемых 1;НЕПРАВИЛЬНЫЙ ОТВЕТ, получил 34394, ожидал 2
Все остальные тесты были в порядке.Это код, который я написал:
using System;
class Solution {
public int solution(int[] A)
{
int N = A.Length, P;
if (N == 0)
{
P = 0;
}
else
{
P = findTapeEquilibrium(A, N);
}
return P;
}
private static int findTapeEquilibrium(int[] A, int N)
{
int I = 0, J = N - 1;
if( N > 0 )
{
int leftP = A[I++], rightP = A[J--];
bool AIsPair = N - 1 % 2 == 0;
while((!AIsPair && J - I >= 0) || (AIsPair && J - I >= 1))
{
if (Math.Abs((leftP+A[I])-rightP) <= Math.Abs(leftP-(rightP+A[J])))
{
leftP += A[I++];
}
else
{
rightP += A[J--];
}
}
return Math.Abs(leftP - rightP);
}
return 0;
}
}