刷题记录帖子

Myron2017

111. Minimum Depth of Binary Tree

from collections import deque
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
# 使用 deque 保证 popleft 是 O(1)
queue = deque([root])
depth = 1 # 根节点本身就是第 1 层
while queue:
# 当前层的节点数量
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
# 核心判断：如果遇到叶子节点，直接返回当前深度
if not node.left and not node.right:
return depth
# 将下一层节点入队
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# 处理完当前层，深度加 1
depth += 1
return depth

复制代码

Myron2017

LC 1758. Minimum Changes To Make Alternating Binary String
理解错题意了，这道题目是每个位置每个位置的单独操作，所以每个位置改动一次，就是一次操作。

小技巧，如果知道变成 0101 的操作数，1010 的操作数，一定是 n - count0

class Solution:
def minOperations(self, s: str) -> int:
count0 = 0 # 变成 0101... 需要的步数
n = len(s)
for i in range(n):
# 期望在 i 位置看到的字符（0, 1, 0, 1...）
expected = str(i % 2)
if s[i] != expected:
count0 += 1
# 变成 1010... 的步数一定是 n - count0
return min(count0, n - count0)

复制代码

Myron2017

LC 1784. Check if Binary String Has at Most One Segment of Ones

简单题，直接用指标遍历！

class Solution:
def checkOnesSegment(self, s: str) -> bool:
      # without leading zeros ==> begining with 1
      # 只能以这个 1 作为 segment
      i = 0
      n = len(s)
      while i < n:
         if s[i] == '1':
            i += 1
         else:
            break
      if i == n: return True # ALL 1

      while i < n:
         if s[i] == '0':
            i += 1
         else:
            return False
      return True

不过和 AI 学习还是可以提高的，

更高效的解法，

解法 B：利用 Python 分割字符串我们可以直接按

'0'

复制代码

切分，看看切出来的非空片段有几个。

class Solution:
def checkOnesSegment(self, s: str) -> bool:
# 过滤掉空字符串，看剩下的 '1' 片段数量
return len([sect for sect in s.split('0') if sect]) <= 1

Myron2017

1888. Minimum Number of Flips to Make the Binary String Alternating

很精彩的题目，利用了 LC 1758. Minimum Changes To Make Alternating Binary String, https://www.1point3acres.com/bbs ... 37&pid=20868425 的结论，同时用到了旋转环，s+s 接起来的技巧，和滑动窗口，不需要统计全部，只需要统计左端移出窗口和右端进入窗口的两个位置即可。

其次是，判断需要字符的时候的小技巧。只需要统计和 010101 或者 101010 中一个 diff ，另外一个一定是 n - diff。

而针对某个位置，是 0 还是 1，其实直接 index 模 2 即可，

# 期望在 i 位置看到的字符（0, 1, 0, 1...）
         expected = str(i % 2)
         if s[i] != expected:
            count0 += 1

当然这个题目在知道了思路之后写起来也是需要注意，需要处理好边界条件同时慎重处理如何高效代码。

'''
Moving windows : maintain left out and right in 2 checks
'''
class Solution:
def minFlips(self, s: str) -> int:
n = len(s)
s2 = s + s
# diff 代表当前窗口与 "010101..." 序列的不匹配程度
diff = 0
ans = n # 最大翻转次数不会超过 n
for i in range(2 * n):
# 1. 进场：处理右端点 s2[i]
# 期望值：i % 2 == 0 时为 '0'，i % 2 == 1 时为 '1'
expected = '0' if i % 2 == 0 else '1'
if s2[i] != expected:
diff += 1
# 2. 出场：当窗口长度超过 n，减去左端点 s2[i-n] 的影响
if i >= n:
left_idx = i - n
# 同样的逻辑判断左端点当初是否贡献了 diff
left_expected = '0' if left_idx % 2 == 0 else '1'
if s2[left_idx] != left_expected:
diff -= 1
# 3. 更新答案：只有当窗口填满 n 个字符时才计算
if i >= n - 1:
# 变成 "0101..." 需要 diff 次翻转
# 变成 "1010..." 需要 n - diff 次翻转
ans = min(ans, diff, n - diff)
return ans
'''
# TLE ~ N^2
class Solution:
def minFlips(self, s: str) -> int:
n = len(s)
s2 = s + s
l = 0
ans = float('inf')
while l <= n:
curr_ops = 0
for i in range(n):
actual_idx = i + l
if actual_idx % 2 == 0:
expected = '0'
else:
expected = '1'
if s2[actual_idx] != expected:
curr_ops += 1
ans = min(ans, curr_ops, n - curr_ops)
l += 1
return ans
'''

复制代码

因为：Type-1（位移）只是在选择我们要观察哪 $n$ 个位置。Type-2（翻转）只是在对比这 $n$ 个位置和“标准答案”的差异。

Myron2017

196. Delete Duplicate Emails

DELETE FROM Person
WHERE Id NOT IN (
SELECT id FROM (
SELECT MIN(Id) AS id
FROM Person
GROUP BY Email
) AS temp
);

复制代码

笛卡尔积（Cartesian Product），即把表中的每一行都和表中的每一行（包括它自己）配对一次。

1. 什么是笛卡尔积？假设 Person 表只有 3 行：| id | email || :--- | :--- || 1 | A || 2 | B || 3 | A |当你写 FROM Person p1, Person p2 时，数据库会生成一个包含 $3 \times 3 = 9$ 条记录的虚拟大表。每一行都是 (p1.id, p1.email, p2.id, p2.email)。2. 通过 WHERE 子句进行“漏斗式”筛选笛卡尔积产生的大表里充满了垃圾信息。我们通过 WHERE 条件像漏斗一样把我们想要的“重复行”过滤出来。第一步：WHERE p1.email = p2.email过滤后，只剩下 Email 相同的组合：(1, A, 1, A) —— 自己跟自己配对(1, A, 3, A) —— 1号跟3号配对(3, A, 1, A) —— 3号跟1号配对(3, A, 3, A) —— 自己跟自己配对(2, B, 2, B) —— 自己跟自己配对第二步：AND p1.id > p2.id这一步是杀手锏，它定义了谁该死，谁该活：(1, A, 3, A)：$1 > 3$ 为假，丢弃。(3, A, 1, A)：$3 > 1$ 为真，保留！(1, A, 1, A)：$1 > 1$ 为假，丢弃（这就是为什么它能保住最小 ID 的原因）。最后剩下的只有：(3, A, 1, A)。3. DELETE p1 的真正含义当你写 DELETE p1 时，SQL 引擎会看最后筛选出来的结果：结果中 p1 对应的行是 id=3 的那一行。于是，引擎就会回到原表中，把 id=3 的那行删掉。总结一下这个逻辑：FROM p1, p2：把所有可能的成对情况列出来。p1.email = p2.email：找出所有“长得像”的兄弟。p1.id > p2.id：在每对兄弟里，标记出那个“弟弟”（ID 较大的那个）。DELETE p1：把所有被标记为“弟弟”的行全部抹除。

DELETE p1
FROM Person p1, Person p2
WHERE
p1.Email = p2.Email
AND p1.Id > p2.Id;

复制代码

Myron2017

195. Tenth Line

# Read from the file file.txt and output the tenth line to stdout.
# sed -n '10p;10q' file.txt
# -n：默认情况下 sed 会打印处理过的每一行。使用 -n 可以关闭自动打印。
# '10p'：这里的 10 指的是行号，p 是 print。只有当处理到第 10 行时，才会执行打印操作。
# 优点：代码极短。如果文件不足 10 行，sed 根本等不到第 10 行，所以不会产生任何输出，完美符合题意。
# awk 'NR == 10' file.txt
# NR == 10：这是一个模式（Pattern）。awk 会逐行扫描，当当前行号 NR 等于 10 时，执行默认动作（即打印整行）。
# 优点：可读性极强，逻辑非常接近编程语言。
# cnt=$(wc -l < file.txt)
# if [ $cnt -ge 10 ]; then
# head -n 10 file.txt | tail -n 1
# fi

复制代码

Myron2017

LC 194. Transpose File

核心算法：使用 awk 模拟二维矩阵
awk 是处理这种“行列”结构化数据的神器。我们可以利用 awk 的关联数组来存储每一列的内容。

逻辑步骤：
遍历每一行：用一个变量 i 代表当前列号。

存储数据：把第 i 列的数据拼接到数组 res[i] 中。

打印结果：处理完所有行后（在 END 块中），循环打印 res 数组。

4. 关键点拨
1. 为什么用 res[i] = res[i] " " $i？
在 awk 中，两个字符串直接写在一起就是拼接（Concatenation）。

第一行读取后：res[1] = "name", res[2] = "age"

第二行读取后：res[1] = "name alice", res[2] = "age 21"

第三行读取后：res[1] = "name alice ryan", res[2] = "age 21 30"

2. 内置变量的妙用
NF (Number of Fields)：这行有多少列。题目保证每行列数相同，所以我们可以放心使用。

NR (Number of Records)：当前是第几行。我们用它来判断是否需要添加前导空格。

# 使用 awk 处理转置
awk '{
# NF 是 awk 内置变量，代表当前行的字段数（列数）
for (i = 1; i <= NF; i++) {
if (NR == 1) {
# 如果是第一行，直接初始化数组
res[i] = $i;
} else {
# 如果不是第一行，在原有内容后拼接一个空格和当前字段
res[i] = res[i] " " $i;
}
}
}
END {
# 遍历存储好的每一列数据并打印
for (i = 1; i <= NF; i++) {
print res[i];
}
}' file.txt

复制代码

Myron2017

193. Valid Phone Numbers
Easy
Topics
conpanies icon
Companies
Given a text file file.txt that contains a list of phone numbers (one per line), write a one-liner bash script to print all valid phone numbers.

You may assume that a valid phone number must appear in one of the following two formats: (xxx) xxx-xxxx or xxx-xxx-xxxx. (x means a digit)

You may also assume each line in the text file must not contain leading or trailing white spaces.

Example:

Assume that file.txt has the following content:

987-123-4567
123 456 7890
(123) 456-7890
Your script should output the following valid phone numbers:

987-123-4567
(123) 456-7890

Leetcode 刷题伴侣
Custom Gem
Leetcode 刷题伴侣 said
这道题是经典的**正则表达式（Regular Expression）**实战题。题目要求在一堆文本中筛选出符合特定格式的电话号码。

在 Linux 命令行中，处理这种“模式匹配”最快的工具就是 grep。

1. 拆解题意：定义“合法”
题目给出了两种合法格式：

xxx-xxx-xxxx（三个数字 - 三个数字 - 四个数字）

(xxx) xxx-xxxx（括号内三个数字，空格，三个数字 - 四个数字）

容易踩的坑：

括号转义：在正则表达式中，( 和 ) 是特殊字符（用于分组），如果要匹配物理上的括号，需要转义 $ 或使用扩展正则。

精确匹配：题目要求每行一个号码，且没有前后空格。这意味着我们要匹配整行，不能让类似 1234-123-4567 这种多出数字的号码混进来。

2. 核心思路：构建正则表达式
我们需要用 |（逻辑“或”）把两种格式连接起来。

格式 A: xxx-xxx-xxxx
正则写法：^[0-9]{3}-[0-9]{3}-[0-9]{4}$

^ 和 $：分别代表行首和行尾，确保整行只有这个号码。

[0-9]{3}：连续 3 个数字。

格式 B: (xxx) xxx-xxxx
正则写法：^\([0-9]{3}$ [0-9]{3}-[0-9]{4}$

$ 和 $：匹配物理括号。

注意中间有一个空格。

# Read from the file file.txt and output all valid phone numbers to stdout.
#分组和或运算：(\d{3}-|$\d{3}$ ) 表示要么是“三位数字加连字符”，要么是“括号三位数字加空格”。
grep -P '^(\d{3}-|$\d{3}$ )\d{3}-\d{4} file.txt
#-E (Extended Regular Expression) 允许我们直接使用 |、{} 和 () 而不需要加一堆繁琐的反斜杠。
grep -E '^([0-9]{3}-|$[0-9]{3}$ )[0-9]{3}-[0-9]{4} file.txt
awk '/^([0-9]{3}-|$[0-9]{3}$ )[0-9]{3}-[0-9]{4}$/' file.txt

复制代码

Myron2017

192. Word Frequency

Write a bash script to calculate the frequency of each word in a text file words.txt.

For simplicity sake, you may assume:

words.txt contains only lowercase characters and space ' ' characters.
Each word must consist of lowercase characters only.
Words are separated by one or more whitespace characters.
Example:

Assume that words.txt has the following content:

the day is sunny the the
the sunny is is
Your script should output the following, sorted by descending frequency:

the 4
is 3
sunny 2
day 1
Note:

Don't worry about handling ties, it is guaranteed that each word's frequency count is unique.
Could you write it in one-line using Unix pipes?

逐个命令拆解（深度理解）
第一步：tr -s ' ' '\n'
作用：将空格替换为换行符。

-s (squeeze)：非常关键！如果单词之间有多个空格，它会将连续的空格压缩成一个，防止出现多余的空行。

结果：所有单词现在都垂直站立，一行一个。

第二步：sort
作用：将单词按字母顺序排列。

原因：下一步的 uniq 命令有一个“怪癖”——它只能统计相邻的重复行。所以必须先排序，让所有的 "the" 都排在一起。

第三步：uniq -c
作用：去重并计数。

-c (count)：在每个单词前面加上它出现的次数。

输出示例：4 the, 3 is ...

第四步：sort -nr
作用：按数字进行倒序排列。

-n (numeric)：告诉 sort 按照数值大小排，而不是按字符（不然 10 会排在 2 前面）。

-r (reverse)：从大到小排。

第五步：awk '{print $2, $1}'
作用：调整输出格式。

原因：uniq -c 默认输出是次数单词，而题目要求是单词次数。awk 轻松地交换了这两列。

4. 常见坑点 (Debug Checklist)
忘记 tr -s：如果文件里有两个空格连在一起，简单的替换会产生一个空行，导致统计结果里出现一个莫名其妙的数字。

忘记先 sort 再 uniq：这是最常见的错误。uniq 不会自动在全文件中找重复，它只看“邻居”是否一样。

sort 没加 -n：如果你不加 -n，次数为 11 的单词会排在次数为 2 的单词后面，因为字符 '1' 比 '2' 小。

cat words.txt | tr -s ' ' '\n' | sort | uniq -c | sort -nr | awk '{print $2, $1}'

复制代码

awk '{
for(i=1; i<=NF; i++) {
count[$i]++
}
}
END {
for(w in count) {
print w, count[w]
}
}' words.txt | sort -rnk2

复制代码

用 awk

awk '{
for(i=1; i<=NF; i++) {
count[$i]++
}
}
END {
for(w in count) {
print w, count[w]
}
}' words.txt | sort -rnk2

复制代码

Myron2017

LC. 1980. Find Unique Binary String

这题是真的没想到解法，对角线法。当然传统方法没想到也是不应该的，因为至少可以生成所有的组合嘛，其实就是 0～n 的所有数字。

核心算法模型：康托尔对角线法 (Cantor's Diagonal Argument)这道题在 LeetCode 上的最优解法其实是一个数学天才发现的方法：康托尔对角线法。拆解题意：你有 $n$ 个字符串，每个长度也是 $n$。你需要构造一个长度为 $n$ 的新字符串，只要它和这 $n$ 个里的每一个至少有一位不同，它就是唯一的。算法思路：我们可以构造一个字符串 ans，使得：ans 的第 $0$ 位与 nums[0] 的第 $0$ 位相反。ans 的第 $1$ 位与 nums[1] 的第 $1$ 位相反。...ans 的第 $i$ 位与 nums[i] 的第 $i$ 位相反。这样构造出来的 ans：它一定和 nums[0] 不同（因为第 0 位就不一样）。它也一定和 nums[1] 不同（因为第 1 位就不一样）。以此类推，它和 nums 里的每一个字符串都至少有一位不同！3. 优化后的代码实现这种写法简洁、高效（$O(n)$ 时间复杂度），且完全不需要额外的空间。

class Solution:
def findDifferentBinaryString(self, nums: List[str]) -> str:
ans = []
n = len(nums)
for i in range(n):
# 观察第 i 个字符串的第 i 位
current_bit = nums[i][i]
# 取反：如果是 '0' 就给 '1'，如果是 '1' 就给 '0'
if current_bit == '0':
ans.append('1')
else:
ans.append('0')
# 将列表拼成字符串返回
return "".join(ans)

复制代码

哈希集合 (Set)如果你在面试时没想起对角线法，另一种稳健的思维是：把 nums 转换成整数集合，然后从 $0$ 到 $n$ 尝试寻找。因为 nums 只有 $n$ 个元素，而前 $n+1$ 个二进制数（从 $0, 1, \dots, n$）中必然有一个是不在 nums 里的（抽屉原理）。

class Solution:
def findDifferentBinaryString(self, nums: List[str]) -> str:
n = len(nums)
# 转换成数字集合，查找效率 O(1)
num_set = {int(x, 2) for x in nums}
# 只需要在 0 到 n 之间找，一定能找到一个缺失的
for i in range(n + 1):
if i not in num_set:
# 格式化回长度为 n 的二进制字符串
return bin(i)[2:].zfill(n)

复制代码

刷题记录帖子

浏览过的版块