DataStructureAndAlgorithm

目录

• DataStructure

  • 排序
    • 基础排序
    • 高级排序
  • 线性
    • 数组
    • 栈
    • 队列
  • 堆
  • 树
    • 二分搜索树
    • AVL树
    • 线段树
    • 字典树/前缀树
  • 并查集
  • 图
    • 无权图
    • 带权图
    • 最小生成树
    • 最短路径

• LeetCode

  • Array
  • String
  • Sort
  • LinkedList
  • Tree
  • Math
  • HashTable
  • DP
  • Graph
  • Others
  • Backtracking
  • Heap
  • Greedy

datastructure

排序

基础排序

名称	描述
选择排序
冒泡排序
插入排序
插入排序优化	通过减少交换的操作,提升效率

高级排序

名称	描述
希尔排序	强化版的插入排序
归并排序
归并排序优化	针对近乎有序的数组，通过减少merge操作以及当元素的数量少于等于16个时使用插入排序
归并排序BU	改递归为遍历，自底向上进行归并
快速排序
快速排序优化	针对近乎有序的数组，防止时间复杂度退化到O(n^2)
二路快速排序	针对近乎有序的数组，提升效率
三路快速排序	针对存在大量重复元素的数组，提升效率
堆排序
堆排序优化	通过Heapify数组建堆代替原先的insert逐个插入
原地堆	没有开辟新的数组空间，直接在原来的数组上进行堆排

线性

数组

名称	描述
数组	动态数组

栈

名称	描述
栈	基于数组的实现

队列

名称	描述
队列
循环队列	出队操作为O(1)

堆

名称	描述
最大堆
最小堆
最大索引堆	通过增加索引数组，避免直接对数据进行交换操作
最小索引堆	同上

树

二分搜索树

名称	描述
二分查找
二分搜索树
二分搜索树遍历	深度优先（前中后序遍历）、广度优先(层序遍历)
二分搜索树删除	Hibbard Deletion

avl树

名称	描述
AVL树	通过LL/RR/LR/RL 操作维护平衡因子，达到自平衡

线段树

名称	描述
线段树	存放给定区间内对应的信息,针对区间内数据频繁变更

trie

名称	描述
Trie	查询与添加操作的效率取决于元素的长度而非树中的数量

并查集

名称	描述
并查集	QUICK FIND，union和isConnected时间复杂度分别为O(n) 和 O(1)
并查集优化	QUICK UNION，提升union过程的效率
并查集优化	基于SIZE的优化
并查集优化	基于RANK的优化
并查集优化	路径压缩 (Path Compression)
并查集优化	路径压缩 (Path Compression) 递归方式

图

无权图

名称	描述
图的表示	邻接矩阵
图的表示	邻接表
图文件读取	用于测试图
DFS求连通分量

带权图

名称	描述
图的表示	邻接矩阵
图的表示	邻接表

最小生成树

名称	描述
Prim算法	(Lazy Prim)
Prim算法优化
Kruskal算法

最短路径

名称	描述
Dijkstra算法	针对没有负权边的图
Bellman Ford算法	针对有负权边而没有负权环的图

LeetCode

(备注: "🤔" 表示还不太满意当前解法，等有时间了再优化!)

Array

Difficulty	Title
easy	Count Pairs Of Similar Strings
easy	Maximum Count of Positive Integer and Negative Integer
easy	Difference Between Element Sum and Digit Sum of an Array
easy	Minimum Common Value
easy	Alternating Digit Sum
easy	Count Distinct Numbers on Board
easy	Separate the Digits in an Array
easy	Take Gifts From the Richest Pile
easy	Find the Array Concatenation Value
easy	Number of Arithmetic Triplets
easy	Largest Local Values in a Matrix
easy	Longest Subsequence With Limited Sum
easy	Minimum Amount of Time to Fill Cups
easy	Find Closest Number to Zero
easy	Count Elements With Strictly Smaller and Greater Elements
easy	Most Frequent Number Following Key In an Array
easy	Count Equal and Divisible Pairs in an Array
easy	Time Needed to Buy Tickets
easy	Two Sum
easy	Two Sum II Input array is sorted
easy	Single Number
easy	Rotate Array
easy	Move Zeroes
easy	Contains Duplicate
easy	Remove Duplicates from Sorted Array
easy	Intersection Of Two Arrays II
easy	Plus One
easy	Best Time To Buy And Sell Stock II
easy	Rotate Image
easy	Range Sum Query - Immutable
easy	Valid Sudoku
easy	Single Number
easy	Find All Numbers Disappeared in an Array
easy	Flipping an Image
easy	Array Partition I
easy	Transpose Matrix
easy	Max Consecutive Ones
easy	Majority Element
easy	Toeplitz Matrix
easy	Largest Number At Least Twice of Others
easy	Remove Element
easy	Search Insert Position
easy	Positions of Large Groups
easy	Maximum Product of Three Numbers
easy	Peak Index in a Mountain Array
easy	Intersection of Two Arrays
easy	Find Smallest Letter Greater Than Target
easy	Binary Search
easy	Fair Candy Swap
easy	Non decreasing Array
easy	Max Area of Island
easy	Next Greater Element I
easy	1 bit and 2 bit Characters
easy	Monotonic Array
easy	Reshape the Matrix
easy	Find Pivot Index
easy	Maximum Average Subarray I
easy	Sort Array By Parity
easy	X of a Kind in a Deck of Cards
easy	Teemo Attacking
easy	Sort Array By Parity II
easy	Relative Ranks
easy	Smallest Range I
easy	Unique Email Addresses
easy	Degree of an Array
easy	Reorder Log Files
easy	Valid Mountain Array
easy	N-Repeated Element in Size 2N Array
easy	Squares of a Sorted Array
easy	Largest Perimeter Triangle
easy	Sum of Even Numbers After Queries
easy	Add to Array Form of Integer
easy	Binary Prefix Divisible By 5
easy	Destination City
easy	Kids With the Greatest Number of Candies
easy	Minimum Subsequence in Non-Increasing Order
easy	Find Lucky Integer in an Array
easy	Create Target Array in the Given Order
easy	Lucky Numbers in a Matrix
easy	How Many Numbers Are Smaller Than the Current Number
easy	Contains Duplicate II
easy	Build an Array With Stack Operations
easy	Count Negative Numbers in a Sorted Matrix
easy	The K Weakest Rows in a Matrix
easy	Decompress Run-Length Encoded List
easy	Number of Students Doing Homework at a Given Time
easy	Minimum Time Visiting All Points
easy	Replace Elements with Greatest Element on Right Side
easy	Find N Unique Integers Sum up to Zero
easy	Unique Number of Occurrences
easy	Relative Sort Array
easy	Fibonacci Number
easy	Minimum Absolute Difference
easy	Distribute Candies to People
easy	Element Appearing More Than 25% In Sorted Array
easy	Duplicate Zeros
easy	Partition Array Into Three Parts With Equal Sum
easy	Shuffle the Array
easy	Maximum Product of Two Elements in an Array
easy	Make Two Arrays Equal by Reversing Sub-arrays
easy	Running Sum of 1d Array
easy	Cells with Odd Values in a Matrix
easy	Final Prices With a Special Discount in a Shop
easy	Third Maximum Number
easy	Minimum Value to Get Positive Step by Step Sum
easy	Find the Distance Value Between Two Arrays
easy	Compare Strings by Frequency of the Smallest Character
easy	Rank Transform of an Array
easy	Height Checker
easy	Divide Array in Sets of K Consecutive Numbers
easy	XOR Operation in an Array
easy	Shift 2D Grid
easy	Surface Area of 3D Shapes
easy	N-th Tribonacci Number
easy	Average Salary Excluding the Minimum and Maximum Salary
easy	Find the Town Judge
easy	Path Crossing
easy	Range Addition II
easy	Number of Good Pairs
easy	Can Make Arithmetic Progression From Sequence
easy	Occurrences After Bigram
easy	Shuffle String
easy	Bulb Switcher IV
easy	Count Odd Numbers in an Interval Range
easy	Number of Good Ways to Split a String
easy	Count Good Triplets
easy	Three Consecutive Odds
easy	Special Array With X Elements Greater Than or Equal X
easy	Mean of Array After Removing Some Elements
easy	Sort Array by Increasing Frequency
easy	Longer Contiguous Segments of Ones than Zeros
easy	Maximum Population Year
easy	Minimum Distance to the Target Element
easy	Maximum Ascending Subarray Sum
easy	Count Items Matching a Rule
easy	Sum of Unique Elements
easy	Maximum Number of Balls in a Box
easy	Find the Highest Altitude
easy	Minimum Difference Between Highest and Lowest of K Scores
easy	Find Greatest Common Divisor of Array
easy	Convert 1D Array Into 2D Array
easy	Smallest Index With Equal Value
medium	Maximum Swap
medium	3Sum
medium	Group Anagrams
medium	Single Number II
medium	Single Number III
medium	Find All Duplicates in an Array
medium	Find Minimum in Rotated Sorted Array
medium	Single Element in a Sorted Array
medium	Set Matrix Zeroes
medium	Next Greater Element II
medium	Increasing Triplet Subsequence
medium	Search a 2D Matrix
medium	Search a 2D Matrix II
medium	Find Peak Element
medium	Merge Intervals
medium	Task Scheduler
medium	Reveal Cards In Increasing Order
medium	Check If All 1's Are at Least Length K Places Away
medium	Contains Duplicate III
medium	Minimum Size Subarray Sum
medium	Sort the Matrix Diagonally
medium	Remove Duplicates from Sorted Array II
medium	Product of Array Except Self
medium	Subrectangle Queries
medium	Max Increase to Keep City Skyline
medium	Reduce Array Size to The Half
medium	Count Number of Teams
medium	Subarray Sums Divisible by K 🤔
medium	Subarray Sum Equals K
medium	Continuous Subarray Sum
medium	Least Number of Unique Integers after K Removals
medium	Longest Subarray of 1's After Deleting One Element
medium	Minimum Difference Between Largest and Smallest Value in Three Moves
medium	Minimum Operations to Make Array Equal
medium	Arithmetic Subarrays
hard	Find Minimum in Rotated Sorted Array II

String

Difficulty	Title
easy	Minimum Recolors to Get K Consecutive Black Blocks
easy	Divide a String Into Groups of Size k
easy	Calculate Digit Sum of a String
easy	Cells in a Range on an Excel Sheet
easy	Counting Words With a Given Prefix
easy	Count Vowel Substrings of a String
easy	Reverse String
easy	First Unique Character In A String
easy	Reverse Integer
easy	Valid Anagram
easy	Longest Common Prefix
easy	Valid Palindrome
easy	String To Integer atoi
easy	Implement strStr
easy	CountAndSay
easy	Valid Parentheses
easy	To Lower Case
easy	Unique Morse Code Words
easy	Length of Last Word
easy	Reverse Words in a String III
easy	Detect Capital
easy	Rotate String
easy	Judge Route Circle
easy	Shortest Distance to a Character
easy	Find the Difference
easy	Goat Latin
easy	Ransom Note
easy	Most Common Word
easy	Rotated Digits
easy	Reverse Only Letters
easy	Long Pressed Name
easy	Groups of Special Equivalent Strings
easy	Count Binary Substrings
easy	Reverse Vowels of a String
easy	Camelcase Matching
easy	Remove All Adjacent Duplicates In String
easy	Maximum Score After Splitting a String
easy	Reformat The String
easy	String Matching in an Array
easy	Generate a String With Characters That Have Odd Counts
easy	Increasing Decreasing String
easy	Number of Days Between Two Dates
easy	Defanging an IP Address
easy	Split a String in Balanced Strings
easy	Decrypt String from Alphabet to Integer Mapping
easy	Check If a Word Occurs As a Prefix of Any Word in a Sentence
easy	Find Words That Can Be Formed by Characters
easy	Consecutive Characters
easy	Maximum Number of Balloons
easy	Add Binary
easy	Greatest Common Divisor of Strings
easy	Day of the Year
easy	Longest Uncommon Subsequence I
easy	Reformat Date
easy	Make The String Great
easy	Thousand Separator
easy	Maximum Nesting Depth of the Parentheses
easy	Largest Substring Between Two Equal Characters
easy	Sorting the Sentence
easy	Check if Word Equals Summation of Two Words
easy	Substrings of Size Three with Distinct Characters
easy	Replace All Digits with Characters
easy	Check if the Sentence Is Pangram
easy	Truncate Sentence
easy	Determine Color of a Chessboard Square
easy	Number of Different Integers in a String
easy	Second Largest Digit in a String
easy	Check if One String Swap Can Make Strings Equal
easy	Check if Binary String Has at Most One Segment of Ones
easy	Merge Strings Alternately
easy	Longest Nice Substring
easy	Number of Strings That Appear as Substrings in Word
easy	Check If String Is a Prefix of Array
easy	Delete Characters to Make Fancy String
easy	Sum of Digits of String After Convert
easy	Check if Numbers Are Ascending in a Sentence
medium	Longest Substring Without Repeating Characters
medium	Longest Palindromic Substring
medium	Partition Labels
medium	Minimum Number of Frogs Croaking
medium	HTML Entity Parser
medium	Number of Substrings Containing All Three Characters
medium	Longest Repeating Character Replacement
medium	Find All Anagrams in a String
medium	Minimum Number of Steps to Make Two Strings Anagram
medium	Minimum Add to Make Parentheses Valid
medium	Search Suggestions System
medium	Custom Sort String

Sort

Difficulty	Title
easy	Largest Number After Digit Swaps by Parity
easy	Sort Even and Odd Indices Independently
easy	Merge Sorted Array
easy	First Bad Version
easy	Matrix Cells in Distance Order 🤔
medium	Find First and Last Position of Element in Sorted Array
medium	Sort Colors
medium	Kth Largest Element in an Array
medium	Search in Rotated Sorted Array
medium	Pancake Sorting
medium	Sort an Array

LinkedList

Difficulty	Title
easy	Delete Node In A Linked List
easy	Linked List Cycle
easy	Reverse Linked List
easy	Palindrome Linked List
easy	Merge Two Sorted Lists
easy	Remove Linked List Elements
easy	Middle of the Linked List
easy	Remove Duplicates from Sorted List
easy	Intersection of Two Linked Lists
easy	Convert Binary Number in a Linked List to Integer
medium	Remove Nth Node From End of List

Tree

Difficulty	Title
easy	Root Equals Sum of Children
easy	Binary Tree Level Order Traversal
easy	Maximum_Depth_of_Binary_Tree
easy	Validate_Binary_Search_Tree
easy	Convert_Sorted_Array_to_Binary_Search_Tree
easy	Symmetric Tree
easy	Invert Binary Tree
easy	Average of Levels in Binary Tree
easy	Two Sum IV Input is a BST
easy	Sum of Left Leaves
easy	Binary Tree Level Order Traversal II
easy	Search in a Binary Search Tree
easy	Convert BST to Greater Tree
easy	Same Tree
easy	Binary Tree Paths
easy	Second Minimum Node In a Binary Tree
easy	Path Sum
easy	Merge Two Binary Trees
easy	Leaf Similar Trees
easy	Maximum Depth of N-ary Tree
easy	N-ary Tree Postorder Traversal
easy	N-ary Tree Preorder Traversal
easy	N-ary Tree Level Order Traversal
easy	Trim a Binary Search Tree
easy	Binary Tree Tilt
easy	Diameter of Binary Tree
easy	Subtree of Another Tree
easy	Construct String from Binary Tree
easy	Lowest Common Ancestor of a Binary Search Tree
easy	Balanced Binary Tree
easy	Minimum Depth of Binary Tree
easy	Increasing Order Search Tree
easy	Univalued Binary Tree
easy	Sum of Root To Leaf Binary Numbers
easy	Path Sum III 🤔
easy	Minimum Absolute Difference in BST
easy	Minimum Distance Between BST Nodes
easy	Cousins in Binary Tree
easy	Find Mode in Binary Search Tree
medium	Range Sum Query - Mutable
medium	Binary Tree Inorder Traversal
medium	Binary Tree Zigzag Level Order Traversal
medium	Kth Smallest Element in a BST
medium	Construct Binary Tree from Preorder and Inorder Traversal
medium	Implement Trie Prefix Tree
medium	Add and Search Word - Data structure design
medium	Map Sum Pairs
medium	Maximum Binary Tree
medium	Binary Tree Pruning
medium	Find Bottom Left Tree Value
medium	Find Largest Value in Each Tree Row
medium	Insert into a Binary Search Tree
medium	Binary Tree Preorder Traversal
medium	Range Sum of BST
medium	Flip Equivalent Binary Trees
medium	Balance a Binary Search Tree
medium	Find a Corresponding Node of a Binary Tree in a Clone of That Tree
medium	Longest ZigZag Path in a Binary Tree
medium	Deepest Leaves Sum
medium	Delete Leaves With a Given Value
medium	Path Sum II
medium	Construct Binary Search Tree from Preorder Traversal
medium	All Elements in Two Binary Search Trees
medium	Find Elements in a Contaminated Binary Tree
medium	Count Good Nodes in Binary Tree
medium	Maximum Level Sum of a Binary Tree
medium	Sum of Nodes with Even Valued Grandparent
medium	Even Odd Tree

Math

Difficulty	Title
easy	Count the Digits That Divide a Number
easy	Add Two Integers
easy	Count Operations to Obtain Zero
easy	Count Integers With Even Digit Sum
easy	Count_Primes
easy	Power_of_Three
easy	Fizz Buzz
easy	Roman to Integer
easy	Power of Two
easy	Self Dividing Numbers
easy	Add Digits
easy	Add Strings
easy	Power of Four
easy	Factorial Trailing Zeroes
easy	Ugly Number
easy	Palindrome Number
easy	Happy Number
easy	Excel Sheet Column Number
easy	DI String Match
easy	Largest Time for Given Digits
easy	Divisor Game
easy	Closest Divisors
easy	Subtract the Product and Sum of Digits of an Integer
easy	Find Numbers with Even Number of Digits
easy	Maximum 69 Number
easy	Day of the Week
easy	Convert Integer to the Sum of Two No-Zero Integers
easy	Check If It Is a Straight Line
easy	Find Positive Integer Solution for a Given Equation
easy	Sum of Digits in Base K
easy	Sign of the Product of an Array
easy	Kth Distinct String in an Array
medium	Pow x n
medium	Ugly Number II
medium	The kth Factor of n

HashTable

Difficulty	Title
easy	Keep Multiplying Found Values by Two
easy	Check Whether Two Strings are Almost Equivalent
easy	Jewels and Stones
easy	Uncommon Words from Two Sentences
easy	Set Mismatch
easy	Subdomain Visit Count
easy	Keyboard Row
easy	Number of Lines To Write String
easy	Island Perimeter
easy	Distribute Candies
easy	Shortest Completing Word
easy	Employee Importance
easy	Verifying an Alien Dictionary
easy	Longest Palindrome
easy	Minimum Index Sum of Two Lists
easy	Longest Word in Dictionary
easy	Longest Harmonious Subsequence
easy	Isomorphic Strings
easy	Find Common Characters
medium	Daily Temperatures
medium	Battleships in a Board
medium	Find Duplicate File in System
medium	Display Table of Food Orders in a Restaurant
medium	Replace Words
hard	Maximum Frequency Stack

Heap

Difficulty	Title
easy	Kth Largest Element in a Stream
medium	Top K Frequent Elements
medium	Kth Smallest Element in a Sorted Matrix
medium	Sort Characters By Frequency
medium	Top K Frequent Words

Greedy

Difficulty	Title
easy	Minimum Hours of Training to Win a Competition
easy	Minimum Cost of Buying Candies With Discount
easy	Minimum Sum of Four Digit Number After Splitting Digits
easy	Lemonade Change
easy	Assign Cookies
easy	String Without AAA or BBB
easy	Two City Scheduling
easy	Delete Columns to Make Sorted
easy	Play with Chips
easy	Is Subsequence
easy	Last Stone Weight
easy	Water Bottles
easy	Minimum Operations to Make the Array Increasing
easy	Minimum Changes To Make Alternating Binary String
easy	Minimum Time to Type Word Using Special Typewriter
medium	Group the People Given the Group Size They Belong To

Others

Difficulty	Title
easy	Missing Number
easy	Number of 1 Bits
easy	Hamming Distance
easy	Reverse Bits
easy	Pascal's Triangle
easy	Find the Duplicate Number
easy	Binary Number with Alternating Bits
easy	Binary Gap
easy	Backspace String Compare
easy	Baseball Game
easy	Nim Game
easy	Number Complement
easy	Number of Recent Calls
easy	Complement of Base 10 Integer
easy	Remove Outermost Parentheses
easy	Prime Number of Set Bits in Binary Representation
easy	Sort Integers by The Number of 1 Bits
easy	Number of Steps to Reduce a Number to Zero
easy	Print in Order
medium	Evaluate Reverse Polish Notation
medium	Score of Parentheses
medium	Longest Word in Dictionary through Deleting
medium	Boats to Save People
medium	Validate Stack Sequences
medium	Counting Bits 🤔
medium	Print FooBar Alternately
medium	Print Zero Even Odd
medium	Building H2O

Design

Difficulty	Title
easy	Min Stack
easy	Shuffle an Array
easy	Guess Number Higher or Lower
easy	Implement Queue using Stacks
easy	Implement Stack using Queues
easy	Design HashMap
easy	Design HashSet
medium	Encode and Decode TinyURL
medium	Design a Stack With Increment Operation
medium	Product of the Last K Numbers
medium	Design Browser History
medium	Apply Discount Every n Orders
medium	Design Underground System
medium	Serialize and Deserialize BST 🤔

Graph

Difficulty	Title
medium	Keys and Rooms

DP

Difficulty	Title
easy	Climbing Stairs
easy	Best Time to Buy and Sell Stock
easy	Maximum Subarray
easy	House Robber

Backtracking

Difficulty	Title
medium	Letter Combinations of a Phone Number
medium	Permutations
medium	Combinations
medium	Subsets
medium	Word Search
medium	Combination Sum III
medium	Letter Case Permutation
medium	Letter Tile Possibilities