Я тоже читал это решение

Надо просто хранить на "концах" подряд идущих значений длину

а я крутил-вертел, а до этого не додумался. в итоге, так и не сдал все тесты 😄

Ну сортировкой то сделали?

class Solution { private: template <class I> int check(unordered_set<long long> s, I begin, I end) { int result = 0; unordered_set<long long> visited; for (auto it = begin; it != end; ++it) { int n = *it; if (visited.find(n) == visited.end()) { long long k = 1LL * n + 1; int curr = 1; while (visited.find(k) == visited.end() && s.find(k) != s.end()) { visited.insert(k); curr++; k++; } result = max(result, curr); } } return result; } public: int longestConsecutive(vector<int>& nums) { unordered_set<long long> s(nums.begin(), nums.end()); return max(max( check(s, nums.begin(), min_element(nums.begin(), nums.end())), check(s, min_element(nums.begin(), nums.end()), nums.end()) ),max( check(s, nums.rbegin(), min_element(nums.rbegin(), nums.rend())), check(s, min_element(nums.rbegin(), nums.rend()), nums.rend()) )); } }; Не, я хотел так -> бегать по цепочкам последовательных элементов, попутно помечая их как посещенные. И делать это несколько раз, до первого минимального элемента слева и справа, потом до последнего минимального элемента аналогично. Но есть хитрые тесты, которые всё ломают.

Пхаха, у меня тоже были какие-то гениальные идеи с указателями и цепочками

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

Я на самом деле сейчас анализирую свой ход мысли и понимаю, что попался на крючок первого теста. Где у тебя последовательности возрастают, и сразу подталкивают к такому решению. Потом ты ловишь упавший тест, и вот тут начинается дорога в один конец.

Надо просто хранить на "концах" подряд идущих значений длину

public class Solution { public int LongestConsecutive(int[] nums) { if (nums.Length <= 1) return nums.Length; HashSet<int> hset = new HashSet<int>(); Dictionary<int,int> ranges = new Dictionary<int,int>(); foreach (int n in nums) { if (hset.Contains(n)) continue; hset.Add(n); if (ranges.ContainsKey(n-1) && ranges.ContainsKey(n+1)) { int diffLeft = ranges[n-1]; int diffRight = ranges[n+1]; int len = (n+1)+diffRight-((n-1)+diffLeft); ranges[(n-1)+diffLeft] = len; ranges[(n+1)+diffRight] = -len; if (ranges[n-1] < 0) ranges.Remove(n-1); if (ranges[n+1] > 0) ranges.Remove(n+1); } else if (ranges.ContainsKey(n-1)) { int diff = ranges[n-1]; ranges[(n-1)+diff] += 1; if (ranges[n-1] < 0) ranges.Remove(n-1); ranges.Add(n, -ranges[(n-1)+diff]); } else if (ranges.ContainsKey(n+1)) { int diff = ranges[n+1]; ranges[(n+1)+diff] -= 1; if (ranges[n+1] > 0) ranges.Remove(n+1); ranges.Add(n, -ranges[(n+1)+diff]); } else { ranges.Add(n, 0); } } return ranges.Values.Max()+1; } }

Ой, страшно

Мне тоже. Поэтому упростить хочу

Не, страшно т.к. не Питон. Зря мне Питон показали

Зато на питоне быстро можно написать

Да черт, устал уже лениться, хочется плато текста как плюсах, или листы как в Ждаве

окстись, лениться это нормально, не надо тебе в эту кроличью нору 🙂

Ну вот на собесе и буду писать на... А, я же джун 😅 Меня не спрашивают)

шо? вроде ж можно выбрать любой язык из списка разрешённых, нет?

Не на собес для фронта)

На фронт только js?

public class Solution { public int LongestConsecutive(int[] nums) { if (nums.Length <= 1) return nums.Length; HashSet<int> hset = new HashSet<int>(); Dictionary<int,int> ranges = new Dictionary<int,int>(); foreach (int n in nums) { if (hset.Contains(n)) continue; hset.Add(n); if (ranges.ContainsKey(n-1) && ranges.ContainsKey(n+1)) { int diffLeft = ranges[n-1]; int diffRight = ranges[n+1]; int len = (n+1)+diffRight-((n-1)+diffLeft); ranges[(n-1)+diffLeft] = len; ranges[(n+1)+diffRight] = -len; if (ranges[n-1] < 0) ranges.Remove(n-1); if (ranges[n+1] > 0) ranges.Remove(n+1); } else if (ranges.ContainsKey(n-1)) { int diff = ranges[n-1]; ranges[(n-1)+diff] += 1; if (ranges[n-1] < 0) ranges.Remove(n-1); ranges.Add(n, -ranges[(n-1)+diff]); } else if (ranges.ContainsKey(n+1)) { int diff = ranges[n+1]; ranges[(n+1)+diff] -= 1; if (ranges[n+1] > 0) ranges.Remove(n+1); ranges.Add(n, -ranges[(n+1)+diff]); } else { ranges.Add(n, 0); } } return ranges.Values.Max()+1; } }

https://leetcode.com/problems/longest-consecutive-sequence/discuss/918938/C-O(n)-solution-using-HashSet-and-Dictionary

Так, не спойлерите 🤣🤣🤣

По времени, кстати, вообще никак не отразилось

У меня есть товарищ, который в Гугл устроился. Нарешал 500+ задач, ему коллеги говорят, мол, совсем уже что ли, мы максимум 100 решили. Потому что кто на что учился как говорится, и у кого какой бекграунд в алгоритмах с вуза.

Это кто?

Да, вы говорили. Еще помню, что это говорили ему всякие олимпиадники

Поцан, который в БиВикли первее всех все решил и сказал что легко

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

🔥 по рейтингу его нашёл?

Я наоборот, ищу самое лучшее решение, поэтому могу убить полдня на решение

Это правильно. Если только времени много.

В принципе, я скучаю по временам когда занимался с Федей. Он мне предложил с ним пописать книгу по числам, вот думаю насколько мне хочется опять выпасть из жизни на год 😆

Главное чтобы бабки капали. А там можно чем угодно заниматься

public class Solution { public int LongestConsecutive(int[] nums) { if (nums.Length <= 1) return nums.Length; HashSet<int> hset = new HashSet<int>(); Dictionary<int,int> ranges = new Dictionary<int,int>(); foreach (int n in nums) { if (hset.Contains(n)) continue; hset.Add(n); if (ranges.ContainsKey(n-1) && ranges.ContainsKey(n+1)) { int diffLeft = ranges[n-1]; int diffRight = ranges[n+1]; int len = (n+1)+diffRight-((n-1)+diffLeft); ranges[(n-1)+diffLeft] = len; ranges[(n+1)+diffRight] = -len; if (ranges[n-1] < 0) ranges.Remove(n-1); if (ranges[n+1] > 0) ranges.Remove(n+1); } else if (ranges.ContainsKey(n-1)) { int diff = ranges[n-1]; ranges[(n-1)+diff] += 1; if (ranges[n-1] < 0) ranges.Remove(n-1); ranges.Add(n, -ranges[(n-1)+diff]); } else if (ranges.ContainsKey(n+1)) { int diff = ranges[n+1]; ranges[(n+1)+diff] -= 1; if (ranges[n+1] > 0) ranges.Remove(n+1); ranges.Add(n, -ranges[(n+1)+diff]); } else { ranges.Add(n, 0); } } return ranges.Values.Max()+1; } }

class Solution: def longestConsecutive(self, nums: List[int]) -> int: m = defaultdict(int) for n in set(nums): l, r = m[n-1], m[n+1] m[n] = m[n-l] = m[n+r] = l + r + 1 return max([m[n] for n in nums], default=0)

class Solution: def longestConsecutive(self, nums: List[int]) -> int: m = defaultdict(int) for n in set(nums): l, r = m[n-1], m[n+1] m[n] = m[n-l] = m[n+r] = l + r + 1 return max([m[n] for n in nums], default=0)

class Solution: def longestConsecutive(self, nums: List[int]) -> int: m = defaultdict(int) for n in set(nums): l, r = m[n-1], m[n+1] m[n] = m[n-l] = m[n+r] = l + r + 1 return max([m[n] for n in nums], default=0)

public class Solution { public int LongestConsecutive(int[] nums) { if (nums.Length <= 1) return nums.Length; HashSet<int> hset = new HashSet<int>(); Dictionary<int,int> ranges = new Dictionary<int,int>(); foreach (int n in nums) { if (hset.Contains(n)) continue; hset.Add(n); if (ranges.ContainsKey(n-1) && ranges.ContainsKey(n+1)) { int diffLeft = ranges[n-1]; int diffRight = ranges[n+1]; int len = (n+1)+diffRight-((n-1)+diffLeft); ranges[(n-1)+diffLeft] = len; ranges[(n+1)+diffRight] = -len; if (ranges[n-1] < 0) ranges.Remove(n-1); if (ranges[n+1] > 0) ranges.Remove(n+1); } else if (ranges.ContainsKey(n-1)) { int diff = ranges[n-1]; ranges[(n-1)+diff] += 1; if (ranges[n-1] < 0) ranges.Remove(n-1); ranges.Add(n, -ranges[(n-1)+diff]); } else if (ranges.ContainsKey(n+1)) { int diff = ranges[n+1]; ranges[(n+1)+diff] -= 1; if (ranges[n+1] > 0) ranges.Remove(n+1); ranges.Add(n, -ranges[(n+1)+diff]); } else { ranges.Add(n, 0); } } return ranges.Values.Max()+1; } }

Happy Monday! 👋 Задача этой недели на динамическое программирование. По-моему, является классическим примером введения в такой тип задач. https://vitkarpov.me/posts/unique-paths/

О, знакомый поцан на картинке Честно, уже не помню что там за решение, но вроде формула 🤣

Я так и думал, что ты через комбинаторику решал бы 😃

Да, я даже вроде рассказывал. Вот Unique Paths 2 и Unique Paths 3 придется ДПшкой

там где стены есть? точно, точно.

Happy Monday! 👋 Продолжаем решать задачи, на этой неделе — «найти медиану в потоке чисел». Любопытная задача на кучи с очень компактным, но необычным решением. https://vitkarpov.me/posts/find-median-from-data-stream/

КСТАТИ, еще можно решить эту задачу не 2 heap ами, а 1им BST )

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