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

По leetcode шлифовать, я не рекомендую использовать только leetcode, но и другие веб-сайты, такие как GeeksForGeeks, HackerRank и т. д., чтобы получить больше информации по различным вопросам.

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

Возможно, вы слышали о многих паттернах программирования, таких как Blind75, Sean Prashad, Grokking на собеседовании по программированию и т. д., которые великолепны (я тоже их использую), но задают только эти вопросы, но гарантируют, что вы хорошо разбираетесь в кодировании. Эти вопросы охватывают все паттерны, которые важно, но только их выполнение не гарантирует, что вы сможете ответить на все аналогичные вопросы, связанные с ними.

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

В.) Учитывая root бинарного дерева и целое число targetSum, вернуть все пути от корня к листу, где сумма значений узлов в пути равнаtargetSum.

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

Допустим, вы знаете, что этот вопрос требует от вас использования DFS, но как вы собираетесь хранить отдельные значения всех узлов и суммировать их, чтобы найти, равны ли они targetSum.

Для полного новичка это может не пригодиться, если вы не практиковали много таких вопросов.

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

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

РЕШЕНИЕ:

def pathSum(root):
    if not root: return None
    stack = [(root,root.val,[root.val])]
    ans = []
    while stack:
        node,val,li = stack.pop()
        if not node.left and not node.right and val == targetSum:
            ans.append(li)
        if node.right:
            stack.append((node.right,val+node.right.val,li+[node.right.val]))
        if node.left:
            stack.append((node.left,val+node.left.val,li+[node.left.val]))
            
    return ans

Этот трюк с использованием кортежей в стеке поможет вам решить гораздо больше вопросов.

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

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

Небольшая мотивация

«Причина победы в игре в том, чтобы освободиться от нее». — Наваль Равикант

СЧАСТЛИВАЯ ГРИНДИНГ