Видео

var findWinners = function (arr) { const losers = {}; const res = [[], []]; for (let i = 0; i < arr.length; i++) { if (!(arr[i][0] in losers)) { losers[arr[i][0]] = 0; } losers[arr[i][1]] = losers[arr[i][1]] ? losers[arr[i][1]] + 1 : 1; } for (let key in losers) { if (losers[key] === 1) { res[1].push(key); } if (losers[key] === 0) { res[0].push(key); } } return res; };

function findWinners(arr) { const tempArr = Array(10 ** 5 + 1).fill(-1, 0, 10 ** 5 + 1); const res = [[], []]; for (let i = 0; i < arr.length; i++) { if (tempArr[arr[i][0]] === -1) { tempArr[arr[i][0]] = 0; } if (tempArr[arr[i][1]] === -1) { tempArr[arr[i][1]] = 1; } else { tempArr[arr[i][1]] = tempArr[arr[i][1]] + 1; } } for (let i = 0; i < tempArr.length; i++) { if (tempArr[i] === 0) { res[0].push(i); } if (tempArr[i] === 1) { res[1].push(i); } } return res; }

function missingNumber(arr) { let set = new Set(arr); for (let i = 0; i <= arr.length; i++) { if (!set.has(i)) { return i; } } }

function minSubArrayLen(arr, target) { let sum = 0; let qwt = Infinity; for (let i = 0; i < arr.length; i++) { stop: for (let j = i; j < arr.length; j++) { sum = sum + arr[j]; if (sum >= target) { console.log(i, qwt); qwt = qwt < j - i + 1 ? qwt : j - i + 1; break stop; } } sum = 0; } return qwt === Infinity ? 0 : qwt; }

function findSubstring(str) { let max = 0; let left = 0; let right = 0; const set = new Set(); for (let i = 0; i < str.length; i++) { if (set.has(str[right])) { set.delete(str[left]); left = left + 1; } else { set.add(str[right]); right = right + 1; max = Math.max(max, right - left + 1); } } return max; }

я цикл while забыл по сету, без него нельзя решить?

....ღღღღღღ......................ღღღღღღ ..ღღღღღღღღღ............ღღღღღღღღღ ღღღღღღღღღღღღ....ღღღღღღღღღღ ღღღღღღღღღღღღღ.ღღღღღღღღღღ ..ღღღღღღღღღღღღღღღღღღღღღღ ....ღღღღღღღღღღღღღღღღღღღღ ........ღღღღღღღღღღღღღღღღღ ..............ღღღღღღღღღღღღღ ....................ღღღღღღღღღ ........................ღღღღღღ ...........................ღღღღ ............................ღღღ .............................ღღ ..............................ღ

Скоро будет новый сезон, пока распространяйте, чтобы было побольше подписчиков)

Функция min в коде вызывается для двух аргументов и работает за константное время O(1), а не O(n). Она не влияет на общую сложность алгоритма, потому что каждый элемент массива рассматривается в циклах не более двух раз (один раз добавляется в сумму, один раз вычитается), и таким образом общая сложность алгоритма остаётся линейной, O(n).

@@leonid_murzinov точно спасибо. я перепутал с min( my_list)

Сложность O(n) по времени Здесь главная идея, что нет вложенного цикла благодаря проверки на то является ли элемент началом последовательности или нет, грубо работа с каждым элементом 1 раз. То есть у нас есть цикл for number in set_numbers: В нем если элемент не является началом последовательности, то мы его пропускаем через проверку - if (number - 1) not in set_numbers: Если является началом последовательности, то берем этот элемент, а также все те элементы, которые в этой последовательности. То есть если у нас [1,2,3,4,5] То мы берем 1, дальше мы уходим в while (number + length) in set_numbers: Там мы проходимся по всей последовательности, получаем наш максимум, а уже 2,3,4,5 мы пропускаем при проверке на то, что это не начало последовательности.

000000000000000000000000000000000000000000000000000000 000000000000001111114000000000000011111140000000000000 000000000011111111111111000000111111111111110000000000 000000005111111111111111110051111111111111111100000000 000000011111111111111111111111111111111111111110000000 000000111111111110000001111111140000051111111111000000 000005111111114000000000051110000000000011111111100000 000001111111140000000000000400000000000001111111100000 000001111111000000000000000000000000000000111111110000 000001111111000000000000000000000000000000111111110000 000001111111000000000000000000000000000000111111150000 000001111111000000000000000000000000000000111111100000 000005111111100000000000000000000000000001111111100000 000000111111110000000000000000000000000011111111000000 000000011111111100000000000000000000005111111110000000 000000001111111111500000000000000004111111111100000000 000000000011111111111100000000005111111111114000000000 000000000004111111111111000000511111111111500000000000 000000000000004111111111140001111111111500000000000000 000000000000000001111111110011111111100000000000000000 000000000000000000051111111111111110000000000000000000 000000000000000000000111111111111000000000000000000000 000000000000000000000041111111150000000000000000000000 000000000000000000000000111111500000000000000000000000 000000000000000000000000011111000000000000000000000000 000000000000000000000000051110000000000000000000000000 000000000000000000000000001100000000000000000000000000 000000000000000000000000000400000000000000000000000000 000000000000000000000000000000000000000000000000000000

Здесь константа по памяти, где O(n)?

В контексте пространственной сложности, "O(1)" дополнительное пространство означает, что объем памяти, необходимый для работы алгоритма, не зависит от размера входных данных, то есть от размера массива nums. В данном случае алгоритм использует исходный массив nums для отслеживания посещенных чисел, меняя знаки элементов массива. Он не требует дополнительного массива или структуры данных, которые были бы пропорциональны размеру входного массива. Вместо этого, алгоритм использует фиксированное количество дополнительной памяти для хранения переменных цикла и временных значений, таких как res и n. Эти переменные не увеличиваются в размере в зависимости от размера входных данных.

​@@leonid_murzinovв каких-нибудь плюсах массив будет приходить по константной ссылке, так что все равно придётся копировать его, что займет O(n), поэтому проще уже по старинке мапу создавать и все код поймут, кто смотреть будет

​@@leonid_murzinovну и в самом питоне не комильфо создавать сайд эффекты на ровном месте, я вот хочу просто получить дубликаты из массива, а мне его меняют без спроса

А что советуете учить?

@@leonid_murzinov сам даже не знаю. Думаю над этим. Если так подумать, то все "бело-воротничковые" профессии под угрозой..

@@mndtr0 а мы вот с мужиками не согласны, завод это конечно стабильно, но мы выбираем решать алгоритмы

у вас кто-то спрашивал совета?

@@ДанилДмитриев-я5м искренне хочу помочь людям в профориентации

Какую бы вы хотели, чтобы решили посложнее?

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

@@logicalelton8711 если вы знаете, можете дать название задачи на leetcode, мы можем разобрать в следующих выпусках

вы работаете уже?

Так же, как и с вторым циклом, существуют более простые методы реализации с точки зрения Python. Однако наша задача - продемонстрировать алгоритм решения и написать код, который будет максимально читабельным и наглядно описывающим алгоритм, даже для тех, кто не знаком с языком

Миражи - hehehe, ask eternity music.yandex.ru/album/29511815/track/119269334? Swing Lynn Harmless ruclips.net/video/D7DVSZ_poHk/видео.html

Напоминаю, что все друзья с Бусти имеют доступ к плейлистам)

Строка 21: Да, в строке 21 мы добавляем весь оставшийся список (list1 или list2) к нашему сформированному списку. Поскольку один из списков уже полностью пройден, мы просто прикрепляем остаток другого списка к текущему концу объединенного списка (tail). Поскольку список уже упорядочен, нет необходимости проходить по каждому его узлу - мы просто устанавливаем ссылку. Строка 13: Здесь мы выбираем меньший узел из двух списков (либо из list1, либо из list2) и добавляем его к объединенному списку. Важный момент заключается в том, что после добавления узла, мы продвигаемся дальше по списку, из которого был взят этот узел (перемещаем list1 или list2 на следующий узел). Таким образом, мы не добавляем весь остаток списка сразу, а лишь один узел из него. После этого, мы перемещаем tail на tail.next, чтобы в следующей итерации добавлять узлы уже к следующему элементу объединенного списка. Таким образом в результате, мы получается добавим как бы одну ноду. Таким образом, в обоих случаях происходит добавление узлов, но в строчке 13 мы добавляем один узел и продвигаемся дальше по списку, из которого этот узел был взят, тогда как в строчке 21 мы добавляем оставшуюся часть списка целиком.

tail.next = list2.val нельзя использовать потому что tail.next должен ссылаться на узел (объект ListNode), а не на отдельное значение (например, число). В связанных списках каждый узел (ListNode) содержит два элемента: val (значение узла) и next (ссылку на следующий узел в списке). Когда вы присваиваете tail.next = list2, вы устанавливаете ссылку на следующий узел. Если же вы попытаетесь сделать tail.next = list2.val, то это попытка установить ссылку на простое число или значение, что нарушает структуру связанного списка.

Да, конечно можно, я поэтому и говорю, что мы просто для наглядности используем там словарь, но в целом есть разные варианты как проверить

Чтобы веселее было задачи решать

В чем именно?