转型刷Leetcode记录帖

lintcode1640有点强，推荐大家练一下。明确是DP Hard

- 11/04
    - (lt)1640H. Duplicates Digits
        - (35min+). {DNF} DP.
        - use top-bottom search when get stuck.
    - (lt)109M. Triangle
        - (4min). DP
    - (lt)1642M. Query String
        - (10min). pure brutal force. meaningless problem.
    - (lt)1643M. Pick Fruits
        - (5min). sliding window
    - (lt)1634M. Secret Word
        - (8min). mapping count.
    - (lt)1644M. Plane Maximum Rectangle
        - (10min). hash.
    - (lt)1633E. Strings That Satisfies The Condition
        - (5min). imple
    - (lt)1645E. Least Subsequences
        - (6min). Bin-search
        - `bisect_left: arr[lo:i]<val arr[i:hi]>=val`
    - (lt)1580M. Transition String
        - (20min) {buggy}. hash. find loop
    - (g4g)E. Check if Tree is Isomorphic
        - (5min). recursive
    - 659M. Split Array into Consecutive Subsequences
        - (12min). queue+hash. dont overkill, just focus on the essential property.
        - {DNF}. O(1) space.

G家有一题(lintcode1576)，给一个地图，有一些人和自行车（相同数量），需要你一个人匹配一个单车（一对一），然后总路程最短。
可以转化成二分图带权值的最大完美匹配。这个说实话不是像不带权值的匈牙利算法那么简单...还是需要一定的设计的。

总的来说还是找增广路，但是从一个tight edge找起，如果没有tight edge就调整图直至有tight edge augmentation path。
tight edge的定义就是y(u)+y(v) = w(u, v)。其中y()是对每一个点的分数，w是边的权值。保证所有点y(u)+y(v) >= w(u, v)。当y(u)+y(v)=w(u,v)则为tight。
怎么调整呢？就是从左边的点把权值推到右边去，（减小y_L，增大y_R，这样没有访问过的y_R就有可能和减小的y_L组成新的tight edge）。

可能会开一个新的帖子来写模板


- 11/06
    - (lt)315H. Count of Smaller Numbers After Self
        - (10min). mergesort
    - (lt)1576H. Optimal Match
        - (60min). bipartite max perfect matching. hungarian algorithm with weights (dual value+tight edge+augmentation path+delta). O(MN^2)
    - (lt)1641M. Max Remove Order
        - (13min). Union-find set
    - (lt)1646M. CheckWords
        - (15min). BFS
    - (lt)1640H. Duplicates Digits
        - (15min). DP. add another dimension if have to handle different cases
    - 936H. Stamping The Sequence
        - greedy simulation

楼主好厉害啊，我也是python刷的，喜欢你分享的模版。

最近生活出了一些问题。可能会暂时停更。

- 11/07~11/10
    - 940. Distinct Subsequences II
        - DP
    - (lt)458E. Last Position of Target
        - {buggy} bin search
    - (lt)1541H. Put Box
        - DP
    - (lt)825H. Bus Station
        - BFS
    - (lt)1555H. Flower Problem
        - union find set
    - (lt)1538M. Card Game II
        - search
    - (lt)903M. Range Addition
        - {buggy}. imple
    - (lt)1539M. Flipped the Pixel
        - imple
    - (lt)1542M. NextTime Norepeat
        - imple
    - (lt)1543M. Unique Path IV
        - DP
    - (lt)1545M. Last Closest Time
        - imple
    - (lt)1554M. LastTime Norepeat
        - {buggy} corner-case.
    - (lt)1086E. Repeated String Match
        - imple