Comments 24
HashMap занимает гораздо больше памяти, чем количество хранящихся в нём элементов.
Согласен ,но обычно затраты памяти берут условно при оценке алгоритма ,в данном случае оценка сводится к кол-ву элементов в хешмапе.
>>В обоих случаях сумма всех нулей = 2
Прикольное заявление)
обоих случаях сумма всех нулей = 2
Точно сумма нулей == 2 ? А не 0? )))
Вы что тут устроили пехотинцы?
Отличная статья, как раз хотел начать изучение алгоритмов!!! Начну с нее)
Если currentSum равен 0, то можно просто взять i+1, это заведомо больше текущего maxLen
Ну и вспомогательный массив не нужен, преобразовывать 0 к -1 можно в основном цикле, например currentSum += arr[i] || -1;
А можно привести пример хоть одной реальной практической проблемы, которая бы свелась к этой задаче и необходимости её вот так помпезно решать? /s
Пример ,боюсь ,что не приведу. А необходимость в том ,чтобы научиться проходить алгоритмические секции собеседований. Я хотел привести свою модель рассуждений при решении подобных задач. Не без косяков ,конечно))
как и образование в целом - это возможность выстроить мышление определенным образом. Например находясь в какой-то компании легко вычислить человека который имеет ВО и который закончил 9 классов, и нет, не потому что человек с 9-ю классами тупой, это абсурдное утверждение. Разница в том как люди мыслят, какие отправные точки для формирования логики и т.д.
Я пока не увлёкся решением задач highload писал код сильно иначе.
а есть ли смысл делать Max тут
maxLength = Math.max(maxLength, i + 1);
как я понимаю i+1 всегда будет максимальным значением.
Долго пытался понять формулировку: "суммы их кол-ва равны друг другу", суммы количества какие-то, почему было не написать: "количество нулей и единиц совпадает"?!
Эту формулировку можно даже сократить до "кол-во 0 и 1 равно", если уж на символах начали экономить.
Самой большой трудностью оказалось понять формулировку задачи. Поправьте как-нибудь
int[] arr = new int[] { 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1 };
Dictionary<int, int> hm = new Dictionary<int, int>();
int cSum = 0, max = 0;
for (int i = 0; i < arr.Length; i++)
{
cSum += arr[i] == 0 ? -1 : arr[i];
{
if (!hm.ContainsKey(cSum))
{
hm[cSum] = i;
if (cSum == 0) max = i + 1;
}
else if (max < i - hm[cSum]) max = i - hm[cSum];
}
}
Console.WriteLine(max);мой вариант на C#, убран второй массив изменено положение проверки на ноль и её код, изменён код выбора максимального значения.
отличный вариант! Заслуживает отдельного лайка)
int[] arr = new int[] { 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1 };
Console.WriteLine(code1(arr));
Console.WriteLine(code2(arr));
int code1(int[] arr)
{
Dictionary<int, int> hm = new Dictionary<int, int>();
int cSum = 0, max = 0;
for (int i = 0; i < arr.Length; i++)
{
cSum += arr[i] == 0 ? -1 : arr[i];
{
if (!hm.ContainsKey(cSum))
{
hm[cSum] = i;
if (cSum == 0) max = i + 1;
}
else if (max < i - hm[cSum]) max = i - hm[cSum];
}
}
return max;
}
int code2(int[] nums)
{
Dictionary<int, int> hashMap = new Dictionary<int, int>();
hashMap[0] = -1;
int maxLength = 0;
int count = 0;
for (int i = 0; i < nums.Length; i++)
{
count += (nums[i] == 1) ? 1 : -1;
if (hashMap.ContainsKey(count))
maxLength = Math.Max(maxLength, i - hashMap[count]);
else
hashMap[count] = i;
}
return maxLength;
}code2 это ответ на задание от ChatGPT
Не очень удачное объяснение. Почему надо искать текущую сумму в хешмапе-то? Вы так и не объяснили. После замены 0 на -1 вы сказали, что надо найти нибольший кусок с суммой ноль. Дальше надо было бы ввести понятие частичных сумм и указать, что сумма на отрезке есть разность двух таких сумм. И чтобы сумма отрезка была 0, у вас должны быть 2 одинаковые частичные суммы. И вот задача свелась к нахождению одинаковых чисел на наибольшем расстоянии друг от друга. Вот тут уже понятно, откуда взялся хешмап - вы просто запоминаете для каждого числа, где оно первый раз встретилось, и для каждого числа берете разницу между текущей позицией и первой как вариант ответа. И вот эта обработка 0 как особого случая тоже понятнее, если сначала ввести частичные суммы (их же n+1, и первая всегда 0).
И вообще, очень часто задачи, где фигурируют суммы на отрезках в массиве, решаются через частичные суммы. Так что их обязательно надо рассказать.
Решение задачи про поиск наибольшего подмассива из 0 и 1, где сумма их кол-ва равна друг другу