LeetCode经典题目

Binary Search

Given an sorted integer array - nums, and an integer - target.

• Find the any/first/last position of target in nums
• Return -1 if target does not exist.
• Time Complexity: O(logn)

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

Binary tree and divide and conquer

• traverse a binary tree:
  • preorder: root, left, right
  • inorder: left, root, right
  • postorder: left, right, root
• divide and conquer:
  • divide the problem into subproblems
  • solve the subproblems
  • combine the solutions of the subproblems

BFS

• Breadth-First Search
• Use a queue to store the nodes to be visited
• Visit all the nodes at the current level before moving on to the next level
• Time Complexity: O(n)

def bfs(root):
    queue = [root]
    while queue:
        node = queue.pop(0)
        # process the node
        # add the children of the node to the queue

DFS

• Depth-First Search
• Use a stack to store the nodes to be visited
• Visit the deepest nodes first
• Time Complexity: O(n)

def dfs(root):
    stack = [root]
    while stack:
        node = stack.pop()
        # process the node
        # add the children of the node to the stack

数组和链表

1. Three Sum（求三数之和）
2. Majority Element（求众数）
3. Missing Positive（求缺失的第一个正数）
4. Linked List Cycle I（环形链表
5. Merge k Sorted Lists（合并 k 个排序链表）

栈、队列和递归

1. Valid Parentheses（有效的括号）
2. Longest Valid Parentheses（最长有效的括号）
3. Evaluate Reverse Polish Notatio（逆波兰表达式求值）
4. Design Circular Deque（设计一个双端队列）
5. Sliding Window Maximum（滑动窗口最大值）
6. Climbing Stairs（爬楼梯）

排序和二分查找

1. Sqrt(x) （x 的平方根）

散列表和字符串

1. Reverse String （反转字符串）
2. Reverse Words in a String（翻转字符串里的单词）
3. String to Integer (atoi)（字符串转换整数 (atoi)）

二叉树和堆

1. Invert Binary Tree（翻转二叉树）
2. Maximum Depth of Binary Tree（二叉树的最大深度）
3. Validate Binary Search Tree（验证二叉查找树）
4. Path Sum（路径总和）

图

1. Number of Islands（岛屿的个数）
2. Valid Sudoku（有效的数独）

贪心、分治、回溯和动态规划

1. Regular Expression Matching（正则表达式匹配）
2. Minimum Path Sum（最小路径和）
3. Coin Change （零钱兑换）
4. Best Time to Buy and Sell Stock（买卖股票的最佳时机）
5. Maximum Product Subarray（乘积最大子序列）
6. Triangle（三角形最小路径和）