刷题每日打卡

近期集中准备tag题

(Medium) 1570. Dot Product of Two Sparse Vectors
hash，follow-up用列表存然后二分

(Medium) 1762. Buildings With an Ocean View
单调栈，返回所有栈元素index

(Medium) 1004. Max Consecutive Ones III
滑窗，size不用缩小，返回最终窗口大小

(Medium) 253. Meeting Rooms II
按起始时间遍历，维护结束时间的最小堆，返回堆的最大size

(Medium) 454. 4Sum II
两两组合字典计数

(Medium) 277. Find the Celebrity
按顺序call一次n->n+1，选出candidate，再检查一遍

(Medium) 973. K Closest Points to Origin
quick select，原地排序

(Medium) 215. Kth Largest Element in an Array
同quick select

(Medium) 560. Subarray Sum Equals K
prefix sum计数

(Medium) 323. Number of Connected Components in an Undirected Graph
经典并查集

(Hard) 296. Best Meeting Point
找x y轴上的中位数

(Hard) 2076. Process Restricted Friend Requests
并查集，每次检查是否能连通

(Medium) 1428. Leftmost Column with at Least a One
从右上开始向左或向下移动直到最后一行，类似sorted lists找数

(Medium) 825. Friends Of Appropriate Ages
数学题，前缀和算总数，第三个条件是多余的

(Medium) 227. Basic Calculator II
栈，根据前一个符号操作，最后相加

(Medium) 380. Insert Delete GetRandom O(1)
list保存数据，dict记录位置，删除时和最后一个交换

(Medium) 515. Find Largest Value in Each Tree Row
dfs，记录高度，更新列表结果

(Medium) 78. Subsets
回溯

(Medium) 286. Walls and Gates
BFS

(Medium) 525. Contiguous Array
每日一题 hashmap记录0和1的差值最早出现的位置

(Medium) 34. Find First and Last Position of Element in Sorted Array
两次二分，分别找左右端点

(Medium) 71. Simplify Path
常规stack，结尾补"/"处理边界情况

(Medium) 670. Maximum Swap
遍历每个数字判断后面是否存在更大的数字

(Medium) 695. Max Area of Island
dfs，记录visited避免重复

(Hard) 778. Swim in Rising Water
二分+dfs

(Medium) 56. Merge Intervals
按左端点排序，从前往后合并

(Medium) 31. Next Permutation
找nums[i+1]>nums[i]，交换nums[i]和右侧最小的大于它的数，再反转右侧

(Medium) 958. Check Completeness of a Binary Tree
bfs 检查剩下全为空节点

(Medium) 1257. Smallest Common Region
LCA，用bfs

(Medium) 1091. Shortest Path in Binary Matrix
bfs，先检查起点终点

(Medium) 314. Binary Tree Vertical Order Traversal
bfs，顺序遍历，不用排序

(Medium) 16. 3Sum Closest
排序+双指针

(Medium) 348. Design Tic-Tac-Toe
记录每行每列每条对角线上X和O的个数

(Medium) 921. Minimum Add to Make Parentheses Valid
记录未匹配的左括号数

(Medium) 498. Diagonal Traverse
按顺序遍历，到边界转向

(Medium) 1249. Minimum Remove to Make Valid Parentheses
维持栈记录未匹配左括号位置

(Hard) 987. Vertical Order Traversal of a Binary Tree
遍历存dict再分组排序

(Medium) 162. Find Peak Element
二分，往高处缩小范围

(Medium) 658. Find K Closest Elements
二分+双指针

(Medium) 1209. Remove All Adjacent Duplicates in String II
栈记录字母和次数

(Medium) 398. Random Pick Index
水库抽样

(Medium) 739. Daily Temperatures
单调栈从右往左

(Medium) 523. Continuous Subarray Sum
记录模k余数最早出现的位置

(Medium) 510. Inorder Successor in BST II
找右子树或祖先节点

(Medium) 339. Nested List Weight Sum
BFS，记录深度

(Medium) 986. Interval List Intersections
双指针

(Medium) 1868. Product of Two Run-Length Encoded Arrays
双指针，合并相同数值

(Medium) 199. Binary Tree Right Side View
bfs，先序遍历，更新每一层数值

(Hard) 827. Making A Large Island
dfs，标记每个岛求面积

(Hard) 42. Trapping Rain Water
双指针，记录左右最值

(Hard) 23. Merge k Sorted Lists
最小堆

(Hard) 65. Valid Number
按规则检查

(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) 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) 647. Palindromic Substrings
每个点/两点为中心向外扩展

(Medium) 536. Construct Binary Tree from String
扫一遍字符串，先序顺序维护节点栈

(Medium) 532. K-diff Pairs in an Array
每日一题，先转化为Counter，再对k=0分情况讨论

(Hard) 126. Word Ladder II
先建图，再做bfs记录路径

(Hard) 301. Remove Invalid Parentheses
bfs按长度遍历尝试所有情况

(Hard) 4. Median of Two Sorted Arrays
二分，边界情况很多

Meta 近6月top100目前已经刷完，费劲啃下了KMP和Manacher

(Medium) 451. Sort Characters By Frequency
计数+排序

(Medium) 200. Number of Islands
常规dfs

(Medium) 113. Path Sum II
常规dfs

(Medium) 445. Add Two Numbers II
反转链表+高精度加法

(Medium) 5. Longest Palindromic Substring
Manacher

(Medium) 102. Binary Tree Level Order Traversal
bfs，按顺序添加

(Medium) 678. Valid Parenthesis String
左右括号和星号计数，正反各扫一遍，每步检查

(Medium) 567. Permutation in String
滑窗，固定窗口大小计频率

(Medium) 103. Binary Tree Zigzag Level Order Traversal
bfs，记录层数

(Medium) 261. Graph Valid Tree
并查集

(Medium) 360. Sort Transformed Array
双指针，从头尾开始找，判断开口方向

(Medium) 366. Find Leaves of Binary Tree
dfs返回深度，直接构建结果列表

(Medium) 516. Longest Palindromic Subsequence
dp

(Hard) 2040. Kth Smallest Product of Two Sorted Arrays
二分

(Medium) 33. Search in Rotated Sorted Array
二分，中点和两端比较

(Medium) 81. Search in Rotated Sorted Array II
二分，左右边界向中间移动直到和中点值不同

(Medium) 470. Implement Rand10() Using Rand7()
舍选抽样

(Medium) 61. Rotate List
遍历求长度，计算新的head节点再拼接

(Medium) 713. Subarray Product Less Than K
滑窗

(Medium) 150. Evaluate Reverse Polish Notation
栈，遇到符号弹出栈顶两个数做计算

(Medium) 151. Reverse Words in a String
先反转字符串，再反转每个单词

(Medium) 128. Longest Consecutive Sequence
并查集

(Medium) 187. Repeated DNA Sequences
rolling hash

(Medium) 611. Valid Triangle Number
排序后同向双指针

(Medium) 254. Factor Combinations
backtrack

(Medium) 46. Permutations
backtrack

(Medium) 1541. Minimum Insertions to Balance a Parentheses String
栈

(Medium) 655. Print Binary Tree
第一遍dfs算高度，第二遍dfs打印

(Medium) 57. Insert Interval
二分找合并位置，再插入区间

(Hard) 127. Word Ladder
每日一题，bfs

(Hard) 149. Max Points on a Line
从每个点出发计算所有向量再计数

(Hard) 68. Text Justification
双指针，按条件加空格

(Hard) 72. Edit Distance
dp，比较word1[:i]和word2[:j]

开始准备狗家电面，整理了大约70题

(Medium) 2171. Removing Minimum Number of Magic Beans
贪心

(Medium) 156. Binary Tree Upside Down
递归

(Medium) 341. Flatten Nested List Iterator
存两个栈记录当前位置

(Medium) 539. Minimum Time Difference
转化为分钟，排序

(Medium) 650. 2 Keys Keyboard
递归，分解质因数求和

(Medium) 1048. Longest String Chain
按长度排序，dp

(Medium) 1877. Minimize Maximum Pair Sum in Array
贪心，排序后前后第i个相加

(Medium) 2007. Find Original Array From Doubled Array
从小到大取，注意0的情况

(Medium) 954. Array of Doubled Pairs
类似2007，多了负数的情况

(Medium) 690. Employee Importance
dfs

(Medium) 334. Increasing Triplet Subsequence
LIS，长度达到3即存在

(Medium) 2128. Remove All Ones With Row and Column Flips
先转换第一列为0，再检查剩余列

(Medium) 1423. Maximum Points You Can Obtain from Cards
prefix + suffix sum

(Medium) 981. Time Based Key-Value Store
hash+二分

(Medium) 777. Swap Adjacent in LR String
LR出现顺序相同，R向后移，L向前移，计数比较即可