刷题记录帖子

LC. 3653. XOR After Range Multiplication Queries I

数据量小，直接暴力解决。

当然我犯了个错，用了 OR 而不是 XOR； 也忘记了 XOR 的性质。

1. # 你的代码：
   
2. for i in range(1, len(nums)):
   
3.     ans = ans | nums[i]  # ❌ 这里的 '|' 是按位或 (OR)
   
4. 
   
5. # 正确写法：
   
6. for i in range(1, len(nums)):
   
7.     ans = ans ^ nums[i]  # ✅ 这里的 '^' 是按位异或 (XOR)

复制代码

异或的初始值技巧：根据异或的性质 0 ^ X = X，我们可以直接把初始值设为 0，然后遍历整个数组，这样就不需要把 nums[0] 单独拎出来，代码更整洁。

1. class Solution:
   
2.     def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
   
3.         mod = 10**9 + 7
   
4.         for q in queries:
   
5.             l, r, k, v = q
   
6.             for i in range(l, r+1, k):
   
7.                 nums[i] = (nums[i] * v) % mod
   
8.         
   
9.         ans = 0
   
10. 
    
11.         for num in nums:
    
12.             ans = ans ^ num
    
13. 
    
14.         return ans  

复制代码

当然这题，如果数据量扩大，就是 Hard 了，3655. XOR After Range Multiplication Queries II

LC 3687. Library Late Fee Calculator

You are given an integer array daysLate where daysLate[i] indicates how many days late the ith book was returned.

The penalty is calculated as follows:

If daysLate[i] == 1, penalty is 1.
If 2 <= daysLate[i] <= 5, penalty is 2 * daysLate[i].
If daysLate[i] > 5, penalty is 3 * daysLate[i].
Return the total penalty for all books.



Example 1:

Input: daysLate = [5,1,7]

Output: 32

Explanation:

daysLate[0] = 5: Penalty is 2 * daysLate[0] = 2 * 5 = 10.
daysLate[1] = 1: Penalty is 1.
daysLate[2] = 7: Penalty is 3 * daysLate[2] = 3 * 7 = 21.
Thus, the total penalty is 10 + 1 + 21 = 32.
Example 2:

Input: daysLate = [1,1]

Output: 2

Explanation:

daysLate[0] = 1: Penalty is 1.
daysLate[1] = 1: Penalty is 1.
Thus, the total penalty is 1 + 1 = 2.


Constraints:

1 <= daysLate.length <= 100
1 <= daysLate[i] <= 100

1. class Solution:
   
2.     def lateFee(self, daysLate: List[int]) -> int:
   
3.         total = 0
   
4. 
   
5.         for dl in daysLate:
   
6. 
   
7.             if dl == 1: total += 1
   
8.             elif dl >= 2 and dl <= 5:
   
9.                 total += (2 * dl)
   
10.             else:
    
11.                 total += (3 * dl)
    
12.             
    
13.         return total
    
14.         

复制代码

LC 3688. Bitwise OR of Even Numbers in an Array

1. class Solution:
   
2.     def evenNumberBitwiseORs(self, nums: List[int]) -> int:
   
3.         FOUND = False
   
4.         ans = 0
   
5. 
   
6.         for num in nums:
   
7.             if num % 2 == 0:
   
8.                 FOUND = True
   
9.                 ans = ans | num
   
10. 
    
11.         if FOUND:
    
12.             return ans
    
13.         else:
    
14.             return 0

复制代码

LC. 3684. Maximize Sum of At Most K Distinct Elements

1. class Solution:
   
2.     def maxKDistinct(self, nums: List[int], k: int) -> List[int]:
   
3.         
   
4. 
   
5.         nums.sort(reverse = True)
   
6.         ans = []
   
7. 
   
8.         for i in range(len(nums)):
   
9.             if not ans:
   
10.                 ans.append(nums[i])
    
11.             elif len(ans) < k and nums[i] != ans[-1]:
    
12.                 ans.append(nums[i])
    
13.             
    
14.             if len(ans) == k: break
    
15.         
    
16.         return ans
    
17. 
    
18.         

复制代码

更加 Python 一点的code

1. class Solution:
   
2.     def maxKDistinct(self, nums: List[int], k: int) -> List[int]:
   
3.         # 1. 使用 set 去重，得到所有唯一的数字
   
4.         unique_nums = list(set(nums))
   
5.         
   
6.         # 2. 从大到小排序
   
7.         unique_nums.sort(reverse=True)
   
8.         
   
9.         # 3. 返回前 k 个（如果 unique_nums 长度小于 k，切片会自动处理，不会报错）
   
10.         return unique_nums[:k]

复制代码

LC. 3683. Earliest Time to Finish One Task

1. class Solution:
   
2.     def earliestTime(self, tasks: List[List[int]]) -> int:
   
3.         ans = float('inf')
   
4. 
   
5.         for t in tasks:
   
6.             ans = min( ans, t[0] + t[1])
   
7. 
   
8.         return ans
   
9.         

复制代码

LC. 3678. Smallest Absent Positive Greater Than Average

Easy 题目，但是我居然漏看了条件，必须是 postive number，所以逻辑需要加上 i > 0

1. class Solution:
   
2.     def smallestAbsent(self, nums: List[int]) -> int:
   
3.         s = sum(nums)
   
4.         avg = s // len(nums)
   
5.         set_nums = set(nums)
   
6.         curr = avg + 1
   
7.         while True:
   
8.             if curr not in set_nums and curr > 0:
   
9.                 return curr
   
10.             else:
    
11.                 curr += 1

复制代码

优化下 code，其实 Smallest Positive 应该是从 1 开始！somehow 忘记了 Python 的地板除。。。向 负无穷取整的特性。

1. import math
   
2. 
   
3. class Solution:
   
4.     def smallestAbsent(self, nums: List[int]) -> int:
   
5.         s = sum(nums)
   
6.         n = len(nums)
   
7.         avg = s / n  # 使用浮点数除法
   
8.         
   
9.         # 1. 核心逻辑：找到严格大于 avg 的最小整数
   
10.         # 如果 avg = 1.5, start = 2
    
11.         # 如果 avg = 2.0, start = 3
    
12.         start = math.floor(avg) + 1
    
13.         
    
14.         # 2. 必须是正整数，所以如果 start 小于 1，从 1 开始
    
15.         curr = max(1, start)
    
16.         
    
17.         # 3. 使用 set 优化查找效率到 O(1)
    
18.         num_set = set(nums)
    
19.         
    
20.         # 4. 暴力向上找即可。因为 nums 长度才 100，很快就能找到
    
21.         while curr in num_set:
    
22.             curr += 1
    
23.             
    
24.         return curr

复制代码

LC. 3674. Minimum Operations to Equalize Array

乍一看 DP，仔细一看， 直接做。

1. class Solution:
   
2.     def minOperations(self, nums: List[int]) -> int:
   
3.         if len(set(nums)) == 1:
   
4.             return 0
   
5.         else:
   
6.             return 1
   
7.         

复制代码

空间优化， 其实不用整个数组做 set，直接判断所有数字是不是和 第一个数字一样，不一致直接返回 1；只有到结尾都一致才返回0.

1. class Solution:
   
2.     def minOperations(self, nums: List[int]) -> int:
   
3.         # 只要找到任何一个元素和第一个元素不等，就说明需要操作
   
4.         for i in range(1, len(nums)):
   
5.             if nums[i] != nums[0]:
   
6.                 return 1
   
7.         
   
8.         # 如果循环结束都没触发 return，说明全相等
   
9.         return 0

复制代码

LC 3668. Restore Finishing Order
Solved
Easy
Topics
Hint
You are given an integer array order of length n and an integer array friends.

order contains every integer from 1 to n exactly once, representing the IDs of the participants of a race in their finishing order.
friends contains the IDs of your friends in the race sorted in strictly increasing order. Each ID in friends is guaranteed to appear in the order array.
Return an array containing your friends' IDs in their finishing order.



Example 1:

Input: order = [3,1,2,5,4], friends = [1,3,4]

Output: [3,1,4]

Explanation:

The finishing order is [3, 1, 2, 5, 4]. Therefore, the finishing order of your friends is [3, 1, 4].

Example 2:

Input: order = [1,4,5,3,2], friends = [2,5]

Output: [5,2]

Explanation:

The finishing order is [1, 4, 5, 3, 2]. Therefore, the finishing order of your friends is [5, 2].



Constraints:

1 <= n == order.length <= 100
order contains every integer from 1 to n exactly once
1 <= friends.length <= min(8, n)
1 <= friends[i] <= n
friends is strictly increasing

简化算法， order 本身就是完成顺序，所以按序提取即可

1. class Solution:
   
2.     def recoverOrder(self, order: List[int], friends: List[int]) -> List[int]:
   
3.         # 将朋友 ID 存入哈希集合，查找时间复杂度 O(1)
   
4.         friends_set = set(friends)
   
5.         
   
6.         # 按照 order 的顺序筛选出在 friends_set 中的元素
   
7.         # 因为 order 本身就是完成顺序，所以按序提取即可
   
8.         res = [person for person in order if person in friends_set]
   
9.         
   
10.         return res

复制代码

3667. Sort Array By Absolute Value
Solved
Easy
Topics
Hint
You are given an integer array nums.

Rearrange elements of nums in non-decreasing order of their absolute value.

Return any rearranged array that satisfies this condition.

Note: The absolute value of an integer x is defined as:

x if x >= 0
-x if x < 0


Example 1:

Input: nums = [3,-1,-4,1,5]

Output: [-1,1,3,-4,5]

Explanation:

The absolute values of elements in nums are 3, 1, 4, 1, 5 respectively.
Rearranging them in increasing order, we get 1, 1, 3, 4, 5.
This corresponds to [-1, 1, 3, -4, 5]. Another possible rearrangement is [1, -1, 3, -4, 5].
Example 2:

Input: nums = [-100,100]

Output: [-100,100]

Explanation:

The absolute values of elements in nums are 100, 100 respectively.
Rearranging them in increasing order, we get 100, 100.
This corresponds to [-100, 100]. Another possible rearrangement is [100, -100].

我的解法太麻烦，更好的方法是，直接用内置函数，或者用 装饰者模式 (Decorate-Sort-Undecorate)
这其实就是 Python 内部 key 参数的底层思想，也被称为 DSU 模式。

思路：
装饰 (Decorate): 将数组转换为一个元组列表，元组的第一个元素是“排序依据”（绝对值），第二个是“原始值”。

排序 (Sort): 对这个元组列表进行默认排序。

去装饰 (Undecorate): 提取出原始值。

我的原始解法，太繁琐。

1. class Solution:
   
2.     def sortByAbsoluteValue(self, nums: List[int]) -> List[int]:
   
3.         absSet = set()
   
4.         absDict = defaultdict(list)
   
5. 
   
6.         for n in nums:
   
7.             absSet.add(abs(n))
   
8.             absDict[abs(n)].append(n)
   
9. 
   
10.         absList = [x for x in absSet]
    
11.         absList.sort()
    
12. 
    
13.         res = []
    
14.         for a in absList:
    
15.             res += absDict[a]
    
16.         
    
17.         return res
    
18. 
    
19.         

复制代码

用 Python 内置函数 sort with key

1. class Solution:
   
2.     def sortByAbsoluteValue(self, nums: List[int]) -> List[int]:
   
3.         # 直接原地排序，使用 abs 函数作为排序的依据
   
4.         # 时间复杂度: O(n log n)
   
5.         # 空间复杂度: O(1) 或 O(n) 取决于排序算法实现
   
6.         nums.sort(key=abs)
   
7.         return nums

复制代码

不用 sort with key，可以用 装饰者模式 (Decorate-Sort-Undecorate)
这其实就是 Python 内部 key 参数的底层思想，也被称为 DSU 模式。

思路：
装饰 (Decorate): 将数组转换为一个元组列表，元组的第一个元素是“排序依据”（绝对值），第二个是“原始值”。

排序 (Sort): 对这个元组列表进行默认排序。

去装饰 (Undecorate): 提取出原始值。

1. class Solution:
   
2.     def sortByAbsoluteValue(self, nums: List[int]) -> List[int]:
   
3.         # 1. 构造包含 (绝对值, 原始值) 的元组列表
   
4.         # 比如 [3, -1] -> [(3, 3), (1, -1)]
   
5.         decorated = [(abs(x), x) for x in nums]
   
6.         
   
7.         # 2. 对元组进行排序
   
8.         # Python 排序元组时，会先比第一个元素，若相同再比第二个
   
9.         decorated.sort()
   
10.         
    
11.         # 3. 提取排序后的原始值
    
12.         return [pair[1] for pair in decorated]

复制代码

或者最 raw 的手写 quick sort

1. class Solution:
   
2.     def sortByAbsoluteValue(self, nums: List[int]) -> List[int]:
   
3.         def quick_sort(arr):
   
4.             if len(arr) <= 1:
   
5.                 return arr
   
6.             pivot = arr[len(arr) // 2]
   
7.             
   
8.             # 修改这里的比较逻辑：对比的是 abs(x)
   
9.             left = [x for x in arr if abs(x) < abs(pivot)]
   
10.             middle = [x for x in arr if abs(x) == abs(pivot)]
    
11.             right = [x for x in arr if abs(x) > abs(pivot)]
    
12.             
    
13.             return quick_sort(left) + middle + quick_sort(right)
    
14.         
    
15.         return quick_sort(nums)

复制代码

LC  569. Median Employee Salary
Solved
Hard
Topics
conpanies icon
Companies
Hint
SQL Schema
Pandas Schema
Table: Employee

+--------------+---------+
| Column Name  | Type    |
+--------------+---------+
| id           | int     |
| company      | varchar |
| salary       | int     |
+--------------+---------+
id is the primary key (column with unique values) for this table.
Each row of this table indicates the company and the salary of one employee.


Write a solution to find the rows that contain the median salary of each company. While calculating the median, when you sort the salaries of the company, break the ties by id.

Return the result table in any order.

The result format is in the following example.



Example 1:

Input:
Employee table:
+----+---------+--------+
| id | company | salary |
+----+---------+--------+
| 1  | A       | 2341   |
| 2  | A       | 341    |
| 3  | A       | 15     |
| 4  | A       | 15314  |
| 5  | A       | 451    |
| 6  | A       | 513    |
| 7  | B       | 15     |
| 8  | B       | 13     |
| 9  | B       | 1154   |
| 10 | B       | 1345   |
| 11 | B       | 1221   |
| 12 | B       | 234    |
| 13 | C       | 2345   |
| 14 | C       | 2645   |
| 15 | C       | 2645   |
| 16 | C       | 2652   |
| 17 | C       | 65     |
+----+---------+--------+
Output:
+----+---------+--------+
| id | company | salary |
+----+---------+--------+
| 5  | A       | 451    |
| 6  | A       | 513    |
| 12 | B       | 234    |
| 9  | B       | 1154   |
| 14 | C       | 2645   |
+----+---------+--------+
Explanation:
For company A, the rows sorted are as follows:
+----+---------+--------+
| id | company | salary |
+----+---------+--------+
| 3  | A       | 15     |
| 2  | A       | 341    |
| 5  | A       | 451    | <-- median
| 6  | A       | 513    | <-- median
| 1  | A       | 2341   |
| 4  | A       | 15314  |
+----+---------+--------+
For company B, the rows sorted are as follows:
+----+---------+--------+
| id | company | salary |
+----+---------+--------+
| 8  | B       | 13     |
| 7  | B       | 15     |
| 12 | B       | 234    | <-- median
| 11 | B       | 1221   | <-- median
| 9  | B       | 1154   |
| 10 | B       | 1345   |
+----+---------+--------+
For company C, the rows sorted are as follows:
+----+---------+--------+
| id | company | salary |
+----+---------+--------+
| 17 | C       | 65     |
| 13 | C       | 2345   |
| 14 | C       | 2645   | <-- median
| 15 | C       | 2645   |
| 16 | C       | 2652   |
+----+---------+--------+


Follow up: Could you solve it without using any built-in or window functions?

1. # Write your MySQL query statement below
   
2. WITH RankedEmployees AS (
   
3.     SELECT
   
4.         id,
   
5.         company,
   
6.         salary,
   
7.         ROW_NUMBER() OVER(PARTITION BY company ORDER BY salary, id) AS rn,
   
8.         COUNT(*) OVER(PARTITION BY company) AS total_count
   
9.     FROM Employee
   
10. )
    
11. SELECT id, company, salary
    
12. FROM RankedEmployees
    
13. WHERE rn BETWEEN total_count / 2.0 AND total_count / 2.0 + 1;

复制代码