八年級數(shù)學雙矩形問題;八年級數(shù)學雙矩形問題公式

注：

黃色：簡單

綠色：可以重復練習

藍色：稍有難度

1. 2. Add Two Numbers
1. https://leetcode.com/problems/add-two-numbers/
2. 用鏈表表示的數(shù)字，求和
1. Input: l1 = [2,4,3], l2 = [5,6,4]
2. Output: [7,0,8]
3. 前綴 listnode
2. 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. 兩個棧：兩個都需要存全量的數(shù)據(jù)，只是第二個每次都 push 當前的 min 而已
3. 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 就行
4. 641. Design Circular Deque
1. https://leetcode.com/problems/design-circular-deque/
2. 實現(xiàn)一個環(huán)形 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. 數(shù)組 + index 模擬
5. 526. Beautiful Arrangement
1. https://leetcode.com/problems/beautiful-arrangement/
2. [1, 2, ..., n] 的全排列，求其中符合要求的序列個數(shù)：a[i] 被 i 整除 或者 i 被 a[i] 整除
1. Input: n = 2
2. Output: 2
3. 先把每個位置上可選的候選集弄出來，然后 dfs (visited)
6. 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)) 這種情況時不要緊張
7. 452. Minimum Number of Arrows to Burst Balloons
1. https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/
2. 給定區(qū)間序列，求最少需要多少點可以把這些區(qū)間都覆蓋
1. Input: points = [[10,16],[2,8],[1,6],[7,12]]
2. Output: 2
3. 和上課有點像，排序即可
1. vector sort + 邊界處理 + 用指針引用 vector 可以減少很多時間
8. 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. 奇數(shù)字符個數(shù) <= k 即可，腦經(jīng)急轉彎
9. 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

1. 970. Powerful Integers
1. https://leetcode.com/problems/powerful-integers/
2. 給定 i 和 j 和 t，求 i^x + j^y <= t 的數(shù)量
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 的數(shù)量
2. 其實是剪枝策略：較小的 a 和某個 b 都已經(jīng)超過了，那么較大的 a 不用和更大的 b 比較了
2. 1798. Maximum Number of Consecutive Values You Can Make
1. https://leetcode.com/problems/maximum-number-of-consecutive-values-you-can-make/
2. 給你不同面額的硬幣各若干，求 從 0 開始的金額能連續(xù)構造出來多少
1. Input: coins = [1,1,1,4]
2. Output: 8
3. 排序：if a[i] <= x+1, x+=a[i] else 后面的肯定也不行，因為構造不出來 x+1 了
3. 811. Subdomain Visit Count
1. https://leetcode.com/problems/subdomain-visit-count/
2. 統(tǒng)計域名和子域名出現(xiàn)的次數(shù)
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. 字符串處理
4. 1915. Number of Wonderful Substrings
1. https://leetcode.com/problems/number-of-wonderful-substrings/
2. 求字符串的 wonderful 子串數(shù)量，wonderful = 最多只有一個字符出現(xiàn)奇數(shù)次
1. Input: word = "aabb"
2. Output: 9
3. 用 bitmask 的形式來表現(xiàn)一個字符串中每個字符的奇偶狀態(tài)
4. 根據(jù)條件， 我們找到與當前 bitmask 相同和差一位的所有**之前的**字符串的數(shù)量
5. 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. 重點是需要原地做，實現(xiàn)起來不麻煩
6. 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. 只有連續(xù) AAA 或者連續(xù) BBB 才能刪除中間的，求最后是 A 不能刪還是 B 不能刪
1. 如果是 B 不能則返回 true，否則返回 false
2. Input: colors = "AAABABB"
3. Output: true
3. 因為刪除 A 或者 B 都不會影響后續(xù)的博弈，所以就遍歷計算數(shù)量即可
7. 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. 找到規(guī)律就好解決了
8. 1451. Rearrange Words in a Sentence
1. https://leetcode.com/problems/rearrange-words-in-a-sentence/
2. 按照長度重新排列（穩(wěn)定排序）
1. Input: text = "Leetcode is cool"
2. Output: "Is cool leetcode"
3. 排序 + 字符串處理; 好像可以計數(shù)排序
9. 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. 需要區(qū)分記錄是 ( 還是中間結果
10. 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 開始能走的步數(shù)”
1. Input: n = 3, startPos = [0,1], s = "RRDDLU"
2. Output: [1,5,4,3,1,0]
11. 1234. Replace the Substring for Balanced String
1. https://leetcode.com/problems/replace-the-substring-for-balanced-string/
2. string 變成 4 個字符 (QWER) 出現(xiàn)的次數(shù)都相同，最小變多少 “連續(xù)的子串”
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. 滑動窗口
12. 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，然后把后面的數(shù)字 sort 一下之后依次填入
13. 769. Max Chunks To Make Sorted
1. https://leetcode.com/problems/max-chunks-to-make-sorted/
2. 數(shù)組分段排序，排完本身也就有序了，問最多分多少段
3. 如果序列的長度是 n，那么序列里的內(nèi)容肯定是 [0, n-1] 的某個排列
1. Input: arr = [1,0,2,3,4]
2. Output: 4
4. 找最大值：如果前 i 個最大數(shù)等于 i，那么 a[i] 肯定可以可以單獨分一段，且前后最大段都不會受到影響
1. o(n)
14. 1376. Time Needed to Inform All Employees
1. https://leetcode.com/problems/time-needed-to-inform-all-employees/
2. 一棵樹，遍歷完，需要多少 cost
3. n 是節(jié)點數(shù)，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
15. 36. Valid Sudoku
1. https://leetcode.com/problems/valid-sudoku/
2. 數(shù)獨
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：重點是方形的區(qū)間如何表達
16. 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. 如果結果 < 所有的序列，那么最長的那個肯定也是的
17. 647. Palindromic Substrings
1. https://leetcode.com/problems/palindromic-substrings/
2. 回文子串的數(shù)量
1. Input: s = "aaa"
2. Output: 6
3. dp 即可 -> 寫的時候不要寫單層數(shù)組
18. 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
19. 2245. Maximum Trailing Zeros in a Cornered Path
1. https://leetcode.com/problems/maximum-trailing-zeros-in-a-cornered-path/
2. 矩陣中最多轉一次且不能走重復路，求乘積最大的后綴 0 數(shù)量
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] 為轉折點
20. 877. Stone Game
1. https://leetcode.com/problems/stone-game/
2. 兩個人依次從首或者尾取硬幣，求最終先手是否穩(wěn)贏 (誰的數(shù)字和最大誰贏)
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 最外層循環(huán)的寫法
4. 面對這種題目能用 dp 表達的肯定也能用 dfs，選一個好寫的即可
21. 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()：超過就不要唄
22. 1882. Process Tasks Using Servers
1. https://leetcode.com/problems/process-tasks-using-servers/
2. 計算每個 task 最終會被哪個 server 處理
1. server 數(shù)組表示的是權重 (每次都從不忙的 server 中取權重最小的執(zhí)行 task)
2. tasks 數(shù)組表示的是每個任務執(zhí)行的時間
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 排序
23. 172. Factorial Trailing Zeroes
1. https://leetcode.com/problems/factorial-trailing-zeroes/
2. 階乘的后綴 0 數(shù)量
1. Input: n = 5
2. Output: 1
3. 其實就是數(shù) 5 的倍數(shù)的數(shù)量
24. 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) 的就可以
25. 1261. Find Elements in a Contaminated Binary Tree
1. https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree/
2. 根據(jù)規(guī)則重建 tree 反查某個數(shù)在不在
1. Input ["FindElements","find","find"][[[-1,null,-1]],[1],[2]
2. Output[null,false,true]
26. 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."
27. 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，且不正交，求滿足條件的子序列的元素數(shù)量和的最小值
1. Input: arr = [7,3,4,7], target = 7
2. Output: 2
3. 只統(tǒng)計一序列的最小長度比較簡單：前綴和即可
4. 如果統(tǒng)計兩個序列的最小長度，則在一個的基礎上記錄 min_len[i] 即可
28. 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. 字典樹
29. 451. Sort Characters By Frequency
1. https://leetcode.com/problems/sort-characters-by-frequency/
2. 按照字符出現(xiàn)的次數(shù)排序
1. Input: s = "tree"
2. Output: "eert"
30. 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]，求從節(jié)點 1 到節(jié)點 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 三層
31. 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 去模擬中序遍歷的過程
32. 979. Distribute Coins in Binary Tree
1. https://leetcode.com/problems/distribute-coins-in-binary-tree/
2. 每個節(jié)點有 coin 可以往相鄰節(jié)點轉移，轉移多少次可以每個都有一個
3. 保證所有節(jié)點初始 coin 數(shù)量和 = 節(jié)點數(shù)
1. Input: root = [3,0,0]
2. Output: 2
4. 遞歸，重點 pair<int, int> 返回的是什么，是 <coin count, node count>
33. 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()) 即可
34. 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. 求最少操作次數(shù)使得 min(a) > max(b) or min(b) > max(a) or a/b 全相同
1. Input: a = "dabadd", b = "cda"
2. Output: 3
4. 統(tǒng)計次數(shù) + 前綴和：以某個字符為邊界，a 全部小于等于 b 全部大于 (或者反過來)
35. 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 記錄每層的信息
36. 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. 用模擬函數(shù)參數(shù)棧的方式處理嵌套的 struct
37. 1387. Sort Integers by The Power Value
1. https://leetcode.com/problems/sort-integers-by-the-power-value/

1. 按照某種規(guī)則變換數(shù)字，最后變成 1；把 [lo,hi] 的數(shù)字按照 pow 排序，然后返回第 k 個數(shù)
1. Input: lo = 12, hi = 15, k = 2
2. Output: 13
2. 直接算然后取第 k 大的數(shù)
1. 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] 比較，小的放到最后，問連續(xù)比較贏至少 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])
2. 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：二叉樹是否是每層都優(yōu)先排 left 節(jié)點的
1. Input: root = [1,2,3,4,5,6]
2. Output: true
3. 層次遍歷，同時處理 left == nil && right != nil 等特殊情況
3. 2261. K Divisible Elements Subarrays
1. https://leetcode.com/problems/k-divisible-elements-subarrays/
2. 給定序列，尋找子序列的數(shù)量，子序列滿足：被 p 整除的數(shù)字個數(shù) <= 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 整除的數(shù)字” 的 index
4. 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 的順序排序之后遍歷