ladder_code
  • Introduction
  • Meta 2024
    • The Sum of Legal Set
    • 有效回文串(二)
    • 寻找峰值
    • 最短路径
    • 删除无效的括号
    • 单词搜索
    • 最大的交换
    • 使括号有效的最少添加
    • 二叉树垂直遍历
    • 子树
    • 贴纸拼单词
    • 岛屿的个数II
    • 嵌套列表的加权和II
    • 前K个高频元素
    • Check if an Original String Exists Given Two Encoded Strings
    • 对角线遍历
    • 移动零
    • 单词拆分(一)
  • Python code cheatsheet
  • knowledge base
    • 模板
  • Wish
    • Sudoku Solver
  • BB
    • Convert Sorted List to Binary Search Tree
  • Math
    • GCD
  • Monotonic Queue/Stack
    • Online Stock Span
    • Daily Temperatures
    • Shortest Subarray with Sum at Least K
  • Wish
    • Get Relations
  • braze OA
  • Twilio
    • Subarray Sums Divisible by K
  • Expedia oa
    • Construct Binary Search Tree from Preorder Traversal
    • Valid Triangle Number
    • String Compression
  • Gusto
  • Twitter OA
    • view path
    • Reaching Points
    • Paint House
    • Palindromic Substrings
    • K-diff Pairs in an Array
    • Parking Dilemma
    • Partitioning Array
    • Balanced Sales Array
    • Unique Twitter User Id Set
  • MS
    • Odd Even Linked List
    • Plus One Linked List
    • Max Stack
    • Design Log Storage System
    • Longest Common Prefix
    • Bulb Switcher
    • Populating Next Right Pointers in Each Node
    • Valid Tic-Tac-Toe State
    • Sort List
    • Remove K Digits
    • Design Tic-Tac-Toe
    • Find the Celebrity
    • Spiral Matrix
    • Majority Element II
    • Convert a Number to Hexadecimal
      • Compare Version Numbers
    • Squares of a Sorted Array
    • Binary Search Tree to Greater Sum Tree
    • Encode and Decode TinyURL
  • Graph and Search
  • Binary Search and Sorted Array
    • Find Minimum in Rotated Sorted Array
    • Find Minimum in Rotated Sorted Array II
    • Search in Rotated Sorted Array
    • Search in Rotated Sorted Array II
    • Find Peak Element
    • Recover Rotated Sorted Array
    • Rotate String
    • Implement Queue using Stacks
  • Data Structure
    • Max Tree
    • Queue Reconstruction by Height
  • High Frequency
    • Single Number
    • Single NumberII
    • Single Number III
    • 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
    • Maximum Subarray
    • Maximum Subarray II
    • Maximum Subarray III
    • 2 Sum
    • 3 Sum
    • 4 Sum
    • k Sum I&II
    • 3Sum With Multiplicity
    • 3 Sum Closest
    • 3Sum Smaller
    • Best Time to Buy and Sell Stock with Cooldown
  • 练习
    • Happy number
    • Untitled
    • Find K Closest Elements
    • Text Justification
    • Group Anagrams
    • Maximal Rectangle
    • Number Complement
    • Maximum XOR of Two Numbers in an Array
    • Reconstruct Original Digits from English
    • Longest Repeating Character Replacement
    • Minimum Genetic Mutation
    • Non-overlapping Intervals
    • Find Right Interval
    • Find All Duplicates in an Array
    • My Calendar III
    • Minimum number of Parentheses to be added to make it valid
    • Merge Two Sorted Lists
    • Merge k Sorted Lists
    • Path Sum
    • Median of Two Sorted Arrays
    • Pascal's Triangle
    • Best Time to Buy and Sell Stock
    • Decode String
    • Valid Sudoku
    • Flatten Nested List Iterator
    • Game of Life
    • Radius_union find_same name
    • Find Median from Data Stream
    • Max Points on a Line
    • Lexicographical Numbers
  • Dropbox
    • Data Stream as Disjoint Intervals
    • Word Pattern
    • My Calendar I
    • Grid Illumination
    • Design Phone Directory
    • Design Hit Counter
    • Minimize Malware Spread
    • Find Duplicate File in System
  • DFS
    • Word Search
    • Path Sum II
    • Validate Binary Search Tree
    • Binary Tree Paths
    • Binary Tree Right Side View(FB)
    • Combination Sum I(可重复取)
    • Combination Sum II(只取一次)
    • Combination Sum III(取单个,限制个数)
    • Graph Valid Tree
    • Longest Increasing Path in a Matrix
    • Number of Connected Components in an Undirected Graph(UF and DFS)
    • Nested List Weight Sum
    • Pacific Atlantic Water Flow
    • Nested List Weight Sum II
    • Find Leaves of Binary Tree
    • Ternary Expression Parser
    • Sentence Similarity II
    • Number of Distinct Islands II
    • Number of Distinct Islands
    • Lonely Pixel I
    • Lonely Pixel II
    • The Maze
    • The Maze II
    • The Maze III
    • Reconstruct Itinerary
    • Flatten a Multilevel Doubly Linked List
    • Matchsticks to Square
    • Increasing Subsequences
    • Find Bottom Left Tree Value
    • Find Largest Value in Each Tree Row
    • 01 Matrix(DP)
    • Friend Circles
    • Out of Boundary Paths
    • Shopping Offers
    • Max Area of Island
    • Network Delay Time
    • Pyramid Transition Matrix
    • Find Eventual Safe States
    • Keys and Rooms
    • Loud and Rich
    • All Nodes Distance K in Binary Tree
    • Possible Bipartition
    • Shortest Bridge
    • Most Stones Removed with Same Row or Column
    • Regions Cut By Slashes
    • Flip Binary Tree To Match Preorder Traversal
    • Distribute Coins in Binary Tree
    • Binary Tree Cameras
    • Sum of Distances in Tree
    • Smallest String Starting From Leaf
    • Number of Enclaves
    • Maximum Difference Between Node and Ancestor
    • Coloring A Border
    • Minesweeper
    • All Paths from Source Lead to Destination
    • Lexicographically Smallest Equivalent String
    • Maximum Depth of N-ary Tree
    • Employee Importance
    • Flood Fill
    • Leaf-Similar Trees
    • Increasing Order Search Tree
  • sweep line & interval
    • embold html
    • Number of Airplanes in the Sky(sweep line)
    • Minimum Number of Arrows to Burst Balloons
  • 强化2(Union Find, Trie, sweep line)
    • Connecting Graph I II III
    • Number of Islands
    • Implement Trie
    • Word Search II
    • Add and Search Word
    • Number of Islands
    • Friend Circle
    • AutoComplete
  • 强化3(data structure II)
    • Trapping Rain Water II
    • Trapping Rain Water
    • Building Outline
    • Sliding Window Maximum
    • Swim in Rising Water
    • Valid Parentheses(stack)
  • 强化4(双指针)
    • 验证二叉查找树
    • 二叉树中的最大路径和
    • 将二叉搜索树转换为已排序的双向链接列表
    • 整数排序 II - quick_sort and merge_sort
    • 合并排序数组(简单版)
    • 最长回文串
    • 和相同的二元子数组
    • 两数之和 VII
    • Substring with Concatenation of All Words
    • No k consecutive repeated char
    • Triangle Count
    • Container With Most Water
    • Nuts & Bolts Problem
    • Partition Array
    • Sort Colors
    • Partition Array by Odd and Even
    • Valid Palindrome
    • Wiggle Sort II
    • Kth Largest Element
    • Kth Smallest Number in Sorted Matrix
    • Longest Substring Without Repeating Characters
    • Minimum Window Substring(FB 模板)
    • Minimum string array coverage
    • Longest Substring with At Most K Distinct Characters(模板)
    • Longest Substring with At Least K Repeating Characters(区别)
    • Is Subsequence
    • Window Sum(sliding window)
    • Longest Substring with At Most Two Distinct Characters(map)
    • Find the Duplicate Number
    • Reverse Vowels of a String
    • Intersection of Two Arrays II
    • Sort Transformed Array
    • Sliding Window Maximum
    • Find All Anagrams in a String(类似Minimum Window Substring)
    • Repeated DNA Sequences
    • strStr
    • Longest Repeating Character Replacement
    • Longest Word in Dictionary through Deleting
    • Max Consecutive Ones II
    • K-diff Pairs in an Array
    • Permutation in String
    • Smallest Range
    • Subarray Product Less Than K
    • Candy Crush
    • Partition Labels
    • Most Profit Assigning Work
    • Unique Letter String
    • Push Dominoes
    • Backspace String Compare
    • Longest Mountain in Array
    • Boats to Save People
    • Long Pressed Name
    • Squares of a Sorted Array
    • Interval List Intersections
    • Subarrays with K Different Integers
    • Max Consecutive Ones III
    • two sum 集合
      • 两数之和 VII
      • 和相同的二元子数组
  • amz oa
    • Find All Anagrams in a String
    • Cut Off Trees for Golf Event
    • Most Common Word
    • Max Pair双指针
    • Aerial Movie(双指针,2sum)
    • Least Substring
    • Number of restaurants双指针
    • K-Substring with K different characters(sliding window)
    • BST Node Distance(递归和树)
    • K Closest Points(sort)
    • Tree problem(Tree & Graph)
    • Reorder Log Files
  • 强化7(DP)
    • Coin Change 2
    • Backpack II
    • House Robber
    • House Robber III
    • House Robber II
  • 强化8 matrix
    • Submatrix Sum
    • Find Peak Element II
    • Subarray Sum II
    • Sliding Window Matrix Maximum
    • Build Post Office
    • Build Post Office II
  • L1_字符串,子集,排列
    • subsets
    • Subsets II
    • Permutations
    • Permutations II
    • Reverse Words in a String
    • Rotate String
    • Repeated Substring Pattern
  • L2_二分查找
    • Search a 2D Matrix II
    • Classical Binary Search
    • First Position of Target
    • Sqrt(x)
    • search a 2D matrix
    • Search Insert Position
    • Count of Smaller Numbers After Self
    • Search for a Range
    • First Bad Version
    • Search in a Big Sorted Array
    • Find Minimum in Rotated Sorted Array
    • Search in Rotated Sorted Array
    • Find Peak Element
    • Recover Rotated Sorted Array
    • Rotate String
    • 在排序数组中找最接近的K个数
    • 书籍复印
  • L3_二叉树和分治法
    • BST中第K小的元素
    • Binary Tree Preorder Traversal
    • Binary Tree Inorder Traversal
    • Binary Tree Postorder Traversal
    • Maximum Depth of Binary Tree
    • Balanced Binary Tree
    • Lowest Common Ancestor of a Binary Search Tree
    • Binary Tree Maximum Path Sum II
    • Binary Tree Level Order Traversal(dfs,bfs,python)
    • Binary Tree Level Order Traversal II
    • Binary Tree Zigzag Level Order Traversal
    • Validate Binary Search Tree
    • Inorder Successor in Binary Search Tree(中序后继)
    • Binary Search Tree Iterator
    • Search Range in Binary Search Tree
    • Sum Root to Leaf Numbers(recrusive)
    • Kth Smallest Element in a BST
  • L4_动态规划
    • Triangle
    • Longest Consecutive Sequence
    • Minimum Path Sum
    • Unique Paths
    • Climbing Stairs
    • Jump Game
    • Jump Game II
    • Unique Paths II
    • Longest Increasing Subsequence(FB 区间DP)
    • Palindrome Partitioning
    • Palindrome Partitioning II
    • Word Break
    • Longest Common Subsequence
    • Edit Distance
    • Distinct subsequences
    • Interleaving String
    • Maximum Product Subarray
    • Min Cost Climbing Stairs(sequence dp)
    • Decode Ways
    • Ugly Number II
    • Perfect Squares
    • Coin Change
    • Counting Bits
    • Integer Break
    • Count Numbers with Unique Digits
    • Largest Divisible Subset
    • Guess Number Higher or Lower II
    • Burst Balloons
    • Wiggle Subsequence
    • Partition Equal Subset Sum
    • Can I Win
    • Predict the Winner
    • Unique Substrings in Wraparound String
    • Ones and Zeroes
    • Longest Palindromic Subsequence
    • Maximum Length of Pair Chain
    • 2 Keys Keyboard
    • Knight Probability in Chessboard
    • Partition to K Equal Sum Subsets
    • Minimum ASCII Delete Sum for Two Strings
    • Maximum Length of Repeated Subarray
    • House Robber
    • Delete and Earn
    • Cheapest Flights Within K Stops
    • Bomb Enemy
    • 4 Keys Keyboard
    • Campus Bikes II
    • Soup Servings
    • Largest Sum of Averages
    • New 21 Game
    • Length of Longest Fibonacci Subsequence
    • Stone Game
    • Bitwise ORs of Subarrays
    • Minimum Falling Path Sum
    • Knight Dialer
    • Numbers With Same Consecutive Differences
    • Longest Turbulent Subarray
    • Minimum Cost For Tickets
    • Video Stitching
    • Longest Arithmetic Sequence
    • Minimum Score Triangulation of Polygon
    • Longest String Chain
    • Last Stone Weight II
    • Unique Binary Search Trees II
    • Filling Bookcase Shelves
    • Partition Array for Maximum Sum
    • Dungeon Game
    • Russian Doll Envelopes
    • 526. Beautiful Arrangement
    • 403. Frog Jump
  • L6_链表(快慢指针)
    • Median of LinkedList
    • remove duplicates from sorted list II
    • reverse linked list II
    • partition list
    • sort list
    • reorder list
    • Linked list cycle
    • rotate list
    • Merge k sorted list
    • copy list with random pointer
    • Remove Nth Node From End of List
    • Linked List cycle
    • Intersection of Two Linked Lists
  • L7_数组
    • Merge Sorted Array
    • Merge Two Sorted Arrays II
    • Median of Two Sorted Arrays
    • 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
    • Shortest Distance to a Character
    • Binary Subarrays With Sum
    • Sentence Screen Fitting
    • Number of Matching Subsequences
    • Minimize Rounding Error to Meet Target
    • Maximum Size Subarray Sum Equals k
  • L8_数据结构
    • Min Stack
    • Largest Rectangle in Histogram
    • Implement Queue by Two Stacks
    • Rehashing
    • Median
    • Ugly Number
  • L9_图和搜索(拓扑,DFS,BFS)
    • 因式分解
    • 01 矩阵
    • Clone Graph
    • Topological Sorting
    • N-Queens
    • Combination Sum
    • Combination Sum II
    • Word Ladder
    • Word Ladder II
    • Course Schedule
  • Indeed
    • Product of Array Except Self
    • Minimum Size Subarray Sum
    • Graph Valid Tree(union find)
    • Walls and Gates(反向BFS)
    • Course Schedule(拓扑)
    • Course Schedule II
    • Course Schedule III(heap,sort)
    • Word Search(dfs)
    • Meeting room(sweep line)
    • Meeting room II(sweep line)
  • Amazon
    • Design Search Autocomplete System
    • Unique Email Addresses
    • Split BST
  • facebook
    • Number Of Corner Rectangles(排列组合公式)
    • Smallest Subtree with all the Deepest Nodes(树,分治法)
    • Friends Of Appropriate Ages(数学逻辑
    • Goat Latin(String)
    • Minimum Swaps To Make Sequences Increasing(动归
    • Is Graph Bipartite(BFS和DFS)
    • Letter Case Permutation(DFS)
    • Largest Plus Sign(DP)
    • Prefix and Suffix Search(Trie)
    • Accounts Merge(Union Find)
    • Best Time to Buy and Sell Stock with Transaction Fee(greddy, dp)
    • Maximum Sum of 3 Non-Overlapping Subarrays(dp)
    • Valid Palindrome II(dfs带while循环)
    • Longest Continuous Increasing Subsequence(dp)
    • Number of Longest Increasing Subsequence(dp)
    • Maximum Swap
    • Two Sum IV - Input is a BST(bfs+set)
    • Palindromic Substrings(dp)
    • Design Search Autocomplete System (trie)
      • 带大写小写的auto complete
    • Decode Ways II(dp)
    • Average of Levels in Binary Tree(BFS Tree)
    • Exclusive Time of Functions(stack)
    • Task Scheduler
    • Subtree of Another Tree(stack,bfs,递归)
    • Brick Wall
    • Diameter of Binary Tree(递归含条件判断)
    • Encode and Decode TinyURL
    • Contiguous Array(2 sum)
    • Continuous Subarray Sum(2 sum)
    • Target Sum(01背包dp,dfs with memo)
    • Robot Room Cleaner(dfs)
    • Total Hamming Distance(位运算 bit)
      • Hamming Distance
    • Convert Binary Search Tree to Sorted Doubly Linked List (Tree)
    • Split Array Largest Sum(二分,dp?)
    • Sum of Left Leaves(递归和分治,dfs,树)
    • Random Pick Index(概率)
    • Decode String(状态机)
    • Insert Delete GetRandom O(1)
    • Combination Sum IV(dp,recursive)
    • Flatten Nested List Iterator(DFS,Iter)
    • Increasing Triplet Subsequence(二分得递增子序列)
    • Maximum Size Subarray Sum Equals k(2sum和Map)
    • 314. Binary Tree Vertical Order Traversal(树bfs)
    • Sparse Matrix Multiplication(matrix)
    • Remove Invalid Parentheses(dfs,bfs)
    • Serialize and Deserialize Binary Tree(bfs&dfs)
    • Inorder Successor in BST(tree traverse)
    • Move Zeroes(数组)
    • Expression Add Operators(dfs)
    • Find the Celebrity(双指针)
    • H-Index II(二分)
    • Integer to English Words
    • Alien Dictionary(topo)
    • Missing Number(异或)
    • Paint House II(DP)
    • Graph Valid Tree(bfs&uinion find)
    • Binary Tree Paths(dfs,分治)
    • Meeting Rooms II(sort)
    • Meeting Rooms
    • Product of Array Except Self(array)
    • Lowest Common Ancestor of a Binary Tree(递归)
    • Lowest Common Ancestor of a Binary Search Tree(递归)
    • Palindrome Linked List(linked list)
    • Maximal Square(matrix)
    • The Skyline Problem(priority queue)
    • Kth Largest Element in an Array(快排)
    • Add and Search Word - Data structure design(Trie)
    • Course Schedule II(topo)
    • Minimum Size Subarray Sum(追击指针)
    • Implement Trie (Prefix Tree)
    • Reverse Linked List(dfs)
    • Number of Islands(union find)
    • Binary Search Tree Iterator(tree inorder)
    • Excel Sheet Column Title(math)
    • One Edit Distance
    • LRU Cache
    • Read N Characters Given Read4 II - Call multiple times
      • Read N Characters Given Read4
    • Word Break(dp)
    • Word Break II(dp with memo)
    • Clone Graph(bfs,dfs)
    • Longest Consecutive Sequence(math)
    • Valid Palindrome
    • Best Time to Buy and Sell Stock
    • Populating Next Right Pointers in Each Node II(BFS)
    • Validate Binary Search Tree(iterative,dfs)
    • Decode Ways(dp)
    • Add Binary(bit.iter,recur)
    • Multiply Strings(math)
    • merge K array list
    • Sort Colors(双指针)
    • Merge Intervals(sort)
    • Nested List Weight Sum(dfs,bfs)
    • Nested List Weight SumII(dfs,bfs)
    • Subsets II(dfs)
    • Custom Sort String(math)
    • Leftmost One
    • Letter Combinations of a Phone Number(dfs)
    • Intersection of Two Arrays
    • Divide Two Integers(math)
    • Merge Sorted Array
    • Arithmetic Slices(dp)
      • Arithmetic Slices II - Subsequence
    • Flatten Binary Tree to Linked List(inorder)
    • Insert Interval(sweep line)
    • Find All Duplicates in an Array
    • Subarray Sum Equals K(2sum and presum)
    • Regular Expression Matching(DP)
    • Add Two Numbers(linked list)
    • Range Minimum Query (Square Root Decomposition and Sparse Table)
    • Pow(x, n)(recursive, iterative)
    • Range Sum Query 2D - Immutable(matrix)
    • Minimum Add to Make Parentheses Valid
    • Group Shifted String
    • Swap Nodes in Pairs(linked list)
    • Reverse Nodes in k-Group(linkedlist)
    • First Unique Character in a String
    • valid number(regular expression)
    • Kth Largest Element in a Stream
    • anagram
  • 背包问题
    • Backpack(可否装满)
    • Score Inflation (01)
    • Stamps(多重带总数限制)
    • Backpack X(多重背包)
    • nugget
    • Rockers(01变形)
  • TODO
  • Sort
    • insertion
    • MergeSort
  • Karat
    • Evaluate Division
    • Optimal Account Balancing
    • 227. Basic Calculator II
    • karat calculator 三题
    • Basic Calculator
    • Basic Calculator IV
  • Concurrent
    • Print Zero Even Odd
    • Print FooBar Alternately
    • Print in Order
  • 贪心
    • Shortest Way to Form String
  • 灌水类
  • 线段树&binary index tree
    • Range Sum Query - Mutable
    • Range Sum Query 2D - Mutable
    • Count of Smaller Numbers After Self
    • Count of Range Sum
    • Reverse Pairs
  • Doordash
    • 329. Longest Increasing Path in a Matrix
  • 滑动窗口
    • Permutation in String
    • Segment
    • Minimum Window Substring
  • Interval
    • 436. Find Right Interval
  • airbnb2025
    • 2043. Simple Bank System
    • 1235. Maximum Profit in Job Scheduling
    • 605. Can Place Flowers
    • 3076. Shortest Uncommon Substring in an Array
    • 713.Subarray Product Less Than K
    • 251. Flatten 2D Vector
    • 755. Pour Water
    • 336. Palindrome Pairs
    • 864. Shortest Path to Get All Keys
    • 1257 - Smallest Common Region.
    • 1091. Shortest Path in Binary Matrix
    • 827.Making A Large Island
    • 295. Find Median from Data Stream
  • Meta 2025
    • 543. Diameter of Binary Tree
    • 1249. Minimum Remove to Make Valid Parent
    • 408. Valid Word Abbreviation
    • 680. Valid Palindrome II
    • 1762. Buildings With an Ocean View
    • 1650. Lowest Common Ancestor of a Binary Tree III
    • 339. Nested List Weight Sum
    • 528. Random Pick with Weight
    • 50. Pow(x, n)
    • 346. Moving Average from Data Stream
    • 34. Find First and Last Position of Element in Sorted Array
    • 215. Kth Largest Element in an Array
    • 31. Next Permutation
    • 1570. Dot Product of Two Sparse Vectors
    • 129. Sum Root to Leaf Numbers
    • 938. Range Sum of BST
    • 169. Majority Element
    • 354. Russian Doll Envelopes
    • 287. Find the Duplicate Number
    • 71. Simplify Path
    • 986. Interval List Intersections
    • 138. Copy List with Random Pointer
    • 1110. Delete Nodes And Return Forest
    • 863. All Nodes Distance K in Binary Tree
    • 791. Custom Sort String
    • 1539. Kth Missing Positive Number
    • 1229. Meeting Scheduler
    • 173. Binary Search Tree Iterator
    • 2265. Count Nodes Equal to Average of Subtree
    • 498. Diagonal Traverse
    • 536. Construct Binary Tree from String
    • 1047. Remove All Adjacent Duplicates In String
    • 124. Binary Tree Maximum Path Sum
    • 647. Palindromic Substrings
    • 1216. Valid Palindrome III
    • 670. Maximum Swap
    • 270. Closest Binary Search Tree Value
  • To retro
Powered by GitBook
On this page

Was this helpful?

  1. L4_动态规划

Last Stone Weight II

We have a collection of rocks, each rock has a positive integer weight.

Each turn, we chooseany two rocks and smash them together. Suppose the stones have weightsxandywithx <= y. The result of this smash is:

  • If

    x == y

    , both stones are totally destroyed;

  • If

    x != y

    , the stone of weight

    x

    is totally destroyed, and the stone of weight

    y

    has new weight

    y-x

    .

At the end, there is at most 1 stone left. Return thesmallest possibleweight of this stone (the weight is 0 if there are no stones left.)

Example 1:

Input: 
[2,7,4,1,8,1]

Output: 
1

Explanation: 

We can combine 2 and 4 to get 2 so the array converts to [2,7,1,8,1] then,
we can combine 7 and 8 to get 1 so the array converts to [2,1,1,1] then,
we can combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we can combine 1 and 1 to get 0 so the array converts to [1] then that's the optimal value.

Note:

  1. 1

    <

    = stones.length

    <

    = 30

  2. 1

    <

    = stones[i]

    <

    = 100

分析

其实就是分成2个尽量大的组,2个sum的diff

看成01背包,分成2个尽量等分背包d。最后就是sum-2*d.2个等分抵消

记住这里dp[v]是bool,表示该数是否可以到达,最后结果是sum-2*v 开始写成sum-2*dp[v ]错半死

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        n = len(stones)
        sm = sum(stones)
        sm2 = sm//2
        mx = float('-inf')
        dp = [0]*(sm2+1)
        dp[0] = True
        # mindiff = float('inf')
        for i in range(n):
            for v in range(sm2,stones[i]-1,-1):
                dp[v] |= dp[v-stones[i]]
                if dp[v]:
                    mx = max(mx, v)

        return sm - 2*mx

本题也可以看成2个group A,B ,2个组和的diff, res=abs( A-B)。 所以当前元素入A就+ 入B就-。最后取正数

记住set的相加就是|

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        n = len(stones)
        dp ={0}
        for i in range(n):
            dp = {x-stones[i] for x in dp} | {x+stones[i] for x in dp} #2种可能性都要加入

        return min(abs(x) for x in dp)
PreviousLongest String ChainNextUnique Binary Search Trees II

Last updated 5 years ago

Was this helpful?