刷题记录帖子

Myron2017

LC 401. Binary Watch

题目希望的做法，用 bit—count

class Solution:
def readBinaryWatch(self, turnedOn: int):
res = []
for h in range(12):
for m in range(60):
if (h.bit_count() + m.bit_count()) == turnedOn:
res.append(f"{h}:{m:02d}")
return res

复制代码

但是我觉得更好的程序员的想法应该是，DFS

from typing import List
class Solution:
def readBinaryWatch(self, turnedOn: int) -> List[str]:
if turnedOn > 8: # 最多 8 个灯还能合法
return []
hours = [8, 4, 2, 1]
minutes = [32, 16, 8, 4, 2, 1]
res = []
# 生成所有和为 val 且使用 k 个灯的组合
def dfs(arr, start, k, cur_sum, result, limit):
if k == 0:
if cur_sum <= limit:
result.append(cur_sum)
return
for i in range(start, len(arr)):
dfs(arr, i + 1, k - 1, cur_sum + arr[i], result, limit)
# 枚举小时用几个灯
for h_used in range(0, min(4, turnedOn) + 1):
m_used = turnedOn - h_used
if m_used > 6:
continue
hour_vals = []
minute_vals = []
dfs(hours, 0, h_used, 0, hour_vals, 11)
dfs(minutes, 0, m_used, 0, minute_vals, 59)
for h in hour_vals:
for m in minute_vals:
res.append(f"{h}:{m:02d}")
return res

复制代码

这道题目完全可以作为 DFS 的练手题目。

Myron2017

LC 696. Count Binary Substrings

发现子串必须是 000111 或 111000 结构

本质是相邻连续段匹配

每一对相邻段贡献 min(长度1, 长度2)

class Solution:
def countBinarySubstrings(self, s: str) -> int:
# prev 表示前一段连续字符的长度
prev = 0
# curr 表示当前这段连续字符的长度
# 初始化为 1，因为第一个字符已经构成一个长度为 1 的连续段
curr = 1
# 用来统计符合条件的子串数量
ans = 0
# 从第二个字符开始遍历
for i in range(1, len(s)):
# 如果当前字符和前一个字符相同
# 说明还在同一个连续段内
if s[i] == s[i-1]:
curr += 1
else:
# 出现字符变化，说明当前连续段结束
# 相邻两段可以构成的合法子串数量为
# min(前一段长度, 当前段长度)
ans += min(prev, curr)
# 当前段变成下一次的前一段
prev = curr
# 重置当前段长度为 1（当前字符是新一段的开始）
curr = 1
# 循环结束后，最后一段还没有计算
# 需要再计算一次
ans += min(prev, curr)
return ans

复制代码

Myron2017

LC 762. Prime Number of Set Bits in Binary Representation

数量级比较小，直接暴力统计 1 in binary number 的个数统计下就行。

class Solution:
def countPrimeSetBits(self, left: int, right: int) -> int:
# 2^20 > 10^6 > 2^19
# so the total length of left, right in binary musht < 20
# < 20, we have 2, 3, 5, 7, 11, 13, 17, 19 prime numbers
ans = 0
primes = (2, 3, 5, 7, 11, 13, 17, 19)
def count_bit(n):
count = 0
while n:
n = n & (n-1)
count += 1
return count
for i in range(left, right+1):
#if i.bit_count() in primes: ans += 1
if count_bit(i) in primes: ans += 1
return ans

复制代码

当然复杂了的话，就是区间 DP 了。

一、问题转化

我们要计算：

[left, right] 区间中
bit_count(x) 是质数的个数

经典套路：

f(right) - f(left - 1)

所以核心变成：

计算 0 ~ n 中，bit_count 是质数的个数

二、数位 DP 思路

我们按二进制位，从高位到低位枚举。

定义状态：

dp(pos, count_ones, is_limit)

含义：

pos：当前处理到第几位

count_ones：当前已经用了多少个 1

is_limit：当前是否受上界限制

三、为什么这样设计？

因为我们是逐位构造数字。

例如：

n = 13 = 1101 (二进制)

我们逐位决定：

这一位放 0 还是 1

不能超过上界

四、完整代码（真正数位 DP）

class Solution:
def countPrimeSetBits(self, left: int, right: int) -> int:
primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}
# 计算 0 ~ n 的答案
def count(n: int) -> int:
if n < 0:
return 0
bits = list(map(int, bin(n)[2:])) # 二进制位列表
length = len(bits)
from functools import lru_cache
@lru_cache(None)
def dp(pos: int, count_ones: int, is_limit: bool) -> int:
# 所有位处理完
if pos == length:
return 1 if count_ones in primes else 0
total = 0
# 当前位最多能填多少
upper = bits[pos] if is_limit else 1
for digit in range(upper + 1):
total += dp(
pos + 1,
count_ones + digit,
is_limit and digit == upper
)
return total
return dp(0, 0, True)
return count(right) - count(left - 1)

复制代码

Myron2017

LC 183. Customers Who Never Order

183. Customers Who Never Order
Solved
Easy
Topics
conpanies icon
Companies
SQL Schema
Pandas Schema
Table: Customers

+-------------+---------+
| Column Name | Type |
+-------------+---------+
| id       | int    |
| name       | varchar |
+-------------+---------+
id is the primary key (column with unique values) for this table.
Each row of this table indicates the ID and name of a customer.

Table: Orders

+-------------+------+
| Column Name | Type |
+-------------+------+
| id       | int  |
| customerId  | int  |
+-------------+------+
id is the primary key (column with unique values) for this table.
customerId is a foreign key (reference columns) of the ID from the Customers table.
Each row of this table indicates the ID of an order and the ID of the customer who ordered it.

Write a solution to find all customers who never order anything.

Return the result table in any order.

The result format is in the following example.

Example 1:

Input:
Customers table:
+----+-------+
| id | name  |
+----+-------+
| 1  | Joe |
| 2  | Henry |
| 3  | Sam |
| 4  | Max |
+----+-------+
Orders table:
+----+------------+
| id | customerId |
+----+------------+
| 1  | 3       |
| 2  | 1       |
+----+------------+
Output:
+-----------+
| Customers |
+-----------+
| Henry    |
| Max    |
+-----------+

SELECT c.name AS Customers
FROM Customers c
LEFT JOIN Orders o
ON c.id = o.customerId
WHERE o.id IS NULL;

复制代码

Myron2017

181. Employees Earning More Than Their Managers
Easy
Topics
conpanies icon
Companies
SQL Schema
Pandas Schema
Table: Employee

+-------------+---------+
| Column Name | Type |
+-------------+---------+
| id       | int    |
| name       | varchar |
| salary    | int    |
| managerId | int    |
+-------------+---------+
id is the primary key (column with unique values) for this table.
Each row of this table indicates the ID of an employee, their name, salary, and the ID of their manager.

Write a solution to find the employees who earn more than their managers.

Return the result table in any order.

The result format is in the following example.

Example 1:

Input:
Employee table:
+----+-------+--------+-----------+
| id | name  | salary | managerId |
+----+-------+--------+-----------+
| 1  | Joe | 70000  | 3       |
| 2  | Henry | 80000  | 4       |
| 3  | Sam | 60000  | Null    |
| 4  | Max | 90000  | Null    |
+----+-------+--------+-----------+
Output:
+----------+
| Employee |
+----------+
| Joe    |
+----------+
Explanation: Joe is the only employee who earns more than his manager.

自连接（Self Join）

解释

JOIN Employee m ON e.managerId = m.id

这里把 Employee 表自己和自己连起来

e 是普通员工，m 是经理

e.managerId 对应 m.id

WHERE e.salary > m.salary

筛选出工资高于经理的员工

SELECT e.name AS Employee

返回员工姓名

SELECT e.name AS Employee
FROM Employee e
JOIN Employee m
ON e.managerId = m.id
WHERE e.salary > m.salary;

复制代码

补充内容 (2026-02-21 11:11 +08:00):
注意点

如果
1. managerId IS NULL
复制代码
的员工（顶级经理）
- JOIN 后不会匹配到 m.id
- 自然不会出现在结果里 ✅

Myron2017

178. Rank Scores
Medium
Topics
conpanies icon
Companies
SQL Schema
Pandas Schema
Table: Scores

+-------------+---------+
| Column Name | Type |
+-------------+---------+
| id | int |
| score | decimal |
+-------------+---------+
id is the primary key (column with unique values) for this table.
Each row of this table contains the score of a game. Score is a floating point value with two decimal places.

Write a solution to find the rank of the scores. The ranking should be calculated according to the following rules:

The scores should be ranked from the highest to the lowest.
If there is a tie between two scores, both should have the same ranking.
After a tie, the next ranking number should be the next consecutive integer value. In other words, there should be no holes between ranks.
Return the result table ordered by score in descending order.

The result format is in the following example.

# Write your MySQL query statement below
SELECT
score,
DENSE_RANK() OVER (ORDER BY score DESC) AS 'rank'
FROM Scores
ORDER BY score DESC;

复制代码

DENSE_RANK() OVER (ORDER BY score DESC)

按分数从高到低排序

相同分数得到相同排名

下一个不同分数的排名紧跟前面的排名（不跳号）

ORDER BY score DESC

最终输出按分数从高到低排列

如果你用 RANK()：

会出现跳号：

score: 90.50 90.50 88.00 85.00
rank: 1 1 3 4

Myron2017

LC 868. Binary Gap

class Solution:
def binaryGap(self, n: int) -> int:
ans = -1
prev_one_index = -1
bin_n = str(bin(n)[2:])
for i in range(len(bin_n)):
if bin_n[i] == '1':
if prev_one_index == -1:
prev_one_index = i
else:
ans = max(ans, i - prev_one_index)
prev_one_index = i
if ans != -1: return ans
else: return 0

复制代码

更好的 code，先处理 happy case

class Solution:
def binaryGap(self, n: int) -> int:
s = bin(n)[2:] # 转为二进制字符串，去掉 '0b' 前缀
max_dist = 0
last_pos = -1
for i, char in enumerate(s):
if char == '1':
if last_pos != -1:
max_dist = max(max_dist, i - last_pos)
last_pos = i
return max_dist

复制代码

Myron2017

LC. 1461. Check If a String Contains All Binary Codes of Size K

class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
# get all substring with length k
sub_str_set = set()
for i in range(0, len(s) - k + 1):
sub_str_set.add(s[i:i+k])
return len(sub_str_set) == 2**k

复制代码

Myron2017

319. Bulb Switcher

There are n bulbs that are initially off. You first turn on all the bulbs, then you turn off every second bulb.

On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb.

Return the number of bulbs that are on after n rounds.

Example 1:

Input: n = 3
Output: 1
Explanation: At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off].
So you should return 1 because there is only one bulb is on.
Example 2:

Input: n = 0
Output: 0
Example 3:

Input: n = 1
Output: 1

Constraints:

0 <= n <= 109

其实我不喜欢这道题目，我也不觉得这是一道好的面试题目，因为你在考察面试者是不是知道这个数学知识点。
我觉得想到反过来说，第 $k$ 个灯泡会在所有是 $k$ 的约数的轮次被切换。
但是对于某个数来说，

普通数字（非完全平方数）：约数总是成双成对出现的。例如 $n = 12$：$1 \times 12 = 12$$2 \times 6 = 12$$3 \times 4 = 12$约数集合：$\{1, 2, 3, 4, 6, 12\}$，共 6 个（偶数）。完全平方数：约数依然成对出现，但其中有一对是重复的。例如 $n = 16$：$1 \times 16 = 16$$2 \times 8 = 16$$4 \times 4 = 16$ $\leftarrow$ 重点在这里！约数集合：$\{1, 2, 4, 8, 16\}$，共 5 个（奇数）。数字 $4$ 独自成对，导致总数变成了奇数。

这里需要注意，虽然约数个数是偶数，但是因为 1 不参与打开灯的操作，所以偶数个约数的灯最后是关闭的，因为实际是奇数次开关。
奇数个约数的灯，因为排除了 1 ，所以最后是打开的。

所以题目代码很简单。

class Solution:
def bulbSwitch(self, n: int) -> int:
if n == 0: return 0
if n == 1: return 1
return int(n**0.5)

复制代码

Myron2017

877. Stone Game
Solved
Medium
Topics
conpanies icon
Companies
Alice and Bob play a game with piles of stones. There are an even number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].

The objective of the game is to end with the most stones. The total number of stones across all the piles is odd, so there are no ties.

Alice and Bob take turns, with Alice starting first. Each turn, a player takes the entire pile of stones either from the beginning or from the end of the row. This continues until there are no more piles left, at which point the person with the most stones wins.

Assuming Alice and Bob play optimally, return true if Alice wins the game, or false if Bob wins.

Example 1:

Input: piles = [5,3,4,5]
Output: true
Explanation:
Alice starts first, and can only take the first 5 or the last 5.
Say she takes the first 5, so that the row becomes [3, 4, 5].
If Bob takes 3, then the board is [4, 5], and Alice takes 5 to win with 10 points.
If Bob takes the last 5, then the board is [3, 4], and Alice takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alice, so we return true.
Example 2:

Input: piles = [3,7,2,3]
Output: true

Constraints:

2 <= piles.length <= 500
piles.length is even.
1 <= piles[i] <= 500
sum(piles[i]) is odd.

如果你尝试用动态规划 (DP) 去解，你会写出 $O(n^2)$ 的代码并顺利通过；但如果你看穿了这道题的本质，你会发现它的答案永远是 return True。这又是数学思维对暴力模拟的一次“降维打击”。1. 核心前提（三个关键点）题目给出了三个至关重要的限制条件：石子堆的总数是偶数（piles.length is even）。石子的总数是奇数（sum(piles) is odd），这意味着不可能平局。Alice 先手。2. Alice 的“必胜策略”：奇偶位选择权因为总堆数是偶数，我们可以把这些堆按索引分为奇数位和偶数位。假设 piles = [5, 3, 4, 5]：偶数位（索引 0, 2）：5, 4，总和为 $9$。奇数位（索引 1, 3）：3, 5，总和为 $8$。Alice 作为先手，可以控制自己拿走所有的偶数位，或者所有的奇数位！她是怎么做到的？想拿全部偶数位：Alice 先拿 piles[0]（偶数位）。剩下的数组两端就变成了索引 1 和索引 $n-1$（都是奇数位）。无论 Bob 拿哪一头，他都只能拿走一个奇数位。Bob 拿完后，数组的两端又会露出一堆偶数位供 Alice 选择。想拿全部奇数位：Alice 先拿 piles[n-1]（最后一个，索引是奇数）。同理，她可以迫使 Bob 只能接触偶数位，而自己把奇数位全卷走。3. 为什么 Alice 必胜？既然 Alice 可以计算出“奇数位总和”与“偶数位总和”哪个更大，而总数又是奇数（保证了两者一定不相等），那么：如果偶数位总和 > 奇数位总和，Alice 就全程只拿偶数位。如果奇数位总和 > 偶数位总和，Alice 就全程只拿奇数位。结论：只要 Alice 足够聪明（Optimal Play），她从第一步开始就已经锁定了胜局。

刷题记录帖子

浏览过的版块