ywang305/dot_leetcode

algorithm practice

context

Note login with vscode extension

• us login use third-party linkedin
• cn login use account/password
• us username cookie (recommand )

Note vsc extension

• markdown-hashtags

Note debug with rdbg

• rdbg <ruby file>
  • i : info
  • b + #num : break point number
  • c : continue

    Note debug with ruby and binding.irb binding.irb

---

summary

• 3.longest-substring-without-repeating-characters #双指针哈西
  双指针 + Hash 记录位置, 注意更新 i 时候要比较并取最大值

• 4.median-of-two-sorted-arrays #BS
  hard BS， 长度 分奇偶 2 种情况讨论， median 和 nums1，nums2 的分割点存在“此消彼长”关系（见图），分割点关联着 2 个数组总长的 median 位置。 nums1 比 nums2 长， 只在 nums2 上做二分搜索（见图） ref video: Median of Two Sorted Arrays - Binary Search - Leetcode 4

  total len is ODD case

  

  total len is EVEN case

  

• 5.longest-palindromic-substring #DP #字符串-DP
  经典 DP, s[i] === s[j] && (j - i <= 2 || dp[i + 1][j - 1] === true

• 11.container-with-most-water #Greedy
  简单 Greedy， 两边缩减

• 12.integer-to-roman.java #Greedy
  图解 贪心哈希表

• 17.letter-combinations-of-a-phone-number #DFS, #组合

• 22.generate-parentheses #DFS 经典 DFS

• 23.merge-k-sorted-lists #分治
  俩俩 merge， 效率 T = nlogk。 如果 brute， T = nk

• 30.substring-with-concatenation-of-all-words #双指针哈西
  sliding window 变种， 参见youtube理解题意

• 31.next-permutation #Array
  array 技巧

• 32.longest-valid-parentheses #DP
  较难， 关键: 结合 leetcode solution example，理解连续有效括号时的推导过程，

  else if (s[i - dp[i - 1] - 1] === "(") { // i - dp[i - 1] - 1 是匹配的左括号index
    dp[i] = dp[i - 1] + (dp[i - dp[i - 1] - 2] ?? 0) + 2; // i - dp[i - 1] - 2 匹配的左括号index再前一个dp状态
  }

  leetcode solution example

  

• 33.search-in-rotated-sorted-array #BS
  经典 旋转数组

• 34.find-first-and-last-position-of-element-in-sorted-array #BS
  经典 BS lowerBound/upperBound, 关于二分查找，我有话说

• 37.sudoku-solver #DFS
  经典 DFS

• 39.combination-sum #DFS #组合
  组合变种， 包括重复元素， every time go from i

• 40.combination-sum-ii #DFS #组合
  组合变种, 跳过重复的元素, if (i > start && candidates[i] === candidates[i - 1]) continue;

• 42.trapping-rain-water #Monotonic #DP
  解法 （1） DP 空间（n) 比较好理解， （2） 双指针 空间（1）。 ref:youtube, key: 对每个位置，找到最大的左右墙壁高度
  （3）单调递减栈，简洁代码

• 44.wildcard-matching #DP #字符串-DP
  grandyang 的解法

• 45.jump-game-ii #DP #Greedy
  DP T(n^2); Greedy T(n), greedy is better, youtube neetcode, 类似于 BFS, 每次算出 reachFarthest

• 47.permutations-ii #DFS
    并不简单，涉及剪枝，递归逻辑也与 46.js 交换的写法 不一样（每次从 0 开始）

• 51.n-queens #DFS 经典 DFS, 吃吐

• 55.jump-game #Greedy
  每次算出 reachFarthest,

• 57.insert-interval #Array
  区间问题排除 no overlap 的 2 种情况， overlap 的情况 动态更新 start/end

• 60.permutation-sequence #DFS #排列
  hard, 不能用经典的吃吐(or I don't know how)， 对字母次序有要求

• 62.unique-paths #DP #DFS
  DFS 更简洁

• 63.unique-paths-ii #DP #DFS \

• 64.minimum-path-sum #DP
  经典 DP

• 69.sqrtx #BS
  easy 经典 binary search

• 71.simplify-path #String
  经典 stack

• 72.edit-distance #DP
  难, Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1. dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]分别对应插入/删除/替换(trick) 完美题解

• 74.search-a-2d-matrix #BS
  经典 highbound

• 75.sort-colors #QuickSelect \

• 76.minimum-window-substring #双指针哈西
  hard, 双指针哈西-变种js 解题思路 清晰明了, Java 注释版

• 77.combinations #组合
  经典

• 78.subsets #组合 \

• 79.word-search #DFS
  经典 2d-map

• 80.remove-duplicates #双指针
  经典

• 81.search-in-rotated-sorted-array-ii #BS
  33.旋转数组之变种， BS 需要考虑重复元素，即重复元素下分不清是左边/右边有序，此时 start++ 即可。相当于去掉一个重复的干扰项，详见题解搜索旋转排序数组 II

• 84.largest-rectangle-in-histogram #Monotonic
  hard, 核心**:求每条柱子可以向左右延伸的长度->矩形最大宽度 : 枚举高度 + 单调栈找 x 左边界 Monotonic 入门，使用 Monotonic 快速寻找边界

• 85.maximal-rectangle #Monotonic
  hard, 84 题的变种，从第一行到第 n 行形成的柱状图可以利用 84 题求解，Monotonic 解法

• 87.scramble-string #DFS
  dfs+memo: s 分解 s_left, s_right; t 分解 t_left, t_right. 原问题转化为((s_left,t_left) and (s_right, t_right) || (s_left, t_right) && (s_right, t+left)) 的子问题组合

• 90.subsets-ii #组合
  78.subsets 的扩展, 去重

• 91.decode-ways #DP
  类似打家劫舍,第 i 个下标能表示的解码方法个数依赖于 i-1 和 i-2 的情况

• 92.reverse-linked-list-ii #DFS
  直接 DFS 简洁，见 rb 版

• 93.restore-ip-addresses #DFS
  经典

• 95.unique-binary-search-trees-ii #DFS
  结合 Tree 的 DFS，更像是分治. 如果求 1...n 的所有可能：把 1 作为根节点，[ ] 空作为左子树，[ 2 ... n ] 的所有可能作为右子树；2 作为根节点，[ 1 ] 作为左子树，[ 3...n ] 的所有可能作为右子树。

• 96.unique-binary-search-trees #DP #贡献值
  枚举 root，当前 root 的解 = 左解 * 右解 （贡献值）

• 97.interleaving-strings #DP #字符串-DP
  类似 2d 路径问题

• 98.validate-binary-search-tree #DFS #alpha-beta
  类似 alpha-beta 限界

• 99.recover-binary-search-tree #DFS #alpha-beta
  有难度，利用 pre 记录 inOrder 前一个节点! ps: alpha-beta 版本见 ruby
  并利用规律：错误 1：出现了两对不满足前小后大，需要交换第一对的第一个元素与第二对的第二个元素。错误 2：只出现一对不满足前小后大，交换这一对元素即可。 这两行关键代码可以 cover 以上 2 种错误（结合手画图解自己体会）

  if(pre.val > root.val && null == err1) err1 = pre;  // tricky
  if(pre.val > root.val && null != err1) err2 = root; // tricky

• 115.distinct-subsequences #DP #字符串-DP
  hard! 这是 0-1 背包问题变种？
  dp[i][j] = dp[i-1][j] + ( s.charAt(i-1)==t.charAt(j-1) ? dp[i-1][j-1] : 0 );

• 121.best-time-to-buy-and-sell-stock #DP \

  1. 这种可以无限次买卖的， 使用 dp - hold/ no_hold
  2. 贪婪-仅需记住最小价

• 122.best-time-to-buy-and-sell-stock-ii #DP #Greedy \

• 123.best-time-to-buy-and-sell-stock-iii #DP
  一套模板，几行代码，闭着眼睛轻松默写所有彩票题

• 124.binary-tree-maximum-path-sum #DFS
  hard! DFS 返回 和 结果不是一个东西

• 126.word-ladder-ii #BFS #DFS #Graph
  hard！BFS 建立图，方向为邻居点指向源点，BFS 再从后向前搜索最短路径

• 128.longest-consecutive-sequence #UnionFind
  UnionFind 极简; 另一种做法利用连续数的规律

• 129.sum-root-to-leaf-numbers #Tree, #DFS
  经典吃吐 on the tree

• 131.palindrome-partitioning #DP, #DFS
  DP + backtracking
  注意 dp 内 j i 的顺序， 先决定 j 再向前决定 i。

• 132.palindrome-partitioning-ii #DP #字符串-DP
  hard! 双 DP, dp2[j] = Math.min(dp2[j], dp2[i - 1] + 1);

• 134.gas-station #Greedy
  贪婪：从前往后找，找到第一个满足条件的，就是结果

• 135.candy #Greedy
  贪婪， 按照条件两边扫描更新结果

• 139.word-break #DP
  经典 DP[i]： s[0, i)是否可以分割, 设初始[0,0)空字符串 true

• 140.word-break-ii #DFS
  经典 DFS, 吃吐

• 146.lru-cache #设计
  JS Map 是有序 hash, 每次 get/set 都先删除再加入

• 152.maximum-product-subarray #DP
  easy DP

• 153.find-minimum-in-rotated-sorted-array #BS
  Binary Search 变种（无重复元素）, 比较 pivot 和 right 判断哪边 unsorted， 注意 min 值 可能位于 pivot

• 154.find-minimum-in-rotated-sorted-array-ii #BS
  Binary Search 变种（有重复元素）, 额外处理重复情况

• 156.binary-tree-upside-down $$
  premium

• 159.longest-substring-with-at-most-k-distinct-characters #双指针哈西
  sliding window, 左右指针 + hashmap， hashmap 记录 char 和 last index

• 161.one-edit-distance #String
  String, 分两种情况：字符串长度相等 或 相差 1。 找出第一个不同的位置，根据两种情况 分别比较之后子串是否相等

• 162.find-peak-element #BS
  Binary Search 非标准变种， 注意 i<j 和 j = m 变化

• 163.missing-ranges $$ #Array
  [premium] array, 注意边界条件

• 164.maximum-gap #Bucket
  Bucket Sort, 3:00 桶排（线性）性能前提是数字均匀分布，数组能均匀映射到各个桶内, 本题大数据分布1 <= nums.length <= 105, 0 <= nums[i] <= 109， 桶排性能比较好。
  本题 tick： （1） num->bucket 映射函数，(涉及 interval- 见解bucketIndexMappingFunc) (2) 鸽洞原理，“这是因为所有的数字要尽量平均分配到每个桶中，而不是都拥挤在一个桶中，这样保证了最大值和最小值一定不会在同一个桶中，具体的证明博主也不会”。
  重点理解 bucket sort, bucketIndexMappingFunc, 鸽洞原理不重要

• 167.two-sum-ii-input-array-is-sorted #BS
  Binary Search, 退化版 每次++i 或 --j

• 169.majority-element #Array
  Moorer's Voting Alg, 见官方

• 174.dungeon-game #DP
  DP, 逆向推正是本题的精髓所在, 因为是求起点的状态

• 186.reverse-words-in-a-string #Array
  array, 反转数组， 再反转每个单词

• 188.best-time-to-buy-and-sell-stock-iv #DP
  DP, 3 维!， dp[act次数][day]{no_hold, hold},
  交易次数 act k=0 是实际不可呢的情况(至少得有一次交易吧)，但是需要初始化。 只有买入才会消耗一个交易次数，所以本次买入状态dp[act][day]取决于 dp[act-1][day-1]; 其他情况 dp[act][day] 取决于本次 act 维度·dp[act][day-1]`

• 189.rotate-array #Array
  array, 反转数组， 再反转左右半部分

• 198.house-robber.js #DP
  DP, easy 经典 to be or not to be

• 200.number-of-islands #UnionFind \

• 201.bitwise-and-of-numbers-range #bit
  Brian Kernighan 算法的关键在于我们每次对 number 和 number−1 之间进行按位与运算后，number 中最右边的 1 会被抹去变成 0. 本题**是 :对数字 n 迭代地应用上述技巧，清除最右边的 1，直到它小于或等于 m，此时非公共前缀部分的 1 均被消去。

• 207.course-schedule #Topo \

• 209.Minimum-Size-Subarray-Sum #双指针
  just straightforward sliding window

• 210.course-schedule-ii #Topo

• 211.design-add-and-search-words-data-structure #Trie
  Trie + （forloop 内混合 DFS）

• 212.word-search-ii #Trie
  hard, 没有那么难。 Trie + DFS

• 213.house-robber-ii #DP
  此题是 198. 打家劫舍 的拓展版： 唯一的区别是此题中的房间是环状排列的（即首尾相接), 环状排列意味着第一个房子和最后一个房子中只能选择一个偷窃，因此可以把此环状排列房间问题约化为两个单排排列房间子问题：(1) 在不偷窃第一个房子的情况; (2) 在不偷窃最后一个房子的情况. 综合偷窃最大金额： 为以上两种情况的较大值.

• 214.shortest-palindrome #String
  hard, 虽然是 HARD，涉及 KMP 算法， 但是本质很简单：s2=反转，比较直至 s1 前缀 == s2 后缀。。。 ruby 很容易实现

• 215.kth-largest-element-in-an-array #QuickSelect
  QuickSelect 从大到小， 清晰写法

• 216.combination-sum-iii #组合 \

• 218.the-skyline-problem #扫描线 #PriorityQueue
  hard! 大顶堆，扫描线算法基本思路

• 220.contains-duplicate-iii #TreeSet
  利用 TreeSet 作为 sliding window，用法：floor, ceiling, TreeSet.pollFirst() // 取出最小值, 本题不能用 pollFrist，而是 remove(someValue)

• 221.maximal-square #DP
  理解 min(上, 左, 左上) + 1

• 222.count-complete-tree-nodes #Tree
  有难度，技巧，工整简洁 利用完全二叉树的性质优化

• 224.basic-calculator #Stack
  hard! 双栈，given +，-，（，）， 考虑 op 左右括号; ruby 版本更清晰简洁， 仅在')'进行清算， 符合直觉

• 227.basic-calculator-ii #Stack
  双栈， given +,-,*,/, 考虑 op 优先级； 思路和 224 类似，ruby 版清晰

• 231.power-of-two #bit
  easy, n & (n-1) 会去掉一个最低位的 1

• 233.number-of-digit-one #贡献值
  hard! 自行车锁算法

• 236.lowest-common-ancestor-of-a-binary-tree #Tree
  🌲 经典

• 239.sliding-window-maximum #Monotonic
  经典例题 单调队列

• 240.search-a-2d-matrix-ii #Tree #Greedy
  貌似 BinarySearch，但是本题没有确保「每行的第一个整数大于前一行的最后一个整数, 因此我们无法采取「两次二分」的做法。(骗我). 【宫水三叶】抽象 BST

  抽象 BST

  

• 241.different-ways-to-add-parentheses #DFS
  括号题，针对操作符分成左右两部分递归

• 244.shortest-word-distance-ii $$ #TreeSet
  利用 TreeSet floor(target) ceiling(target) 快速查找 target 之在 TreeSet 内的上下界，注意如果未找到返回 null

• 247.strobogrammatic-number-ii $$ #DFS
  Following this pattern, we can conclude that to find all strobogrammatic numbers with N-digits, we first need to find all strobogrammatic numbers with (N - 2) digits and then append reversible digits to the beginning and the end.

• 248.strobogrammatic-number-iii $$ #DFS
  hard，不难，利用 247solution 直接求解

• 249.group-shifted-strings $$
  自造 hashcode

• 251.flatten-2d-vecto $$
  内外指针

• 253.meeting-rooms-ii $$ #Greedy #Stack
  建立有序数组 starts， ends. 需要的会议室仅和(任意)start/end 前后关系决定， 不必要 start/end 必须来自同一 meeting （大局观） NeetCode 7:35 / 11:45

• 254.factor-combinations $$ #DFS
  经典吃吐，但有变化（不易想到）

• 255.verify-preorder-sequence-in-binary-search-tree $$ #DFS #Tree
  minmax 限界

• 256.paint-house $$ #DP
  DP, easy 经典 to be or not to be

• 259.3sum-smaller $$ #双指针

• 260.single-number-iii #bit
  ~(n-1) & n ：只保留最后一位 1. 本题利用 xor 后都结果中任意一位 1 作为区分标志

• 261.graph-valid-tree $$ #DFS #UnionFind
  一题双解，判断 given graph 是不是 tree

  • DFS 因给的条件是有向图，但求解构造的 adjList 是无向图，所以 dfs 增加参数 from 来跳过不必要的邻点
  • UnionFind 巧妙利用 2 个 conditions

• 265.paint-house-ii $$ #DP
  同 256， 此题应该 easy（但标的 hard）

• 267.palindrome-permutation-ii $$ #排列
  虽然是 median，但是较难。 思路： 收集字母次数，取字符数量一半来作为 palindrome 的 first half string 来全排序，并且去重 cs[i]==cs[start]，但依然会产生重复解， 所以需要 HashSet 来去重复（因此 过程中 continue if cs[i]==cs[start] 不写也可以）

• 269.alien-dictionary $$ #Topo
  hard, 难点只是 edge cases 比较多

• 270.closest-binary-search-tree-value $$ #Tree

• 271.encode-and-decode-strings $$ #设计
  不仅 askii 字符集，如果是其它字符集怎么办？ 每个字符串前面插入（固定 4 bytes ）meta 记录后面的字符串长度

• 272.closest-binary-search-tree-value-ii $$ #PriorityQueue #Tree
  hard, 但是不觉难, 使用 PQ 后代码很简洁

  description

  

• 273.integer-to-english-words #分治
  hard, 考虑情况很多，技巧-将问题分解为子问题

• 276.paint-fence $$ #DFS #DP
  DFS+memo or DP,
  dp[i] 用来表示 i 个栅栏柱的涂色的方案数，有两种情况：如果：i 与 i-1 的颜色相同，则表明 i-1 与 i-2 的颜色不同，则 i 的数目为dp[i-2]*(k-1); 如果：i 与 i-1 的颜色不同，则 i 的数目为dp[i-1]*(k-1), 则递推公式为：dp[i] = dp[i-2](k-1) + dp[i-1](k-1)

• 277.find-the-celebrity $$ #Greedy
  题目中说明如果存在解， 则 exact one celebrity，所以用 Greedy， 两步走：先选出可能的候选人，再检验事否满足条件

• 279.perfect-squares #DP
  dp[i] = Math.min(dp[i], dp[i-j*j]+1)

• 280.wiggle-sort #Greedy
  直觉的仅考虑交换相邻的两位（典型的 Greedy）

• 282.expression-add-operators #DFS
  hard! 超级难的 DFS，这里 cn 官方解法， 难点在于（1）前导 0 的处理，（2）乘法优先级的处理

• 283.move-zeroes #Array
  easy, 后面覆盖前面（不需要交换）

• 284.peeking-iterator #设计
  peek 是新功能，提前一步存储 next 值

• 285.inorder-successor-in-bst $$ #Tree
  PD利用 BFS 二分遍历 tricky

• 286.walls-and-gates $$ #BFS
  多源 BFS

• 287.find-the-duplicate-number #bit
  官方题解-表格例子

• 289.game-of-life #复合状态
  如果复制 board 浪费空间。本题向周围辐射影响，巧妙利用个位和十位区分自己和周边的复合状态

• 291.word-pattern-ii $$ #DFS
  经典结构，但是做不出来 :(, 分两类情况考虑，（1）字符 c 已经映射过某 substring，（2）否则逐个构建 substring，注意跳过已经被映射过的 substring

• 294.flip-game-ii.rb $$ #DFS \

• 295.find-median-from-data-stream #设计
  双优先队列，令 lq 为大根堆，rq 为小根堆, 中位取决于两个堆顶元素

• 296.best-meeting-point $$ #降维
  hard! 归纳推理，由于是曼哈顿距离，把问题分解为 2 个一维的距离问题. solution

• 297.serialize-and-deserialize-binary-tree #Tree #DFS #BFS

  • 本题知识点多解法多！ DFS 序列化 Tree，参数 Index start 在反序列化的技巧 （ps： 发现 Java Integer 穿参是 value copy，即和 int 一样 ！！，不得已又增加了一个 wrapper class Index）
  • BFS 297.serialize-and-deserialize-binary-tree.js 反序列化时层序遍历。
  • 构建 inorder 和 preorder 俩个序列然后再构造 tree, 注意如果有重复值需要区分它们（如 inorder [3,..3,.,3...], 无法区分哪个 3 是 root), 所以使用小数位来区分它们 如[3.0,... 3.2，... 3.1,...] (当然 mute 了原 treenode 的值), 297.serialize-and-deserialize-binary-tree(2).js

• 298.binary-tree-longest-consecutive-sequence $$ #Tree 可以记录全局和当前的最优值，也可以使用一个 count 更加简洁

• 300.longest-increasing-subsequence #DP
  经典 DP - LIS

• 301.remove-invalid-parentheses #DFS
  hard! 括号题， 【宫水三叶】将括号的「是否合法」转化为「数学判定」, 这里的数学判定是巧妙利用 平衡度 score（见 code）来简化逻辑.

• 304.range-sum-query-2-d-immutable #PreSum
  二维 Presum

• 305.number-of-islands-ii $$ #UnionFind
  hard, 但是运用 ufo 很简单，涉及到小岛数量的融合，有几个 corner 要小心。

• 306.additive-number #DFS
  经典 DFS

• 307.range-sum-query-mutable #SegmentTree
  线段树入门题型，本题实现方式简化版 SegmentTree, 本题是未使用 lazy pushDown， update 仅 node 而非 range (标准版见 715 题)

• 308.range-sum-query-2d-mutable $$ #SegmentTree
  hard, 并不难如果熟悉 307 解法。 2d range 求和，quad segment tree 原理和 1d 二分 segment tree 一样。

• 309.best-time-to-buy-and-sell-stock-with-cooldown #DP
  持股/不持股：细分为四状态

• 310.minimum-height-trees #Topo
  常规逐点 DFS 导致 LTE，Topo 用到 Tree 结构上，想法非常巧妙！逐层去掉叶节点-参考图解 310. 最小高度树（拓扑排序，多写法）

• 312.burst-balloons #DP
  hard, 数列范围扩展到 2d DP，状态方程关键点是 K 是最后被戳破的那一个 图解：动态规划解决戳气球问题

• 313.super-ugly-number #PriorityQueue
  技巧在于防止生成重复的数

• 314.binary-tree-vertical-order-traversal $$ #Tree \

• 315.count-of-smaller-numbers-after-self #SegmentTree
  hard, 可以用 BS 但是依然 TLE。 SegmentTree 的 Ruby 版,动态生成子树利用 left/right one-line getter 很方便。 思路:对某数 n，统计 min..n-1 个数

• 316.remove-duplicate-letters #Monotonic
  一招吃遍力扣四道题

• 317.shortest-distance-from-all-buildings #BFS
  hard, 曼哈顿距离，从目标点开始探索并更新空位点(见方法 2)，涟漪现象

• 329.longest-increasing-path #DFS
  DFS + Memo 经典

• 338.counting-bits #bit
  easy, n & (n-1) 会去掉一个最低位的 1

• 394.decode-string #Stack
  双栈解决

• 347.top-k-frequent-elements #Bucket

    bucket sort
    trick: ( 和传统的bucket sort 的index value 反过来！), index 是 计数，value 是 num list，
     因为count是bounded，buckets是有界的。num可能非常大，buckets很长，很多空位置浪费了。(这不就是HashMap吗？)
    e.g. 1,1,1,2,2,100,100
      buckets:
        values: []    []  [2,100]  [1]   []    []   []
        index:  0     1     2      3     4     5     6
    [Bucket Sort](https://www.youtube.com/watch?v=YPTqKIgVk-k)
  

• 373.find-k-pairs-with-smallest-sums #PriorityQueue
  补充官方题解【优先队列】

• 402.remove-k-digits #Monotonic
  对于两个数 123a456 和 123b456，如果 a > b， 那么数字 123a456 大于 数字 123b456。 123[a or b]456, a 的取舍在于 a>b?, 重复这个过程 123a[b or d]46, b 的取舍...

• 449.serialize-and-deserialize-bst #Tree #BS
  因为 BST 所以可以二分搜索 rootVal 的分界点（如 lowerBound 或 higherBound ） 前序遍历与 BST 特性（含二分优化）

• 472.concatenated-words #Trie
  hard! Trie + DFS, 另外也可以用 hashset 替代 Trie

• 496.next-greater-element-i #Monotonic
  easy, Monotonic 只算右边界， 套路参考[907.sum-of-subarray-minimums](./solutions/907.sum-of-subarray-minimums.js

• 545.boundary-of-binary-tree $$ #Tree
  tree 边界分三种情况分别 DFS

• 588.design-in-memory-file-system #Trie
  hard, but not hard with Trie

• 684.redundant-connection #DFS #UnionFind #Topo
  (1)dfs：边构建图，边检测环，对于 s->t 的边，检查 s 的邻接点是否能到达 t，如果可以，则说明 s->t 是环路. (2)本题 union find 比较容易, (3)另外也可以用拓扑排序: 三种解法总结

• 694.number-of-distinct-islands $$ #DFS #UnionFind
  关键 计算岛屿点坐标与自己基点坐标差， 利用 set 去重

• 715.range-module #SegmentTree
  hard! 标准的线段树实现

• 739.daily-temperatures #Monotonic
  同496.next-greater-element-i

• 741.cherry-pickup #DP
  hard! 三维 DP （官方题解）

• 828.count-unique-characters-of-all-substrings-of-a-given-string #DP #String #贡献值
  hard。 暴力的方法是枚举 substring，然后考察这个区间里的字符哪些是 unique 的。这需要大致 o(N^2*26)的复杂度。聪明的方法是考察每个字符，它可能在哪些 substring 里是 unique 的。
  重点是转换为计算每一个字符对 substring 对贡献值，并累计。 并且利用了乘法组合性质，e.g. XXXA[XX A X]AXX， given cur A index is 6, pre A index is 3, post A index 8, then all possible substring combination for cur A is (6-3) * (8-6)
  还有 DP 解法 (2262 变种) : 四种方法 统计子串中的唯一字符

• 852. #BS
  BS 变种

• 907.sum-of-subarray-minimums #Monotonic #贡献值
  解题思路：Monotonic+贡献值, 又是每个位置的左右乘积组合 【超小白】动画详解保证教会你这道题

• 926.flip-string-to-monotone-increasing #DP #PreSum
  前缀和 / 动态规划

• 973.k-closest-points-to-origin #QuickSelect
  quickSelect， O(n)

• 1143.longest-common-subsequence #DP #字符串-DP
  DP, 经典

  if (text1[i - 1] === text2[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1] + 1;
  } else {
    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
  }

• 1151.minimum-swaps-to-group-all-1s-togethe $$
  问题转换为移动窗口内有多少个 1

• 1249.minimum-remove-to-make-valid-parentheses #Stack
  括号题

• 1268.search-suggestions-system #Trie
  Trie + DFS , Trie's startsWith 有变化， 增加了一个 dfs_search, 当 startsWith 满足时，调用 dfs_search 搜索前缀尾节点（current node）之后的 3 个单词(isEnd)

• 1301 #DP
  经典路径 DP

• [1567.maximum-length-of-subarray-with-positive-product]./solutions/1567.maximum-length-of-subarray-with-positive-product.java) #DP
  正/负 两个状态 层层递推 思路
  也可以用 DFS

• 1762.buildings-with-an-ocean-view $$ #Monotonic
  简单版的 Monotonic Stack， 没啥可说

  description

  

• 1911.maximum-alternating-subsequence-sum #DP
  to be or not to be. 两个数组表示当前位置取奇数/偶数得到的最大收益; 奇数 oddMax[i]: 不取，则沿用前一个奇 oddMax[i-1]，取则 evenMax[i-1]-nums[i]; 偶数 evenMax[i]: 不取，则沿用前一个奇 evenMax[i-1]，取（又分 2 种情况），仅 nums[i]，或 oddMax[i-1]+nums[i];

• 1926.nearest-exit-from-entrance-in-maze #BFS

• 2104.sum-of-subarray-ranges #Monotonic #贡献值
  hard! 利用'Monotonic' 和 '乘法组合'： 使用「Monotonic」找到某个 nums[i]nums[i] 的左边/右边的最近一个符合某种性质的位置，从而知道 nums[i]nums[i] 作为区间最值时，左右端点的可选择个数，再结合乘法原理知道 nums[i]nums[i] 能够作为区间最值的区间个数，从而知道 nums[i]nums[i] 对答案的贡献。 907.sum-of-subarray-ranges 的套路

• 2130.maximum-twin-sum-of-a-linked-list 快慢指针 + 反转子链表

• 2214.minimum-health-to-beat-game $$
  从整体考虑 题目看起来挺吓人其实是一道 easy 题

• 2262.total-appeal-of-a-string #贡献值
  Hard ! (super easy if you know it!) 又是对每个字符计算贡献值，左右组合乘法。 对于每个字符统计贡献

• 2272.substring-with-largest-variance #DP
  hard ！ 根据题意枚举 2 个字符，DP 使用到的 2 个状态变量感觉很 tricky（无法直观理解） ， 参考最大子数组和的变形题

• 2320.count-number-of-ways-to-place-houses #DP
  两种 DP 构造解法， 第一种： 选或不选结构； 第二种：dp[i] = (dp[i-1] + dp[i-2]) Fibonacci 结构

• 2786.visit-array-positions-to-maximize-score #DP
  https://leetcode.cn/problems/visit-array-positions-to-maximize-score/solutions/1/javapython3cdong-tai-gui-hua-wei-hu-qi-o-t67c/comments/2320748