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

21 DP

PreviousL581 Longest Repeating SubsequenceNext1235 Maximum Profit in Job Scheduling

Last updated 2 years ago

Was this helpful?

所有dp都能用记忆化搜索，只是用那个的话难做空间优化。在初始状态难找或状态转移麻烦的时候，我们可以从大到小用memorization。

如果是求可行与否，最大/最小值，方案总数之类的很有可能是DP。

  • 动归的时间计算：状态个数 × 每个状态要用的时间

  • 感觉这几个dp的格局有点，jump game，LIS，work break，palindrome min cut。两个循环，外层枚举i，内层j从0找到i，边找边更新。

  • dp空间优化可以用%来做，如果只需要2行的话，我们可以用i%2来优化空间。

所谓“划分类” DP，是指给定原数组之后，将其划分为k个子数组，使其sum / product最大/最小的DP类问题。

而这类问题的optimal substructure是，对于给定区间的globalMax，其最优解一定由所属区间内的localMax区间组成，可能不连续。以“必须以当前结尾”来保证local子问题之间的连续性；用global来记录最优解之间可能的不连续性。

划分类DP与区间类DP主要区别在于，我们只取其中k段，而中间部分可以留空；而区间类DP子问题之间是连贯而不留空的。区间类DP是记忆化的divide & conquer,划分类DP则是不连续subarray的组合，不同于区间类DP每一个区间都要考虑与计算，划分类DP很多元素和子区间是可以忽略的，有贪心法的思想在里面，因此也依赖于正确的local / global结构来保证算法的正确性。

摘自：

简单的DP：

坐标型：状态表示dp[i]/dp[i][j]为第i个，从起点走到那个位置

(L110)

-- fibonacci (L111)

-- fibonacci

(L114)

L631 Maximal Square II

单序列型：状态表示dp[i]为前i个位置/数字/字符，通常要加一，dp[0]前0个

双序列型：dp[i][j]表示第一个的前i个与第二个的前j个

博弈类：靠人品来画搜索树来解决

292 Nim Game

MiniMax :

375 Guess Number higher or Lower II

464 Can I Win

区间类：大区间依赖于小区间，按区间来枚举；也可以记忆化搜索不用考虑顺序

-------- 什么时候适合repeat的方法来做呢？规模为n的问题可以在链上做，变成环以后，求环的各种断开方式里最好的一种

L435 Post Office Problem

划分类：

背包类：

L89 k Sum

L91 Minimum Adjustment Cost

貌似做了未分类：

95 Unique Binary Search Tree II -- 搜索

343 Integer Break

其他类？

ip address 那题跟work break有点像，work break又跟min cut palindrome有点像。

L20 Dices Sum

363 Max Sum of Rectangle No Larger Than K

321 Create Maximum Number (L552)

376 Wiggle Subsequence

446 Arithmetic Slices II - Subsequence

418 Sentence Screen Fitting -- memorization (MIT course)

474 Ones and Zeros

466 Count The Repetitions

489 Predict the Winner

467 Unique Substrings in Wraparound String

471 Encode String with Shortest Length

472 Concatenated Words

338 Counting Bits -- Bit manipulation

other related:

L90 k Sum II - DFS

L623 K Edit Distance

L518 Super Ugly Number (313)

(L115)

(L436)

(L76)

-- L300变形 (L602)

-- L300变形 (L603)

-- weighted interval scheduling problem L300变形

-- 这题好像354，但其实更像meeting room

-- 继续变

-- memorization (329 Longest Increasing Path in a Matrix) <--听说还能topo sort来做

(L622) -- hm做dp

-- hm做dp

(L107)

-- min cut (132)

(L152)

(L392) -- cc17.16

-- (L534) 破环：1. repeat算区间， 2.断开算两边

-- (L119) 相关但解决方法不同。edit distance终极版本是snapchat面经edit distance to palindrome突然發現Leetcode有了

-- 是這題的edit one版本，不過比較像2ptr的解法，雖然我用了递归。

(L118)

(L29)

(L192)

(L154)

(168)

(L430)

-- 破环， 用repeat的方法

-- 加起来除以2，然后求背包容量就是那个avg值

-- DP

(L191)

-- DP, Catalan number (L163)

(L4)

-- can use stack

(L514)

- 也可以二分答案，我也只会二分

- 也可以二分答案，我也只会二分

-- 也可以二分答案，我也只会二分

-- 什么鬼自动机，也可以用二分

(L136) -- search

--(L582) search

(L510) --

(263)

https://mnmunknown.gitbooks.io/algorithm-notes/content/626,_dong_tai_gui_hua_ff0c_subarray_lei.html
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
174 Dungeon Game
221 Maximal Square
300 Longest Increasing Subsequence
354 Russian Doll Envelopers
368 Largest Divisible Subset
meeting room 3
1235 Maximum Profit in Job Scheduling
334 Increasing Triplet Subsequence
L116 Jump Game
L117 Jump Game II
L398 Longest Increasing Continuous Subsequence II
403 Frog Jump
494 Target Sum
139 Word Break
L108 Palindrome Partitionaing II
91 Decode Ways
198 House Robber
213 House Robber II
413 arithmetic Slices
L77 Longest Common Subsequence
L79 Longest Common SubString
72 Edit Distance
161 One Edit Distance
1216 Valid Palindrome III
680 Valid Palindrome II
115 Distinct Subsequences
97 Interleaving String
L581 Longest Repeating Subsequence
44 Wildcard matching
10 Regular Expression Matching
L395 Coins in Line II
L394 Coins in Line
312 Burst Ballons
L396 Coins in line III
87 Scramble String
L476 Stone Game
L593 Stone Game II
188 Best Time to Buy and Sell Stock IV (L393)
L43 Maximum Subarray III
BackPacks
416 Partition Equal Subset Sum
L584 Drop Eggs II
152 Maximum Product Subarray
96 Unique Binary Search Tree
264 Ugly Number II
32 Longest Valid Parentheses
256 Paint House
265 Paint House II
276 Paint Fence
361 Bomb Enemy
392 Is Subsequence
516 Longest Palindromic Subsequence
5 Longest Palindromic Substring
494 Target Sum
1641 Count Sorted Vowel Strings
750 Number Of Corner Rectangles
L437 copy books I
L438 copy books II
410 Split Array Largest Sum
517 Super Washing Machines
L194 Find Words
131 Palindrome Partitioning
140 Word Break II
85 Maximal Rectangle
histogram
L517 Ugly Number