刷题记录帖子

2710. Remove Trailing Zeros From a String
Solved
Easy
Topics
Hint
Given a positive integer num represented as a string, return the integer num without trailing zeros as a string.



Example 1:

Input: num = "51230100"
Output: "512301"
Explanation: Integer "51230100" has 2 trailing zeros, we remove them and return integer "512301".
Example 2:

Input: num = "123"
Output: "123"
Explanation: Integer "123" has no trailing zeros, we return integer "123".


Constraints:

1 <= num.length <= 1000
num consists of only digits.
num doesn't have any leading zeros.

我的解法

1. class Solution:
   
2.     def removeTrailingZeros(self, num: str) -> str:
   
3.         s = [ ch for ch in num]
   
4. 
   
5.         for i in range(len(s)-1, -1, -1):
   
6.             if s[i] == '0':
   
7.                 s.pop(i)
   
8.             else:
   
9.                 break
   
10.         
    
11.         # num is postive
    
12.         return "".join(s)

复制代码

优化，其实不需要转成 List，只需要知道下标就行。

由于 Python 的字符串是不可变（immutable）的，我们不需要把它转成列表，只需要找到最后一个不是 0 的字符的下标，然后直接切片即可。

核心思路：
用一个指针 i 从字符串最末尾往前扫描，只要遇到 '0' 就往前走；遇到不是 '0' 的，就直接截取 0 到 i 的子串。

1. class Solution:
   
2.     def removeTrailingZeros(self, num: str) -> str:
   
3.         # 从后往前找，找到第一个不是 '0' 的字符索引
   
4.         i = len(num) - 1
   
5.         while i >= 0 and num[i] == '0':
   
6.             i -= 1
   
7.             
   
8.         # 切片截取，注意切片是左闭右开，所以要 i + 1
   
9.         return num[:i + 1]

复制代码

Python 提供了一个专门处理这种场景的内置字符串方法：rstrip()。

1. class Solution:
   
2.     def removeTrailingZeros(self, num: str) -> str:
   
3.         # rstrip('0') 会自动剥除字符串右侧（末尾）所有的 '0'
   
4.         return num.rstrip('0')

复制代码

说明：

rstrip() 底层是由 C 语言高度优化的，执行速度比我们手动写 while 循环还要快得多。

在面试中，你可以先写出 解法 2（双指针），然后提一句：“如果在实际工程中，我会直接使用 Python 内置的 num.rstrip('0')，代码更简洁且底层效率更高。” 面试官会觉得你既懂算法，又非常熟悉语言特性。

LC. 2697. Lexicographically Smallest Palindrome
Solved
Easy
Topics
conpanies icon
Companies
Hint
You are given a string s consisting of lowercase English letters, and you are allowed to perform operations on it. In one operation, you can replace a character in s with another lowercase English letter.

Your task is to make s a palindrome with the minimum number of operations possible. If there are multiple palindromes that can be made using the minimum number of operations, make the lexicographically smallest one.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b.

Return the resulting palindrome string.



Example 1:

Input: s = "egcfe"
Output: "efcfe"
Explanation: The minimum number of operations to make "egcfe" a palindrome is 1, and the lexicographically smallest palindrome string we can get by modifying one character is "efcfe", by changing 'g'.
Example 2:

Input: s = "abcd"
Output: "abba"
Explanation: The minimum number of operations to make "abcd" a palindrome is 2, and the lexicographically smallest palindrome string we can get by modifying two characters is "abba".
Example 3:

Input: s = "seven"
Output: "neven"
Explanation: The minimum number of operations to make "seven" a palindrome is 1, and the lexicographically smallest palindrome string we can get by modifying one character is "neven".


Constraints:

1 <= s.length <= 1000
s consists of only lowercase English letters.


我的解法，双指针，同时判断用哪个字符，选小的那一个。

注意 l 《= r，不然会漏掉奇数长度字符串中间的那个字符。

1. class Solution:
   
2.     def makeSmallestPalindrome(self, s: str) -> str:
   
3.         n = len(s)
   
4.         ans = [0] * n
   
5.         l, r = 0, n - 1
   
6. 
   
7.         while l <= r:
   
8.             if s[l] != s[r]:
   
9.                 if s[l] < s[r]:
   
10.                     ans[l] = s[l]
    
11.                     ans[r] = s[l]
    
12.                 else:
    
13.                     ans[l] = s[r]
    
14.                     ans[r] = s[r]
    
15.             else:
    
16.                 ans[l] = s[l]
    
17.                 ans[r] = s[r]
    
18.             
    
19.             l += 1
    
20.             r -= 1
    
21.         
    
22.         return "".join(ans)

复制代码

对你的代码进行点评与优化
初始化结果数组：
你用了 ans = [0] * n。虽然在 Python 里列表是可以混装数字和字符串的（最后你赋了值），但更常见且规范的做法是直接把原字符串转成列表：ans = list(s)。这样不仅省去了相等时的赋值操作，也更符合大家对“修改字符串”的习惯。

简化条件分支：
比较 s[l] 和 s[r] 谁大谁小时，你的 if-else 嵌套得很严密，但其实可以直接用 Python 内置的 min() 函数搞定，一行代码代替五六行。

双指针的边界判断：
你用了 while l <= r:，这没问题。但对于回文串，最中间的那个字符（当字符串长度为奇数时 l == r）是不需要和自己比较、也不需要修改的。所以写 while l < r: 就可以了，能稍微省一点点循环次数。

1. class Solution:
   
2.     def makeSmallestPalindrome(self, s: str) -> str:
   
3.         # 字符串在 Python 中不可变，先转换为 list 以便修改
   
4.         ans = list(s)
   
5.         l, r = 0, len(s) - 1
   
6. 
   
7.         # l < r 即可，奇数长度时最中间的字符不用动
   
8.         while l < r:
   
9.             if ans[l] != ans[r]:
   
10.                 # 贪心思路：不相等时，两边都变成较小的那个字符
    
11.                 smaller_char = min(ans[l], ans[r])
    
12.                 ans[l] = smaller_char
    
13.                 ans[r] = smaller_char
    
14.             
    
15.             l += 1
    
16.             r -= 1
    
17.         
    
18.         return "".join(ans)

复制代码

LC. 2696. Minimum String Length After Removing Substrings
Solved
Easy
Topics
conpanies icon
Companies
Hint
You are given a string s consisting only of uppercase English letters.

You can apply some operations to this string where, in one operation, you can remove any occurrence of one of the substrings "AB" or "CD" from s.

Return the minimum possible length of the resulting string that you can obtain.

Note that the string concatenates after removing the substring and could produce new "AB" or "CD" substrings.



Example 1:

Input: s = "ABFCACDB"
Output: 2
Explanation: We can do the following operations:
- Remove the substring "ABFCACDB", so s = "FCACDB".
- Remove the substring "FCACDB", so s = "FCAB".
- Remove the substring "FCAB", so s = "FC".
So the resulting length of the string is 2.
It can be shown that it is the minimum length that we can obtain.
Example 2:

Input: s = "ACBBD"
Output: 5
Explanation: We cannot do any operations on the string so the length remains the same.


Constraints:

1 <= s.length <= 100
s consists only of uppercase English letters.

这道题目，我用了暴力来做的，但是其实不对，应该要能识别出来这是 stack 消字符串！

我的解法

1. class Solution:
   
2.     def minLength(self, s: str) -> int:
   
3.         removing_sub_str = ['AB', 'CD']
   
4. 
   
5.         while 'AB' in s or 'CD' in s:
   
6.             if 'AB' in s:
   
7.                 ind = s.index('AB')
   
8.                 s = s[:ind] + s[ind+2:]
   
9.             if 'CD' in s:
   
10.                 ind = s.index('CD')
    
11.                 s = s[:ind] + s[ind+2:]
    
12.             
    
13.         return len(s)

复制代码

优化

如果你就是想原地修改字符串，在 Python 中可以用 str.replace()，代码会精简得多，而且底层是 C 语言实现的，实际运行速度比切片快：

1. class Solution:
   
2.     def minLength(self, s: str) -> int:
   
3.         # 只要 AB 或 CD 还在字符串里，就一直替换为空
   
4.         while 'AB' in s or 'CD' in s:
   
5.             s = s.replace('AB', '').replace('CD', '')
   
6.         return len(s)

复制代码

凡是遇到 “相邻元素匹配消除” 的问题（比如消除括号、消除相邻重复字母），第一反应一定要是：栈 (Stack)。

核心思路：
我们就像贪吃蛇一样，把字符一个个吃进（Push）栈里。每次吃进去之前，看看当前要吃的字符，能不能和栈顶（最后吃进去的）字符发生消除反应。

如果当前字符是 'B'，且栈顶是 'A' ➡️ 发生消除，把栈顶的 'A' 吐出来（Pop），当前字符 'B' 也不进栈了。

如果当前字符是 'D'，且栈顶是 'C' ➡️ 发生消除，弹出栈顶。

其他情况 ➡️ 老老实实进栈。

这样，无论怎么嵌套拼接，我们都只需要遍历一次字符串。

1. class Solution:
   
2.     def minLength(self, s: str) -> int:
   
3.         stack = []
   
4.         
   
5.         for char in s:
   
6.             # 当栈不为空，且当前字符能与栈顶字符配对时，弹出栈顶
   
7.             if stack and stack[-1] == 'A' and char == 'B':
   
8.                 stack.pop()
   
9.             elif stack and stack[-1] == 'C' and char == 'D':
   
10.                 stack.pop()
    
11.             else:
    
12.                 # 不能配对，当前字符压入栈
    
13.                 stack.append(char)
    
14.                
    
15.         # 栈里剩下的就是消除不了的字符，返回它的长度即可
    
16.         return len(stack)

复制代码

刷到 1000 题了，纪念一下。

LC. 2689. Extract Kth Character From The Rope Tree

You are given the root of a binary tree and an integer k. Besides the left and right children, every node of this tree has two other properties, a string node.val containing only lowercase English letters (possibly empty) and a non-negative integer node.len. There are two types of nodes in this tree:

Leaf: These nodes have no children, node.len = 0, and node.val is some non-empty string.
Internal: These nodes have at least one child (also at most two children), node.len > 0, and node.val is an empty string.
The tree described above is called a Rope binary tree. Now we define S[node] recursively as follows:

If node is some leaf node, S[node] = node.val,
Otherwise if node is some internal node, S[node] = concat(S[node.left], S[node.right]) and S[node].length = node.len.
Return k-th character of the string S[root].

Note: If s and p are two strings, concat(s, p) is a string obtained by concatenating p to s. For example, concat("ab", "zz") = "abzz".



Example 1:

Input: root = [10,4,"abcpoe","g","rta"], k = 6
Output: "b"
Explanation: In the picture below, we put an integer on internal nodes that represents node.len, and a string on leaf nodes that represents node.val.
You can see that S[root] = concat(concat("g", "rta"), "abcpoe") = "grtaabcpoe". So S[root][5], which represents 6th character of it, is equal to "b".


Example 2:

Input: root = [12,6,6,"abc","efg","hij","klm"], k = 3
Output: "c"
Explanation: In the picture below, we put an integer on internal nodes that represents node.len, and a string on leaf nodes that represents node.val.
You can see that S[root] = concat(concat("abc", "efg"), concat("hij", "klm")) = "abcefghijklm". So S[root][2], which represents the 3rd character of it, is equal to "c".


Example 3:

Input: root = ["ropetree"], k = 8
Output: "e"
Explanation: In the picture below, we put an integer on internal nodes that represents node.len, and a string on leaf nodes that represents node.val.
You can see that S[root] = "ropetree". So S[root][7], which represents 8th character of it, is equal to "e".




Constraints:

The number of nodes in the tree is in the range [1, 103]
node.val contains only lowercase English letters
0 <= node.val.length <= 50
0 <= node.len <= 104
for leaf nodes, node.len = 0 and node.val is non-empty
for internal nodes, node.len > 0 and node.val is empty
1 <= k <= S[root].length


我的解法

1. # Definition for a rope tree node.
   
2. # class RopeTreeNode(object):
   
3. #     def __init__(self, len=0, val="", left=None, right=None):
   
4. #         self.len = len
   
5. #         self.val = val
   
6. #         self.left = left
   
7. #         self.right = right
   
8. class Solution:
   
9.     def getKthCharacter(self, root: Optional[object], k: int) -> str:
   
10.         """
    
11.         :type root: Optional[RopeTreeNode]
    
12.         """
    
13.         curr = root
    
14. 
    
15.         self.ans = ""
    
16. 
    
17.         def preOrder(node):
    
18.             if node.len == 0:
    
19.                 self.ans += node.val
    
20.             
    
21.             if node.left: preOrder(node.left)
    
22.             if node.right: preOrder(node.right)
    
23. 
    
24.         preOrder(root)
    
25. 
    
26.         return self.ans[k-1]

复制代码

你的思路： 前序遍历整棵树，把所有叶子节点的字符串拼接到一起，最后直接通过索引 k-1 取出字符。

存在的问题与隐患：

时间/空间复杂度退化： 你的做法是 $O(N)$，把整棵树展开成了一个完整的长字符串。如果文本长达几个 G，内存直接就爆了。Rope Tree 发明出来的初衷，就是为了避免做全量字符串拼接。

Python 字符串拼接开销： 在 Python 中，字符串是不可变的（Immutable）。频繁使用 self.ans += node.val 会不断创建新字符串，底层开销是 $O(N^2)$。更标准的写法是放进数组里，最后 "".join(arr)。

1. 2. 核心思路：利用“树上二分”实现 $O(H)$ 查找我们不需要把整棵树拼起来，因为每个内部节点（Internal Node）都记录了 node.len。只要我们知道左子树代表的字符串总长度，我们就能判断第 k 个字符到底在左子树还是右子树。拆解逻辑：假设当前我们在节点 curr，要找当前子树的第 k 个字符。我们先计算出左子树代表的字符串长度 left_len：如果 curr.left 是叶子节点，长度就是 len(curr.left.val)如果 curr.left 是内部节点，长度就是 curr.left.len判断走向：如果 k <= left_len，说明第 k 个字符在左边，我们直接向左走：curr = curr.left。如果 k > left_len，说明第 k 个字符在右边，我们向右走，并且 k 要减去左边的长度：k = k - left_len，curr = curr.right。一直走到叶子节点（node.len == 0），直接返回 curr.val[k-1] 即可。

复制代码

1. # Definition for a rope tree node.
   
2. # class RopeTreeNode(object):
   
3. #     def __init__(self, len=0, val="", left=None, right=None):
   
4. #         self.len = len
   
5. #         self.val = val
   
6. #         self.left = left
   
7. #         self.right = right
   
8. class Solution:
   
9.     def getKthCharacter(self, root: Optional[object], k: int) -> str:
   
10.         """
    
11.         :type root: Optional[RopeTreeNode]
    
12.         """
    
13.         
    
14.         """
    
15. 
    
16.         核心思路：利用“树上二分”实现 $O(H)$ 查找我们不需要把整棵树拼起来，因为每个内部节点（Internal Node）都记录了 node.len。只要我们知道左子树代表的字符串总长度，我们就能判断第 k 个字符到底在左子树还是右子树。拆解逻辑：假设当前我们在节点 curr，要找当前子树的第 k 个字符。我们先计算出左子树代表的字符串长度 left_len：如果 curr.left 是叶子节点，长度就是 len(curr.left.val)如果 curr.left 是内部节点，长度就是 curr.left.len判断走向：如果 k <= left_len，说明第 k 个字符在左边，我们直接向左走：curr = curr.left。如果 k > left_len，说明第 k 个字符在右边，我们向右走，并且 k 要减去左边的长度：k = k - left_len，curr = curr.right。一直走到叶子节点（node.len == 0），直接返回 curr.val[k-1] 即可。
    
17. 
    
18.         """
    
19. 
    
20.         # 辅助函数：快速获取任意子树的字符串总长度
    
21.         def get_len(node):
    
22.             if not node:
    
23.                 return 0
    
24.             # 根据题目定义：叶子节点 len 为 0，但有实际字符串；内部节点有 len，但字符串为空
    
25.             if node.len == 0:
    
26.                 return len(node.val)
    
27.             return node.len
    
28. 
    
29.         curr = root
    
30.         
    
31.         # 只要当前还是内部节点（node.len > 0），就继续往下找
    
32.         while curr.len > 0:
    
33.             left_len = get_len(curr.left)
    
34.             
    
35.             if k <= left_len:
    
36.                 # 目标在左子树
    
37.                 curr = curr.left
    
38.             else:
    
39.                 # 目标在右子树，减去左子树的长度
    
40.                 k -= left_len
    
41.                 curr = curr.right
    
42.                
    
43.         # 退出循环时，curr 一定是叶子节点
    
44.         return curr.val[k - 1]

复制代码

为什么这个解法更好？

时间复杂度： $O(H)$，$H$ 为树的高度。对于平衡的 Rope 树，时间复杂度是 $O(\log N)$。不需要遍历所有节点。

空间复杂度： $O(1)$，不需要额外开辟空间存拼接后的完整字符串，也不需要递归调用栈。

LC. 2682. Find the Losers of the Circular Game
There are n friends that are playing a game. The friends are sitting in a circle and are numbered from 1 to n in clockwise order. More formally, moving clockwise from the ith friend brings you to the (i+1)th friend for 1 <= i < n, and moving clockwise from the nth friend brings you to the 1st friend.

The rules of the game are as follows:

1st friend receives the ball.

After that, 1st friend passes it to the friend who is k steps away from them in the clockwise direction.
After that, the friend who receives the ball should pass it to the friend who is 2 * k steps away from them in the clockwise direction.
After that, the friend who receives the ball should pass it to the friend who is 3 * k steps away from them in the clockwise direction, and so on and so forth.
In other words, on the ith turn, the friend holding the ball should pass it to the friend who is i * k steps away from them in the clockwise direction.

The game is finished when some friend receives the ball for the second time.

The losers of the game are friends who did not receive the ball in the entire game.

Given the number of friends, n, and an integer k, return the array answer, which contains the losers of the game in the ascending order.



Example 1:

Input: n = 5, k = 2
Output: [4,5]
Explanation: The game goes as follows:
1) Start at 1st friend and pass the ball to the friend who is 2 steps away from them - 3rd friend.
2) 3rd friend passes the ball to the friend who is 4 steps away from them - 2nd friend.
3) 2nd friend passes the ball to the friend who is 6 steps away from them  - 3rd friend.
4) The game ends as 3rd friend receives the ball for the second time.
Example 2:

Input: n = 4, k = 4
Output: [2,3,4]
Explanation: The game goes as follows:
1) Start at the 1st friend and pass the ball to the friend who is 4 steps away from them - 1st friend.
2) The game ends as 1st friend receives the ball for the second time.


Constraints:

1 <= k <= n <= 50

我的解法 -- 模拟

1. class Solution:
   
2.     def circularGameLosers(self, n: int, k: int) -> List[int]:
   
3.         l = [0] * n
   
4.         # ball at 1st friend
   
5.         curr = 1
   
6.         turns = 1
   
7. 
   
8.         while True:
   
9.             if l[curr - 1] == 0:
   
10.                 l[curr - 1] = 1
    
11.                 curr = (curr + turns * k) % n
    
12.                 turns += 1
    
13.             else:
    
14.                 break
    
15.         
    
16.         ans = []
    
17. 
    
18.         for i in range(n):
    
19.             if l[i] == 0:
    
20.                 ans.append(i+1)
    
21.         
    
22.         return ans
    
23. 
    

复制代码

改进 == > 一个隐藏 bug

curr = (curr + turns * k) % n
...
if l[curr - 1] == 0:

这在大多数情况下是对的，但是当计算出的位置正好是 n 的倍数时，取模结果 curr 会变成 0。
这时候你执行 l[curr - 1]，就变成了 l[-1]。

为什么它能跑通？
因为 Python 支持负数索引，l[-1] 恰好指向数组的最后一个元素，而这个位置恰恰代表第 n 个人！所以你的代码歪打正着地跑通了。

心思路 / 优化方案：环形问题的“零索引黄金法则”
在处理所有的环形数组、取模循环问题时，最佳实践是：从头到尾统一使用 0-based（从 0 开始）索引计算，只在最后返回结果时再转换成 1-based（从 1 开始）。

这样无论是取模还是查数组，思路都会极其清晰，绝不会出现越界或边界情况。

优化后的代码 (标准面试解法)

1. class Solution:
   
2.     def circularGameLosers(self, n: int, k: int) -> List[int]:
   
3.         # 用布尔值(True/False)表示是否拿到球，语义更清晰
   
4.         visited = [False] * n
   
5.         
   
6.         curr = 0  # 统一使用 0-based 索引，0 代表第 1 个人
   
7.         turns = 1
   
8. 
   
9.         # 只要当前的人没有拿到过球，就继续传
   
10.         while not visited[curr]:
    
11.             visited[curr] = True           # 标记当前的人拿到了球
    
12.             curr = (curr + turns * k) % n  # 算出下一个拿球人的 index
    
13.             turns += 1
    
14.             
    
15.         # 找出所有没拿到球的 index，并加 1 还原成题目里的真实编号
    
16.         ans = []
    
17.         for i in range(n):
    
18.             if not visited[i]:
    
19.                 ans.append(i + 1)
    
20.                
    
21.         # (上面这块也可以用更 pythonic 的写法：return [i + 1 for i in range(n) if not visited[i]])
    
22.         
    
23.         return ans

复制代码

LC. 4038. Count Integers Appearing in a Single Block

我的解法

1. class Solution:
   
2.     def countSpecialIntegers(self, nums: list[int]) -> int:
   
3.         ans = set()
   
4.         prev = nums[0]
   
5.         ans.add(prev)
   
6.         duplicates = set()
   
7. 
   
8.         for i in range(1, len(nums)):
   
9. 
   
10.             if nums[i] not in duplicates:
    
11.                 if prev != nums[i]:
    
12.                     # differnt block
    
13.                     
    
14.                     if nums[i] in ans:
    
15.                         # duplicate
    
16.                         ans.remove(nums[i])
    
17.                         duplicates.add(nums[i])
    
18.                     else:
    
19.                         # first occurance
    
20.                         ans.add(nums[i])
    
21. 
    
22.             prev = nums[i]
    
23. 
    
24.         return len(ans)
    

复制代码

另一种核心思路：数学距离法

在 LeetCode 中，处理 “所有元素是否都在一个连续块里” 这类问题，有一个非常通用且不容易写错的套路：记录第一次出现的位置和最后一次出现的位置。核心思路：如果一个数字 $x$ 在数组中出现了 $K$ 次，并且这 $K$ 次是完全连续的，那么必然满足一个数学公式：最后一次出现的索引 - 第一次出现的索引 + 1 == 出现的总次数举个例子：nums = [1, 2, 2, 1]对于 2：第一次在 index=1，最后一次在 index=2。长度为 2 - 1 + 1 = 2。它总共出现了 2 次。2 == 2，所以 2 是 special 的。对于 1：第一次在 index=0，最后一次在 index=3。长度为 3 - 0 + 1 = 4。但它只出现了 2 次。4 != 2，所以 1 是被拆开了，不 special。

1. class Solution:
   
2.     def countSpecialIntegers(self, nums: list[int]) -> int:
   
3.         first = {}
   
4.         last = {}
   
5.         count = {}
   
6.         
   
7.         # 1. 遍历一遍，收集每个数字的情报
   
8.         for i, num in enumerate(nums):
   
9.             if num not in first:
   
10.                 first[num] = i
    
11.             last[num] = i
    
12.             count[num] = count.get(num, 0) + 1
    
13.             
    
14.         # 2. 检查情报，筛选符合条件的数字
    
15.         ans = 0
    
16.         for num in count:
    
17.             if last[num] - first[num] + 1 == count[num]:
    
18.                 ans += 1
    
19.                
    
20.         return ans

复制代码

Python 的原生艺术 (Groupby)
这里给你分享一个 LeetCode 刷题时用来开拓思路的 Python 原生技巧。
如果把相邻的相同元素合并（比如 [3, 3, 1, 2, 2, 1] 压缩成 [3, 1, 2, 1]），那么那些在这个新列表中只出现过一次的数字，就是我们要找的！

Python 中有一个专门做相邻合并的库 itertools.groupby：

1. from itertools import groupby
   
2. from collections import Counter
   
3. 
   
4. class Solution:
   
5.     def countSpecialIntegers(self, nums: list[int]) -> int:
   
6.         # [3, 3, 1, 2, 2, 1] 经过 groupby 会得到由 key 组成的 [3, 1, 2, 1]
   
7.         blocks = [key for key, group in groupby(nums)]
   
8.         
   
9.         # 统计每个 block 出现了几次，只出现 1 次的就是 special
   
10.         counts = Counter(blocks)
    
11.         
    
12.         return sum(1 for val in counts.values() if val == 1)

复制代码

LC. 4030. Check ASCII Palindromic
Solved
Easy
Hint
You are given a string s consisting of lowercase English letters.

Construct a binary string by replacing each character in s with the 8-bit binary representation of its ASCII value, including leading zeros, while preserving the original order of the characters.

Return true if the resulting binary string is a palindrome. Otherwise, return false.



Example 1:

Input: s = "ff"

Output: true

Explanation:

The ASCII value of f is 102, whose 8-bit binary representation is 01100110.
Thus, the binary string is 0110011001100110.
Since this binary string is a palindrome, the output is true.
Example 2:

Input: s = "leet"

Output: false

Explanation:

The ASCII values of l, e, e, and t are 108, 101, 101, and 116, respectively.
Their 8-bit binary representations are 01101100, 01100101, 01100101, and 01110100.
Thus, the binary string is 01101100011001010110010101110100.
Since this binary string is not a palindrome, the output is false.


Constraints:

1 <= s.length <= 100
s consists of lowercase English letters.

我的解法

1. class Solution:
   
2.     def isPalindromic(self, s: str) -> bool:
   
3.         bin_str_list = []
   
4. 
   
5.         for ch in s:
   
6.             bin_str_list.append(bin(ord(ch))[2:].zfill(8))
   
7.         
   
8.         bin_str = "".join(bin_str_list)
   
9. 
   
10.         
    
11.         i, j = 0, len(bin_str) - 1
    
12.         while i < j:
    
13.             if bin_str[i] != bin_str[j]:
    
14.                 return False
    
15.             i += 1
    
16.             j -= 1
    
17.         
    
18.         return True

复制代码

可以优化的小细节（Python 面试常用写法）：
在 Python 中，获取 8 位二进制字符串有一个更简洁且规范的写法，即使用字符串格式化 format(num, '08b') 或者 f-string f"{num:08b}"。这比 bin()[2:].zfill(8) 看起来更优雅，也是面试中很受欢迎的标准写法。

另外，Python 判断回文最快的方法是切片 [::-1]，虽然你写双指针绝对没问题，但在实际做题时，切片底层是 C 语言实现的，速度更快。

O(1) 空间复杂度的“虚拟索引”解法上面的解法空间复杂度是 O(N)（因为我们创建了一个新的长字符串 bin_str）。这道题由于约束条件 $N \le 100$，O(N) 空间完全没问题。但是，如果面试官追问：“能不能不生成这个很长的二进制字符串，直接在原字符串上使用 O(1) 的额外空间判断？”这就是拉开差距的地方了。我们可以使用位运算 + 虚拟索引 (Virtual Indexing)。核心思路：如果原字符串长度为 $L$，那么虚拟的二进制字符串总长度就是 $8 \times L$。我们依然使用双指针，left = 0，right = 8 * L - 1。对于任意一个虚拟的二进制索引 index：它属于原字符串的哪个字符？ char_idx = index // 8它是这个字符的第几位？ bit_offset = index % 8 (注意：0 是最高位，7 是最低位)如何提取这一位？ 将该字符的 ASCII 码向右平移 7 - bit_offset 位，然后和 1 进行按位与操作（& 1）。

1. class Solution:
   
2.     def isPalindromic(self, s: str) -> bool:
   
3.         n = len(s)
   
4.         left, right = 0, 8 * n - 1
   
5.         
   
6.         # 辅助函数：根据虚拟索引提取对应的 0 或 1
   
7.         def get_bit(index: int) -> int:
   
8.             char_idx = index // 8
   
9.             bit_offset = index % 8
   
10.             # 比如我们要找最高位 (bit_offset=0)，就要右移 7 位
    
11.             shift = 7 - bit_offset
    
12.             return (ord(s[char_idx]) >> shift) & 1
    
13. 
    
14.         while left < right:
    
15.             if get_bit(left) != get_bit(right):
    
16.                 return False
    
17.             left += 1
    
18.             right -= 1
    
19.             
    
20.         return True

复制代码

LC. 4032. Longest Subarray With at Most K Distinct Prime Factors
Solved
Medium
Hint
You are given an integer array nums consisting of positive integers and an integer k.

The prime factor set of a subarray is the union of the distinct prime factors of all its elements.

Return the length of the longest subarray whose prime factor set contains at most k distinct prime factors. If no such subarray exists, return 0.

Example 1:

Input: nums = [7,6,10,12,11], k = 3

Output: 3

Explanation:

Consider the subarray [6, 10, 12]:

The distinct prime factors of 6 are {2, 3}.
The distinct prime factors of 10 are {2, 5}.
The distinct prime factors of 12 are {2, 3}.
The union of these sets is {2, 3, 5}, which contains 3 distinct prime factors.
No longer subarray satisfies the condition. Therefore, the answer is 3.

Example 2:

Input: nums = [4,6,9,18], k = 4

Output: 4

Explanation:

Consider the entire array [4, 6, 9, 18]:

The distinct prime factors of 4 are {2}.
The distinct prime factors of 6 are {2, 3}.
The distinct prime factors of 9 are {3}.
The distinct prime factors of 18 are {2, 3}.
The union of these sets is {2, 3}, which contains 2 distinct prime factors.
Since 2 <= 4, the entire array is valid. Therefore, the answer is 4.

Example 3:

Input: nums = [6,10,15], k = 2

Output: 1

Explanation:

Every subarray of length at least 2 has prime factor set {2, 3, 5}, which contains 3 distinct prime factors.

Since 3 > 2, only subarrays of length 1 are valid. Therefore, the answer is 1.

Constraints:

1 <= nums.length <= 105
2 <= nums[i] <= 105
1 <= k <= 104

题目意思很直接，看起来也很直接，滑动窗口 + Prime 动态比较 maxLen。但是写起来还是需要注意的，它其实融合了这几个题目。

第一，如何求一个数的全部质因数？注释掉的就是低效的解法，我用了两个函数，不同循环求解。其实核心就是如果找到一个质因数，就把这个质因数的所有次幂除掉。

# 核心：把这个质数因子全部除干净！
while num % d == 0:
num //= d

'''
        def getPrimeFactors(num):
            ans = []

            for i in range(2, num + 1):
                if num % i == 0 and isPrime(i):
                    ans.append(i)
            
            return ans
            
        def isPrime(num):
            if num == 2: return True
            if num == 3: return True

            for i in range(2, int(sqrt(num)) + 1):
                if num % i == 0:
                    return False
            return True
        '''
        @cache
        def getPrimeFactors(num):
            ans = []
            d = 2
            # 只需要遍历到 sqrt(num) 即可
            while d * d <= num:
                if num % d == 0:
                    ans.append(d)
                    # 核心：把这个质数因子全部除干净！
                    while num % d == 0:
                        num //= d
                d += 1
            # 如果最后剩下一个 >1 的数，它本身也是质数
            if num > 1:
                ans.append(num)
            return ans
第二点，滑动窗口的写法。

外层用

1. for

复制代码

循环强行推动右指针

1. j

复制代码

（保证每个元素只进一次），内层用

1. while

复制代码

循环专门处理左指针

1. i

复制代码

的收缩。

left = 0

for right in range(len(nums)): # 1. 进窗口：把 nums[right] 的信息加进去

    # 2. 判断窗口是否非法（种类 > k）
    while 非法:
        # 3. 出窗口：把 nums[left] 的信息减掉
        left += 1
   
    # 4. 此时窗口必定合法，更新最大长度
    max_len = max(max_len, right - left + 1)

from collections import defaultdict from functools import cache

class Solution:

def longestSubarray(self, nums: list[int], k: int) -> int:

    # 优化点 1：高效质因数分解 + 缓存 (memoization)
    # @cache 装饰器会自动把计算过的结果存起来，下次遇到同样的数字直接 $O(1)$ 返回
    @cache
    def get_prime_factors(num):
        factors = []
        d = 2
        # 只需要遍历到 sqrt(num) 即可
        while d * d <= num:
            if num % d == 0:
                factors.append(d)
                # 把这个质因子除干净
                while num % d == 0:
                    num //= d
            d += 1
        
        # 如果最后剩下一个大于 1 的数，它也是个质数（比如 num=10，除以2剩5，5*5>10跳出，5就是质数）
        if num > 1:
            factors.append(num)
            
        return factors

    # 优化点 2：标准的滑动窗口模板
    prime_freq = defaultdict(int) # 记录窗口内每个质因数的出现次数
    max_len = 0
    left = 0
   
    for right in range(len(nums)):
        # 1. 右指针进窗口：获取 nums[right] 的所有质因数，并更新频次
        for p in get_prime_factors(nums[right]):
            prime_freq[p] += 1
        
        # 2. 如果窗口内质因数种类超过了 k，左指针必须收缩
        while len(prime_freq) > k:
            for p in get_prime_factors(nums[left]):
                prime_freq[p] -= 1
                # 关键：当某个质因数频次归零时，从哈希表中彻底删除，这样 len(prime_freq) 才会变小
                if prime_freq[p] == 0:
                    del prime_freq[p]
            left += 1 # 左边界收缩
            
        # 3. 此时窗口一定满足 len(prime_freq) <= k，更新最大长度
        max_len = max(max_len, right - left + 1)
        
    return max_len

注意上面还有的一个优化是，窗口收缩时的状态维护太复杂： 你用

1. prime_num_list_dict

复制代码

存了每个质数对应的原数字列表，并在缩窗口时使用

1. .remove(nums[i])

复制代码

。 Python 中

1. list.remove()

复制代码

的时间复杂度是 $O(L)$ 的。在滑动窗口中，如果要统计种类，

最经典的做法是用 “频率字典” (Frequency Map)，只需要

1. +1

复制代码

和

1. -1

复制代码

，如果是

1. 0

复制代码

就

1. del

复制代码

，复杂度是 $O(1)$。

2. 如果窗口内质因数种类超过了 k，左指针必须收缩

        while len(prime_freq) > k:
            for p in get_prime_factors(nums[left]):
                prime_freq[p] -= 1
                # 关键：当某个质因数频次归零时，从哈希表中彻底删除，这样 len(prime_freq) 才会变小
                if prime_freq[p] == 0:
                    del prime_freq[p]
            left += 1 # 左边界收缩

补充内容 (2026-09-03 11:30 +08:00):
from collections import defaultdict from functools import cache

class Solution:
def longestSubarray(self, nums: list[int], k: int) -> int:

    # 优化点 1：高效质因数分解 + 缓存 (memoization)
    # @cache 装饰器会自动把计算过的结果存起来，下次遇到同样的数字直接 $O(1)$ 返回
    @cache
    def get_prime_factors(num):
        factors = []
        d = 2
        # 只需要遍历到 sqrt(num) 即可
        while d * d <= num:
            if num % d == 0:
                factors.append(d)
                # 把这个质因子除干净
                while num % d == 0:
                    num //= d
            d += 1
        
        # 如果最后剩下一个大于 1 的数，它也是个质数（比如 num=10，除以2剩5，5*5>10跳出，5就是质数）
        if num > 1:
            factors.append(num)
            
        return factors

    # 优化点 2：标准的滑动窗口模板
    prime_freq = defaultdict(int) # 记录窗口内每个质因数的出现次数
    max_len = 0
    left = 0
   
    for right in range(len(nums)):
        # 1. 右指针进窗口：获取 nums[right] 的所有质因数，并更新频次
        for p in get_prime_factors(nums[right]):
            prime_freq[p] += 1
        
        # 2. 如果窗口内质因数种类超过了 k，左指针必须收缩
        while len(prime_freq) > k:
            for p in get_prime_factors(nums[left]):
                prime_freq[p] -= 1
                # 关键：当某个质因数频次归零时，从哈希表中彻底删除，这样 len(prime_freq) 才会变小
                if prime_freq[p] == 0:
                    del prime_freq[p]
            left += 1 # 左边界收缩
            
        # 3. 此时窗口一定满足 len(prime_freq) <= k，更新最大长度
        max_len = max(max_len, right - left + 1)
        
    return max_len

代码编辑器功能越做越垃圾了， 把代码再贴一遍

1. from collections import defaultdict
   
2. from functools import cache
   
3. 
   
4. class Solution:
   
5.     def longestSubarray(self, nums: list[int], k: int) -> int:
   
6.         
   
7.         # 优化点 1：高效质因数分解 + 缓存 (memoization)
   
8.         # [url=home.php?mod=space&uid=34263]@cache[/url] 装饰器会自动把计算过的结果存起来，下次遇到同样的数字直接 $O(1)$ 返回
   
9.         @cache
   
10.         def get_prime_factors(num):
    
11.             factors = []
    
12.             d = 2
    
13.             # 只需要遍历到 sqrt(num) 即可
    
14.             while d * d <= num:
    
15.                 if num % d == 0:
    
16.                     factors.append(d)
    
17.                     # 把这个质因子除干净
    
18.                     while num % d == 0:
    
19.                         num //= d
    
20.                 d += 1
    
21.             
    
22.             # 如果最后剩下一个大于 1 的数，它也是个质数（比如 num=10，除以2剩5，5*5>10跳出，5就是质数）
    
23.             if num > 1:
    
24.                 factors.append(num)
    
25.                
    
26.             return factors
    
27. 
    
28.         # 优化点 2：标准的滑动窗口模板
    
29.         prime_freq = defaultdict(int) # 记录窗口内每个质因数的出现次数
    
30.         max_len = 0
    
31.         left = 0
    
32.         
    
33.         for right in range(len(nums)):
    
34.             # 1. 右指针进窗口：获取 nums[right] 的所有质因数，并更新频次
    
35.             for p in get_prime_factors(nums[right]):
    
36.                 prime_freq[p] += 1
    
37.             
    
38.             # 2. 如果窗口内质因数种类超过了 k，左指针必须收缩
    
39.             while len(prime_freq) > k:
    
40.                 for p in get_prime_factors(nums[left]):
    
41.                     prime_freq[p] -= 1
    
42.                     # 关键：当某个质因数频次归零时，从哈希表中彻底删除，这样 len(prime_freq) 才会变小
    
43.                     if prime_freq[p] == 0:
    
44.                         del prime_freq[p]
    
45.                 left += 1 # 左边界收缩
    
46.                
    
47.             # 3. 此时窗口一定满足 len(prime_freq) <= k，更新最大长度
    
48.             max_len = max(max_len, right - left + 1)
    
49.             
    
50.         return max_len

复制代码