Я обсуждал многие темы в своем блоге, но пришло время снова начать с самого начала. В этом блоге и в следующих нескольких мы обсудим, как решать общие вопросы соревновательного программирования, никаких причудливых структур данных или алгоритмов, но мыслить нестандартно и вместе придумывать достаточно хорошие решения.
Понимание того, как работает код, важнее, чем кодирование приложения. Понимание того, как работают ваши собственные мысли, еще важнее.
Воображаемое проблемное время:
Дан целочисленный массив
nums, вернуть массивanswerтакой, чтоanswer[i]равно произведению всех элементовnumsкромеnums[i].
Вы должны написать алгоритм, который работает за
O(n)времени и не использует операцию деления.
На первый взгляд выглядит просто, но копнув глубже, мы найдем много хороших концепций. Не знаю, верная это информация или нет, но leetcode говорит, что об этом спрашивали во время этих важных интервью (Да! Мы даже не можем догадаться, какие названия компаний здесь размыты, LOL!). 😅
Время решения
числа = [1, 2, 3, 4]
Здесь нам нужно найти произведение всех чисел, кроме самого себя, и вернуть результаты в виде массива. Легко!
- 2*3*4 = 24
- 1*3*4 = 12
- 1*2*4 = 8
- 1*2*3 = 6
Результат: [24, 12, 8, 6]
Алгоритм
Прокрутите числа и найдите произведение всех элементов слева и справа. Это может показаться простым, но важно знать, как мы пришли к этому самому решению среди всех возможностей.
Реализация и обсуждение
Жадный способ
Самым заманчивым способом решения такой задачи будет взять произведение всего массива и разделить его на элемент, для которого нам нужно значение. Например: если нам нужно значение для b, тогда: (a*b*c*d) / b = a*c*d, это именно то, что нам нужно для элемента b. , верно? Все, кроме b.
Этот кружок лопнет, когда нам нужно будет рассмотреть случай, когда b равно 0.
Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]
В приведенном выше случае наша логика обязательно даст результат: [0, 0, Infinity, 0, 0].
Путь новичка-ниндзя
Ниндзя всегда принимает во внимание крайние случаи. Один простой и глупый способ сделать это — взять произведение всех чисел в левой части и умножить на произведение всех чисел в правой части, получив произведение всех чисел, кроме самого себя: product([-1, 1] ) * продукт([-3,3]). Это решение будет работать во всех случаях, но впереди одна БОЛЬШАЯ проблема: продукт сам по себе является сложной операцией, и если ее выполнить, скажем, для 10 000 элементов в массиве, результатом будет O(n²) сложность, и вы провалите тест, даже будучи ниндзя.
Идеальный путь ниндзя
Одним из красивых способов умножения в таком случае является следующий приятный алгоритм: Произведение до n-го элемента равно произведению до (n-1)-го элемента * n-й элемент. Ранее нам приходилось умножать все элементы. массива, за исключением того, чтобы получить это значение, но теперь мы берем продукт до этого числа и просто умножаем себя. Выполнено и очищено за 1 операцию, тогда как требовалось n операций. Это позаботится о нашем продукте с левой стороны.
Небольшая модификация позаботится и о правой стороне. Мы начинаем с правого конца массива, в отличие от левого продукта, где нам нужно было начинать с левой стороны, что интуитивно понятно! Одна загвоздка в моей реализации — перестановка правых продуктов, чтобы привести их в тот же порядок, что и левый, помните, мы заполнили массив правых продуктов в обратном порядке.
Пример: [1,2,3,4,5,6,7,8]
Для 4:
Оставшийся продукт:(Уже рассчитанный продукт для [1 , 2])* 3 = 6
Правильный продукт:(Уже рассчитанный продукт для [6, 7, 8])* 5= 1680
Код
Заключение
Это совершенно новая область для обсуждения с вами, ребята, но независимо от того, сколько причудливых технологий мы касаемся или ролей, которые нам дороги, мы кодеры и кодируем решения проблем вокруг нас. Я хотел бы писать больше таких блогов, может быть, раз в неделю, если хотите, дайте мне знать.
Подключить
🏭 LinkedIn: https://www.linkedin.com/in/sameerkumar1612
🏠 Веб-сайт: https://hi-sameer.web.app
