Leetcode 刷题汇总系列(2)_leetcode刷题总结

注：

黄色：简单

绿色：可以重复练习

蓝色：稍有难度

51. 2. Add Two Numbers
1. https://leetcode.com/problems/add-two-numbers/
2. 用链表表示的数字，求和
1. Input: l1 = [2,4,3], l2 = [5,6,4]
2. Output: [7,0,8]
3. 前缀 listnode
52. 155. Min Stack
1. https://leetcode.com/problems/min-stack/
1. Input["MinStack","push","push","push","getMin","pop","top","getMin"][[],[-2],[0],[-3],[],[],[],[]]
2. Output[null,null,null,null,-3,null,0,-2]
2. 两个栈：两个都需要存全量的数据，只是第二个每次都 push 当前的 min 而已
53. 1019. Next Greater Node In Linked List
1. https://leetcode.com/problems/next-greater-node-in-linked-list/
2. 计算每个链表元素，最近一个比他大的元素 (以序列形式返回)
1. Input: head = [2,1,5]
2. Output: [5,5,0]
3. O(N) stack 就行
54. 641. Design Circular Deque
1. https://leetcode.com/problems/design-circular-deque/
2. 实现一个环形 queue
1. Input ["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"] [[3], [1], [2], [3], [4], [], [], [], [4], []]
2. Output [null, true, true, true, false, 2, true, true, true, 4]
3. 数组 + index 模拟
55. 526. Beautiful Arrangement
1. https://leetcode.com/problems/beautiful-arrangement/
2. [1, 2, ..., n] 的全排列，求其中符合要求的序列个数：a[i] 被 i 整除 或者 i 被 a[i] 整除
1. Input: n = 2
2. Output: 2
3. 先把每个位置上可选的候选集弄出来，然后 dfs (visited)
56. 935. Knight Dialer
1. https://leetcode.com/problems/knight-dialer/
2. 手机键盘，每次拨号只能走 “马”，起点随机，拨 n 次可能拨出多少号码
1. Input: n = 2
2. Output: 20
3. dp：其实是很简单的转移方程 -> f(n) = sum(f(n-1)) 这种情况时不要紧张
57. 452. Minimum Number of Arrows to Burst Balloons
1. https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/
2. 给定区间序列，求最少需要多少点可以把这些区间都覆盖
1. Input: points = [[10,16],[2,8],[1,6],[7,12]]
2. Output: 2
3. 和上课有点像，排序即可
1. vector sort + 边界处理 + 用指针引用 vector 可以减少很多时间
58. 1400. Construct K Palindrome Strings
1. https://leetcode.com/problems/construct-k-palindrome-strings/
2. 给个字符串，用字符串里的所有字符，组成 k 个子串，且 k 个都是回文，问能不能做到
1. Input: s = "annabelle", k = 2
2. Output: true
3. 奇数字符个数 <= k 即可，脑经急转弯
59. 1401. Circle and Rectangle Overlapping
1. https://leetcode.com/problems/circle-and-rectangle-overlapping/
2. 圆和矩形是否相交（矩形和坐标轴平行）
1. Input: radius = 1, xCenter = 0, yCenter = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
2. Output: true
3. 不能直接转化为两个矩形是否正交的问题
1. https://hackmd.io/@bob81135/Leetcode_1401
2. https://blog.csdn.net/fuxuemingzhu/article/details/105331519

60. 970. Powerful Integers
1. https://leetcode.com/problems/powerful-integers/
2. 给定 i 和 j 和 t，求 i^x + j^y <= t 的数量
1. Input: x = 2, y = 3, bound = 10
2. Output: [2,3,4,5,7,9,10]
3. 思路类似两个指针
1. a / b 有序序列，求 a[i] + b[j] <= target 的数量
2. 其实是剪枝策略：较小的 a 和某个 b 都已经超过了，那么较大的 a 不用和更大的 b 比较了
61. 1798. Maximum Number of Consecutive Values You Can Make
1. https://leetcode.com/problems/maximum-number-of-consecutive-values-you-can-make/
2. 给你不同面额的硬币各若干，求 从 0 开始的金额能连续构造出来多少
1. Input: coins = [1,1,1,4]
2. Output: 8
3. 排序：if a[i] <= x+1, x+=a[i] else 后面的肯定也不行，因为构造不出来 x+1 了
62. 811. Subdomain Visit Count
1. https://leetcode.com/problems/subdomain-visit-count/
2. 统计域名和子域名出现的次数
1. Input: cpdomains = ["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
2. Output: ["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
3. 字符串处理
63. 1915. Number of Wonderful Substrings
1. https://leetcode.com/problems/number-of-wonderful-substrings/
2. 求字符串的 wonderful 子串数量，wonderful = 最多只有一个字符出现奇数次
1. Input: word = "aabb"
2. Output: 9
3. 用 bitmask 的形式来表现一个字符串中每个字符的奇偶状态
4. 根据条件， 我们找到与当前 bitmask 相同和差一位的所有**之前的**字符串的数量
64. 2149. Rearrange Array Elements by Sign
1. https://leetcode.com/problems/rearrange-array-elements-by-sign/
2. 按照 偶奇偶奇 的顺序排序
1. Input: nums = [3,1,-2,-5,2,-4]
2. Output: [3,-2,1,-5,2,-4]
3. 重点是需要原地做，实现起来不麻烦
65. 2038. Remove Colored Pieces if Both Neighbors are the Same Color
1. https://leetcode.com/problems/remove-colored-pieces-if-both-neighbors-are-the-same-color/
2. 只有连续 AAA 或者连续 BBB 才能删除中间的，求最后是 A 不能删还是 B 不能删
1. 如果是 B 不能则返回 true，否则返回 false
2. Input: colors = "AAABABB"
3. Output: true
3. 因为删除 A 或者 B 都不会影响后续的博弈，所以就遍历计算数量即可
66. 779. K-th Symbol in Grammar
1. https://leetcode.com/problems/k-th-symbol-in-grammar/
2. 0 -> 01 -> 0110 -> 01101001
1. n 表示变化多少次，k 表示返回第 k 个字符
2. Input: n = 2, k = 2
3. Output: 1
3. 找到规律就好解决了
67. 1451. Rearrange Words in a Sentence
1. https://leetcode.com/problems/rearrange-words-in-a-sentence/
2. 按照长度重新排列（稳定排序）
1. Input: text = "Leetcode is cool"
2. Output: "Is cool leetcode"
3. 排序 + 字符串处理; 好像可以计数排序
68. 856. Score of Parentheses
1. https://leetcode.com/problems/score-of-parentheses/
2. ()=1 && (a) = 2*a && ab=a+b，求字符串得分
1. Input: s = "()()"
2. Output: 2
3. stack
1. 需要区分记录是 ( 还是中间结果
69. 2120. Execution of All Suffix Instructions Staying in a Grid
1. https://leetcode.com/problems/execution-of-all-suffix-instructions-staying-in-a-grid/
2. DFS 机器人走格子，计算 “假设从 s 的每个 index 开始能走的步数”
1. Input: n = 3, startPos = [0,1], s = "RRDDLU"
2. Output: [1,5,4,3,1,0]
70. 1234. Replace the Substring for Balanced String
1. https://leetcode.com/problems/replace-the-substring-for-balanced-string/
2. string 变成 4 个字符 (QWER) 出现的次数都相同，最小变多少 “连续的子串”
1. Input: s = "QQQW"
2. Output: 2
3. Use 2-pointers algorithm to make sure all amount of characters outside the 2 pointers are smaller or equal to n/4.
4. 滑动窗口
71. 1286. Iterator for Combination
1. https://leetcode.com/problems/iterator-for-combination/
2. 字符串的全排列
1. Input ["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"] [["abc", 2], [], [], [], [], [], []]
2. Output [null, "ab", true, "ac", true, "bc", false]
3. 这道题就是全排列的逐个递增式写法
1. 先找到需要 +1 的位置：nums[i]+1 在 i 后面
2. 然后 nums[i] = nums[i]+1，然后把后面的数字 sort 一下之后依次填入
72. 769. Max Chunks To Make Sorted
1. https://leetcode.com/problems/max-chunks-to-make-sorted/
2. 数组分段排序，排完本身也就有序了，问最多分多少段
3. 如果序列的长度是 n，那么序列里的内容肯定是 [0, n-1] 的某个排列
1. Input: arr = [1,0,2,3,4]
2. Output: 4
4. 找最大值：如果前 i 个最大数等于 i，那么 a[i] 肯定可以可以单独分一段，且前后最大段都不会受到影响
1. o(n)
73. 1376. Time Needed to Inform All Employees
1. https://leetcode.com/problems/time-needed-to-inform-all-employees/
2. 一棵树，遍历完，需要多少 cost
3. n 是节点数，manager 表示每个 index 的父亲 index，informerTime 表示父亲通知儿子的时间
1. Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
2. Output: 1
4. dfs
74. 36. Valid Sudoku
1. https://leetcode.com/problems/valid-sudoku/
2. 数独
1. Input: board = [["5","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]]
2. Output: true
3. dfs：重点是方形的区间如何表达
75. 522. Longest Uncommon Subsequence II
1. https://leetcode.com/problems/longest-uncommon-subsequence-ii/
2. 最长非公共子序列
3. An uncommon subsequence between an array of strings is a string that is a subsequence of one string but not the others.
4. A subsequence of a string s is a string that can be obtained after deleting any number of characters from s.
1. Input: strs = ["aba","cdc","eae"]
2. Output: 3
5. 最终结果一定等于某个序列的长度
1. 如果结果 < 所有的序列，那么最长的那个肯定也是的
76. 647. Palindromic Substrings
1. https://leetcode.com/problems/palindromic-substrings/
2. 回文子串的数量
1. Input: s = "aaa"
2. Output: 6
3. dp 即可 -> 写的时候不要装逼写单层数组
77. 994. Rotting Oranges
1. https://leetcode.com/problems/rotting-oranges/
2. 矩阵中，橘子坏影响四周，橘子分好坏，每分钟坏橘子都会让四周的好橘子变坏，求可以撑多少分钟
1. Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
2. Output: 4
3. bfs
78. 2245. Maximum Trailing Zeros in a Cornered Path
1. https://leetcode.com/problems/maximum-trailing-zeros-in-a-cornered-path/
2. 矩阵中最多转一次且不能走重复路，求乘积最大的后缀 0 数量
1. Input: grid = [[23,17,15,3,20],[8,1,20,27,11],[9,4,6,2,21],[40,9,1,10,6],[22,7,4,5,3]]
2. Output: 3
3. 以 [i,j] 为转折点
79. 877. Stone Game
1. https://leetcode.com/problems/stone-game/
2. 两个人依次从首或者尾取硬币，求最终先手是否稳赢 (谁的数字和最大谁赢)
1. Input: piles = [5,3,4,5]
2. Output: true
3. dp 即可
1. a[i][j] = max(p[i]+ max(a[i+1][j-2], a[i+2][j-2]), p[i+j-1]+max(a[i][j-2], a[i+1][j-2]))
2. j 是长度：常见的 dp 最外层循环的写法
4. 面对这种题目能用 dp 表达的肯定也能用 dfs，选一个好写的即可
80. 470. Implement Rand10() Using Rand7()
1. https://leetcode.com/problems/implement-rand10-using-rand7/
1. Input: n = 1
2. Output: [2]
2. (rand7()-1) * 7 + rand7()：超过就不要呗
81. 1882. Process Tasks Using Servers
1. https://leetcode.com/problems/process-tasks-using-servers/
2. 计算每个 task 最终会被哪个 server 处理
1. server 数组表示的是权重 (每次都从不忙的 server 中取权重最小的执行 task)
2. tasks 数组表示的是每个任务执行的时间
3. cases
1. Input: servers = [3,3,2], tasks = [1,2,3,2,1,2]
2. Output: [2,2,0,2,1,2]
4. priority_queue
1. waiting_queue 和 running_queue，前者用完成时间排序，后者用 weight 排序
82. 172. Factorial Trailing Zeroes
1. https://leetcode.com/problems/factorial-trailing-zeroes/
2. 阶乘的后缀 0 数量
1. Input: n = 5
2. Output: 1
3. 其实就是数 5 的倍数的数量
83. 1300. Sum of Mutated Array Closest to Target
1. https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/
2. 把序列中比 x 大的都变成 x 使得 sum 和 target 最接近，求 x
1. Input: arr = [60864,25176,27249,21296,20204], target = 56803
2. Output: 11361
3. 先 sort 然后再用二分，target > sum 就往右边去，否则就往左边去
1. 其实第二步不需要 log(n)，直接遍历用 o(n) 的就可以
84. 1261. Find Elements in a Contaminated Binary Tree
1. https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree/
2. 根据规则重建 tree 反查某个数在不在
1. Input ["FindElements","find","find"][[[-1,null,-1]],[1],[2]
2. Output[null,false,true]
85. 1410. HTML Entity Parser
1. https://leetcode.com/problems/html-entity-parser/
2. 字符串处理，去掉特殊字符串
1. Input: text = "& is an HTML entity but &ambassador; is not."
2. Output: "& is an HTML entity but &ambassador; is not."
86. 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum
1. https://leetcode.com/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/
2. 找到两个子序列，和为 target，且不正交，求满足条件的子序列的元素数量和的最小值
1. Input: arr = [7,3,4,7], target = 7
2. Output: 2
3. 只统计一序列的最小长度比较简单：前缀和即可
4. 如果统计两个序列的最小长度，则在一个的基础上记录 min_len[i] 即可
87. 648. Replace Words
1. https://leetcode.com/problems/replace-words/
2. 字符串替换成前缀
1. Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
2. Output: "the cat was rat by the bat"
3. 字典树
88. 451. Sort Characters By Frequency
1. https://leetcode.com/problems/sort-characters-by-frequency/
2. 按照字符出现的次数排序
1. Input: s = "tree"
2. Output: "eert"
89. 1786. Number of Restricted Paths From First to Last Node
1. https://leetcode.com/problems/number-of-restricted-paths-from-first-to-last-node/
2. 图的最短路径：[i, j, weight]，求从节点 1 到节点 n 的最短路径
1. Input: n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
2. Output: 3
3. Dijkstra pop min：需要用 priority queue 才行
1. floid i/j/k 三层
90. 173. Binary Search Tree Iterator
1. https://leetcode.com/problems/binary-search-tree-iterator/
2. bst 树支持 next 操作
1. Input ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"] [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
2. Output [null, 3, 7, true, 9, true, 15, true, 20, false]
3. 用 stack 去模拟中序遍历的过程
91. 979. Distribute Coins in Binary Tree
1. https://leetcode.com/problems/distribute-coins-in-binary-tree/
2. 每个节点有 coin 可以往相邻节点转移，转移多少次可以每个都有一个
3. 保证所有节点初始 coin 数量和 = 节点数
1. Input: root = [3,0,0]
2. Output: 2
4. 递归，重点 pair<int, int> 返回的是什么，是 <coin count, node count>
92. 1910. Remove All Occurrences of a Substring
1. https://leetcode.com/problems/remove-all-occurrences-of-a-substring/
2. 找到 a 中所有匹配 b 的字串 然后删除：中间可以拼出来新的要删除的
1. Input: s = "daabcbaabcbc", part = "abc"
2. Output: "dab"
3. 遍历每次都比较最后的 a.substr(a.length()-b-1, b.length()) 即可
93. 1737. Change Minimum Characters to Satisfy One of Three Conditions
1. https://leetcode.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/
2. a/b 两个字符串，每次操作可以把 a/b 的任意字符改成另外的任意字符
3. 求最少操作次数使得 min(a) > max(b) or min(b) > max(a) or a/b 全相同
1. Input: a = "dabadd", b = "cda"
2. Output: 3
4. 统计次数 + 前缀和：以某个字符为边界，a 全部小于等于 b 全部大于 (或者反过来)
94. 388. Longest Absolute File Path
1. https://leetcode.com/problems/longest-absolute-file-path/
1. Input: input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
2. Output: 32
2. 字符串处理最大难度是 \n \t 是一个字符
3. 需要用 stack 记录每层的信息
95. 341. Flatten Nested List Iterator
1. https://leetcode.com/problems/flatten-nested-list-iterator/
2. 给定带嵌套关系的 struct，将起转成序列
1. Input: nestedList = [1,[4,[6]]]
2. Output: [1,4,6]
3. stack + 递归
1. 用模拟函数参数栈的方式处理嵌套的 struct
96. 1387. Sort Integers by The Power Value
1. https://leetcode.com/problems/sort-integers-by-the-power-value/

1. 按照某种规则变换数字，最后变成 1；把 [lo,hi] 的数字按照 pow 排序，然后返回第 k 个数
1. Input: lo = 12, hi = 15, k = 2
2. Output: 13
2. 直接算然后取第 k 大的数
97. 1535. Find the Winner of an Array Game
1. https://leetcode.com/problems/find-the-winner-of-an-array-game/
2. a[0] 和 a[1] 比较，小的放到最后，问连续比较赢至少 k 次的是谁
1. Input: arr = [2,1,3,5,4,6,7], k = 2
2. Output: 5
3. 如果是 k>size()-1 直接是最大
4. 否则 a[i] 赢 说明 a[i] > max(a[0] ... a[i-1]) 且 a[i] > (a[i+1]... a[i+k-2])
98. 958. Check Completeness of a Binary Tree
1. https://leetcode.com/problems/check-completeness-of-a-binary-tree/
2. In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible：二叉树是否是每层都优先排 left 节点的
1. Input: root = [1,2,3,4,5,6]
2. Output: true
3. 层次遍历，同时处理 left == nil && right != nil 等特殊情况
99. 2261. K Divisible Elements Subarrays
1. https://leetcode.com/problems/k-divisible-elements-subarrays/
2. 给定序列，寻找子序列的数量，子序列满足：被 p 整除的数字个数 <= k
1. Input: nums = [2,3,3,2,2], k = 2, p = 2
2. Output: 11
3. 解释
1. [2], [2,3], [2,3,3], [2,3,3,2], [3], [3,3], [3,3,2], [3,3,2,2], [3,2], [3,2,2], [2,2]
2. 还要去重，比如 [2]
3. 从左往右的同时记录 “能被 p 整除的数字” 的 index
100. 2280. Minimum Lines to Represent a Line Chart
1. https://leetcode.com/problems/minimum-lines-to-represent-a-line-chart/
2. 给定的坐标总共连成多少条线段
1. Input: stockPrices = [[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]]
2. Output: 3
3. 按照 x,y 的顺序排序之后遍历