刷题记录帖子

LC  3546. Equal Sum Grid Partition I

暴力做超时了，主要在 判断 row 的和的时候，如果每次都计算，重复计算了很多次。

首先要用前缀合的概念。

其次是要知道，找到一半的 total—sum，这个目标然后再求解。

复杂度分析：时间复杂度：O(m x n)。我们遍历了两次矩阵（一次算行和，一次算列和），剩下的切分检查是 O(m) 和 O(n)。空间复杂度：O(m + n)，用于存储 row_sums 和 col_sums。

1. class Solution:
   
2.     def canPartitionGrid(self, grid: List[List[int]]) -> bool:
   
3.         nrows = len(grid)
   
4.         ncols = len(grid[0])
   
5.         sum_rows = [0] * nrows
   
6.         sum_cols = [0] * ncols
   
7.         
   
8.         for i in range(nrows):
   
9.             sum_rows[i] = sum(grid[i])
   
10.         
    
11.         for j in range(ncols):
    
12.             for i in range(nrows):
    
13.                 sum_cols[j] += grid[i][j]
    
14. 
    
15. 
    
16.         '''
    
17.         for i in range(1, nrows):
    
18.             if sum(sum_rows[:i]) == sum(sum_rows[i:]):
    
19.                 return True
    
20.             
    
21.         for i in range(1, ncols):
    
22.             if sum(sum_cols[:i]) == sum(sum_cols[i:]):
    
23.                 return True
    
24.         '''
    
25. 
    
26.         total = sum(sum_rows)
    
27. 
    
28.         if total % 2 == 1: return False
    
29. 
    
30.         curr_row_sum = 0
    
31.         for i in range(nrows-1):
    
32.             curr_row_sum += sum_rows[i]
    
33.             if curr_row_sum == total // 2:
    
34.                 return True
    
35. 
    
36.         curr_col_sum = 0
    
37.         for i in range(ncols-1):
    
38.             curr_col_sum += sum_cols[i]
    
39.             if curr_col_sum == total // 2:
    
40.                 return True
    
41.         
    
42.         return False

复制代码

LC. 607. Sales Person
Solved
Easy
Topics
conpanies icon
Companies
Hint
SQL Schema
Pandas Schema
Table: SalesPerson

+-----------------+---------+
| Column Name     | Type    |
+-----------------+---------+
| sales_id        | int     |
| name            | varchar |
| salary          | int     |
| commission_rate | int     |
| hire_date       | date    |
+-----------------+---------+
sales_id is the primary key (column with unique values) for this table.
Each row of this table indicates the name and the ID of a salesperson alongside their salary, commission rate, and hire date.


Table: Company

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| com_id      | int     |
| name        | varchar |
| city        | varchar |
+-------------+---------+
com_id is the primary key (column with unique values) for this table.
Each row of this table indicates the name and the ID of a company and the city in which the company is located.


Table: Orders

+-------------+------+
| Column Name | Type |
+-------------+------+
| order_id    | int  |
| order_date  | date |
| com_id      | int  |
| sales_id    | int  |
| amount      | int  |
+-------------+------+
order_id is the primary key (column with unique values) for this table.
com_id is a foreign key (reference column) to com_id from the Company table.
sales_id is a foreign key (reference column) to sales_id from the SalesPerson table.
Each row of this table contains information about one order. This includes the ID of the company, the ID of the salesperson, the date of the order, and the amount paid.


Write a solution to find the names of all the salespersons who did not have any orders related to the company with the name "RED".

Return the result table in any order.

The result format is in the following example.



Example 1:

Input:
SalesPerson table:
+----------+------+--------+-----------------+------------+
| sales_id | name | salary | commission_rate | hire_date  |
+----------+------+--------+-----------------+------------+
| 1        | John | 100000 | 6               | 4/1/2006   |
| 2        | Amy  | 12000  | 5               | 5/1/2010   |
| 3        | Mark | 65000  | 12              | 12/25/2008 |
| 4        | Pam  | 25000  | 25              | 1/1/2005   |
| 5        | Alex | 5000   | 10              | 2/3/2007   |
+----------+------+--------+-----------------+------------+
Company table:
+--------+--------+----------+
| com_id | name   | city     |
+--------+--------+----------+
| 1      | RED    | Boston   |
| 2      | ORANGE | New York |
| 3      | YELLOW | Boston   |
| 4      | GREEN  | Austin   |
+--------+--------+----------+
Orders table:
+----------+------------+--------+----------+--------+
| order_id | order_date | com_id | sales_id | amount |
+----------+------------+--------+----------+--------+
| 1        | 1/1/2014   | 3      | 4        | 10000  |
| 2        | 2/1/2014   | 4      | 5        | 5000   |
| 3        | 3/1/2014   | 1      | 1        | 50000  |
| 4        | 4/1/2014   | 1      | 4        | 25000  |
+----------+------------+--------+----------+--------+
Output:
+------+
| name |
+------+
| Amy  |
| Mark |
| Alex |
+------+
Explanation:
According to orders 3 and 4 in the Orders table, it is easy to tell that only salesperson John and Pam have sales to company RED, so we report all the other names in the table salesperson.

1. SELECT
   
2.     name
   
3. FROM
   
4.     SalesPerson
   
5. WHERE
   
6.     sales_id NOT IN (
   
7.         -- 子查询：找到所有给 RED 公司卖过货的销售 ID (黑名单)
   
8.         SELECT
   
9.             sales_id
   
10.         FROM
    
11.             Orders
    
12.         JOIN
    
13.             Company ON Orders.com_id = Company.com_id
    
14.         WHERE
    
15.             Company.name = 'RED'
    
16.     );

复制代码

LC 2946. Matrix Similarity After Cyclic Shifts
Solved
Easy
Topics
conpanies icon
Companies
Hint
You are given an m x n integer matrix mat and an integer k. The matrix rows are 0-indexed.

The following proccess happens k times:

Even-indexed rows (0, 2, 4, ...) are cyclically shifted to the left.

Odd-indexed rows (1, 3, 5, ...) are cyclically shifted to the right.

Return true if the final modified matrix after k steps is identical to the original matrix, and false otherwise.

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 4

Output: false

Explanation:

In each step left shift is applied to rows 0 and 2 (even indices), and right shift to row 1 (odd index).

Example 2:

Input: mat = [[1,2,1,2],[5,5,5,5],[6,3,6,3]], k = 2

Output: true

Explanation:

Example 3:

Input: mat = [[2,2],[2,2]], k = 3

Output: true

Explanation:

As all the values are equal in the matrix, even after performing cyclic shifts the matrix will remain the same.

这道题目看着简单但是做起来其实并不容易。。。。

我就是笨方法解，左移动不太好判断还写了循环。

其实我当时有感觉，这个是镜像，必须有规律，但是没想到。。。

LC. 3712. Sum of Elements With Frequency Divisible by K

1. class Solution:
   
2.     def sumDivisibleByK(self, nums: List[int], k: int) -> int:
   
3.         freq = Counter(nums)
   
4.         ans = 0
   
5. 
   
6.         for key, val in freq.items():
   
7.             if val % k == 0:
   
8.                 ans += (key * val)
   
9.         
   
10.         return ans

复制代码

LC  3875. Construct Uniform Parity Array I

分情况讨论，

全奇数，全偶数 Return True

有奇数，有偶数，因为变换 2 : nums2[i] = nums1[i] - nums1[j], for an index j != i, 没有任何限制，所以任何偶数都可以变成奇数。

所以直接 Return True。

1. class Solution:
   
2.     def uniformArray(self, nums1: list[int]) -> bool:
   
3.         return True

复制代码

LC. 3876. Construct Uniform Parity Array II

上一道题的进阶，主要在与变化 2 被加了限制条件，

nums2[i] = nums1[i] - nums1[j], for an index j != i, such that nums1[i] - nums1[j] >= 1

必须是比当前数小的数才行，同时 nums1 of n distinct integers。

所以先排除全偶数这个 case。

然后排序，这样对于每个偶数，只要判断前面有没有奇数，就可以保证所有的偶数变成奇数。

这样就可以写代码。

1. class Solution:
   
2.     def uniformArray(self, nums1: list[int]) -> bool:
   
3.         n = len(nums1)
   
4.         nums1.sort()
   
5.         # rule out all even
   
6.         allEven = True
   
7.         allOdd = True
   
8.         for num in nums1:
   
9.             if num % 2 == 1:
   
10.                 allEven = False
    
11.             else:
    
12.                 allOdd = False
    
13. 
    
14.         if allEven: return True
    
15.         if allOdd:  return True
    
16. 
    
17.         pre_odd_num = 0
    
18. 
    
19.         for i in range(n):
    
20.             if nums1[i] % 2 == 0:
    
21.                 if pre_odd_num == 0:
    
22.                     return False
    
23.             else:
    
24.                 pre_odd_num += 1
    
25. 
    
26.         return True
    
27.                
    
28.         

复制代码

但是进一步简化，你需要知道每一个偶数前面有没有奇数吗？不需要，你只需要最小的一位是奇数就行。这是因为，如果排序后最小的数，不是奇数，那么它前面没有比它更小的奇数了，返回 False。

同时如果它是奇数，后面所有的偶数都可以用这个排序最小的数，因为它是奇数。

1. class Solution:
   
2.     def uniformArray(self, nums1: list[int]) -> bool:
   
3.         # 1. 排序是核心，保证我们能拿到最小值
   
4.         nums1.sort()
   
5.         
   
6.         # 2. 逻辑 A: 如果本身全是偶数，直接成功
   
7.         # 3. 逻辑 B: 如果有奇数，最小值必须是奇数（才能把偶数带成奇数）
   
8.         # 结合起来就是：
   
9.         return all(x % 2 == 0 for x in nums1) or (nums1[0] % 2 == 1)

复制代码

LC. 3880. Minimum Absolute Difference Between Two Values

虽然是一道简单题，但是其实还是考察了特别的一点，在这种题目中，需要随时记录下 last seen 1 or 2，然后计算距离。

就类似找一个新的 1， 我不需要看下一个 2 在哪里，因为后面的数字我不确定，还没遍历过；但是在前面我最后见到的最近的 2，我是知道 last—two。直接计算 diff。

一句话总结：
“不要总想着去后面找谁，要学会记录刚才路过了谁。”

1. class Solution:
   
2.     def minAbsoluteDifference(self, nums: list[int]) -> int:
   
3.         last_one = -1
   
4.         last_two = -1
   
5.         n = len(nums)
   
6. 
   
7.         min_diff = float('inf')
   
8. 
   
9.         for ind, val in enumerate(nums):
   
10.             if val == 1:
    
11.                 last_one = ind
    
12.                 if last_two != -1:
    
13.                     min_diff = min( min_diff, abs(last_one - last_two))
    
14. 
    
15.             elif val == 2:
    
16.                 last_two = ind
    
17.                 if last_one != -1:
    
18.                     min_diff = min( min_diff, abs(last_one - last_two))
    
19.         
    
20.         if min_diff != float('inf'):
    
21.             return min_diff
    
22.         else:
    
23.             return -1
    
24. 
    
25.         

复制代码

楼主坚持了6年 请问你有刷题群吗

vvqqdd 发表于 2026-3-31 00:40
楼主坚持了6年 请问你有刷题群吗

中间断了三年，直到今年被裁，才醒悟过来继续刷题。
虽然也上岸了，但是惊弓之鸟，只能朝乾夕惕。

你要加刷题群可以找板上有的，那个群还挺好的，这个随意。

https://www.1point3acres.com/bbs/thread-1133259-1-1.html

LC 246. Strobogrammatic Number

Given a string num which represents an integer, return true if num is a strobogrammatic number.

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).



Example 1:

Input: num = "69"
Output: true
Example 2:

Input: num = "88"
Output: true
Example 3:

Input: num = "962"
Output: false


Constraints:

1 <= num.length <= 50
num consists of only digits.
num does not contain any leading zeros except for zero itself.

虽然是道简单题，但是优化做法还是值得学习的。可能脑子僵住了。。。我写了个巨复杂的解法，

1. class Solution:
   
2.     def isStrobogrammatic(self, num: str) -> bool:
   
3.         num = str(num)
   
4.         n = len(num)
   
5.         if n == 1:
   
6.             if num not in ['1', '0', '8']: return False
   
7.             else: return True
   
8.         rev = []
   
9.         NotFound = True
   
10.         for ind,val in enumerate(num):
    
11.             if val in ['2', '3', '4', '5', '7']:
    
12.                 NotFound = False
    
13.                 break
    
14.             elif val == '6':
    
15.                 if num[n-1-ind] != '9':
    
16.                     NotFound = False
    
17.                     break
    
18.                 else:
    
19.                     rev.append('9')
    
20.             elif val == '9':
    
21.                 if num[n-1-ind] != '6':
    
22.                     NotFound = False
    
23.                     break
    
24.                 else:
    
25.                     rev.append('6')
    
26.             else:
    
27.                 rev.append(val)
    
28.             
    
29.         if NotFound:
    
30.             if "".join(rev[::-1]) == num:
    
31.                 return True
    
32.             else:
    
33.                 return False
    
34.         else:
    
35.             return False
    
36.         

复制代码

优化的代码，

Map 映射 + 双指针


“中心对称” (Strobogrammatic) 在字符串处理上，完全等同于：

映射 (Mapping)：每个数字变成它旋转后的样子。

倒序 (Reversing)：旋转后原本在左边的数会跑到右边。

1. class Solution:
   
2.     def isStrobogrammatic(self, num: str) -> bool:
   
3.         # 定义旋转映射关系
   
4.         # 0->0, 1->1, 8->8, 6->9, 9->6
   
5.         maps = {
   
6.             '0': '0',
   
7.             '1': '1',
   
8.             '8': '8',
   
9.             '6': '9',
   
10.             '9': '6'
    
11.         }
    
12.         
    
13.         l, r = 0, len(num) - 1
    
14.         
    
15.         while l <= r:
    
16.             # 1. 如果当前的数字根本不在映射表里，直接出局
    
17.             if num[l] not in maps:
    
18.                 return False
    
19.             
    
20.             # 2. 核心逻辑：左边的数字旋转后，必须等于右边的数字
    
21.             if maps[num[l]] != num[r]:
    
22.                 return False
    
23.             
    
24.             # 指针向中间移动
    
25.             l += 1
    
26.             r -= 1
    
27.             
    
28.         return True

复制代码