Бинарные деревья — решение алгоритмических задач, часть 1

Речь идет об ArrayList, в основе которого и лежит массив.

Вставка элементов осуществляет за O(1) -(см. https://www.baeldung.com/java-collections-complexity - пруф не из спеки, но да простите меня:)). В худшем сценарии, да, вы правы вставка будет за O(n) - когда мы превысим capacity и нужно будет создавать новый массив и копировать все элементы. Для очень глубоких деревьев пару перестроек, все-таки случится, спорить не буду.

Удаление элементов из ArrayList, действительно, осуществляется за О(n). Но когда речь идет об удалении последнего элемента, то это займет O(1). Для удаления элемента используется метод fastRemove. Смотрим реализацию:

private void fastRemove(Object[] es, int i) {   
  modCount++;    
  final int newSize;   
  if ((newSize = size - 1) > i)        
    System.arraycopy(es, i + 1, es, i, newSize - i);    
  es[size = newSize] = null;}

При удалении последнего элемента нам не приходится создавать копию массива и сдвигать все элементы слева от него (потому что их нет), т.е. мы не попадаем в условие:

if ((newSize = size - 1) > i) {
  System.arraycopy(es, i + 1, es, i, newSize - i);
}

Все что происходит - обнуление последнего элемента и изменение размера массива.

Нахождение сильно преобладающего элемента последовательности >n/2 (алгоритм большинства голосов Бойера-Мура)

Спасибо:) над видео подумаю🙂

Нахождение сильно преобладающего элемента последовательности >n/2 (алгоритм большинства голосов Бойера-Мура)

Скорректировала:) надеюсь, теперь не будет путаницы

Ну, и, кстати в статье уже был пример, похожий на ваш, где я написала, что в таком случае нет преобладающего элемента.

Нахождение сильно преобладающего элемента последовательности >n/2 (алгоритм большинства голосов Бойера-Мура)

Нет, задача алгоритма (и, собственно, условие самой задачи на leetcode) найти число, которое встречается больше, чем n/2 раз, где n - длина входного массива.

Нахождение сильно преобладающего элемента последовательности >n/2 (алгоритм большинства голосов Бойера-Мура)

Согласна, скорректировала.

Нахождение сильно преобладающего элемента последовательности >n/2 (алгоритм большинства голосов Бойера-Мура)

В ссылке, действительно, была ошибка. Скорректировала.

Использование очередей (Queue/Deque) для решения алгоритмических задач на Java

Ответила ниже, но продублирую - Deque использовала потому, что Stack является устаревшим по спеке.

Использование очередей (Queue/Deque) для решения алгоритмических задач на Java

Перечитала, действительно, неполно было описано отличие. Добавила, спасибо:)

Использование очередей (Queue/Deque) для решения алгоритмических задач на Java

Спасибо:)

Deque использовала потому, что Stack является устаревшим по спеке.

Использование алгоритма бинарного поиска для нахождения квадратного корня числа на Java

А как вы определили 46340 на этапе, когда мы записываем значение right, без использования встроенных функций?

Использование алгоритма бинарного поиска для нахождения квадратного корня числа на Java

ну, можете прогнать кейс с х = 2^31-1:), mid*mid вылетит за пределы int:)

Использование алгоритма бинарного поиска для нахождения квадратного корня числа на Java

По условию задачи заданное число может быть в пределах отрезка от 0 до 2 в 31 степени - 1, поэтому mid выйдет за пределы при использовании умножения.

Использование алгоритма бинарного поиска для нахождения квадратного корня числа на Java

Спасибо за фидбек.

Согласна, что этот момент стоило бы расписать подробнее. Возьму на заметку для следующих статей.

Использование алгоритма бинарного поиска для нахождения квадратного корня числа на Java

Если вы сделаете left = 0, то словите ArithmeticException для х от 0 до 3 включительно

Использование алгоритма бинарного поиска для нахождения квадратного корня числа на Java

зачем определять 4 таких случая, загрязняя код, если все, кроме того, что обозначено с 0, и так отсеется на первом шаге цикла. Мы ничего не выиграем по скорости, а лишь только накрутим код.

Использование алгоритма бинарного поиска для нахождения квадратного корня числа на Java

Нельзя, потому что если х = 1, в ответе вы получите 0, что неверно.

Использование алгоритма бинарного поиска для нахождения квадратного корня числа на Java

Массива тут как таковой неочевиден, но фактически он есть. Ведь числа, которыми мы огибаем границы, как раз выстраиваются в упорядоченный массив (от 1 до Х)

С остальными замечаниями согласна, поправила/добавила:)

Рекурсия в Java с примером решения задачи с LeetCode

на мой взгляд, рекурсия гораздо понятнее, если в ней разобраться

Но тут, кому что нравится)

Рекурсия в Java с примером решения задачи с LeetCode

Про непрямую и косвенную рекурсию не было плана рассказывать в этой статье:)

По поводу головной и хвостовой - обсуждали в комментарии выше: оба примера, действительно являются головной рекурсией, в статье скорректировала.

Рекурсия в Java с примером решения задачи с LeetCode

Да, спасибо. В обоих случаях, действительно, используется головная рекурсия, поправила

Насчет использования цикла: в случае с факториалом, согласна, но здесь пример просто для базового понимания работы рекурсии приведен.

А вот в случае решения задачи с ListNode - мне кажется, код без рекурсии, будет довольно громоздким и сложным.