刷题记录帖子

Myron2017

3963. Create Grid With Exactly One Path

You are given two integers m and n, representing the number of rows and columns of a grid.
Construct any m x n grid consisting only of the characters '.' and '#', where:
'.' represents a free cell.
'#' represents an obstacle cell.
A valid path is a sequence of free cells that:
Starts at the top-left cell (0, 0).
Ends at the bottom-right cell (m - 1, n - 1).
Moves only:Right, from (i, j) to (i, j + 1), or
Down, from (i, j) to (i + 1, j).
Return any grid such that there is exactly one valid path from the top-left cell to the bottom-right cell.

Example 1:
Input: m = 2, n = 3
Output: ["..#","#.."]
Explanation:

The only valid path is: (0,0) → (0,1) → (1,1) → (1,2)
Example 2:
Input: m = 3, n = 3
Output: ["..#","#..","##."]
Explanation:

The only valid path is: (0,0) → (0,1) → (1,1) → (1,2) → (2,2)
Example 3:
Input: m = 1, n = 4
Output: ["...."]
Explanation:
The only valid path is: (0,0) → (0,1) → (0,2) → (0,3)

Constraints:
1 <= m, n <= 25

class Solution:
def createGrid(self, m: int, n: int) -> list[str]:
grid = []
for _ in range(m):
grid.append(['#']*n)
for i in range(m):
grid[i][0] = '.'
for j in range(n):
grid[m-1] = ['.'] * n
for i in range(m):
grid[i] = "".join(grid[i])
return grid

复制代码

简单题，直接走 L 型。

当然还是可以提高我的代码的，主要是我在最后一列忘了去掉循环了，其实在重复做无用功。。。。

最大的槽点在这里：Python for j in range(n):
grid[m-1] = ['.'] * n
你在这里用了一个 for 循环，但循环体内做的却是“把最后一行整个替换成了 $n$ 个 .”。这意味着你把一模一样的赋值操作重复执行了 $n$ 次。其实你只需要执行一次赋值就够了。另外关于列表初始化和字符串拼接：使用 grid.append(['#']*n) 是可以的，但在 Python 中，通常我们更喜欢用列表推导式 (List Comprehension)，不仅可读性更好，执行速度也稍快一点。最后的合并操作 "".join(grid[i]) 同样可以用列表推导式一行搞定。

class Solution:
def createGrid(self, m: int, n: int) -> list[str]:
# 1. 初始化全为 '#' 的 m x n 网格
grid = [['#'] * n for _ in range(m)]
# 2. 打通第一列（全设为 '.'）
for i in range(m):
grid[i][0] = '.'
# 3. 打通最后一行（全设为 '.'），直接赋值即可，无需循环
grid[m-1] = ['.'] * n
# 4. 把每一行的字符列表拼成字符串，并返回
return ["".join(row) for row in grid]

复制代码

Myron2017

LC. 3954. Sum of Compatible Numbers in Range I

class Solution:
def sumOfGoodIntegers(self, n: int, k: int) -> int:
ans = 0
for x in range(n-k, n+k+1):
if x >0 and (n & x) == 0:
ans += x
return ans

复制代码

Myron2017

252. Meeting Rooms
You are given an array of meeting times intervals where intervals[i] = [starti, endi].

A person can attend all meetings if no two meeting intervals overlap. Meetings ending at time t and starting at time t do not overlap.

Return true if a person can attend all meetings. Otherwise, return false.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false
Example 2:

Input: intervals = [[7,10],[2,4]]
Output: true

Constraints:

0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti < endi <= 106

经典题，还是喜欢刷 Leetcode 经典题，比现在生搬硬套的题目强多了。

核心是

先排序，然后比较相邻元素即可

如果有多个相同 start time 的meeting 肯定不能同时参加；所以需要考虑的是 start time 错开了的话，那么相邻的两个会，前一个的结束是不是在后一个开始之前或者那一刻，因为题目允许重叠。

算法步骤：

按开始时间排序：我们以每个会议的开始时间为基准，对整个 intervals 数组进行升序排序。

顺序遍历对比：排序后，我们只需要比较相邻的两个会议。

判断冲突：比较“前一个会议的结束时间”和“当前会议的开始时间”。如果前一个会议的结束时间 > 当前会议的开始时间，说明两个会议时间有交叉，直接返回 False。

顺利通关：如果遍历完所有的相邻会议都没有冲突，返回 True。

class Solution:
def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
# 边界情况：如果没有会议，自然可以全部参加
if not intervals:
return True
# 核心技巧 1：按照会议的“开始时间”进行升序排序
# x[0] 代表取每个区间的第一个元素（即开始时间）
intervals.sort(key=lambda x: x[0])
# 核心技巧 2：从第二个会议开始遍历，和前一个对比
for i in range(1, len(intervals)):
# 前一个会议：intervals[i-1]
# 当前会议：intervals[i]
# 如果前一个的结束时间严格大于当前的开始时间，说明冲突了
if intervals[i-1][1] > intervals[i][0]:
return False
# 遍历完没有发现任何冲突
return True

复制代码

Myron2017

LC. 1967. Number of Strings That Appear as Substrings in Word
Hint
Given an array of strings patterns and a string word, return the number of strings in patterns that exist as a substring in word.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: patterns = ["a","abc","bc","d"], word = "abc"
Output: 3
Explanation:
- "a" appears as a substring in "abc".
- "abc" appears as a substring in "abc".
- "bc" appears as a substring in "abc".
- "d" does not appear as a substring in "abc".
3 of the strings in patterns appear as a substring in word.
Example 2:

Input: patterns = ["a","b","c"], word = "aaaaabbbbb"
Output: 2
Explanation:
- "a" appears as a substring in "aaaaabbbbb".
- "b" appears as a substring in "aaaaabbbbb".
- "c" does not appear as a substring in "aaaaabbbbb".
2 of the strings in patterns appear as a substring in word.
Example 3:

Input: patterns = ["a","a","a"], word = "ab"
Output: 3
Explanation: Each of the patterns appears as a substring in word "ab".

Constraints:

1 <= patterns.length <= 100
1 <= patterns[i].length <= 100
1 <= word.length <= 100
patterns[i] and word consist of lowercase English letters.

我的解法

class Solution:
def numOfStrings(self, patterns: List[str], word: str) -> int:
set_pattern = set()
ans = 0
for i in range(len(word)):
for j in range(i, len(word)):
if word[i:j+1] not in set_pattern:
set_pattern.add(word[i:j+1])
for p in patterns:
if p in set_pattern:
ans += 1
return ans

复制代码

优化

3. 核心思路与优化写法解法一：利用 Python 原生 in 操作符（最推荐、最实用）在 Python 中，判断 A 是否是 B 的子串，最优雅也最高效的方式就是直接使用 A in B。Python 底层的字符串匹配算法（类似 Boyer-Moore-Horspool 算法的变体）非常快，对于日常开发和绝大多数面试题来说，这也是标准写法。优化后的代码：Pythonclass Solution:

def numOfStrings(self, patterns: List[str], word: str) -> int:
ans = 0
for p in patterns:
if p in word: # 直接判断 p 是否为 word 的子串
ans += 1
return ans

复制代码

如果你想在面试官面前秀一下 Pythonic 的基本功，可以写成一行：Pythonclass Solution:

def numOfStrings(self, patterns: List[str], word: str) -> int:
# 解释：p in word 返回 True(1) 或 False(0)，sum() 可以直接把它们加起来
return sum(p in word for p in patterns)

复制代码

复杂度分析：时间复杂度：$O(M \times L \times N)$。其中 $M$ 是 patterns 的长度，$L$ 是 pattern 中字符串的平均长度，$N$ 是 word 的长度。虽然最坏情况下时间复杂度看起来不低，但在实际字符串匹配中，Python 的 in 操作几乎可以达到接近 $O(N)$ 的效率。空间复杂度：$O(1)$。我们没有开辟任何额外的数据结构来存储子串。相比你的原始解法，大大节省了内存。

不过这个方法其实比较复杂是 Tire Tree + fail 指针的构造方法。

简单来说，fail 指针解决了找子串时的两大痛点，实现了算法复杂度上的“降维打击”。它带来的帮助可以总结为两点：1. 主串指针“永不回退”（极速扫描）在最暴力的子串匹配中（比如在 "ababc" 中找 "abc"），如果你匹配到了 "aba"，发现下一个字符不是 "c" 而是 "b"，失配了。暴力算法会怎么做？它会把 word 的指针退回到第二个位置，从 "b" 重新开始匹配。这种反反复复的“倒车”，在极度恶劣的情况下会让时间复杂度飙升到 $O(N \times M)$。fail 指针的帮助：它相当于一个“智能导航”。当你在 Trie 树上走不通时，fail 指针告诉你：“别退回重来！根据你刚才走过的路，你直接跳去另一个节点接着试就行。”因此，有了 fail 指针后，主字符串 word 的遍历指针永远只往前走，绝对不会倒退。一个长度为 $N$ 的 word，只需要一个简单的 for char in word 就能扫完，把时间复杂度死死钉在了 $O(N)$。2. 多模式串的“买一送一”（一次扫描，全部捞出）这是 fail 指针在多模式匹配（比如这道 LeetCode 1967 有一堆 patterns）中最核心的价值。假设我们的 patterns 里有长有短，比如 ["she", "he", "e"]。这些字符串之间是有包含关系的。fail 指针的帮助：当你在 word 中成功匹配到 "she" 的那一刻，其实你也同时匹配到了 "he" 和 "e"。如果没有 fail 指针，你可能需要拿 "she" 去扫一遍 word，再拿 "he" 去扫一遍，再拿 "e" 去扫一遍。但是，由于 fail 指针专门指向最长后缀："she" 结尾的 fail 指针，连着 "he" 的结尾。"he" 结尾的 fail 指针，连着 "e" 的结尾。当你走到 "she" 的结尾时，只需要顺着 fail 指针往上“拔萝卜”，就能在瞬间把 "he" 和 "e" 一并收集到手。只需扫描一遍 word，就能把所有相互嵌套、重叠的子串一次性全找出来。总结：回到 LeetCode 1967如果我们不用 Python 自带的 in（底层用的是类似 KMP 的单串优化），而是手写对比：传统解法：拿出一个 pattern，去扫描一遍 word。如果有 100 个 pattern，word 就要被扫描 100 遍。AC 自动机 + fail 指针：把 100 个 pattern 融合打造成一棵带有 fail 导航的 Trie 树。然后，word 只需要从头到尾被扫描 1 遍，就结束战斗了。这就是 fail 指针对于找（多个）子串的终极意义：化繁为简，一遍通关。

class TrieNode:
def __init__(self):
self.children = {}
self.fail = None
# 因为题目中 patterns 可能会有重复的元素 (比如 ["a", "a"])
# 所以我们用 count 记录这个单词在 patterns 里出现了几次
self.word_count = 0
class ACAutomaton:
def __init__(self):
self.root = TrieNode()
# 1. 建树 (常规 Trie 树插入)
def insert(self, word: str):
curr = self.root
for char in word:
if char not in curr.children:
curr.children[char] = TrieNode()
curr = curr.children[char]
curr.word_count += 1
# 2. 构建 fail 指针 (通过 BFS 层序遍历，这部分你已经懂了，略作展示)
def build_fail_pointers(self):
import collections
queue = collections.deque()
# 初始化第一层
for char, child in self.root.children.items():
child.fail = self.root
queue.append(child)
while queue:
curr = queue.popleft()
for char, child in curr.children.items():
# 寻找 fail 指针
fail_node = curr.fail
while fail_node and char not in fail_node.children:
fail_node = fail_node.fail
if fail_node:
child.fail = fail_node.children[char]
else:
child.fail = self.root
queue.append(child)
# 3. 核心：怎么扫描 Word？
def search(self, word: str) -> int:
ans = 0
curr = self.root
for char in word:
# 状态转移：如果没有匹配的字符，顺着 fail 指针一直回退
while curr != self.root and char not in curr.children:
curr = curr.fail
# 如果找到了匹配的字符，往下走一步；否则说明退回了 root 且 root 也没有
if char in curr.children:
curr = curr.children[char]
else:
curr = self.root
# 沿途收割答案：顺着当前节点的 fail 指针一路找上去
# 看看有没有包含以当前字符结尾的 pattern
temp = curr
while temp != self.root:
if temp.word_count > 0:
ans += temp.word_count
# 关键去重逻辑：题目问的是 pattern 有没有出现过，不用统计出现次数
# 比如 word="abcabc", patterns=["bc"]，"bc" 出现了两次，但也只算 1 个模式串命中
# 所以统计完后把 count 清零，防止后续重复统计
temp.word_count = 0
temp = temp.fail
return ans

复制代码

Myron2017

LC. 1134. Armstrong Number

Hint
Given an integer n, return true if and only if it is an Armstrong number.

The k-digit number n is an Armstrong number if and only if the kth power of each digit sums to n.

class Solution:
def isArmstrong(self, n: int) -> bool:
strN = str(n)
p = len(strN)
return n == (sum(int(x)**p for x in strN))

复制代码

Follow Up: 不用 String 呢

class Solution:
def isArmstrong(self, n: int) -> bool:
# 因为后续 n 会被除到 0，所以先用 original_n 把初始值存起来
original_n = n
# 1. 计算位数 k (也可以用 math.log10(n) + 1，但用循环更通用)
k = 0
temp = n
while temp > 0:
k += 1
temp //= 10
# 2. 依次取出每一位计算 k 次方
total_sum = 0
temp = n
while temp > 0:
digit = temp % 10 # 取出最后一位
total_sum += digit ** k # 累加 k 次方
temp //= 10 # 砍掉最后一位
# 3. 比较结果
return total_sum == original_n

复制代码

Example 1:

Input: n = 153
Output: true
Explanation: 153 is a 3-digit number, and 153 = 13 + 53 + 33.
Example 2:

Input: n = 123
Output: false
Explanation: 123 is a 3-digit number, and 123 != 13 + 23 + 33 = 36.

Constraints:

1 <= n <= 108

Myron2017

LC. 1288. Remove Covered Intervals

去掉完全覆盖的 interval

key=lambda x: (x[0], -x[1])，interval 的右端点需要用 -x[1] 降序排序！

题目要我们做什么？给定一组区间，如果一个区间完全被另一个区间“包裹”（覆盖）了，就把它删掉。最后问还剩下多少个区间。覆盖的定义：区间 [a, b] 被 [c, d] 覆盖，意味着 c <= a 且 b <= d。容易踩的坑（Pitfalls）：“相交”不等于“覆盖”：比如 [1, 4] 和 [3, 6]，它们有重叠部分，但谁也没完全包住谁，所以两个都要保留。起点相同的区间：这是本题最大的陷阱！如果遇到 [1, 4] 和 [1, 8] 这样起点完全相同的区间，如果不做特殊处理，很容易把大的区间给错误删掉，或者漏删小的区间。二、核心思路：排序是王道对于区间问题，“先排序，再遍历” 是最经典的起手式。

1. 暴力解法（为什么不推荐？）最直观的想法是用两层 for 循环，拿每一个区间去和其他所有区间对比，看看有没有被覆盖。这种写法的时间复杂度是 $O(N^2)$。虽然题目约束 $N \le 1000$，暴力解法也能勉强通过，但面试官一定会问你如何优化。

2. 优化解法：巧妙运用排序 $O(N \log N)$我们可以通过排序，把可能产生覆盖关系的区间放到一起，然后只需要一次遍历就能得出结果。排序规则（非常关键）：

主条件：按照区间的起点 a 升序排列。这样排完后，前面的区间起点一定小于等于后面的起点，满足了覆盖条件里的 c <= a。

次条件：如果起点 a 相同，按照区间的终点 b 降序排列。为什么要降序？如果两个区间起点相同，比如 [1, 4] 和 [1, 8]。如果按常规的终点升序（[1, 4] 在前，[1, 8] 在后）：当你遍历到 [1, 4] 时，它没被前面的覆盖，你保留了它；走到 [1, 8] 时，它也没被 [1, 4] 覆盖，你又保留了它。这就错了，[1, 4] 应该被删掉！如果按终点降序（[1, 8] 在前，[1, 4] 在后）：当你遍历完 [1, 8]，记录下当前能覆盖的最远右边界是 8。走到 [1, 4] 时，发现它的终点 4 <= 8，直接判定它被覆盖，扔掉它！完美解决问题。

同时不需要真的一个个比较internval，直接记录当前的保留的 internval 最远能访问的右端点记录下来即可。因为已经排序了，可以之际判定是不是被覆盖。

class Solution:
def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
# 1. 自定义排序逻辑
# x[0] 是起点，默认升序；-x[1] 是终点，加上负号代表降序
intervals.sort(key=lambda x: (x[0], -x[1]))
# 记录不被覆盖的区间数量
remaining = 0
# 记录遍历过程中，之前遇到的区间能延伸到的最远右边界
max_end = -1
# 2. 遍历判断
for start, end in intervals:
# 如果当前区间的终点 <= 之前记录的最远右边界
# 说明它完全被前一个（或前几个）大区间包裹了
if end <= max_end:
continue
else:
# 否则，它没有被覆盖，成为新的独立区间
remaining += 1
# 更新最远右边界
max_end = end
return remaining

复制代码

Myron2017

LC.1331. Rank Transform of an Array

Given an array of integers arr, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules:

Rank is an integer starting from 1.
The larger the element, the larger the rank. If two elements are equal, their rank must be the same.
Rank should be as small as possible.

Example 1:

Input: arr = [40,10,20,30]
Output: [4,1,2,3]
Explanation: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.
Example 2:

Input: arr = [100,100,100]
Output: [1,1,1]
Explanation: Same elements share the same rank.
Example 3:

Input: arr = [37,12,28,9,100,56,80,5,12]
Output: [5,3,4,2,8,6,7,1,3]

Constraints:

0 <= arr.length <= 105
-109 <= arr[i] <= 109

我的解法

class Solution:
def arrayRankTransform(self, arr: List[int]) -> List[int]:
if not arr: return []
sortedArr = sorted(arr)
rank = dict()
rank[sortedArr[0]] = 1
prev = sortedArr[0]
prevrank = 1
for i in range(1, len(sortedArr)):
if sortedArr[i] != prev:
prev = sortedArr[i]
rank[sortedArr[i]] = prevrank + 1
prevrank += 1
return [rank[x] for x in arr]

复制代码

优化：主要其实是我做的时候没想清楚，去重之后，直接 index 等于 rank，记录下来即可。

from typing import List
class Solution:
def arrayRankTransform(self, arr: List[int]) -> List[int]:
# 1. 去重并排序 (set 去重，sorted 返回一个新的有序列表)
unique_sorted = sorted(set(arr))
# 2. 建立哈希表映射数值到排名
# enumerate(..., 1) 可以让索引从 1 开始，非常适合这道题
rank_dict = {val: index for index, val in enumerate(unique_sorted, 1)}
# 3. 遍历原数组，生成结果
return [rank_dict[x] for x in arr]

复制代码

Myron2017

follow up 就是能不能提高，这个时候就是需要数据是有范围的。

在面试中，只要听到面试官问“能不能突破 $O(N \log N)$ 的时间复杂度瓶颈”，第一反应就应该是反问：“请问数据有固定范围限制吗？” 既然我们已知数据范围限制在 $1 \dots 1000$，我们完全可以抛弃传统的比较排序，用“空间换时间”，把时间复杂度直接降维打击到 $O(N)$。
我们来看看顺着你的思路，代码怎么写最干净：
1. 核心思路拆解
开桶：既然范围是 $1 \dots 1000$，我们直接开一个大小为 1001 的数组（索引 $0 \dots 1000$）。
去重与标记：遍历原数组，把出现的数字在桶里标记为 1。这里我们不需要记录出现次数（因为并列排名一样），只需要知道“它存在”。
分配排名：从左到右遍历这个桶。遇到被标记为 1 的位置，就给它分配一个递增的排名，顺便把这个排名直接覆盖写进桶里（这样桶就变成了一个完美的查表映射）。
查表出结果：再遍历一次原数组，直接去桶里查它的排名。

from typing import List
class Solution:
def arrayRankTransform(self, arr: List[int]) -> List[int]:
if not arr: return []
# 假设题目明确告知：1 <= arr[i] <= 1000
# 开一个大小为 1001 的数组当做“桶”
bucket = [0] * 1001
# 1. 标记出现的数字（相当于哈希表的 key）
for num in arr:
bucket[num] = 1
# 2. 从小到大遍历桶，分配排名（巧妙地将标记替换为排名）
current_rank = 1
for i in range(1, 1001):
if bucket[i] == 1:
bucket[i] = current_rank
current_rank += 1
# 3. 遍历原数组，直接从桶里查排名
return [bucket[num] for num in arr]

复制代码

Myron2017

LC. 3978. Unique Middle Element

我的解法

class Solution:
def isMiddleElementUnique(self, nums: list[int]) -> bool:
freq = Counter(nums)
return freq[nums[len(nums)// 2]] == 1

复制代码

可以优化的地方，

我们真的需要统计所有元素的频率吗？其实不需要。我们只关心中间那个元素出现了几次。因此，我们可以先找出中间元素的值，然后再遍历一次数组，只数这一个值的出现次数。

class Solution:
def isMiddleElementUnique(self, nums: list[int]) -> bool:
# 1. 找到中间元素的值
mid_val = nums[len(nums) // 2]
# 2. 统计这个值在数组中出现的次数
return nums.count(mid_val) == 1

复制代码

不用内置函数，注意可以提前截断。

class Solution:
def isMiddleElementUnique(self, nums: list[int]) -> bool:
mid_val = nums[len(nums) // 2]
count = 0
for num in nums:
if num == mid_val:
count += 1
# 剪枝小技巧：如果发现次数已经大于1了，直接返回 False 即可，没必要看完
if count > 1:
return False
return count == 1

复制代码

Myron2017

LC. 3982. Sum of Integers with Maximum Digit Range

我的解法

class Solution:
def maxDigitRange(self, nums: list[int]) -> int:
digitRange = defaultdict(list)
max_dr = -1
for n in nums:
strn = [int(x) for x in str(n)]
dr = max(strn) - min(strn)
digitRange[dr].append(n)
max_dr = max(dr, max_dr)
return sum(digitRange[max_dr])

复制代码

优化

核心思路：
我们其实并不关心那些较小的 Digit Range 对应的数字是什么。我们可以像“打擂台”一样，在遍历数组的时候，只维护两个变量：

历史最大的 max_dr。

这个 max_dr 对应的累加和 ans_sum。

如果遇到了更大的 dr，就清空之前的和，重新开始累加；如果遇到了相等的 dr，就加到当前的和里。

class Solution:
def maxDigitRange(self, nums: list[int]) -> int:
max_dr = -1
ans_sum = 0
for n in nums:
# 技巧 1：转成字符串
s = str(n)
# 技巧 2：直接用 max() 和 min() 获取最大最小字符，再转回 int 计算
dr = int(max(s)) - int(min(s))
if dr > max_dr:
# 遇到新的更大范围，刷新 max_dr，并重置当前求和
max_dr = dr
ans_sum = n
elif dr == max_dr:
# 遇到一样的最大范围，累加进结果里
ans_sum += n
return ans_sum

复制代码

刷题记录帖子

浏览过的版块