刷题记录帖子

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

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

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

复制代码

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 分割字符串我们可以直接按

1. '0'

复制代码

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


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

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

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

1. '''
   
2. Moving windows : maintain left out and right in 2 checks
   
3. '''
   
4. class Solution:
   
5.     def minFlips(self, s: str) -> int:
   
6.         n = len(s)
   
7.         s2 = s + s
   
8.         
   
9.         # diff 代表当前窗口与 "010101..." 序列的不匹配程度
   
10.         diff = 0
    
11.         ans = n  # 最大翻转次数不会超过 n
    
12.         
    
13.         for i in range(2 * n):
    
14.             # 1. 进场：处理右端点 s2[i]
    
15.             # 期望值：i % 2 == 0 时为 '0'，i % 2 == 1 时为 '1'
    
16.             expected = '0' if i % 2 == 0 else '1'
    
17.             if s2[i] != expected:
    
18.                 diff += 1
    
19.             
    
20.             # 2. 出场：当窗口长度超过 n，减去左端点 s2[i-n] 的影响
    
21.             if i >= n:
    
22.                 left_idx = i - n
    
23.                 # 同样的逻辑判断左端点当初是否贡献了 diff
    
24.                 left_expected = '0' if left_idx % 2 == 0 else '1'
    
25.                 if s2[left_idx] != left_expected:
    
26.                     diff -= 1
    
27.             
    
28.             # 3. 更新答案：只有当窗口填满 n 个字符时才计算
    
29.             if i >= n - 1:
    
30.                 # 变成 "0101..." 需要 diff 次翻转
    
31.                 # 变成 "1010..." 需要 n - diff 次翻转
    
32.                 ans = min(ans, diff, n - diff)
    
33.                
    
34.         return ans
    
35.             
    
36. 
    
37. '''
    
38. # TLE ~ N^2
    
39. 
    
40. class Solution:
    
41.     def minFlips(self, s: str) -> int:
    
42.         n = len(s)
    
43.         s2 = s + s
    
44.         l = 0
    
45.         ans = float('inf')
    
46. 
    
47.         while l <= n:
    
48.             curr_ops = 0
    
49.             for i in range(n):
    
50.                 actual_idx = i + l
    
51.                 if actual_idx % 2 == 0:
    
52.                     expected = '0'
    
53.                 else:
    
54.                     expected = '1'
    
55.                 if s2[actual_idx] != expected:
    
56.                     curr_ops += 1
    
57.             ans = min(ans, curr_ops, n - curr_ops)
    
58.             l += 1
    
59. 
    
60.         return ans
    
61. '''

复制代码

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

196. Delete Duplicate Emails

1. DELETE FROM Person
   
2. WHERE Id NOT IN (
   
3.     SELECT id FROM (
   
4.         SELECT MIN(Id) AS id
   
5.         FROM Person
   
6.         GROUP BY Email
   
7.     ) AS temp
   
8. );

复制代码

笛卡尔积（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：把所有被标记为“弟弟”的行全部抹除。

1. DELETE p1
   
2. FROM Person p1, Person p2
   
3. WHERE
   
4.     p1.Email = p2.Email
   
5.     AND p1.Id > p2.Id;

复制代码

195. Tenth Line

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

复制代码

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)：当前是第几行。我们用它来判断是否需要添加前导空格。

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

复制代码

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}$

\( 和 \)：匹配物理括号。

注意中间有一个 空格。

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

复制代码

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' 小。

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

复制代码

1. awk '{
   
2.     for(i=1; i<=NF; i++) {
   
3.         count[$i]++
   
4.     }
   
5. }
   
6. END {
   
7.     for(w in count) {
   
8.         print w, count[w]
   
9.     }
   
10. }' words.txt | sort -rnk2

复制代码

用 awk

1. awk '{
   
2.     for(i=1; i<=NF; i++) {
   
3.         count[$i]++
   
4.     }
   
5. }
   
6. END {
   
7.     for(w in count) {
   
8.         print w, count[w]
   
9.     }
   
10. }' words.txt | sort -rnk2

复制代码

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)$ 时间复杂度），且完全不需要额外的空间。

1. class Solution:
   
2.     def findDifferentBinaryString(self, nums: List[str]) -> str:
   
3.         ans = []
   
4.         n = len(nums)
   
5.         
   
6.         for i in range(n):
   
7.             # 观察第 i 个字符串的第 i 位
   
8.             current_bit = nums[i][i]
   
9.             
   
10.             # 取反：如果是 '0' 就给 '1'，如果是 '1' 就给 '0'
    
11.             if current_bit == '0':
    
12.                 ans.append('1')
    
13.             else:
    
14.                 ans.append('0')
    
15.         
    
16.         # 将列表拼成字符串返回
    
17.         return "".join(ans)

复制代码

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

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

复制代码

LC. 1536. Minimum Swaps to Arrange a Binary Grid
Medium
Topics
conpanies icon
Companies
Hint
Given an n x n binary grid, in one step you can choose two adjacent rows of the grid and swap them.

A grid is said to be valid if all the cells above the main diagonal are zeros.

Return the minimum number of steps needed to make the grid valid, or -1 if the grid cannot be valid.

The main diagonal of a grid is the diagonal that starts at cell (1, 1) and ends at cell (n, n).



Example 1:


Input: grid = [[0,0,1],[1,1,0],[1,0,0]]
Output: 3
Example 2:


Input: grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
Output: -1
Explanation: All rows are similar, swaps have no effect on the grid.
Example 3:


Input: grid = [[1,0,0],[1,1,0],[1,1,1]]
Output: 0


Constraints:

n == grid.length == grid[i].length
1 <= n <= 200
grid[i][j] is either 0 or 1

这道题目还真是没做出来，我想到了，可以用每行1的个数来确认它可以待在变换后矩阵的位置，但是没想到 greedy。
同时这题从结尾 0 的个数除法，比我的想法更好，更加直接。

1. 题目特征：一眼识破“贪心 + 冒泡”以后看到满足以下条件的题目，往这方面想：操作限制： 题目规定只能**“交换相邻元素”**（Adjacent Swaps）。目标状态： 最终要达成某种有序或特定的排列（比如对角线以上为 0，或者按大小排序）。最优化问题： 求**“最小步数”**。经验总结： > 在这类限制下，“最小步数”通常等于“逆序对”的数量，或者可以用贪心策略下的冒泡排序来解决。因为相邻交换不会产生“跨越式”的收益，你必须老老实实地把需要的那个元素“挪”过去。2. 算法模型：信息压缩与降维这道题最核心的突破点是：把二维矩阵压缩成一维数组。原始信息： 一个 $n \times n$ 的 $0/1$ 矩阵。冗余信息： 我们并不关心第 $i$ 行具体的 0 分布在左边还是中间。关键信息： 只关心末尾连续 0 的个数。经验总结：处理复杂数据结构（如矩阵、树、图）时，先问自己：“我到底需要哪些核心属性才能判断它是否合法？”。把 $n \times n$ 的复杂度通过预处理降维到长度为 $n$ 的数组，是解决矩阵类题目（如：LC 1275, LC 48）的常用套路。3. Python 面试技巧：优雅与效率的平衡你在上一问中担心的 pop 和 insert，其实是 Python 面试中的“加分项”：模拟物理过程： 用 pop(j) 弹出，用 insert(i, val) 插入，代码意图极其明显——“我要把这一行抽出来，插到前面去”。这比手写两个 for 循环做 swap 要简洁得多。性能边界： 虽然 pop 和 insert 是 $O(n)$，但这道题 $n=200$，整体 $O(n^2)$ 约为 $40,000$ 次运算。在面试中，代码的可读性和正确性远比在 $O(n^2)$ 内部斤斤计较那点常数项重要。4. 贪心策略的证明思路（面试话术）面试官可能会问：“你凭什么说先满足第 $i$ 行就是全局最优？”你可以这样回答（话术）：“因为这道题对每一行的要求是单调递减的（$n-1, n-2, \dots, 0$）。如果我们现在处理第 $i$ 行，面前有两个选择 A 和 B 都能满足当前这一行，但 A 在物理位置上离我们更近。如果选 A，当前步数最少。把较远的 B 留在后面，它更有可能满足后面更宽松的要求。反之，如果选了远的 B，不仅当前步数变多，还浪费了一个可能更好用的 A。”5. 易错坑点 Checklist以后做类似题，先在心里过一遍：无解判断： 是否存在无论怎么换都达不到要求的情况？（本题中：如果找不到满足 zeros[j] >= target 的行，直接返回 -1）。边界值： $n-1-i$ 这种下标计算，最好用 $i=0$ 或 $i=n-1$ 代入检查一下。贪心方向： 是从第一行开始匹配，还是从最后一行开始？（本题中：第一行最严格，先满足最严格的，剩下的才好安排）。

1. class Solution:
   
2.     def minSwaps(self, grid: List[List[int]]) -> int:
   
3.         # counting ending zeros
   
4.         # this is the finger prints of each row
   
5.         zeros = []
   
6.         n = len(grid)
   
7.         for row in grid:
   
8.             count = 0
   
9.             index = n - 1
   
10.             while index >= 0:
    
11.                 if row[index] == 0:
    
12.                     count += 1
    
13.                     index -= 1
    
14.                 else:
    
15.                     break
    
16.             zeros.append(count)
    
17. 
    
18.         # 遍历 zeros，确定可以填充本行的最近的行 greedy
    
19.         # 对于第 i 行，需要找到的最近行的结尾zeros个数需要满足 >= n - 1 - i
    
20.         ans = 0
    
21.         for i in range(n):
    
22.             target = n - 1 - i
    
23.             ind = i
    
24.             foundTargetIndex = -1
    
25.             while ind < n:
    
26.                 if zeros[ind] >= target:
    
27.                     foundTargetIndex = ind
    
28.                     break
    
29.                 ind += 1
    
30.             
    
31.             if foundTargetIndex == -1:
    
32.                 # no row match the required zeros
    
33.                 return -1
    
34.             else:
    
35.                 ans += (foundTargetIndex - i) # swap row foundTargetIndex to i
    
36.                 # update zeros to make sure i + 1 has the new zeros layout
    
37.                 # this is to simulate swapping
    
38.                 targetZeroVals = zeros.pop(foundTargetIndex)
    
39.                 zeros.insert(i, targetZeroVals)
    
40.         
    
41.         return ans

复制代码