刷题记录帖子

Myron2017

LC. 3769. Sort Integers by Binary Reflection

class Solution:
def sortByReflection(self, nums: List[int]) -> List[int]:
reflection = [(int(bin(n)[2:][::-1], 2), n) for n in nums]
reflection.sort()
return [x[1] for x in reflection]

复制代码

更 Python 的代码

class Solution:
def sortByReflection(self, nums: List[int]) -> List[int]:
def get_reflection(n):
# 将 n 转为二进制字符串，反转，再按 2 进制转回整数
reflected_val = int(bin(n)[2:][::-1], 2)
# 返回一个元组用于多级排序：(主要关键字, 次要关键字)
return (reflected_val, n)
# sort 是稳定的，但直接在 key 里返回元组是最标准的做法
nums.sort(key=get_reflection)
return nums

复制代码

补充内容 (2026-03-16 11:58 +08:00):

Myron2017

LC. 3754. Concatenate Non-Zero Digits and Multiply by Sum I

class Solution:
def sumAndMultiply(self, n: int) -> int:
s = [ch for ch in str(n) if ch != '0']
if not s: s = ['0']
x = int("".join(s))
sum_x = sum([int(x) for x in s])
return x * sum_x

复制代码

不用字符串解法，使用数学，循环提取。

class Solution:
def sumAndMultiply(self, n: int) -> int:
if n == 0: return 0
nums = []
temp = n
# 从低位到高位提取
while temp > 0:
digit = temp % 10
if digit != 0:
nums.append(digit)
temp //= 10
if not nums: return 0
# 因为是从低位提取的，拼接 x 时需要反转
x = 0
total_sum = 0
for d in reversed(nums):
x = x * 10 + d
total_sum += d
return x * total_sum

复制代码

Myron2017

LC. 3750. Minimum Number of Flips to Reverse Binary String

class Solution:
def minimumFlips(self, n: int) -> int:
s = bin(n)[2:]
rev_s = s[::-1]
ans = 0
for i in range(len(s)):
if s[i] != rev_s[i]:
ans += 1
return ans

复制代码

可以快速验证，

class Solution:
def minimumFlips(self, n: int) -> int:
s = bin(n)[2:]
n_len = len(s)
ans = 0
# 只需要遍历一遍字符串即可
for i in range(n_len):
# 对比当前位和它镜像位置的字符
if s[i] != s[n_len - 1 - i]:
ans += 1
return ans

复制代码

Myron2017

LC 3745. Maximize Expression of Three Elements

脑子困住了，第一遍想到的解法居然是 N^3 循环暴力求解。。。

其实做之前就可以想下套路，是不是可以贪心，是不是可以二分，是不是可以 DFS / BFS。

优化思路 (贪心解法)既然 $a, b, c$ 之间没有顺序限制，我们其实只需要关注整个数组中最大的那些数和最小的那颗数。我们需要两个最大的数作为 $a$ 和 $b$。我们需要一个最小的数作为 $c$。但是有一个小细节：如果数组中最大的数恰好也是最小的数（即数组元素都一样），或者最小的数被选作 $a$ 或 $b$ 了怎么办？其实最稳妥的做法是：直接对数组排序。

class Solution:
def maximizeExpressionOfThree(self, nums: List[int]) -> int:
# ans = float('-inf')
# n = len(nums)
# for i in range(n):
# for j in range(i+1, n):
# for k in range(j+1, n):
# sum3 = nums[i] + nums[j] + nums[k]
# for c in [i, j, k]:
# ans = max(ans, sum3 - 2 * nums[c])
# return ans
nums.sort()
return nums[-1] + nums[-2] - nums[0]

复制代码

Myron2017

LC 3740. Minimum Distance Between Three Equal Elements I

完全可以边遍历，边查找最小值。

拓展一下，如果是四个数字，循环 abs 差呢，还是首尾两个位置作差。

class Solution:
def minimumDistance(self, nums: List[int]) -> int:
val_index = defaultdict(list)
ans = float('inf')
for ind, val in enumerate(nums):
val_index[val].append(ind)
# 必须是 indices[-1] - indices[-3]
# 这样才能保证我们检查的是“最近”的三个相同数字
if len(val_index[val]) >= 3:
dist = 2 * (val_index[val][-1] - val_index[val][-3])
if dist < ans:
ans = dist
return ans if ans != float('inf') else -1

复制代码

或者简明写法，

class Solution:
def minimumDistance(self, nums: List[int]) -> int:
val_index = defaultdict(list)
checked_vals = set()
for ind,val in enumerate(nums):
val_index[val].append(ind)
if len(val_index[val]) == 3 and val not in checked_vals:
checked_vals.add(val)
if not checked_vals: return -1
ans = float('inf')
for val in checked_vals:
ind_list = val_index[val]
for i in range(len(ind_list) - 2):
ans = min(ans, abs(ind_list[i+2] - ind_list[i]) + abs(ind_list[i+2] - ind_list[i+1]) + abs(ind_list[i+1] - ind_list[i]))
return ans

复制代码

Myron2017

LC 3070. Count Submatrices with Top-Left Element and Sum Less Than k

S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + grid[i][j]

class Solution:
def countSubmatrices(self, grid: List[List[int]], k: int) -> int:
# s(i,j) means top-left (0,0) to (i,j) sum
# s(i,j) = s(i-1, j) + s(i, j-1) - s(i-1, j-1) + grid(i,j)
n_row = len(grid)
n_col = len(grid[0])
sum_grid = []
for i in range(n_row): sum_grid.append([0] * n_col)
# calculate sum of first row
sum_grid[0][0] = grid[0][0]
for i in range(1, n_col):
sum_grid[0][i] = sum_grid[0][i-1] + grid[0][i]
# calculate sum of first col
for i in range(1, n_row):
sum_grid[i][0] = sum_grid[i-1][0] + grid[i][0]
# loop all other cells that are not 1st row or col
for i in range(1, n_row):
for j in range(1, n_col):
sum_grid[i][j] = sum_grid[i-1][j] + sum_grid[i][j-1] - sum_grid[i-1][j-1] + grid[i][j]
count = 0
for i in range(n_row):
for j in range(n_col):
if sum_grid[i][j] <= k:
count += 1
return count

复制代码

你分开了第一行、第一列和中间部分的计算。在面试中，我们可以通过增加一行一列的偏移（Padding）或者在循环内做边界判断来简化代码，减少出错概率。优化 B：空间复杂度优化其实我们不需要一个完整的 sum_grid 矩阵后再去遍历一遍计数。我们可以在计算当前 sum_grid[i][j] 的同时就进行判断。甚至，如果你不介意修改原数组，可以直接在 grid 上原地操作，空间复杂度降为 $O(1)$（不计输入输出）。优化 C：剪枝（Pruning）题目说了 grid[i][j] >= 0。这意味着如果 sum_grid[i][0] 已经大于 $k$ 了，那么这一行后面的所有 sum_grid[i][j] 肯定也都大于 $k$，可以直接跳过当前行的后续计算。

from typing import List
class Solution:
def countSubmatrices(self, grid: List[List[int]], k: int) -> int:
m, n = len(grid), len(grid[0])
count = 0
# 直接在 grid 上原地计算前缀和，省去额外的 sum_grid 空间
for i in range(m):
for j in range(n):
# 计算当前位置的前缀和
if i > 0:
grid[i][j] += grid[i-1][j]
if j > 0:
grid[i][j] += grid[i][j-1]
if i > 0 and j > 0:
grid[i][j] -= grid[i-1][j-1]
# 核心判断
if grid[i][j] <= k:
count += 1
else:
# 剪枝优化：
# 因为 grid 元素 >= 0，所以同一行往右的和只会更大。
# 注意：由于二维的特性，即使当前位置 > k，下一行的同列位置仍可能通过前面的小值拉回来，
# 所以只能 break 内层循环（当前行），不能直接结束整个函数。
break
return count

复制代码

Myron2017

LC. 3736. Minimum Moves to Equal Array Elements III

class Solution:
def minMoves(self, nums: List[int]) -> int:
ans = 0
max_val = max(nums)
for n in nums:
ans += (max_val - n)
return ans

复制代码

Myron2017

LC. 3212. Count Submatrices With Equal Frequency of X and Y

class Solution:
def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
freq = dict() #freq of 'X', 'Y', and '.'
curr_freq = {'X': [1, 0, 0], 'Y':[0, 1, 0], '.': [0, 0, 1]}
n_row = len(grid)
n_col = len(grid[0])
# set first cell grid[0][0]
freq[(0, 0)] = curr_freq[grid[0][0]]
# first row
for i in range(1, n_col):
freq[(0, i)] = [x + y for x, y in zip(freq[(0, i-1)], curr_freq[grid[0][i]])]
# first col
for i in range(1, n_row):
freq[(i, 0)] = [x + y for x, y in zip(freq[(i-1, 0)], curr_freq[grid[i][0]])]
# loop all other rows and cols
for i in range(1, n_row):
for j in range(1, n_col):
freq[(i, j)] = [ p+q-r+t for p, q, r, t in zip(freq[(i-1, j)], freq[(i, j-1)], freq[(i-1, j-1)], curr_freq[grid[i][j]])]
# count freq with equal freq X and Y
ans = 0
for i in range(n_row):
for j in range(n_col):
if freq[(i,j)][0] > 0 and freq[(i,j)][0] == freq[(i,j)][1]:
ans += 1
return ans

复制代码

优化方向

1. 空间可以优化
你用字典存储，其实可以直接用二维数组，访问更快：
python# 当前写法
freq = dict()
freq[(i, j)] = [x_count, y_count, dot_count]

# 优化写法
freq = [[[0, 0, 0] for _ in range(n_col)] for _ in range(n_row)]
freq[i][j] = [x_count, y_count, dot_count]
2. 不需要存储 '.' 的数量
题目只关心 X 和 Y 的数量，不需要统计 '.'：
python# 简化
curr_freq = {'X': [1, 0], 'Y': [0, 1], '.': [0, 0]}
3. 代码可以更简洁
第一行、第一列、其他格子可以统一处理：

class Solution:
def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
# freq[i][j] = [X的数量, Y的数量] 在子矩阵 (0,0) 到 (i,j) 中
freq = [[[0, 0] for _ in range(n)] for _ in range(m)]
ans = 0
for i in range(m):
for j in range(n):
# 当前格子的贡献
x_add = 1 if grid[i][j] == 'X' else 0
y_add = 1 if grid[i][j] == 'Y' else 0
# 计算前缀和
if i == 0 and j == 0:
freq[i][j] = [x_add, y_add]
elif i == 0:
freq[i][j][0] = freq[i][j-1][0] + x_add
freq[i][j][1] = freq[i][j-1][1] + y_add
elif j == 0:
freq[i][j][0] = freq[i-1][j][0] + x_add
freq[i][j][1] = freq[i-1][j][1] + y_add
else:
# 包含-排斥原理
freq[i][j][0] = freq[i-1][j][0] + freq[i][j-1][0] - freq[i-1][j-1][0] + x_add
freq[i][j][1] = freq[i-1][j][1] + freq[i][j-1][1] - freq[i-1][j-1][1] + y_add
# 检查条件
x_count, y_count = freq[i][j]
if x_count > 0 and x_count == y_count:
ans += 1
return ans

复制代码

Myron2017

LC 3731. Find Missing Elements

class Solution:
def findMissingElements(self, nums: List[int]) -> List[int]:
low, high = min(nums), max(nums)
if len(nums) == (high - low + 1): return []
else:
nums_set = set(nums)
ans = []
for n in range(low, high + 1):
if n not in nums_set:
ans.append(n)
return ans

复制代码

更好的解法，不额外引入空间，

优化解法：排序 + 线性扫描
如果我们将数组排序，那么缺失的数字必然存在于相邻两个元素 nums[i] 和 nums[i+1] 之间的空隙里。

class Solution:
def findMissingElements(self, nums: List[int]) -> List[int]:
# 1. 原地排序，不消耗额外空间（或消耗 O(log N) 的递归栈空间）
nums.sort()
ans = []
# 2. 遍历相邻元素
for i in range(len(nums) - 1):
# 如果两个数不连续（差值大于 1）
# 缺失的部分就是 (nums[i] + 1) 到 (nums[i+1] - 1)
for miss in range(nums[i] + 1, nums[i+1]):
ans.append(miss)
return ans

复制代码

Myron2017

3726. Remove Zeros in Decimal Representation
Solved
Easy
Topics
Hint
You are given a positive integer n.

Return the integer obtained by removing all zeros from the decimal representation of n.

Example 1:

Input: n = 1020030

Output: 123

Explanation:

After removing all zeros from 1020030, we get 123.

Example 2:

Input: n = 1

Output: 1

Explanation:

1 has no zero in its decimal representation. Therefore, the answer is 1.

Constraints:

1 <= n <= 1015

class Solution:
def removeZeros(self, n: int) -> int:
ans = [ch for ch in str(n) if ch != '0']
return int("".join(ans))

复制代码

补充内容 (2026-03-19 10:42 +08:00):
面试小技巧：在 Python 中，其实还有一个更直接的写法：

str(n).replace('0', '')

复制代码

。

刷题记录帖子

浏览过的版块