Introduction

Algorithm and Data Structure Notes
#algorithm# #datastructure# #数据结构和算法#
Problems coming from LeetCode, LintCode, TopCoder, CtCi, etc.
Disclaimer:
1.Under construction
2.Some solutions, comments, concepts, explanation, analysis may come from Internet, discussion forums
3.Personal use only, for learning purpose
Contents
Summary
​Introduction​
​Linked List​
​Sort List​
​Merge Two Sorted Lists​
​Merge k Sorted Lists​
​Linked List Cycle​
​Linked List Cycle II​
​Add Two Numbers II​
​Add Two Numbers​
​Odd Even Linked List​
​Intersection of Two Linked Lists​
​Reverse Linked List​
​Reverse Linked List II​
​Remove Linked List Elements​
​Remove Nth Node From End of List​
​Middle of the Linked List​
​Design Linked List​
​Design Singly Linked List​
​Design Doubly Linked List​
​Palindrome Linked List​
​Remove Duplicates from Sorted List​
​Remove Duplicates from Sorted List II​
​Implement Stack Using Singly Linked List​
​Copy List with Random Pointer​
​Binary Search​
​Search in Rotated Sorted Array​
​Search in Rotated Sorted Array II​
​Search in a Sorted Array of Unknown Size​
​First Bad Version​
​Find Minimum in Rotated Sorted Array​
​Find Minimum in Rotated Sorted Array II​
​Find Peak Element​
​Search for a Range​
​Find K Closest Elements​
​Search Insert Position​
​Peak Index in a Mountain Array​
​Heaters​
​Hash Table​
​Jewels and Stones​
​Single Number​
​Subdomain Visit Count​
​Design HashMap​
​Design HashSet​
​Logger Rate Limiter​
​Isomorphic Strings​
​Minimum Index Sum of Two Lists​
​Contains Duplicate II​
​Contains Duplicate III​
​Longest Consecutive Sequence​
​Valid Sudoku​
​Distribute Candies​
​Shortest Word Distance​
​Shortest Word Distance II​
​String​
​Rotate String​
​Add Binary​
​Implement strStr()​
​Longest Common Prefix​
​Reverse Words in a String​
​Reverse Words in a String II​
​Reverse Words in a String III​
​Valid Word Abbreviation​
​Group Anagrams​
​Unique Email Addresses​
​Next Closest Time​
​License Key Formatting​
​String to Integer - atoi​
​Ransom Note​
​Multiply Strings​
​Text Justification​
​Reorder Log Files​
​Most Common Word​
Valid Parenthesis String
​K-Substring with K different characters​
​Find All Anagrams in a String​
​Find the Closest Palindrome​
​Simplify Path​
​Array​
​Partition Array​
​Median of Two Sorted Arrays​
​Intersection of Two Arrays​
​Intersection of Two Arrays II​
​Maximum Subarray Sum​
​Minimum Subarray Sum​
​Maximum Subarray II​
​Maximum Subarray III​
​Subarray Sum Closest​
​Subarray Sum​
​Plus One​
​Maximum Subarray Difference​
​Maximum Subarray IV​
​Subarray Sum Equals K​
​Intersection of Two Arrays​
​Intersection of Two Arrays II​
​Find Pivot Index​
​Rotate Array​
​Get Smallest Nonnegative Integer Not In The Array​
​Maximize Distance to Closest Person​
​Sort Colors​
​Next Permutation​
​Rotate Image​
​Pour Water​
​Prison Cells After N Days​
​Majority Element​
​Can Place Flowers​
​Candy​
​Matrix​
​Spiral Matrix​
​Set Matrix Zeroes​
​Diagonal Traverse​
​Queue​
​Design Circular Queue​
​Implement Queue using Stacks​
​Implement Queue by Two Stacks​
​Implement Stack using Queues​
​Moving Average from Data Stream​
​Walls and Gates​
​Open the Lock​
​Sliding Window Maximum​
Implement Queue Using Fixed Length Array
​Animal Shelter​
​Stack​
​Valid Parentheses​
​Longest Valid Parentheses​
​Min Stack​
​Max Stack​
​Daily Temperatures​
​Evaluate Reverse Polish Notation​
​Next Greater Element I​
​Next Greater Element II​
​Next Greater Element III​
​Largest Rectangle in Histogram​
​Maximal Rectangle​
​Car Fleet​
​Heap​
​Trapping Rain Water II​
​The Skyline Problem​
​Top K Frequent Words​
​Top K Frequent Words II​
​Top K Frequent Elements​
​Top k Largest Numbers​
​Top k Largest Numbers II​
​Minimum Cost to Hire K Workers​
​Kth Largest Element in an Array​
​Kth Smallest Number in Sorted Matrix​
​Kth Smallest Sum In Two Sorted Arrays​
​K Closest Points to the Origin​
​Merge K Sorted Lists​
​Merge K Sorted Arrays​
​Top K Frequent Words - Map Reduce​
​Data Structure & Design​
​Hash Function​
​Heapify​
​LRU Cache​
​LFU Cache​
​Rehashing​
​Stack Sorting​
​Animal Shelter​
​Sliding Window Maximum​
​Moving Average from Data Stream​
​Find Median from Data Stream​
​Sliding Window Median​
​Design Hit Counter​
​Read N Characters Given Read4 II - Call multiple times​
​Read N Characters Given Read4​
​Flatten 2D Vector​
​Flatten Nested List Iterator​
​Design Search Autocomplete System​
​Time Based Key-Value Store​
​Design Tic-Tac-Toe​
​Insert Delete GetRandom O(1)​
​Union Find​
​Find the Connected Component in the Undirected Graph​
​Find the Weak Connected Component in the Directed Graph​
​Graph Valid Tree​
​Number of Islands​
​Number of Islands II​
​Surrounded Regions​
​Most Stones Removed with Same Row or Column​
​Redundant Connection​
​Trie​
​Implement Trie​
​Add and Search Word​
​Word Search II​
​Longest Word in Dictionary​
​Palindrome Pairs​
​Trie Serialization​
​Trie Service​
​Design Search Autocomplete System​
​Typeahead​
​Trees​
​Binary Tree Inorder Traversal​
​Binary Tree Postorder Traversal​
​Binary Tree Preorder Traversal​
​Binary Tree Level Order Traversal​
​Binary Tree Zigzag Level Order Traversal​
​Binary Tree Vertical Order Traversal​
​N-ary Tree Level Order Traversal​
​N-ary Tree Preorder Traversal​
​N-ary Tree Postorder Traversal​
​Construct Binary Tree from Preorder and Inorder Traversal​
​Populating Next Right Pointers in Each Node​
​Populating Next Right Pointers in Each Node II​
​Maximum Depth of Binary Tree​
​Symmetric Tree​
​Validate Binary Search Tree​
​Convert Sorted Array to Binary Search Tree​
​Path Sum​
​Path Sum II​
​Path Sum III​
​Binary Tree Maximum Path Sum​
​Kth Smallest Element in a BST​
​Same Tree​
​Lowest Common Ancestor of a Binary Tree​
​Lowest Common Ancestor of a Binary Search Tree​
​Nested List Weight Sum II​
​BST Node Distance​
​Minimum Distance (Difference) Between BST Nodes​
​Closet Common Manager​
N-ary Tree Postorder Traversal
​Serialize and Deserialize Binary Tree​
​Serialize and Deserialize N-ary Tree​
​Diameter of a Binary Tree​
​Print Binary Trees​
​Segment Tree​
​Segment Tree Build​
​Range Sum Query - Mutable​
​Binary Indexed Tree​
​Graph & Search​
​Clone Graph​
​N Queens​
​Six Degrees​
​Number of Islands​
​Number of Distinct Islands​
​Word Search​
​Course Schedule​
​Course Schedule II​
​Word Ladder​
​Redundant Connection​
​Redundant Connection II​
​Longest Increasing Path in a Matrix​
​Reconstruct Itinerary​
​The Maze​
​The Maze II​
​The Maze III​
​Topological Sorting​
​Island Perimeter​
​Flood Fill​
​Cheapest Flights Within K Stops​
​Evaluate Division​
​Alien Dictionary​
​Cut Off Trees for Golf Event​
​Jump Game II​
​Most Stones Removed with Same Row or Column​
​Backtracking​
​Subsets​
​Subsets II​
​Letter Combinations of a Phone Number​
​Permutations​
​Permutations II​
​Combinations​
​Combination Sum​
​Combination Sum II​
​Combination Sum III​
​Combination Sum IV​
​N-Queens​
​N-Queens II​
​Generate Parentheses​
​Subsets of Size K​
​Two Pointers​
​Two Sum II​
​Triangle Count​
​Trapping Rain Water​
​Container with Most Water​
​Minimum Size Subarray Sum​
​Minimum Window Substring​
​Longest Substring Without Repeating Characters​
​Longest Substring with At Most K Distinct Characters​
​Longest Substring with At Most Two Distinct Characters​
​Fruit Into Baskets​
​Nuts & Bolts Problem​
​Valid Palindrome​
​The Smallest Difference​
​Reverse String​
​Remove Element​
​Max Consecutive Ones​
​Max Consecutive Ones II​
​Remove Duplicates from Sorted Array​
​Remove Duplicates from Sorted Array II​
​Move Zeroes​
​Longest Repeating Character Replacement​
​3Sum With Multiplicity​
​Merge Sorted Array​
​3Sum Smaller​
​Backspace String Compare​
​Mathematics​
​Ugly Number​
​Ugly Number II​
​Super Ugly Number​
​Sqrt(x)​
​Random Number 1 to 7 With Equal Probability​
​Pow(x, n)​
​Narcissistic Number​
​Rectangle Overlap​
​Happy Number​
​Add N Days to Given Date​
​Reverse Integer​
​Greatest Common Divisor or Highest Common Factor​
​Bit Operation​
​IP to CIDR​
​Random​
​Random Pick with Weight​
​Random Pick Index​
​Linked List Random Node​
​Dynamic Programming​
​House Robber​
​House Robber II​
​House Robber III​
​Longest Increasing Continuous Subsequence​
​Longest Increasing Continuous Subsequence II​
​Coins in a Line​
​Coins in a Line II​
​Coins in a Line III​
​Maximum Product Subarray​
​Longest Palindromic Substring​
​Stone Game​
​Burst Balloons​
​Perfect Squares​
​Triangle​
​Pascal's Triangle​
​Pascal's Triangle II​
​Min Cost Climbing Stairs​
​Climbing Stairs​
​Unique Paths​
​Unique Paths II​
​Minimum Path Sum​
​Word Break​
​Word Break II​
​Range Sum Query - Immutable​
​Decode Ways​
​Edit Distance​
​Unique Binary Search Trees​
​Unique Binary Search Trees II​
​Maximal Rectangle​
​Maximal Square​
​Regular Expression Matching ​
​Wildcard Matching​
​Flip Game II​
​Longest Increasing Subsequence​
​Target Sum​
​Partition Equal Subset Sum​
​Coin Change​
​Jump Game​
​Can I Win​
​Maximum Sum Rectangle in a 2D Matrix​
​Cherry Pick​
​Knapsack​
​Backpack​
​Backpack II​
​Backpack III​
​Backpack IV​
​Backpack V​
​Backpack VI ​
​Backpack VII​
​Coin Change​
​Coin Change II​
​High Frequency​
​2 Sum Closest​
​3 Sum​
​3 Sum Closest​
​Sort Colors II​
​Majority Number​
​Majority Number II​
​Majority Number III​
​Best Time to Buy and Sell Stock​
​Best Time to Buy and Sell Stock II​
​Best Time to Buy and Sell Stock III​
​Best Time to Buy and Sell Stock IV​
​Two Sum​
​Two Sum II - Input array is sorted​
​Two Sum III - Data structure design​
​Two Sum IV - Input is a BST​
​4 Sum​
​4 Sum II​
​Sorting​
Greedy
​Jump Game II​
​Remove K Digits​
Minimax
​Nim Game​
​Can I Win​
​Sweep Line & Interval​
​Meeting Rooms​
​Meeting Rooms II​
​Merge Intervals​
​Insert Interval​
​Number of Airplanes in the Sky​
​Exam Room​
​Employee Free Time​
​Closest Pair of Points​
​My Calendar I​
​My Calendar II​
​My Calendar III​
​Add Bold Tag in String​
​Other Algorithms and Data Structure​
​Huffman Coding​
​Reservoir Sampling​
​Bloom Filter​
​External Sorting​
​Construct Quad Tree​
​Company Tag​