刷题每日打卡

每日刷题打卡记录贴，目前熟练大部分常见算法，积累了一定题量，打算刷前500题和中高频题。

(Medium) 1291. Sequential Digits
每日一题，数据量很小，打表解决

(Hard) 1278. Palindrome Partitioning III
top-down dp，记录第i位结尾，c个回文的最小改动次数，再定义一个函数计算s[i~j]回文的改动次数

(Hard) 1478. Allocate Mailboxes
top-down dp, 和1278几乎一样

(Hard) 514. Freedom Trail
常规dp，dp(r,k)表示达到ring的第r位和key的第k位所需最少步数，求dp(x,len_key-1)最小值

(Hard) 1575. Count All Possible Routes
Bottom-up dp, f(city, fuel)表示到达city时剩下fuel的解的个数，和起点终点距离之和超过fuel的可以剪掉，最后求解f(finish_city, 0)



双周赛No.70 偏重数学题，rank 200-
(Easy) 5971. Minimum Cost of Buying Candies With Discount
贪心，从大到小跳过所有cost[3k+2]求和

(Medium) 5972. Count the Hidden Sequences
计算prefix sum，求极差，再和给定范围比较

(Medium) 5973. K Highest Ranked Items Within a Price Range
bfs遍历所有可达的item，再对结果做排序

(Hard) 5974. Number of Ways to Divide a Long Corridor
数学题，奇数个或0个座位排除，计算prefix count，把[2, num_seat-2]内的偶数个数相乘即可



周赛No. 277 rank 200-，可能是目前最简单的周赛？2000+个四题选手。。
(Easy) 5989. Count Elements With Strictly Smaller and Greater Elements
取最大最小值做比较

(Medium) 5991. Rearrange Array Elements by Sign
分别取得正负数列表，按规则重排

(Medium) 5990. Find All Lonely Numbers in the Array
排序，每个数和左右两边作比较，首尾单独考虑

(Hard) 5992. Maximum Good People Based on Statements
n<=15，直接枚举所有可能性逐一检查，好人数少于目前最优解的情况可以剪去

(Medium) 129. Sum Root to Leaf Numbers
常规dfs

(Medium) 236. Lowest Common Ancestor of a Binary Tree
dfs，看左右子树能否找到p和q

(Medium) 1650. Lowest Common Ancestor of a Binary Tree III
各自往parent移动，到达root后交换，相同返回

(Medium) 426. Convert Binary Search Tree to Sorted Doubly Linked List
dfs，中序遍历

(Medium) 865. Smallest Subtree with all the Deepest Nodes
dfs，比较左右深度，返回第一个两边深度相等的节点

(Medium) 173. Binary Search Tree Iterator
维护栈，记录当前节点及所有祖先

(Medium) 133. Clone Graph
常规dfs/bfs

(Medium) 545. Boundary of Binary Tree
三次dfs分别找左视图、右视图、叶节点，注意去重

(Medium) 721. Accounts Merge
常规并查集

(Medium) 863. All Nodes Distance K in Binary Tree
dfs通过树构建图，再bfs找距离k的节点

(Medium) 1644. Lowest Common Ancestor of a Binary Tree II
dfs检查节点是否存在，返回两侧dfs分别为pq的节点

(Medium) 43. Multiply Strings
经典高精度乘法

(Medium) 708. Insert into a Sorted Circular Linked List
双指针，边界情况很多

(Medium) 1382. Balance a Binary Search Tree
中序遍历求原数列，再构造平衡BST

(Medium) 138. Copy List with Random Pointer
构建原节点到复制节点的hashmap，再复制random

(Medium) 621. Task Scheduler
贪心，按频率递减插入task，最后比较task数和slot数

(Hard) 282. Expression Add Operators
dfs，记录当前index、算式、值

(Medium) 2161. Partition Array According to Given Pivot
扫一遍计数，再扫一遍三指针更新

(Medium) 2165. Smallest Value of the Rearranged Number
每个数字计数，分正负情况合并结果

(Medium) 2166. Design Bitset
维护数组及其和，单独记录flip次数

(Medium) 939. Minimum Area Rectangle
按对角线上两点暴搜

(Medium) 616. Add Bold Tag in String
KMP匹配每个单词 + Range Addition做标记

(Medium) 758. Bold Words in String
Rolling hash + merge interval

(Medium) 528. Random Pick with Weight
前缀和 + 二分

(Medium) 384. Shuffle an Array
第i个元素随机和第i~n中的一个交换

(Medium) 159. Longest Substring with At Most Two Distinct Characters
滑窗，窗口大小不缩小，满足条件更新结果

(Medium) 438. Find All Anagrams in a String
滑窗，26位数组记录频率，每次比较两个数组

(Medium) 8. String to Integer (atoi)
按规则检查

(Medium) 238. Product of Array Except Self
前缀后缀积

(Medium) 211. Design Add and Search Words Data Structure
Trie，dfs做模糊匹配

(Medium) 139. Word Break
dfs+cache，trie或set做匹配

(Medium) 945. Minimum Increment to Make Array Unique
排序，每一步更新下一个最小可能值

(Hard) 269. Alien Dictionary
拓扑排序，Kahn

(Hard) 76. Minimum Window Substring
滑窗，counter比较，慢指针尽可能右移

(Hard) 124. Binary Tree Maximum Path Sum
dfs, 返回左右子树最大路径和

(Medium) 467. Unique Substrings in Wraparound String
dp, 去重只需存储每个字母结尾的wraparound的最大值，最后相加即可

(Medium) 255. Verify Preorder Sequence in Binary Search Tree
recursive在不平衡时复杂度是O(n^2)会超时，只需维护monotonic stack和上一次弹出的值

(Medium) 298. Binary Tree Longest Consecutive Sequence
常规dfs，树上dp？

(Medium) 439. Ternary Expression Parser
常规parse，维护stack从右往左扫

(Medium) 875. Koko Eating Bananas
每日一题，查找满足条件的最小值，二分法

(Hard) 786. K-th Smallest Prime Fraction
常规heap，类似merge n sorted list

(Hard) 302. Smallest Rectangle Enclosing Black Pixels
二分找左右两端，题目给出x,y是为了引出优于O(mn)的复杂度？

前几天开始了Study Plan的DP4，攒了不少题目

(Medium) 688. Knight Probability in Chessboard
常规dp，LRU+递归

(Medium) 754. Reach a Number
数学题，等价于1+..+k=target任意换正负号可以成立。解1+..+k>=target的最小值，再递增到sum和target同奇偶，此时必有解。解方程O(1)，递增不超过3次，总复杂度O(1)。

(Medium) 134. Gas Station
每日一题，得到差值序列的prefix sum序列，最小值作为起点，判断可行性

(Hard) 1269. Number of Ways to Stay in the Same Place After Some Steps
常规dp，LRU+递归，arrLen超过steps的部分可以剪掉

(Hard) 1866. Number of Ways to Rearrange Sticks With K Sticks Visible
dp，递归得到最终结果再取模会MLE，python整数超过long范围会占用更高空间

(Hard) 1312. Minimum Insertion Steps to Make a String Palindrome
递归，dp(l,r)表示s[l:r+1]构成回文的最少插入次数

(Hard) 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons
类似1866，对f(n, k, max_val)递归

(Medium) 1602. Find Nearest Right Node in Binary Tree
每周一题，bfs记录目标节点深度，判断下个访问的节点深度是否相同

(Medium) 837. New 21 Game
注意k=0的特殊情况，动态转移方程需要求和，只对dp函数递归+LRU会超时，需要加入prefix sum函数，还不如直接用iterative dp

(Medium) 1105. Filling Bookcase Shelves
常规dp复杂度O(N*M)，稀疏表+prefix二分大概可以到O(NlgN)？

(Hard) 1510. Stone Game IV
每日一题，f(n)表示n个石子能否获胜，递归判断f(n-i^2)是否有False

今天偷了点懒，明天准备早晚两场周赛

(Medium) 245. Shortest Word Distance III
常规two pointer，i->word1, j->word2，注意word1=word2的情况

(Medium) 271. Encode and Decode Strings
把string长度列表放在加密字符串开头，["Hello", "World"] => "5,5#HelloWorld"

(Medium) 291. Word Pattern II
dfs，两个dict检查bijection

(Medium) 306. Additive Number
枚举前两个数所有可能性，注意边界情况：0开头、序列少于两个数

(Hard) 770. Basic Calculator IV
parsing惯例stack，用dict表示多项式，edge case相当多，替换字典中的词/表达式结尾/多项式相乘的常数或0项...，浪费了人生的一个小时

(Medium) 294. Flip Game II
暴搜+LRU，30个'+'的情况样例程序已经给不出答案，可以做很小的优化，用tuple记录连续+的个数，去掉单独的+号

(Medium) 320. Generalized Abbreviation
递归，不用去重

(Medium) 351. Android Unlock Patterns
dfs，bitmask记录可选数集

(Medium) 393. UTF-8 Validation
谜语题，看懂了按条件扫一遍data就行

(Medium) 444. Sequence Reconstruction
拓扑排序，Kahn算法，构建序列时检查每一步只有一个可能的节点

(Medium) 464. Can I Win
TSP，bitmask记录可选数集，再做dfs

(Medium) 474. Ones and Zeroes
二维0-1背包

(Medium) 1696. Jump Game VI
dp+单调队列

(Hard) 1879. Minimum XOR Sum of Two Arrays
TSP，bitmask

(Medium) 794. Valid Tic-Tac-Toe State
按规则检查

(Medium) 853. Car Fleet
单调栈，或者倒序找递增序列优化空间

(Medium) 469. Convex Polygon
输入给定了点的顺序，叉乘判断相邻边手性相同

(Medium) 985. Sum of Even Numbers After Queries
按顺序更新列表以及偶数和

(Medium) 1305. All Elements in Two Binary Search Trees
每日一题，中序遍历+merge 2 sorted lists

(Hard) 1526. Minimum Number of Increments on Subarrays to Form a Target Array
单调栈，或者比较相邻数，所有前高后低的差值求和

(Hard) 1377. Frog Position After T Seconds
算目标节点的深度和路径上每个节点的儿子数，注意叶节点不能继续跳

接下来几天低强度leetcode 准备onsite

(Medium) 421. Maximum XOR of Two Numbers in an Array
每日一题，bit trie，倒序构建树

(Medium) 1245. Tree Diameter
dfs记录各子节点往下的深度

(Hard) 84. Largest Rectangle in Histogram
每日一题，正反各扫一次维护单调栈

(Hard) 1216. Valid Palindrome III
dp，求最长回文子串长度

(Hard) 1944. Number of Visible People in a Queue
反向扫一遍，维护单调栈

(Hard) 2056. Number of Valid Move Combinations On Chessboard
bfs遍历所有可能情况，每个状态包括(pos, dir, stop)

周赛 No. 278 难度偏高，rank 1000+
(Easy) 2154. Keep Multiplying Found Values by Two
转化成set，逐步查找

(Medium) 2155. All Divisions With the Highest Score of a Binary Array
从两端开始各自计数，最后扫一次找最值

(Medium) 2156. Find Substring With Given Hash Value
从后向前，避免modulo中的除法，类似rolling hash

(Hard) 2157. Groups of Strings
union find，比赛里找connected的算法写的太差，TLE

(Medium) 636. Exclusive Time of Functions
栈，时间描述的很奇怪，其实就是end要+1

(Medium) 1424. Diagonal Traverse II
根据row+col存dict，倒序输出，拼接list要用append逐个插入，否则会超时

(Medium) 1891. Cutting Ribbons
二分，注意边界情况

(Medium) 1233. Remove Sub-Folders from the Filesystem
遍历一遍建trie，第二遍找sub folder

(Medium) 1361. Validate Binary Tree Nodes
dfs，检查根唯一、入度最多为1、没有环、树包含所有节点

(Medium) 1372. Longest ZigZag Path in a Binary Tree
dfs，记录以节点结尾的左右串长度

(Medium) 1101. The Earliest Moment When Everyone Become Friends
每周一题，经典并查集

(Medium) 438. Find All Anagrams in a String
每日一题，滑动窗口+array记录频率

(Hard) 980. Unique Paths III
bitmask+bfs