刷题记录帖子

LC. 3005. Count Elements With Maximum Frequency

You are given an array nums consisting of positive integers.

Return the total frequencies of elements in nums such that those elements all have the maximum frequency.

The frequency of an element is the number of occurrences of that element in the array.



Example 1:

Input: nums = [1,2,2,3,1,4]
Output: 4
Explanation: The elements 1 and 2 have a frequency of 2 which is the maximum frequency in the array.
So the number of elements in the array with maximum frequency is 4.
Example 2:

Input: nums = [1,2,3,4,5]
Output: 5
Explanation: All elements of the array have a frequency of 1 which is the maximum.
So the number of elements in the array with maximum frequency is 5.


Constraints:

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

我的解法，多变遍历

1. class Solution:
   
2.     def maxFrequencyElements(self, nums: List[int]) -> int:
   
3.         freq = Counter(nums)
   
4.         max_freq = max(freq.values())
   
5. 
   
6.         ans = 0
   
7. 
   
8.         for v in freq:
   
9.             if freq[v] == max_freq:
   
10.                 ans += max_freq
    
11.         
    
12.         return ans
    
13.         

复制代码

优化的同样思路的写法

1. from collections import Counter
   
2. from typing import List
   
3. 
   
4. class Solution:
   
5.     def maxFrequencyElements(self, nums: List[int]) -> int:
   
6.         freq = Counter(nums)
   
7.         max_freq = max(freq.values())
   
8.         
   
9.         # 生成器表达式：遍历所有频次，如果等于最大频次，就累加
   
10.         return sum(f for f in freq.values() if f == max_freq)

复制代码

更加优化的写法， 一次遍历！

核心思路：在遍历数组、累加频率的同时，动态维护当前的 max_freq 和 ans。

如果发现某个数字的频率 大于 当前的 max_freq，说明之前的 ans 都作废了，我们要更新 max_freq，并且把 ans 重置为当前频率。

如果发现某个数字的频率 等于 当前的 max_freq，说明它也是最大频率的候选人，把它的频率累加到 ans 中。

一次遍历代码实现

1. class Solution:
   
2.     def maxFrequencyElements(self, nums: List[int]) -> int:
   
3.         freq = {}
   
4.         max_freq = 0
   
5.         ans = 0
   
6.         
   
7.         for num in nums:
   
8.             # 1. 更新当前数字的频次
   
9.             freq[num] = freq.get(num, 0) + 1
   
10.             cur_freq = freq[num]
    
11.             
    
12.             # 2. 动态维护最大频次和答案
    
13.             if cur_freq > max_freq:
    
14.                 max_freq = cur_freq
    
15.                 ans = cur_freq       # 出现更大的频次，之前的 ans 作废，重新洗牌
    
16.             elif cur_freq == max_freq:
    
17.                 ans += cur_freq      # 和当前最大频次一样，累加到 ans 中
    
18.                
    
19.         return ans

复制代码

LC. 3465. Find Products with Valid Serial Numbers
Easy
Topics
SQL Schema
Pandas Schema
Table: products

+--------------+------------+
| Column Name  | Type       |
+--------------+------------+
| product_id   | int        |
| product_name | varchar    |
| description  | varchar    |
+--------------+------------+
(product_id) is the unique key for this table.
Each row in the table represents a product with its unique ID, name, and description.
Write a solution to find all products whose description contains a valid serial number pattern. A valid serial number follows these rules:

It starts with the letters SN (case-sensitive).
Followed by exactly 4 digits.
It must have a hyphen (-) followed by exactly 4 digits.
The serial number must be within the description (it may not necessarily start at the beginning).
Return the result table ordered by product_id in ascending order.

The result format is in the following example.



Example:

Input:

products table:

+------------+--------------+------------------------------------------------------+
| product_id | product_name | description                                          |
+------------+--------------+------------------------------------------------------+
| 1          | Widget A     | This is a sample product with SN1234-5678            |
| 2          | Widget B     | A product with serial SN9876-1234 in the description |
| 3          | Widget C     | Product SN1234-56789 is available now                |
| 4          | Widget D     | No serial number here                                |
| 5          | Widget E     | Check out SN4321-8765 in this description            |
+------------+--------------+------------------------------------------------------+
   
Output:

+------------+--------------+------------------------------------------------------+
| product_id | product_name | description                                          |
+------------+--------------+------------------------------------------------------+
| 1          | Widget A     | This is a sample product with SN1234-5678            |
| 2          | Widget B     | A product with serial SN9876-1234 in the description |
| 5          | Widget E     | Check out SN4321-8765 in this description            |
+------------+--------------+------------------------------------------------------+
   
Explanation:

Product 1: Valid serial number SN1234-5678
Product 2: Valid serial number SN9876-1234
Product 3: Invalid serial number SN1234-56789 (contains 5 digits after the hyphen)
Product 4: No serial number in the description
Product 5: Valid serial number SN4321-8765
The result table is ordered by product_id in ascending order.

1. 
   
2. 
   
3. SELECT product_id, product_name, description
   
4. FROM products
   
5. WHERE REGEXP_LIKE(description, '\\bSN[0-9]{4}-[0-9]{4}\\b', 'c')
   
6. ORDER BY product_id ASC;
   
7. 
   

复制代码

How it Works:
REGEXP_LIKE() is used to perform a regular expression match on the description column.

'\\b' specifies a word boundary. This ensures we don't accidentally match strings where the pattern is embedded within a longer sequence (e.g., it prevents matching "ASN1234-5678" or "SN1234-56789").

SN matches the literal characters "SN".

[0-9]{4} ensures there are exactly 4 digits before the hyphen.

- matches the literal hyphen.

[0-9]{4} ensures exactly 4 digits follow the hyphen.

'c' is passed as the third argument to force the match to be case-sensitive, strictly ensuring it looks for a capital "SN" and not "sn".

ORDER BY product_id ASC sorts the final output exactly as requested.

LC. 4006. Count Valid Prefixes

You are given a binary string s.

A prefix of s is considered valid if its characters can be rearranged to form an alternating string.

Return the number of valid prefixes of s.

A string is considered alternating if no two adjacent characters are equal.



Example 1:

Input: s = "00101"

Output: 3

Explanation:

The valid prefixes are:

"0": It is already an alternating string.
"001": It can be rearranged into "010", which is an alternating string.
"00101": It can be rearranged into "01010", which is an alternating string.
Thus, the answer is 3.

Example 2:

Input: s = "101"

Output: 3

Explanation:

All prefixes of s = "101" are already alternating strings. Thus, the answer is 3.



Constraints:

1 <= s.length <= 100
s consists only of '0' and '1'

1. class Solution:
   
2.     def countValidPrefixes(self, s: str) -> int:
   
3.         count0, count1 = 0, 0
   
4.         ans = 0
   
5. 
   
6.         for ch in s:
   
7.             if ch == '0': count0 += 1
   
8.             if ch == '1': count1 += 1
   
9. 
   
10.             if abs(count0 - count1) == 1 or count0 == count1 :
    
11.                 ans += 1
    
12.         
    
13.         return ans

复制代码

唯一的优化点是把 if 判断写得更符合 Python 的极简风格：
abs(count0 - count1) == 1 or count0 == count1 其实等价于 abs(count0 - count1) <= 1

1. class Solution:
   
2.     def countValidPrefixes(self, s: str) -> int:
   
3.         count0, count1 = 0, 0
   
4.         ans = 0
   
5. 
   
6.         for ch in s:
   
7.             if ch == '0': count0 += 1
   
8.             if ch == '1': count1 += 1
   
9. 
   
10.             if abs(count0 - count1) <= 1 :
    
11.                 ans += 1
    
12.         
    
13.         return ans

复制代码

LC. 4010. Maximize Pair Strength Using GCD

You are given an integer array nums.

Choose exactly one pair of distinct indices i and j. The strength of the pair is defined as (nums[i] * nums[j]) / gcd(nums[i], nums[j])2.

Return the maximum strength over all possible pairs.



Example 1:

Input: nums = [2,3,5]

Output: 15

Explanation:

Choosing i = 1 and j = 2 gives strength (3 * 5) / gcd(3, 5)2 = 15 / 1 = 15, which is the maximum over all pairs.

Example 2:

Input: nums = [4,6,8]

Output: 12

Explanation:

Choosing i = 1 and j = 2 gives strength (6 * 8) / gcd(6, 8)2 = 48 / 4 = 12, which is the maximum over all pairs.

Example 3:

Input: nums = [3,3]

Output: 1

Explanation:

Choosing i = 0 and j = 1 gives strength (3 * 3) / gcd(3, 3)2 = 9 / 9 = 1, the maximum over all pairs.



Constraints:

2 <= nums.length <= 2000
1 <= nums[i] <= 105

这道题发现了很多基础的地方还是掌握不牢，地动山摇！

1. 辗转相除法

3 行的辗转相除法模板，受用一生
        def gcd(a, b):
            while b > 0:
                a, b = b, a % b
            return a

2， 题目明确要求：distinct indices i and j（不同的下标）。 ==== 》 正确做法：内层循环从 i + 1 开始，既保证了 $i \neq j$，又把计算量直接砍半！

3. Python 的浮点数除法 /
你使用了 (nums[i] * nums[j]) / (g * g)。在 Python 中，单斜杠 / 会返回浮点数 (float)。当数字很大时，浮点数会丢失精度。
正确做法：使用双斜杠 // 进行整数除法，题目保证能整除，这样可以原汁原味保留大整数的精度。

其实这里利用了最大公约数的性质，保证结果一定是个正整数，所以可以直接用 //

1. class Solution:
   
2.     def maxPairStrength(self, nums: list[int]) -> int:
   
3. 
   
4.         def gcd(a, b):
   
5. 
   
6.             while b > 0:
   
7.                 a, b = b, a % b
   
8.             
   
9.             return a
   
10. 
    
11.         n = len(nums)
    
12.         ans = -1
    
13.         for i in range(n):
    
14.             for j in range(i+1, n):
    
15.                 g = gcd(nums[i], nums[j])
    
16.                 ans = max(ans, (nums[i] * nums[j]) // (g * g))
    
17.         
    
18.         return ans
    
19. 
    
20.         

复制代码

LC. 4020. Elevator Requests I

1. class Solution:
   
2.     def elevatorRequests(self, n: int, requests: list[int]) -> int:
   
3.         ans = requests[0]
   
4. 
   
5.         for i in range(1, len(requests)):
   
6.             ans += abs(requests[i] - requests[i-1])
   
7. 
   
8.         return ans

复制代码

虽然你通过拆分 ans = requests[0] 处理了起点，但如果在真实的面试中，遇到更复杂的模拟题，用一个变量维护当前状态（当前位置），代码逻辑会更加统一，可读性也更强。

我们可以用一个变量 curr 来记录电梯“现在停在哪里”，然后遍历所有的请求（包括第一个）。

推荐的通用写法（面试极佳）：

1. class Solution:
   
2.     def elevatorRequests(self, n: int, requests: list[int]) -> int:
   
3.         ans = 0
   
4.         curr = 0  # 核心状态：电梯初始在 0 层
   
5.         
   
6.         for req in requests:
   
7.             # 加上从当前层到目标层的时间
   
8.             ans += abs(req - curr)
   
9.             # 更新电梯的当前位置
   
10.             curr = req
    
11.             
    
12.         return ans

复制代码

LC. 2480. Form a Chemical Bond

Table: Elements

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| symbol      | varchar |
| type        | enum    |
| electrons   | int     |
+-------------+---------+
symbol is the primary key (column with unique values) for this table.
Each row of this table contains information of one element.
type is an ENUM (category) of type ('Metal', 'Nonmetal', 'Noble')
- If type is Noble, electrons is 0.
- If type is Metal, electrons is the number of electrons that one atom of this element can give.
- If type is Nonmetal, electrons is the number of electrons that one atom of this element needs.


Two elements can form a bond if one of them is 'Metal' and the other is 'Nonmetal'.

Write a solution to find all the pairs of elements that can form a bond.

Return the result table in any order.

The result format is in the following example.



Example 1:

Input:
Elements table:
+--------+----------+-----------+
| symbol | type     | electrons |
+--------+----------+-----------+
| He     | Noble    | 0         |
| Na     | Metal    | 1         |
| Ca     | Metal    | 2         |
| La     | Metal    | 3         |
| Cl     | Nonmetal | 1         |
| O      | Nonmetal | 2         |
| N      | Nonmetal | 3         |
+--------+----------+-----------+
Output:
+-------+----------+
| metal | nonmetal |
+-------+----------+
| La    | Cl       |
| Ca    | Cl       |
| Na    | Cl       |
| La    | O        |
| Ca    | O        |
| Na    | O        |
| La    | N        |
| Ca    | N        |
| Na    | N        |
+-------+----------+
Explanation:
Metal elements are La, Ca, and Na.
Nonmeal elements are Cl, O, and N.
Each Metal element pairs with a Nonmetal element in the output table.

1. # Write your MySQL query statement below
   
2. SELECT
   
3.     m.symbol AS metal,
   
4.     n.symbol AS nonmetal
   
5. FROM
   
6.     Elements m
   
7. CROSS JOIN
   
8.     Elements n
   
9. WHERE
   
10.     m.type = 'Metal' AND
    
11.     n.type = 'Nonmetal';

复制代码

LC 2723. Add Two Promises

Given two promises promise1 and promise2, return a new promise. promise1 and promise2 will both resolve with a number. The returned promise should resolve with the sum of the two numbers.


Example 1:

Input:
promise1 = new Promise(resolve => setTimeout(() => resolve(2), 20)),
promise2 = new Promise(resolve => setTimeout(() => resolve(5), 60))
Output: 7
Explanation: The two input promises resolve with the values of 2 and 5 respectively. The returned promise should resolve with a value of 2 + 5 = 7. The time the returned promise resolves is not judged for this problem.
Example 2:

Input:
promise1 = new Promise(resolve => setTimeout(() => resolve(10), 50)),
promise2 = new Promise(resolve => setTimeout(() => resolve(-12), 30))
Output: -2
Explanation: The two input promises resolve with the values of 10 and -12 respectively. The returned promise should resolve with a value of 10 + -12 = -2.


Constraints:

promise1 and promise2 are promises that resolve with a number
/**
* @param {Promise} promise1
* @param {Promise} promise2
* @return {Promise}
*/
var addTwoPromises = async function(promise1, promise2) {
    // 并行等待两个 promise 解析，并解构获取它们的值
    const [val1, val2] = await Promise.all([promise1, promise2]);

    // 返回两个值的和
    return val1 + val2;
};

/**
* addTwoPromises(Promise.resolve(2), Promise.resolve(2))
*   .then(console.log); // 4
*/

LC. 2717. Semi-Ordered Permutation

目标：把数字 1 移到最左边（索引 0），把数字 n 移到最右边（索引 n-1）。

操作：只能交换相邻元素。

核心直觉：

在数组中，通过相邻交换把一个元素从索引 A 移到索引 B，需要的最少步数就是它们距离的绝对值 |A - B|。

因此，移动 1 需要的步数是 ind1 - 0 = ind1。

移动 n 需要的步数是 (n - 1) - ind2。

唯一的坑（交叉重叠）：如果 1 最初在 n 的右边（即 ind1 > ind2），那么在把 1 往左移、把 n 往右移的过程中，它们必然会相遇并发生一次交换。这一次交换同时帮助了 1 往左走了一步，也帮助了 n 往右走了一步。所以总步数可以“白嫖”一步，需要减 1。

我的解法

1. class Solution:
   
2.     def semiOrderedPermutation(self, nums: List[int]) -> int:
   
3.         n = len(nums)
   
4.         ind1 = nums.index(1)
   
5.         ind2 = nums.index(n)
   
6.         if ind1 < ind2:
   
7.             return ind1 + n - 1 - ind2
   
8.         else:
   
9.             return ind1 + n - 2 - ind2
   
10.         

复制代码

优化，

Index 需要两次遍历 List，其实可以一次遍历找出 ind1 和 ind2.

1. class Solution:
   
2.     def semiOrderedPermutation(self, nums: List[int]) -> int:
   
3.         n = len(nums)
   
4.         ind1 = ind2 = -1
   
5.         
   
6.         # 一次遍历，同时找到 1 和 n 的索引
   
7.         for i, num in enumerate(nums):
   
8.             if num == 1:
   
9.                 ind1 = i
   
10.             elif num == n:
    
11.                 ind2 = i
    
12.                
    
13.         # 逻辑合并：利用布尔值转换成整型的特性 (True 为 1，False 为 0)
    
14.         # 这一招在 Python 面试里很显老练，但你原本的 if-else 写法也可读性极高。
    
15.         return ind1 + (n - 1 - ind2) - (ind1 > ind2)

复制代码

LC. 2716. Minimize String Length

Given a string s, you have two types of operation:

Choose an index i in the string, and let c be the character in position i. Delete the closest occurrence of c to the left of i (if exists).
Choose an index i in the string, and let c be the character in position i. Delete the closest occurrence of c to the right of i (if exists).
Your task is to minimize the length of s by performing the above operations zero or more times.

Return an integer denoting the length of the minimized string.



Example 1:

Input: s = "aaabc"

Output: 3

Explanation:

Operation 2: we choose i = 1 so c is 'a', then we remove s[2] as it is closest 'a' character to the right of s[1].
s becomes "aabc" after this.
Operation 1: we choose i = 1 so c is 'a', then we remove s[0] as it is closest 'a' character to the left of s[1].
s becomes "abc" after this.
Example 2:

Input: s = "cbbd"

Output: 3

Explanation:

Operation 1: we choose i = 2 so c is 'b', then we remove s[1] as it is closest 'b' character to the left of s[1].
s becomes "cbd" after this.
Example 3:

Input: s = "baadccab"

Output: 4

Explanation:

Operation 1: we choose i = 6 so c is 'a', then we remove s[2] as it is closest 'a' character to the left of s[6].
s becomes "badccab" after this.
Operation 2: we choose i = 0 so c is 'b', then we remove s[6] as it is closest 'b' character to the right of s[0].
s becomes "badcca" fter this.
Operation 2: we choose i = 3 so c is 'c', then we remove s[4] as it is closest 'c' character to the right of s[3].
s becomes "badca" after this.
Operation 1: we choose i = 4 so c is 'a', then we remove s[1] as it is closest 'a' character to the left of s[4].
s becomes "bdca" after this.


Constraints:

1 <= s.length <= 100
s contains only lowercase English letters

披着“字符串操作”外衣的脑筋急转弯（Brain Teaser）

1. class Solution:
   
2.     def minimizedStringLength(self, s: str) -> int:
   
3.         return len(set([ch for ch in s]))

复制代码

[ch for ch in s] 会在内存中先创建一个完整的列表 (List)，然后再把这个列表扔给 set() 去重。这在字符串很长的时候，会产生不必要的内存开销。

其实，Python 的 set() 原生就支持接收任何可迭代对象（Iterable），包括字符串。所以你可以直接把字符串丢给它：

优化后的极简写法：

1. class Solution:
   
2.     def minimizedStringLength(self, s: str) -> int:
   
3.         return len(set(s))

复制代码

LC. 2715. Timeout Cancellation

Given a function fn, an array of arguments args, and a timeout t in milliseconds, return a cancel function cancelFn.

After a delay of cancelTimeMs, the returned cancel function cancelFn will be invoked.

setTimeout(cancelFn, cancelTimeMs)
Initially, the execution of the function fn should be delayed by t milliseconds.

If, before the delay of t milliseconds, the function cancelFn is invoked, it should cancel the delayed execution of fn. Otherwise, if cancelFn is not invoked within the specified delay t, fn should be executed with the provided args as arguments.



Example 1:

Input: fn = (x) => x * 5, args = [2], t = 20
Output: [{"time": 20, "returned": 10}]
Explanation:
const cancelTimeMs = 50;
const cancelFn = cancellable((x) => x * 5, [2], 20);
setTimeout(cancelFn, cancelTimeMs);

The cancellation was scheduled to occur after a delay of cancelTimeMs (50ms), which happened after the execution of fn(2) at 20ms.
Example 2:

Input: fn = (x) => x**2, args = [2], t = 100
Output: []
Explanation:
const cancelTimeMs = 50;
const cancelFn = cancellable((x) => x**2, [2], 100);
setTimeout(cancelFn, cancelTimeMs);

The cancellation was scheduled to occur after a delay of cancelTimeMs (50ms), which happened before the execution of fn(2) at 100ms, resulting in fn(2) never being called.
Example 3:

Input: fn = (x1, x2) => x1 * x2, args = [2,4], t = 30
Output: [{"time": 30, "returned": 8}]
Explanation:
const cancelTimeMs = 100;
const cancelFn = cancellable((x1, x2) => x1 * x2, [2,4], 30);
setTimeout(cancelFn, cancelTimeMs);

The cancellation was scheduled to occur after a delay of cancelTimeMs (100ms), which happened after the execution of fn(2,4) at 30ms.


Constraints:

fn is a function
args is a valid JSON array
1 <= args.length <= 10
20 <= t <= 1000
10 <= cancelTimeMs <= 1000

1. type JSONValue = null | boolean | number | string | JSONValue[] | { [key: string]: JSONValue };
   
2. type Fn = (...args: JSONValue[]) => void;
   
3. 
   
4. function cancellable(fn: Fn, args: JSONValue[], t: number): Function {
   
5.     // Schedule the function to run after 't' milliseconds
   
6.     const timerId = setTimeout(() => {
   
7.         fn(...args);
   
8.     }, t);
   
9. 
   
10.     // Return a function that cancels the scheduled execution
    
11.     return function cancelFn() {
    
12.         clearTimeout(timerId);
    
13.     };
    
14. }

复制代码