Pan's algorithm notes
  • Introduction
  • My Notes
    • Introduction
    • Content table
    • 1 Sliding window
      • 1918 Kth Smallest Subarray Sum
      • 713 Subarray Product Less Than K
      • 438 Find All Anagrams in a String
      • 76 Minimum Window Substring
      • 159 Longest Substring with At Most Two Distinct Characters
      • 340 Longest Substring with At Most K Distinct Characters
      • 3 Longest Substring Without Repeating Characters
      • 209 Minimum Size Subarray Sum
      • 395 Longest Substring with At Least K Repeating Characters
      • L604 Window Sum
      • 1658 Minimum Operations to Reduce X to Zero
      • 346 Moving Average from Data Stream
      • 567 Permutation in String
    • 2 Rotated Arrays
      • L1790 Rotate String II
      • L39 Recover Rotated Sorted Array
      • L62 Search in Rotated Sorted Array
      • L63 Search in Rotated Sorted Array II
      • L159 Find Minimum in Rotated Sorted Array
      • L160 Find Minimum in Rotated Sorted Array II
      • 189 Rotate Array
      • L53 Reverse Words in a String
      • 151 Reverse Words in a String
      • 186 Reverse Words in a String II
      • 557 Reverse Words in a String III
    • 3 Permutation & Combination
      • 784 Letter Case Permutation
      • 526 Beautiful Arrangement
      • L15 Permutation
      • L16 Permutation II
      • L17 Subsets
      • L18 Subsets II
      • 254 Factor Combinations
      • 39 Combination Sum (L135)
      • 40 Combination Sum II
      • 216 Combination Sum III
      • 77 Combinations
      • 17 Letter Combination of a Phone Number
      • L10 String Permutation II
      • 267 Palindrome Permutaion II
    • 4 Palindrome
      • 336 Palindrome Pairs
      • 409 Longest Palindrome
      • 1332 Remove Palindromic Subsequences
      • 266 Palindrome Permuation
      • 5 Longest Palindromic Substring
      • 516 Longest Palindromic Subsequence
      • 647 Palindromic Substrings
      • 730 Count Different Palindromic Subsequences
    • 5 Quick Sort + Partition
      • 912 Sort an Array
      • 345 Reverse Vowels of a String
      • 125 Valid Palindrome
      • L31 Partition Array
      • 75 Sort colors
      • L143 Sort Colors II
      • L373 Partition Array by Odd and Even
      • L49 Sort Letters by Case
      • L5 Kth Largest Element
      • 86 Partition List
      • 414 Third Maximum Number
      • 280 Wiggle Sort
      • 324 Wiggle Sort II
      • 747 Largest Number At Least Twice of Others
      • L399 Nuts & bolts Problem
      • 917 Reverse Only Letters
    • 6 Matrix
      • 1380 Lucky Numbers in a Matrix
      • 48 Rotate Image
      • 亚麻题库的rotate matrix
      • 54 Spiral Matrix
      • 59 Spiral Matrix II
      • 73 Set Matrix Zeroes
      • L185 Matrix Zigzag Traversal
    • 7 Subarrays (prefix sum)
      • 560 Subarray Sum Equals K
      • 1477 Find Two Non-overlapping Sub-arrays Each With Target Sum
      • 528 Random Pick with Weight
      • L41 Maximum Subarray
      • L42 Maximum Subarray II
      • L44 Minimum Subarray
      • L45 Maximum Subarray Difference
      • 304 Range Sum Query 2D - immutable
      • 303 Range Sum Query - immutable
      • L138 Subarray Sum
      • L405 Submatrix Sum
      • L558 Sliding Window Matrix Maximum
      • L139 Subarray Sum Closest
      • L402 Continuous Subarray Sum
      • L403 Continuous Subarray Sum II
      • L404 Subarray Sum II
      • 325 Maximum Size Subarray Sum Equals k
      • 523 Continuous Subarray Sum
      • 724 Find Pivot Index
    • 8 Intervals
      • 56 Merge Intervals
      • 57 Insert Intervals
      • 436 Find Right Intervals
      • 352 Data Stream as Disjoint Intervals
      • 435 Non-overlapping Intervals
      • 228 Summary Ranges
      • 252 Meeting Rooms
      • 163 Missing Range
    • 9 Stocks
      • 714 Best Time to Buy and Sell Stock with Transaction Fee
      • L149 Best Time to Buy and Sell Stock
      • L150 Best Time to Buy and Sell Stock II
      • L151 Best Time to Buy and Sell Stock III
      • L393 Best Time to Buy and Sell Stock IV
    • 10 2，3，4 Sums
      • 1099 Two Sum Less Than K
      • 2491 Divide Players Into Teams of Equal Skill
      • 633 Sum of Square Numbers
      • 1679 Max Number of K-Sum Pairs
      • 1 Two Sum
      • 167 Two Sum II - input array is sorted
      • L443 Two Sum II - use 2 pointer to count
      • 170 Two Sum III - Data structure design
      • L553 Two Sum Closest
      • 15 3 Sum
      • 16 3 Sum Closest
      • 18 4 Sum
      • 259 3 Sum Smaller
      • 454 4Sum II
      • L609 Two Sum V
      • L587 Two Sum VI - Unique two sum pairs
      • L610 Two Sum VII - Difference equals to target
      • L382 Triangle Count
      • 532 K-diff Pairs in an Array
      • 653 Two Sum IV - Input is a BST
    • 11 backpacks
      • 474 Ones and Zeroes
      • L92 Backpack
      • L125 Backpack II
      • L440 Backpack III
      • L562 Backpack IV
      • L563 Backpack V
      • L564 Backpack VI
      • L279 Number of Ways to Represent N Cents
      • 279 Perfect Squares
      • 322 Coin Change
      • 416 Partition Equal Subset Sum
      • 377 Combination Sum IV
    • 12 graph （BFS）
      • 994 Rotting Oranges
      • 733 Flood Fill
      • 637 Average of Levels in Binary Tree
      • 1091 Shortest Path in Binary Matrix
      • 711 Number of Distinct Islands II
      • 573 Squirrel Simulation
      • 542 01 Matrix
      • 1631 Path With Minimum Effort
      • 200 Number of Islands
      • 133 Clone Graph
      • L531 Six Degrees
      • L431 Connected Component in Undirected Graph
      • L618 Search Graph nodes
      • L611 Knight Shortest Path
      • L598 Zombie in Matrix
      • 317 Shorest Distance from All Buildings
      • 127 Word Ladder
      • 126 Word Ladder II
      • L127 Topological Sort
      • 207 Course Schedule
      • 210 Course Schedule II
      • 444 Sequence Reconstruction
      • L477 Surrounded Regions
      • 269 Alien Dictionary
      • 529 Minesweeper
      • 286 Walls and Gates
      • 785 Is Graph Bipartite
      • Detect Cycle in directed graph
      • Detect Cycle in undirected graph
      • 301 Remove Invalid Parentheses
      • 419 Battleships in a Board
      • L574 Build Post Office
      • PrintShortestPath
      • 310 Minimum Height Trees
      • 695 Max Area of Island
      • 694 Number of Distinct Islands
      • 752 Open the Lock
    • 13 line sweep
      • L391 Number of Airplanes in the Sky
      • ctci 16.10 Living People
      • 370 Range Addition
      • 253 Meeting Rooms II
      • pramp mock 8
      • 554 Brick Wall
    • 14 merge sort
      • 88 Merge Sorted Array
      • L6 Merge Two Sorted Arrays
      • 23 Merge K sorted Lists
      • 21 Merge Two sorted Lists
      • L486 Merge K sorted Arrays
      • L532 Reverse Pairs
      • L408 Add Binary
      • 561 Array Partition I
    • 15 Math
      • L235 Prime Factorization
      • 492 Construct the Rectangle
      • 326 Power of Three
      • 1228 Missing Number In Arithmetic Progression
      • 775 Global and Local Inversions
      • 1551 Minimum Operations to Make Array Equal
      • 1342 Number of Steps to Reduce a Number to Zero
      • 1680 Concatenation of Consecutive Binary Numbers
      • 1037 Valid Boomerang
      • L586 Sqrt x II
      • 202 Happy Number
      • 204 Count Prime
      • 118 Pascal s Triangle
      • 119 Pascal s Triangle II
      • 396 Rotate Function
      • 766 Teoplitz Matrix
      • 89 Gray Code
      • L428 Pow x n
      • L407 Plus One
      • L408 Add Binary
      • L1 A plus B
      • 29 Divide Two Integers
      • 7 reverse Integer
      • L517 Ugly Number
      • Amicable Pair less than n
      • 179 Largest Number
      • 224 Basic Calculator
      • 227 Basic Calculator II
      • 8 String to Integer
      • 43 Multiply Strings
      • 415 Add Strings
      • 169 Majority Element
      • 229 Majority Element II
      • 171 Excel Sheet Column Number
      • 13 Roman to Integer
      • 273 Integer to English Words
      • 168 Excel Sheet Column Title
      • 311 Sparse Matrix Multiplication
      • L140 Fast Power
      • 372 Super Pow
      • 258 Add Digits
      • 12 Integer to Roman
      • 365 Water and Jug Problem
      • 9 Palindrome Number
      • 65 Valid Number
      • L180 Binary Representation
      • 561 Array Partition I
      • 384 Shuffle an Array
      • 172 Factorial Trailing Zeroes
      • 149 Max Points on a Line
      • 836 Rectangle Overlap
    • 16 two pointers - other
      • 795 Number of Subarrays with Bounded Maximum
      • 1004 Max Consecutive Ones III
      • 487 Max Consecutive Ones II
      • 1855 Maximum Distance Between a Pair of Values
      • 1089 Duplicate Zeros
      • 2511 Maximum Enemy Forts That Can Be Captured
      • 977 Squares of a Sorted Array
      • L521 Remove Duplicate Numbers in Array
      • L1870 Number of Substrings with All Zeroes
      • 1437 Check If All 1's Are at Least Length K Places Away
      • 680 Valid Palindrome II
      • 27 Remove Element
      • 26 Remove Duplicate from Sorted Array
      • 80 Remove Duplicate from Sorted Array II
      • 283 Move Zeros
      • 345 Reverse Vowels of a String
      • 28 Implement strStr
      • L387 The Smallest Difference
      • 344 Reverse String
      • 11 Container With Most Water
      • 42 Trapping Rain Water
      • 125 Valid Palindrome
      • 349 Intersection of Two Arrays
      • 350 Intersection of Two Arrays II
      • 485 Max Consecutive Ones
      • 243 Shortest Word Distance
      • 244 Shortest Word Distance II
      • 245 Shortest Word Distance III
      • Shortest Word Distance follow up
    • 17 Binary Search
      • L194 Find Words
      • 540 Single Element in a Sorted Array
      • 878 Nth Magical Number
      • 1712 Ways to Split Array Into Three Subarrays
      • 881 Boats to Save People
      • 1539 Kth Missing Positive Number
      • 744 Find Smallest Letter Greater Than Target
      • 1064 Fixed Point
      • 287 Find the Duplicate number
      • L458 Last Position of Target
      • L14 First Position of Target
      • L462 Total Occurrence of Target
      • 74 Search in a 2D Matrix
      • 240 Search in a 2D matrix II
      • 162 Find Peak Element
      • L390 Find Peak Element II
      • L74 First Bad Version
      • 374 Guess Number Higher or Lower
      • 35 Search Insert Position
      • 367 Valid Perfect Square
      • L447 Search in a Big Sorted Array
      • L459 Closest Number in Sorted Array
      • L585 maximum Number in Mountain Sequence
      • L460 K closest Numbers in Sorted Array
      • 34 Search for a Range
      • 302 Smallest Rectangle Enclosing Black Pixels
      • L437 copy books I
      • L438 copy books II
      • L141 Sqrt x
      • L183 Wood Cut
      • L254 Drop Egg
      • 410 Split Array Largest Sum
      • 274 H-Index
      • 275 H-Index II
      • RootOfNumber
      • 441 Arranging Coins
      • 875 Koko Eating Bananas
    • 18 LinkedList
      • 1721 Swapping Nodes in a Linked List
      • 234 Palindrome Linked List
      • 19 Remove Nth Node From End of List
      • 141 Linked List Cycle
      • 142 Linked List Cycle II
      • 61 Rotate List
      • 445 Add Two Numbers II
      • 206 Reverse Linked List
      • 92 Reverse Linked List II
      • 25 Reveres Nodes in K - Group
      • 2 Add Two Numbers
      • 237 Delete Node in a Linked List
      • 148 Sort List
      • 83 Remove Duplicates from Sorted List
      • 82 Remove Duplicates from Sorted List II
      • 203 Remove Linked List Elements
      • L106 Convert Sorted List to Balanced BST
      • L378 Convert Binary Search Tree to Doubly Linked List
      • 328 Odd Even Linked List
      • 23 Merge k Sorted Lists
      • 160 Intersection of Two Linked Lists
      • 138 Copy LIst with Random Pointer
      • 147 Insertion Sort List
      • 24 Swap Nodes in Pairs
      • L511 Swap Two Node in Linked List
      • 143 Reorder List
      • 369 Plus One Linked List
      • L166 Nth to Last Node in List
      • L453 Flatten Binary Tree to Linked List
      • L217 Remove Duplicate from unsorted List
      • 708 Insert into a Cyclic Sorted List
    • 19 left to right to left get best
      • L50 Product of Array Exclude itself
    • 20 finding missing
      • 448 Find All Numbers Disappeared in an Array
      • 268 Missing Number
      • 41 First Missing positive
      • L581 Longest Repeating Subsequence
    • 21 DP
      • 1235 Maximum Profit in Job Scheduling
      • 413 arithmetic Slices
      • 750 Number Of Corner Rectangles
      • 1641Count Sorted Vowel Strings
      • 1216 Valid Palindrome III
      • 120 Triangle
      • L397 Longest Increasing Continuous Subsequence
      • 64 Minimum Path Sum
      • 70 Climbing Stairs
      • L272 Climbing Stairs II
      • 62 Unique Paths
      • 63 Unique Paths II
      • L76 Longest Increasing Subsequence
      • 354 Russian Doll Envelopers
      • 368 Largest Divisible Subset
      • L116 Jump Game
      • L117 Jump Game II
      • L398 Longest Increasing Continuous Subsequence II
      • 139 Word Break
      • L108 Palindrome Partitionaing II
      • 91 Decode Ways
      • 198 House Robber
      • 213 House Robber II
      • L77 Longest Common Subsequence
      • L79 Longest Common SubString
      • 72 Edit Distance
      • 115 Distinct Subsequences
      • 276 Paint Fence
      • 403 Frog Jump
      • 44 Wildcard matching
      • 85 Maximal Rectangle
      • 312 Burst Ballons
      • 517 Super Washing Machines
      • 152 Maximum Product Subarray
      • 97 Interleaving String
      • L581 Longest Repeating Subsequence
      • 10 Regular Expression Matching
      • 221 Maximal Square
      • 264 Ugly Number II
      • L394 Coins in Line
      • L395 Coins in Line II
      • L396 Coins in line III
      • 87 Scramble String
      • L476 Stone Game
      • L593 Stone Game II
      • L43 Maximum Subarray III
      • 256 Paint House
      • 361 Bomb Enemy
      • L584 Drop Eggs II
      • meeting room 3
      • 392 Is Subsequence
      • 334 Increasing Triplet Subsequence
      • 494 Target Sum
      • 265 Paint House II
      • 174 Dungeon Game
    • 22 Data Structure (stack & queue --“dek”)
      • 1249 Minimum Remove to Make Valid Parentheses
      • 225 Implement Stack using Queues
      • L362 Sliding Window Maximum
      • 439 Ternary Expression Parser
      • 20 Valid Parentheses
      • 155 Min Stack
      • 150 Evaluate Reverse Polish Notation
      • L495 Implement Stack
      • L492 Implement Queue by Linked LIst
      • L493 Implement Queue by Linked List II
      • 232 Implement Queue using Stacks
      • L229 Stack Sorting
      • L224 Implements Three Stacks by Singly Array
      • 71 Simplify Path
      • 32 Longest Valid Parentheses
      • 379 Design Phone Directory
      • L643 Longest Absolute File Path (388)
      • 716 Max Stack
      • 609 Find Duplicate File in System
    • 23 Heap
      • 1337 The K Weakest Rows in a Matrix
      • 1675 Minimize Deviation in Array
      • 1329 Sort the Matrix Diagonally
      • 407 Trapping Rain Water II
      • L81 Data Stream Median
      • L360 Sliding Window Median
      • L130 Hepify
      • 378 Kth Smallest Element in a Sorted Matrix
      • L465 Kth Smallest Sum In Two Sorted Arrays
      • L471 Top K Frequent Words
      • 347 Top K Frequent Elements
      • L131 Building Outline
      • 218 The Skyline Problem
      • 373 Find K Pairs with Smallest Sums
      • 703 Kth Largest Element in a Stream
      • 692 Top K Frequent Words
      • 743 Network Delay Time
    • 24 Union Find (Disjoint Set)
      • L589 Connecting Graph
      • L590 Connecting Graph II
      • L591 Connecting Graph III
      • L137 Graph Valid Tree
      • L432 Find Weak Connected Component in the Directed Graph
      • 305 Number of Island II
      • L629 Minimum Spanning Tree
      • 547 Friend Circles
    • 25 Trie and N-ary Tree
      • 1506 Find Root of N-Ary Tree
      • L559 Trie Service
      • L442 Implement Trie
      • L527 Trie Serialization
      • L473 Add and Search Word
      • L132 Word Search II
    • 26 Tree
      • 1257 Smallest Common Region
      • 617 Merge Two Binary Trees
      • L628 Maximum Subtree
      • 1022 Sum of Root To Leaf Binary Numbers
      • 623 Add One Row to Tree
      • 1245 Tree Diameter
      • 690 Employee Importance
      • 1379 Find a Corresponding Node of a Binary Tree in a Clone of That Tree
      • 938 Range Sum of BST
      • 222 Count Complete Tree Nodes
      • L467 Complete Binary Tree
      • 173 Binary Search Tree Iterator
      • 230 Kth Smallest Element in a BST
      • 100 Same Tree
      • L470 Tweaked identical Binary Tree
      • 101 Symmetric Tree
      • 98 Valid Binary Search Tree
      • 255 Verify Preorder Sequence in BST
      • 226 Invert Binary Tree
      • 110 Balanced Binary Tree
      • 99 Recover Binary Search Tree
      • 156 Binary Tree Upside Down
      • 102 Binary Tree Level Order Traversal
      • 107 Binary Tree Level Order Traversal II
      • 103 Binary Tree Zigzag Level Order Traversal
      • L242 Convert Binary Tree to Linked Lists by Depth
      • 104 Maximum Depth of Binary Tree
      • L155 Minimum Depth of Binary Tree
      • 235 Lowest Common Ancestor of a BST
      • 236 Lowest Common Ancestor of a Binary Tree
      • L474 Lowest Common Ancestor II
      • L578 Lowest Common Ancestor III
      • 297 Serialize and Deserialize Binary Tree
      • 270 Closest Binary Search Tree Value
      • 257 Binary Tree Paths
      • 366 Find Leaves of Binary Tree
      • L11 Search Range in Binary Search Tree
      • 199 Binary Tree Right Side View
      • 116 Populating Next Right Pointers in Each Node
      • 108 Convert Sorted Array to Binary Search Tree
      • 449 Serialize and Deserialize BST
      • L126 Max Tree
      • L472 Binary Tree Path Sum III
      • L246 Binary Tree Path Sum II
      • 112 Path Sum
      • 113 Path Sum II
      • 437 Path Sum III
      • 129 Sum Root to Leaf Numbers
      • L475 Binary Tree Maximum Path Sum II
      • L94 Binary Tree Maximum Path Sum
      • 298 Binary Tree Longest Consecutive Sequence
      • L614 Binary Tree Longest Consecutive Sequence II
      • L619 Binary Tree Longest Consecutive Sequence III
      • 117 Populating Next Right Pointers in Each Node II
      • 404 Sum of Left Leaves
      • L597 Subtree with Maximum Average
      • L596 minimum Subtree
      • 501 Find Mode in Binary Search Tree
      • 333 Largest BST Subtree
      • 508 Most Frequent Subtree Sum
      • 250 Count Univalue Subtrees
      • 513 Find Bottom Left Tree Value
      • 515 Find Largest Value in Each Tree Row
      • L245 Subtree
      • L375 Clone Binary Tree
      • 337 House Robber III
      • 96 Unique Binary Search Tree
      • 538 Convert BST to Greater Tree
      • 536 Construct Binary Tree from String
      • Serilization and Deserialize n-ary Tree
      • 543 Diameter of Binary Tree
      • 105 Construct Binary Tree from Preorder and Inorder Traversal
      • 106 Construct Binary Tree form Inorder and Postorder Traversal
      • 652 Find Duplicate Subtrees
      • 285 Inorder Successor in BST
      • 450 Delete Node in a BST
      • 272 Closest Binary Search Tree Value II
      • 671 Second Minimum Node In a Binary Tree
      • 814 Binary Tree Pruning
      • 669 Trim a Binary Search Tree
      • 95 Unique Binary Search Trees II
      • 510 Inorder Successor in BST II
      • 545 Boundary of Binary Tree
      • 563 Binary Tree Tilt
      • 582 Kill Process
    • 27 Segment Tree or BIT
      • Segment Tree
      • Binary Index Tree （Fenwick Tree）
      • 315 Count of Smaller Numbers After Self
      • 493 Reverse Pairs
      • 1649 Create Sorted Array through Instructions
      • 308 Range Sum Query 2D - Mutable
      • 307 Range Sum Query - Mutable
    • 28 Hash Table or Set
      • 2395 Find Subarrays With Equal Sum
      • 760 Find Anagram Mappings
      • 389 Find the Difference
      • 1198 Find Smallest Common Element in All Rows
      • 1394 Find Lucky Integer in an Array
      • 1133 Largest Unique Number
      • 1461 Check If a String Contains All Binary Codes of Size K
      • 575 Distribute Candies
      • 1165 Single-Row Keyboard
      • 709 To Lower Case
      • 987 Vertical Order Traversal of a Binary Tree
      • 1657 Determine if Two Strings Are Close
      • 1640 Check Array Formation Through Concatenation
      • L389 Valid Sudoku
      • 314 Binary Tree Vertical Order Traversal
      • 49 Group Anagrams
      • 242 Valid Anagram
      • 451 Sort Characters By Frequency
      • L129 Rehashing
      • L128 Hash Function
      • 205 Isomorphic Strings
      • 290 Word Pattern
      • 128 Longest Consecutive Sequence
      • 249 Group Shifted Strings
      • 383 Ransom Note
      • 358 Rearrange String k Distance Apart
      • 525 Contiguous Array
      • 187 Repeated DNA Sequences
      • Rearrange chars in string such that no 2 adjacent are the same
      • 217 Contains Duplicate
      • 219 Contains Duplicate II
      • 220 Contains Duplicate III
      • 599 Minimum Index Sum of Two Lists
      • 387 First Unique Character in a String
      • 771 Jewels and Stones
      • 767 Reorganize String
      • 819 Most Common Word
      • Pramp - Getting a Different Number
    • 29 Search(dfs) and BackTrack
      • 37 Sudoku solver
      • 51 N_Queens
      • 52 N_Queens II
      • 140 Word Break II
      • 131 Palindrome Partitioning
      • 79 Word Search
      • 351 Android Unlock Patterns
      • 291 Word Pttern II
      • 211 Add and Search Word - Data structure Design
      • 22 Generate Parentheses
      • 93 Restore IP Addresses
      • 282 Expression Add Operators
      • 425 Word Squares
      • 698 Partition to K Equal Sum Subsets
    • 30 DFS (recursion)
      • L22 Flatten List
      • L601 Flatten 2D Vector
      • L528 Flatten Nested List Iterator
      • 339 Nested List Weight Sum
      • 364 Nested List Weight Sum II
      • 394 Decode String
      • 385 Mini Parser
      • 430 Flatten a Multilevel Doubly Linked List
    • 31 Bit Manipulation
      • 751 IP to CIDR
      • 1310 XOR Queries of a Subarray
      • 477 Total Hamming Distance
      • 461 Hamming Distance
      • 191 Number of 1 bits
      • 231 Power of Two
      • 136 Single Number
      • 137 Single Number II
      • 260 Single Number III
      • L824 Single Number IV
    • 32 String
      • 58 Length of Last Word
      • 806 Number of Lines To Write String
      • 953 Verifying an Alien Dictionary
      • 1704 Determine if String Halves Are Alike
      • 524 Longest Word in Dictionary through Deleting
      • 821 Shortest Distance to a Character
      • 1662 Check If Two String Arrays are Equivalent
      • 468 Validate IP Address
      • 6 ZigZag Conversion
      • 14 Longest Common Prefix
      • L637 Valid Word Abbreviation
      • 527 Word Abbreviation
      • L659 Encode and Decode Strings
      • 288 Unique Word Abbreviation
      • 443 String Compression & ctci189 1 point 6 String Compression
    • 33 单调栈
      • 1673 Find the Most Competitive Subsequence
      • 84 Largest Rectangle in Histogram
      • 402 Remove K Digits
      • 316 Remove Duplicate Letters
      • 739 Daily Temperatures
    • 34 贪心 Greedy
      • 1005 Maximize Sum Of Array After K Negations
      • 452 Minimum Number of Arrows to Burst Ballons
      • 946 Validate Stack Sequences
      • 134 Gas Station
      • 1663 Smallest String With A Given Numeric Value
    • 35 Arrays
      • 1887 Reduction Operations to Make the Array Elements Equal
    • other
      • hankerrank Data Updates
      • 755 Pour Water
      • 1304 Find N Unique Integers Sum up to Zero
      • 1118 Number of Days in a Month
      • 284 Peeking Iterator
      • 594 Longest Harmonious Subsequence
      • 1629 Slowest Key
      • 985 Sum of Even Numbers After Queries
      • 1646 Get Maximum in Generated Array
      • 667 Beautiful Arrangement II
      • 277 Find the Celebrity
      • L540 Zigzag Iterator
      • L541Zigzag Iterator II
      • 289 Game of Life
      • 161 One Edit Distance
      • 459 Repeated Substring Pattern
      • 38 Count and Say
      • 4 Median of Two Sorted Arrays
      • 157 Read N Characters Given Read4
      • 158 Read N Characters Given Read4 II - Call multiple times
      • 398 Random Pick Index
      • 68 Text Justification
      • 165 Compare Version Numbers
      • 412 fizz buzz
      • 605 Can Place Flowers
      • 796 Rotate String
        • Find Median in super big array
    • Design
      • L134 LRU
      • 355 Design Twitter
      • 460 LFU
      • 380 Insert Delete GetRandom O 1
      • 381 Insert Delete GetRandom O 1 Duplicates allowed
      • 535 Encode and Decode TinyURL
      • L234 Webpage Crawler
      • L231 Typeahead
      • L555 Counting Bloom Filter
      • L556 Standard Bloom filter
      • 432 All O one Data Structure
      • L215 Rate Limiter
      • 359 Logger Rate Limiter
      • 362 Design Hit Counter
      • 348 Design Tic-Tac-Toe
      • L529 GeoHash
      • L530 Geohash II
      • L526 Load Balancer
      • 707 Design Linked List
      • 622 Design Circular Queue
      • 794 Valid Tic-Tac-Toe State
    • 面经
      • 对角线打印矩阵
      • edit distance to palindrome
      • Equilibrium index of an array
      • BigInt sub
      • xml parser
      • Weighted ramdom sampling
      • csv parser
      • password generate according to list
      • Forward backward slash sperated squares
      • gift wrapping algorithm
      • file access
  • 公司
    • Time line
    • Amazon 2017-04
    • Snapchat 2017-04
    • Uber 2017 -06
    • Facebook 2017-06
    • Microsoft 2017-07
    • LinkedIn 2019 -01
    • Micorsoft 2019-02
    • JPMorgan 2019-02
    • Cisco 2019-02
    • Dropbox 2019-02
    • Yahoo 2019-02
    • VMware 2019-02
    • Airbnb 2019-02
    • TikTok
  • Templates
    • 1 Sorting模板
    • 2 2分template
    • 3 树的模板
    • 4 链表基础模板
    • 5 去重基本方法
    • 6 其他常用snipets
    • 8 clarify questions
    • 9 Bit Manipulation 常用公式
    • 10 Common Complexities
    • 11 OOD
    • 12 System Design
      • Grokking Modern System Design Interview notes
        • 关于怎么prepare
      • 关于db
      • 关于estimation
      • General Concepts
        • 其他有待展开
        • Reactive pattern（Reactive Spring）
        • GraphQL
        • Config Management
        • Observability
          • 关于tracing
        • OpenApi - swagger
        • Service Mesh
      • 具体系统
        • Delay Schedule
        • 倒排索引
        • Rate limiter + Datadog
        • Bloom Filter + Count-min sketch
        • Distributed DB bigtable
        • Distributed File System(HDFS/GFS)
        • web crawler
        • TinyURL
        • 设计linkedIn显示几度关系
        • News feed
        • 用户系统设计
        • 设计Memcache + 少少redis相关信息
        • 设计whatsapp chatting
        • typeahead
    • 13 Testing
    • 14 other notes
    • 15 常用数学运算
    • 16 Other stuffs
    • 17 Questions to company
    • 18 Restful Webservices
    • 19 Network stuff
    • 20 Behavior Questions
    • 21 Java 语法注意点
      • String
Powered by GitBook
On this page

Was this helpful?

  1. My Notes

12 graph （BFS）

Previous377 Combination Sum IVNext994 Rotting Oranges

Last updated 2 years ago

Was this helpful?

这里主要是讲些图相关的bfs和dfs题，还有就是topological sort了。bfs主要就是用个Queue，dfs就是递归搜索了。BFS的时间复杂度都是O(m+n)，m是边数，n是点数

技巧：

  1. 如果是矩阵的话可以用 i * m + j来避免用pair class

  2. 上面那个其实很难记住，某次pramp的时候，某亚洲面孔小哥哥，指了条名路。可以用int[] .Queue<int[]> q = new LinkedList<>(); q.add(new int[]{i, j});

  3. 搜的时候可以考虑用direction matrix， int[] x = {0, 0, 1, -1}, int[] y = {1, -1, 0, 0}，然后loop k 从 0 -- 4

  4. 如果是扫雷那样8个方向的话，用这个

        int[] x = {0, 0, -1, 1, 1, 1, -1, -1};
    int[] y = {-1, 1, 0, 0, 1, -1, 1, -1};

BFS / DFS :

- 也可以用union find来做&DFS (130)

(L433) - BFS/DFS/Union Find

-- 跟几乎一样，还是bfs/dfs/union find都能解

- 还可以用bfs，不过2分比较好 (L600)

--与有点关系

399 Evaluate Division

417 Pacific Atlantic Water Flow

490 The Maze

505 The Maze II

499 The Maze III

332 Reconstruct Itinerary

Special BFS node：

Topological Sort:

曼哈顿距离:

296 Best Meeting Point

other related：

407 Trapping Rain Water II -- heap

(L573 Build Post Office II)

- can use bfs or dfs or union find as well （求联通块里具体有什么node） (323 Number of Connected Components in an Undirected Graph -- 求联通块个数)

-- dfs

-- dfs / union find

- bfs with backtrack, Uber

-- Dijkstra （BFS）

-- 还有dp解法

-- 之前是用背包解，然后数学解法是四平方定理，然后还能递归，还有另一种DP解法。太高级，有空再补

(L120)

(L121)

-- 变体

(L615)

(L616)

(L605)

(L434) - Union Find

-- Union Find

-- similar to 296 Best Meeting Point, 这题不一定有解，所以不能用296的方法-- 曼哈顿距离

L477 Surrounded Regions
200 Number of Islands
695 Max Area of Island
200 Number of Islands
694 Number of Distinct Islands
711 Number of Distinct Islands II
302 Smallest Rectangle Enclosing Black Pixels
133 Clone Graph
138 Copy LIst with Random Pointer
301 Remove Invalid Parentheses
286 Walls and Gates
317 Shorest Distance from All Buildings
L531 Six Degrees
L431 Connected Component in Undirected Graph
L618 Search Graph nodes
L611 Knight Shortest Path
L598 Zombie in Matrix
994 Rotting Oranges
529 Minesweeper
785 Is Graph Bipartite
Detect Cycle in directed graph
Detect Cycle in undirected graph
419 Battleships in a Board
PrintShortestPath
743 Network Delay Time
1631 Path With Minimum Effort
542 01 Matrix
1091 Shortest Path in Binary Matrix
733 Flood Fill
279 Perfect Squares
127 Word Ladder
126 Word Ladder II
752 Open the Lock
127 Word Ladder
L127 Topological Sort
269 Alien Dictionary
207 Course Schedule
210 Course Schedule II
444 Sequence Reconstruction
310 Minimum Height Trees
573 Squirrel Simulation
305 Number of Island II
L432 Find Weak Connected Component in the Directed Graph
L574 Build Post Office