Leetcode 刷题汇总系列(2)
注:
黄色:简单
绿色:可以重复练习
蓝色:稍有难度
- 2. Add Two Numbers
- https://leetcode.com/problems/add-two-numbers/
- 用链表表示的数字,求和
- Input: l1 = [2,4,3], l2 = [5,6,4]
- Output: [7,0,8]
- 前缀 listnode
- 155. Min Stack
- https://leetcode.com/problems/min-stack/
- Input["MinStack","push","push","push","getMin","pop","top","getMin"][[],[-2],[0],[-3],[],[],[],[]]
- Output[null,null,null,null,-3,null,0,-2]
- 两个栈:两个都需要存全量的数据,只是第二个每次都 push 当前的 min 而已
- 1019. Next Greater Node In Linked List
- https://leetcode.com/problems/next-greater-node-in-linked-list/
- 计算每个链表元素,最近一个比他大的元素 (以序列形式返回)
- Input: head = [2,1,5]
- Output: [5,5,0]
- O(N) stack 就行
- 641. Design Circular Deque
- https://leetcode.com/problems/design-circular-deque/
- 实现一个环形 queue
- Input ["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"] [[3], [1], [2], [3], [4], [], [], [], [4], []]
- Output [null, true, true, true, false, 2, true, true, true, 4]
- 数组 + index 模拟
- 526. Beautiful Arrangement
- https://leetcode.com/problems/beautiful-arrangement/
- [1, 2, ..., n] 的全排列,求其中符合要求的序列个数:a[i] 被 i 整除 或者 i 被 a[i] 整除
- Input: n = 2
- Output: 2
- 先把每个位置上可选的候选集弄出来,然后 dfs (visited)
- 935. Knight Dialer
- https://leetcode.com/problems/knight-dialer/
- 手机键盘,每次拨号只能走 “马”,起点随机,拨 n 次可能拨出多少号码
- Input: n = 2
- Output: 20
- dp:其实是很简单的转移方程 -> f(n) = sum(f(n-1)) 这种情况时不要紧张
- 452. Minimum Number of Arrows to Burst Balloons
- https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/
- 给定区间序列,求最少需要多少点可以把这些区间都覆盖
- Input: points = [[10,16],[2,8],[1,6],[7,12]]
- Output: 2
- 和上课有点像,排序即可
- vector sort + 边界处理 + 用指针引用 vector 可以减少很多时间
- 1400. Construct K Palindrome Strings
- https://leetcode.com/problems/construct-k-palindrome-strings/
- 给个字符串,用字符串里的所有字符,组成 k 个子串,且 k 个都是回文,问能不能做到
- Input: s = "annabelle", k = 2
- Output: true
- 奇数字符个数 <= k 即可,脑经急转弯
- 1401. Circle and Rectangle Overlapping
- https://leetcode.com/problems/circle-and-rectangle-overlapping/
- 圆和矩形是否相交(矩形和坐标轴平行)
- Input: radius = 1, xCenter = 0, yCenter = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
- Output: true
- 不能直接转化为两个矩形是否正交的问题
- https://hackmd.io/@bob81135/Leetcode_1401
- https://blog.csdn.net/fuxuemingzhu/article/details/105331519
- 970. Powerful Integers
- https://leetcode.com/problems/powerful-integers/
- 给定 i 和 j 和 t,求 i^x + j^y <= t 的数量
- Input: x = 2, y = 3, bound = 10
- Output: [2,3,4,5,7,9,10]
- 思路类似两个指针
- a / b 有序序列,求 a[i] + b[j] <= target 的数量
- 其实是剪枝策略:较小的 a 和某个 b 都已经超过了,那么较大的 a 不用和更大的 b 比较了
- 1798. Maximum Number of Consecutive Values You Can Make
- https://leetcode.com/problems/maximum-number-of-consecutive-values-you-can-make/
- 给你不同面额的硬币各若干,求 从 0 开始的金额能连续构造出来多少
- Input: coins = [1,1,1,4]
- Output: 8
- 排序:if a[i] <= x+1, x+=a[i] else 后面的肯定也不行,因为构造不出来 x+1 了
- 811. Subdomain Visit Count
- https://leetcode.com/problems/subdomain-visit-count/
- 统计域名和子域名出现的次数
- Input: cpdomains = ["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
- Output: ["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
- 字符串处理
- 1915. Number of Wonderful Substrings
- https://leetcode.com/problems/number-of-wonderful-substrings/
- 求字符串的 wonderful 子串数量,wonderful = 最多只有一个字符出现奇数次
- Input: word = "aabb"
- Output: 9
- 用 bitmask 的形式来表现一个字符串中每个字符的奇偶状态
- 根据条件, 我们找到与当前 bitmask 相同和差一位的所有**之前的**字符串的数量
- 2149. Rearrange Array Elements by Sign
- https://leetcode.com/problems/rearrange-array-elements-by-sign/
- 按照 偶奇偶奇 的顺序排序
- Input: nums = [3,1,-2,-5,2,-4]
- Output: [3,-2,1,-5,2,-4]
- 重点是需要原地做,实现起来不麻烦
- 2038. Remove Colored Pieces if Both Neighbors are the Same Color
- https://leetcode.com/problems/remove-colored-pieces-if-both-neighbors-are-the-same-color/
- 只有连续 AAA 或者连续 BBB 才能删除中间的,求最后是 A 不能删还是 B 不能删
- 如果是 B 不能则返回 true,否则返回 false
- Input: colors = "AAABABB"
- Output: true
- 因为删除 A 或者 B 都不会影响后续的博弈,所以就遍历计算数量即可
- 779. K-th Symbol in Grammar
- https://leetcode.com/problems/k-th-symbol-in-grammar/
- 0 -> 01 -> 0110 -> 01101001
- n 表示变化多少次,k 表示返回第 k 个字符
- Input: n = 2, k = 2
- Output: 1
- 找到规律就好解决了
- 1451. Rearrange Words in a Sentence
- https://leetcode.com/problems/rearrange-words-in-a-sentence/
- 按照长度重新排列(稳定排序)
- Input: text = "Leetcode is cool"
- Output: "Is cool leetcode"
- 排序 + 字符串处理; 好像可以计数排序
- 856. Score of Parentheses
- https://leetcode.com/problems/score-of-parentheses/
- ()=1 && (a) = 2*a && ab=a+b,求字符串得分
- Input: s = "()()"
- Output: 2
- stack
- 需要区分记录是 ( 还是中间结果
- 2120. Execution of All Suffix Instructions Staying in a Grid
- https://leetcode.com/problems/execution-of-all-suffix-instructions-staying-in-a-grid/
- DFS 机器人走格子,计算 “假设从 s 的每个 index 开始能走的步数”
- Input: n = 3, startPos = [0,1], s = "RRDDLU"
- Output: [1,5,4,3,1,0]
- 1234. Replace the Substring for Balanced String
- https://leetcode.com/problems/replace-the-substring-for-balanced-string/
- string 变成 4 个字符 (QWER) 出现的次数都相同,最小变多少 “连续的子串”
- Input: s = "QQQW"
- Output: 2
- Use 2-pointers algorithm to make sure all amount of characters outside the 2 pointers are smaller or equal to n/4.
- 滑动窗口
- 1286. Iterator for Combination
- https://leetcode.com/problems/iterator-for-combination/
- 字符串的全排列
- Input ["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"] [["abc", 2], [], [], [], [], [], []]
- Output [null, "ab", true, "ac", true, "bc", false]
- 这道题就是全排列的逐个递增式写法
- 先找到需要 +1 的位置:nums[i]+1 在 i 后面
- 然后 nums[i] = nums[i]+1,然后把后面的数字 sort 一下之后依次填入
- 769. Max Chunks To Make Sorted
- https://leetcode.com/problems/max-chunks-to-make-sorted/
- 数组分段排序,排完本身也就有序了,问最多分多少段
- 如果序列的长度是 n,那么序列里的内容肯定是 [0, n-1] 的某个排列
- Input: arr = [1,0,2,3,4]
- Output: 4
- 找最大值:如果前 i 个最大数等于 i,那么 a[i] 肯定可以可以单独分一段,且前后最大段都不会受到影响
- o(n)
- 1376. Time Needed to Inform All Employees
- https://leetcode.com/problems/time-needed-to-inform-all-employees/
- 一棵树,遍历完,需要多少 cost
- n 是节点数,manager 表示每个 index 的父亲 index,informerTime 表示父亲通知儿子的时间
- Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
- Output: 1
- dfs
- 36. Valid Sudoku
- https://leetcode.com/problems/valid-sudoku/
- 数独
- 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"]]
- Output: true
- dfs:重点是方形的区间如何表达
- 522. Longest Uncommon Subsequence II
- https://leetcode.com/problems/longest-uncommon-subsequence-ii/
- 最长非公共子序列
- An uncommon subsequence between an array of strings is a string that is a subsequence of one string but not the others.
- A subsequence of a string s is a string that can be obtained after deleting any number of characters from s.
- Input: strs = ["aba","cdc","eae"]
- Output: 3
- 最终结果一定等于某个序列的长度
- 如果结果 < 所有的序列,那么最长的那个肯定也是的
- 647. Palindromic Substrings
- https://leetcode.com/problems/palindromic-substrings/
- 回文子串的数量
- Input: s = "aaa"
- Output: 6
- dp 即可 -> 写的时候不要装逼写单层数组
- 994. Rotting Oranges
- https://leetcode.com/problems/rotting-oranges/
- 矩阵中,橘子坏影响四周,橘子分好坏,每分钟坏橘子都会让四周的好橘子变坏,求可以撑多少分钟
- Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
- Output: 4
- bfs
- 2245. Maximum Trailing Zeros in a Cornered Path
- https://leetcode.com/problems/maximum-trailing-zeros-in-a-cornered-path/
- 矩阵中最多转一次且不能走重复路,求乘积最大的后缀 0 数量
- 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]]
- Output: 3
- 以 [i,j] 为转折点
- 877. Stone Game
- https://leetcode.com/problems/stone-game/
- 两个人依次从首或者尾取硬币,求最终先手是否稳赢 (谁的数字和最大谁赢)
- Input: piles = [5,3,4,5]
- Output: true
- dp 即可
- 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]))
- j 是长度:常见的 dp 最外层循环的写法
- 面对这种题目能用 dp 表达的肯定也能用 dfs,选一个好写的即可
- 470. Implement Rand10() Using Rand7()
- https://leetcode.com/problems/implement-rand10-using-rand7/
- Input: n = 1
- Output: [2]
- (rand7()-1) * 7 + rand7():超过就不要呗
- 1882. Process Tasks Using Servers
- https://leetcode.com/problems/process-tasks-using-servers/
- 计算每个 task 最终会被哪个 server 处理
- server 数组表示的是权重 (每次都从不忙的 server 中取权重最小的执行 task)
- tasks 数组表示的是每个任务执行的时间
- cases
- Input: servers = [3,3,2], tasks = [1,2,3,2,1,2]
- Output: [2,2,0,2,1,2]
- priority_queue
- waiting_queue 和 running_queue,前者用完成时间排序,后者用 weight 排序
- 172. Factorial Trailing Zeroes
- https://leetcode.com/problems/factorial-trailing-zeroes/
- 阶乘的后缀 0 数量
- Input: n = 5
- Output: 1
- 其实就是数 5 的倍数的数量
- 1300. Sum of Mutated Array Closest to Target
- https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/
- 把序列中比 x 大的都变成 x 使得 sum 和 target 最接近,求 x
- Input: arr = [60864,25176,27249,21296,20204], target = 56803
- Output: 11361
- 先 sort 然后再用二分,target > sum 就往右边去,否则就往左边去
- 其实第二步不需要 log(n),直接遍历用 o(n) 的就可以
- 1261. Find Elements in a Contaminated Binary Tree
- https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree/
- 根据规则重建 tree 反查某个数在不在
- Input ["FindElements","find","find"][[[-1,null,-1]],[1],[2]
- Output[null,false,true]
- 1410. HTML Entity Parser
- https://leetcode.com/problems/html-entity-parser/
- 字符串处理,去掉特殊字符串
- Input: text = "& is an HTML entity but &ambassador; is not."
- Output: "& is an HTML entity but &ambassador; is not."
- 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum
- https://leetcode.com/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/
- 找到两个子序列,和为 target,且不正交,求满足条件的子序列的元素数量和的最小值
- Input: arr = [7,3,4,7], target = 7
- Output: 2
- 只统计一序列的最小长度比较简单:前缀和即可
- 如果统计两个序列的最小长度,则在一个的基础上记录 min_len[i] 即可
- 648. Replace Words
- https://leetcode.com/problems/replace-words/
- 字符串替换成前缀
- Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
- Output: "the cat was rat by the bat"
- 字典树
- 451. Sort Characters By Frequency
- https://leetcode.com/problems/sort-characters-by-frequency/
- 按照字符出现的次数排序
- Input: s = "tree"
- Output: "eert"
- 1786. Number of Restricted Paths From First to Last Node
- https://leetcode.com/problems/number-of-restricted-paths-from-first-to-last-node/
- 图的最短路径:[i, j, weight],求从节点 1 到节点 n 的最短路径
- 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]]
- Output: 3
- Dijkstra pop min:需要用 priority queue 才行
- floid i/j/k 三层
- 173. Binary Search Tree Iterator
- https://leetcode.com/problems/binary-search-tree-iterator/
- bst 树支持 next 操作
- Input ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"] [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
- Output [null, 3, 7, true, 9, true, 15, true, 20, false]
- 用 stack 去模拟中序遍历的过程
- 979. Distribute Coins in Binary Tree
- https://leetcode.com/problems/distribute-coins-in-binary-tree/
- 每个节点有 coin 可以往相邻节点转移,转移多少次可以每个都有一个
- 保证所有节点初始 coin 数量和 = 节点数
- Input: root = [3,0,0]
- Output: 2
- 递归,重点 pair 返回的是什么,是
- 1910. Remove All Occurrences of a Substring
- https://leetcode.com/problems/remove-all-occurrences-of-a-substring/
- 找到 a 中所有匹配 b 的字串 然后删除:中间可以拼出来新的要删除的
- Input: s = "daabcbaabcbc", part = "abc"
- Output: "dab"
- 遍历每次都比较最后的 a.substr(a.length()-b-1, b.length()) 即可
- 1737. Change Minimum Characters to Satisfy One of Three Conditions
- https://leetcode.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/
- a/b 两个字符串,每次操作可以把 a/b 的任意字符改成另外的任意字符
- 求最少操作次数使得 min(a) > max(b) or min(b) > max(a) or a/b 全相同
- Input: a = "dabadd", b = "cda"
- Output: 3
- 统计次数 + 前缀和:以某个字符为边界,a 全部小于等于 b 全部大于 (或者反过来)
- 388. Longest Absolute File Path
- https://leetcode.com/problems/longest-absolute-file-path/
- Input: input = "dir
subdir1
file1.ext
subsubdir1
subdir2
subsubdir2
file2.ext"
- Output: 32
- 字符串处理最大难度是
是一个字符
- 需要用 stack 记录每层的信息
- 341. Flatten Nested List Iterator
- https://leetcode.com/problems/flatten-nested-list-iterator/
- 给定带嵌套关系的 struct,将起转成序列
- Input: nestedList = [1,[4,[6]]]
- Output: [1,4,6]
- stack + 递归
- 用模拟函数参数栈的方式处理嵌套的 struct
- 1387. Sort Integers by The Power Value
- https://leetcode.com/problems/sort-integers-by-the-power-value/
- 按照某种规则变换数字,最后变成 1;把 [lo,hi] 的数字按照 pow 排序,然后返回第 k 个数
- Input: lo = 12, hi = 15, k = 2
- Output: 13
- 直接算然后取第 k 大的数
- 1535. Find the Winner of an Array Game
- https://leetcode.com/problems/find-the-winner-of-an-array-game/
- a[0] 和 a[1] 比较,小的放到最后,问连续比较赢至少 k 次的是谁
- Input: arr = [2,1,3,5,4,6,7], k = 2
- Output: 5
- 如果是 k>size()-1 直接是最大
- 否则 a[i] 赢 说明 a[i] > max(a[0] ... a[i-1]) 且 a[i] > (a[i+1]... a[i+k-2])
- 958. Check Completeness of a Binary Tree
- https://leetcode.com/problems/check-completeness-of-a-binary-tree/
- 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 节点的
- Input: root = [1,2,3,4,5,6]
- Output: true
- 层次遍历,同时处理 left == nil && right != nil 等特殊情况
- 2261. K Divisible Elements Subarrays
- https://leetcode.com/problems/k-pisible-elements-subarrays/
- 给定序列,寻找子序列的数量,子序列满足:被 p 整除的数字个数 <= k
- Input: nums = [2,3,3,2,2], k = 2, p = 2
- Output: 11
- 解释
- [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]
- 从左往右的同时记录 “能被 p 整除的数字” 的 index
- 2280. Minimum Lines to Represent a Line Chart
- https://leetcode.com/problems/minimum-lines-to-represent-a-line-chart/
- 给定的坐标总共连成多少条线段
- Input: stockPrices = [[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]]
- Output: 3
- 按照 x,y 的顺序排序之后遍历
页面更新:2024-03-03
标签:遍历 前缀 数组 节点 字符串 序列 长度 字符 数量 数字 系列
1
2
3
4
5
上滑加载更多 ↓
所有内容加载完毕