DOCSEARCHbyAlgolia
Submit Docs

Yancey Leo Algorithm and LeetCode Solutions

website·Indexed 32 days ago

https://algorithm.yanceyleo.com

A collection of data structure guides and LeetCode problem solutions. Covers topics including stacks, binary search trees (BST), dynamic programming, monotonic stacks, and graph algorithms, providing problem statements and code implementations.

Tokens
143.4K
Snippets
471
Records
610
Agent score
51%

What's inside Yancey Leo Algorithm

  1. Resolve hash collisions using Open Addressing and Chaining

    Hash collisions occur when two different keys produce the same hash value. The two primary methods for resolving these conflicts are Open Addressing (开放寻址法) and Chaining/Linked List method (链表法).

  2. Core concepts of Dynamic Programming (DP)

    Dynamic Programming is typically used to find optimal values (min/max) by exhaustively searching all feasible answers. A problem is solvable via DP if it possesses three characteristics:

    1. Overlapping Sub-problems: The same sub-problems are solved multiple times, requiring optimization via memoization or a DP table.
    2. Optimal Substructure: The optimal solution to the main problem can be constructed from the optimal solutions of its independent sub-problems.
    3. State Transition Equation: A clear definition of the state (e.g., the meaning of the DP array/function), the choices available, and the base cases.

  3. Understand Binary Heap concepts

    A Binary Heap is a special type of complete binary tree that exists in two forms: Max Heap and Min Heap.

    • Max Heap: Every parent node's value is greater than or equal to its left and right children. The root (heap top) is the maximum element of the heap.
    • Min Heap: Every parent node's value is less than or equal to its left and right children. The root (heap top) is the minimum element of the heap.

    Due to these properties, binary heaps are highly efficient for finding the maximum or minimum value and are commonly used to implement priority queues and heap sort algorithms.

  4. Understand Binary Search Tree (BST) properties

    A Binary Search Tree (BST) is defined by the following properties:

    • If a node's left subtree is not empty, all nodes in the left subtree must have values less than the root node's value.
    • If a node's right subtree is not empty, all nodes in the right subtree must have values greater than the root node's value.
    • Both the left and right subtrees of any node must also be binary search trees.
    • An in-order traversal of a BST results in values sorted in ascending order.

  5. Understand Union-Find for dynamic connectivity

    The Union-Find algorithm is used to solve dynamic connectivity problems in graph theory, which can be abstracted as adding edges between nodes in a graph. It maintains the following properties:

    • Reflexivity: A node p is connected to itself.
    • Symmetry: If p is connected to q, then q is connected to p.
    • Transitivity: If p is connected to q and q is connected to r, then p is connected to r.

  6. Understand Stack data structure characteristics and use cases

    A Stack is a linear data structure that follows the LIFO (Last-In, First-Out) principle, meaning the last element added to the stack is the first one to be removed. Common real-world applications include:

    • Compiler and memory management for storing variables and method calls (Call Stack).
    • Browser history navigation.
    • Tracking visited tasks or paths in algorithms.
    • Implementing 'Undo' operations in software.

  7. Understand the purpose of AVL (Balanced) Binary Search Trees

    In a standard Binary Search Tree (BST), search efficiency depends on the height of the tree. If a BST becomes skewed (resembling a linked list), the time complexity for search, insertion, and deletion degrades to O(n). AVL trees solve this by ensuring the tree remains balanced, keeping the height minimal and guaranteeing O(log n) time complexity for search, insertion, and deletion in both average and worst-case scenarios. Rebalancing is achieved through tree rotations during element addition or removal.

  8. Determine if two strings are isomorphic

    Two strings s and t are isomorphic if the characters in s can be replaced to get t while preserving the order of characters. The mapping must be one-to-one: each character in s must map to exactly one character in t, and no two characters in s can map to the same character in t. A character can map to itself.

    Constraints:

    • Length of s and t are equal: 1 <= s.length <= 5 * 10⁴.
    • Strings consist of any valid ASCII characters.

  9. Understand the Counting Sort algorithm

    Counting Sort is a non-comparison-based sorting algorithm that sorts elements by counting the occurrences of each unique value. It is most effective when the range of input data (the difference between the maximum and minimum values) is small relative to the number of elements.

    The algorithm follows these steps:

    1. Determine Range: Find the maximum and minimum values in the dataset to calculate the range.
    2. Frequency Counting: Create a counting array where the index represents the element value and the value at that index represents the frequency of occurrence.
    3. Position Calculation: Determine the final position of each element by accumulating the counts.
    4. Reconstruct Array: Fill the final sorted array based on the calculated positions and frequencies.

  10. Calculate the h-index of a researcher

    The h-index is defined as the maximum value h such that the researcher has published at least h papers that have each been cited at least h times. Given an integer array citations where citations[i] is the number of citations for the i-th paper, the goal is to find this maximum h value.

    Constraints:

    • Number of papers n: 1 ≤ n ≤ 5000
    • Citations per paper: 0 ≤ citations[i] ≤ 1000

  11. Understand sorting algorithm stability

    A sorting algorithm is considered stable if two elements with equal keys maintain their relative order before and after the sorting process. The primary benefit of stable sorting is that it allows for multi-level sorting: you can sort by one key and then another, and the results of the first sort will be preserved for the second sort.

  12. Reverse words in a string (LeetCode 151)

    Given a string s, reverse the order of the words. Words are defined as sequences of non-space characters separated by at least one space. The resulting string must have words separated by a single space, with no leading or trailing spaces.

    Constraints:

    • 1 <= s.length <= 10⁴
    • s contains English letters, digits, and spaces ' '
    • s contains at least one word.
    Input: s = "the sky is blue"
Output: "blue is sky the"

Input: s = "  hello world  "
Output: "world hello"

Input: s = "a good   example"
Output: "example good a"