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​

• ​Google​

• ​Guess the Word​

• ​Raindrop on Sidewalk​

• Airbnb

• ​Display Pages (Pagination)​

• Amazon

• ​Problem Solving Summary ​

• ​String or Array Rotation​

• ​Tips for Avoiding Bugs ​

• ​Substring or Subarray Search​

• ​Sliding Window​

• ​K Sums​

• ​Combination Sum Series​

• Knapsack Problems

• ​Depth-first Search​

• ​Large Number Operation​

• ​Implementation - Simulation​

• ​Monotonic Stack & Queue​

• ​Top K Problems​

• ​Java Interview Tips​

• ​OOP in Java​

• ​Conversion in Java​

• ​Data Structures in Java​

• ​Algorithm Optimization Tips​

• ​Reference​