刷题记录帖子

LC. 3550. Smallest Index With Digit Sum Equal to Index

You are given an integer array nums.

Return the smallest index i such that the sum of the digits of nums[i] is equal to i.

If no such index exists, return -1.



Example 1:

Input: nums = [1,3,2]

Output: 2

Explanation:

For nums[2] = 2, the sum of digits is 2, which is equal to index i = 2. Thus, the output is 2.
Example 2:

Input: nums = [1,10,11]

Output: 1

Explanation:

For nums[1] = 10, the sum of digits is 1 + 0 = 1, which is equal to index i = 1.
For nums[2] = 11, the sum of digits is 1 + 1 = 2, which is equal to index i = 2.
Since index 1 is the smallest, the output is 1.
Example 3:

Input: nums = [1,2,3]

Output: -1

Explanation:

Since no index satisfies the condition, the output is -1.


Constraints:

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

很有意思的题目，发现 Leetcode 老题目确实比新题目有意思。
情况 A（全是正数）：既然全是正数，那么最大的三个数 nums[-1] * nums[-2] * nums[-3] 一定比最小的三个数乘积更大。

情况 B（全是负数）：三个负数相乘结果是负数。在负数世界里，绝对值越小的值越大（比如 $-6 > -720$）。因此，最靠近 0 的三个最大负数 nums[-1] * nums[-2] * nums[-3] 一定大于最靠左的三个最小负数。

情况 C（有正有负）：如果一正两负，或者两正一负，nums[0] * nums[1] * nums[-1]（两个最小负数 $\times$ 最大正数）一定比三个靠左的数相乘更大或更优。

1. class Solution:
   
2.     def maximumProduct(self, nums: List[int]) -> int:
   
3.         nums.sort()
   
4.         # 结果只可能在两组候选人中产生：
   
5.         # 1. 最大的三个数相乘
   
6.         # 2. 最小的两个数（可能为大负数）* 最大的一个数
   
7.         return max(nums[-1] * nums[-2] * nums[-3], nums[0] * nums[1] * nums[-1])

复制代码

LC. 3545. Minimum Deletions for At Most K Distinct Characters

贪心算法，统计频率，删掉最少的频率即可。

不过我写的时候不太顺手，这里需要考虑不少数据结构到底是怎么样的，做到心中有数。

1. class Solution:
   
2.     def minDeletion(self, s: str, k: int) -> int:
   
3.         freq = Counter(s)
   
4. 
   
5.         freq_list = [freq[key] for key in freq]
   
6.         freq_list.sort(reverse = True)
   
7. 
   
8.         return sum(freq_list[f] for f in range(k, len(freq_list)))
   

复制代码

不过代码可以简化

比如，freq.values() 可以直接取出字典所有的 values

1. from collections import Counter
   
2. 
   
3. class Solution:
   
4.     def minDeletion(self, s: str, k: int) -> int:
   
5.         # 1. 统计每个字符的出现频率
   
6.         freq = Counter(s)
   
7.         
   
8.         # 2. 将频率从大到小排序
   
9.         freq_list = sorted(freq.values(), reverse=True)
   
10.         
    
11.         # 3. 保留前 k 个高频字符，其余低频字符全部删光
    
12.         return sum(freq_list[k:])

复制代码

LC. 1481. Least Number of Unique Integers after K Removals
Solved
Medium
Topics
conpanies icon
Companies
Hint
Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.



Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.
Example 2:
Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.


Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
0 <= k <= arr.length

和上一题类似，只不过逻辑反过来，算最少的 freq 这样保留尽可能多的 freq 的相同 element

1. class Solution:
   
2.     def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
   
3.         freq = Counter(arr)
   
4.         freq_values = sorted(freq.values())
   
5.         n = len(freq_values)
   
6.         tmp = 0
   
7.         ans = 0
   
8. 
   
9.         for v in freq_values:
   
10.             tmp += v
    
11.             if tmp <= k:
    
12.                 ans += 1
    
13. 
    
14.             if tmp >= k: break
    
15. 
    
16.         return n - ans            
    
17. 
    

复制代码

不过我的代码可以精简

1. from collections import Counter
   
2. from typing import List
   
3. 
   
4. class Solution:
   
5.     def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
   
6.         # 1. 统计每个数字的出现频率
   
7.         freq = Counter(arr)
   
8.         
   
9.         # 2. 将频率从小到大排序（优先处理出现次数少的）
   
10.         freq_values = sorted(freq.values())
    
11.         
    
12.         # 3. 贪心消耗 k
    
13.         removed_types = 0
    
14.         for count in freq_values:
    
15.             if k >= count:
    
16.                 k -= count          # 消耗 k 删光当前数字
    
17.                 removed_types += 1  # 成功消灭一个种类
    
18.             else:
    
19.                 break               # k 不够删光当前数字了，直接终止
    
20.                
    
21.         # 4. 剩余种类 = 总种类 - 已消灭种类
    
22.         return len(freq_values) - removed_types

复制代码

这个统计代码删除类的方式比我的简洁明了

1. removed_types = 0
   
2.         for count in freq_values:
   
3.             if k >= count:
   
4.                 k -= count          # 消耗 k 删光当前数字
   
5.                 removed_types += 1  # 成功消灭一个种类
   
6.             else:
   
7.                 break               # k 不够删光当前数字了，直接终止

复制代码

LC. 3541. Find Most Frequent Vowel and Consonant

1. class Solution:
   
2.     def maxFreqSum(self, s: str) -> int:
   
3.         vowel_dict = defaultdict(int)
   
4.         conso_dict = defaultdict(int)
   
5.         max_v, max_c = 0, 0
   
6. 
   
7. 
   
8.         for ch in s:
   
9.             if ch in ('a', 'e', 'i', 'o', 'u'):
   
10.                 vowel_dict[ch] += 1
    
11.                 max_v = max(max_v, vowel_dict[ch])
    
12.             else:
    
13.                 conso_dict[ch] += 1
    
14.                 max_c = max(max_c, conso_dict[ch])
    
15. 
    
16.         return max_v + max_c        
    

复制代码

优化下另外一种解法，

在 Python 刷题和实际开发中，遇到“词频统计”需求，我们最常用的是 collections.Counter。面试中如果你想用更 Pythonic 的方式，可以先全局统计，再分流处理：

1. from collections import Counter
   
2. 
   
3. class Solution:
   
4.     def maxFreqSum(self, s: str) -> int:
   
5.         counts = Counter(s)  # 一次性统计所有字符的频次
   
6.         vowels = set("aeiou")
   
7.         
   
8.         max_v = 0
   
9.         max_c = 0
   
10.         
    
11.         # 遍历统计完的字典，字典大小最多 26，速度极快
    
12.         for ch, freq in counts.items():
    
13.             if ch in vowels:
    
14.                 max_v = max(max_v, freq)
    
15.             else:
    
16.                 max_c = max(max_c, freq)
    
17.                
    
18.         return max_v + max_c

复制代码

LC. 3536. Maximum Product of Two Digits
Solved
Easy
Topics
conpanies icon
Companies
Hint
You are given a positive integer n.

Return the maximum product of any two digits in n.

Note: You may use the same digit twice if it appears more than once in n.



Example 1:

Input: n = 31

Output: 3

Explanation:

The digits of n are [3, 1].
The possible products of any two digits are: 3 * 1 = 3.
The maximum product is 3.
Example 2:

Input: n = 22

Output: 4

Explanation:

The digits of n are [2, 2].
The possible products of any two digits are: 2 * 2 = 4.
The maximum product is 4.
Example 3:

Input: n = 124

Output: 8

Explanation:

The digits of n are [1, 2, 4].
The possible products of any two digits are: 1 * 2 = 2, 1 * 4 = 4, 2 * 4 = 8.
The maximum product is 8.


Constraints:

10 <= n <= 109

我的解法

1. class Solution:
   
2.     def maxProduct(self, n: int) -> int:
   
3.         slist = [int(ch) for ch in str(n)]
   
4.         slist.sort()
   
5.         return slist[-1] * slist[-2]

复制代码

优化，可以动态维护 first， second 变量，

1. class Solution:
   
2. 
   
3.     def maxProduct(self, n: int) -> int:
   
4.         first, second = 0, 0
   
5. 
   
6.         for ch in str(n):
   
7.             digit = int(ch)
   
8.             if digit > first:
   
9.                 # 遇到比最大值还大的，把旧的最大值移位给次大值
   
10.                 second = first
    
11.                 first = digit
    
12.             elif digit > second:
    
13.                 # 介于最大值和次大值之间
    
14.                 second = digit
    
15. 
    
16.         return first * second

复制代码

或者不能用 string 的时候手动写整除 10， 和取余数。

1. class Solution:
   
2. 
   
3.     def maxProduct(self, n: int) -> int:
   
4.         first, second = 0, 0
   
5. 
   
6.         while n > 0:
   
7.             digit = n % 10  # 取最右边一位
   
8.             n //= 10  # 砍掉最右边一位
   
9. 
   
10.             if digit > first:
    
11.                 second = first
    
12.                 first = digit
    
13.             elif digit > second:
    
14.                 second = digit
    
15. 
    
16.         return first * second

复制代码

LC. 3516. Find Closest Person
Solved
Easy
Topics
conpanies icon
Companies
Hint
You are given three integers x, y, and z, representing the positions of three people on a number line:

x is the position of Person 1.
y is the position of Person 2.
z is the position of Person 3, who does not move.
Both Person 1 and Person 2 move toward Person 3 at the same speed.

Determine which person reaches Person 3 first:

Return 1 if Person 1 arrives first.
Return 2 if Person 2 arrives first.
Return 0 if both arrive at the same time.
Return the result accordingly.



Example 1:

Input: x = 2, y = 7, z = 4

Output: 1

Explanation:

Person 1 is at position 2 and can reach Person 3 (at position 4) in 2 steps.
Person 2 is at position 7 and can reach Person 3 in 3 steps.
Since Person 1 reaches Person 3 first, the output is 1.

Example 2:

Input: x = 2, y = 5, z = 6

Output: 2

Explanation:

Person 1 is at position 2 and can reach Person 3 (at position 6) in 4 steps.
Person 2 is at position 5 and can reach Person 3 in 1 step.
Since Person 2 reaches Person 3 first, the output is 2.

Example 3:

Input: x = 1, y = 5, z = 3

Output: 0

Explanation:

Person 1 is at position 1 and can reach Person 3 (at position 3) in 2 steps.
Person 2 is at position 5 and can reach Person 3 in 2 steps.
Since both Person 1 and Person 2 reach Person 3 at the same time, the output is 0.



Constraints:

1 <= x, y, z <= 100

我的解法

1. class Solution:
   
2.     def findClosest(self, x: int, y: int, z: int) -> int:
   
3.         s1 = abs(x - z)
   
4.         s2 = abs(y - z)
   
5. 
   
6.         if s1 < s2:
   
7.             return 1
   
8.         elif s1 > s2:
   
9.             return 2
   
10.         else:
    
11.             return 0

复制代码

变体写法：用减法判定（数学等价）
有的程序员喜欢用两距离之差来做条件判断, 不算优化，但是是一种写法。

1. class Solution:
   
2.     def findClosest(self, x: int, y: int, z: int) -> int:
   
3.         diff = abs(x - z) - abs(y - z)
   
4.         if diff < 0:
   
5.             return 1
   
6.         elif diff > 0:
   
7.             return 2
   
8.         return 0

复制代码

LC. 3512. Minimum Operations to Make Array Sum Divisible by K
Solved
Easy
Topics
conpanies icon
Companies
Hint
You are given an integer array nums and an integer k. You can perform the following operation any number of times:

Select an index i and replace nums[i] with nums[i] - 1.
Return the minimum number of operations required to make the sum of the array divisible by k.

Example 1:

Input: nums = [3,9,7], k = 5

Output: 4

Explanation:

Perform 4 operations on nums[1] = 9. Now, nums = [3, 5, 7].
The sum is 15, which is divisible by 5.
Example 2:

Input: nums = [4,1,3], k = 4

Output: 0

Explanation:

The sum is 8, which is already divisible by 4. Hence, no operations are needed.
Example 3:

Input: nums = [3,2], k = 6

Output: 5

Explanation:

Perform 3 operations on nums[0] = 3 and 2 operations on nums[1] = 2. Now, nums = [0, 0].
The sum is 0, which is divisible by 6.

Constraints:

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

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        s = sum(nums)
        n = s // k

        return s - n * k        

优化， 其实这个就是取模 % 的定义公式，

s - (s // k) * k

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        return sum(nums) % k

LC. 4000. Largest Integer With Given Digit Sum

挺有意思一道题目, 贪心（Greedy），需要考虑边界 edge case，然后其实就是根据 digital sum，填 9 和小 9 的数直接到首位，然后长度不够填 0.

题目目标：构造一个最多包含 n 位数，且各位数字之和恰好为 s 的最大整数。

贪心策略：
要让一个数字最大，我们需要满足两个条件：

位数尽可能多：题目说“最多 n 位”，那我们就把它拉满到 n 位。位数越长，数字越大（比如 90 > 9）。

高位尽可能大：从最高位（最左边）开始，尽量填入最大的数字 9。

1. class Solution:
   
2.     def largestInteger(self, n: int, s: int) -> int:
   
3.         if s == 0: return 0
   
4.         if 9 * n < s: return -1
   
5.         ans = []
   
6.         
   
7.         while s > 0:
   
8.             if s >= 9:
   
9.                 ans.append('9')
   
10.                 s -= 9
    
11.             else:
    
12.                 ans.append(str(s))
    
13.                 s = 0
    
14.         
    
15.         while len(ans) < n:
    
16.             ans.append('0')
    
17.         
    
18.         return int("".join(ans))
    
19.         
    

复制代码

在 Python 中，我们可以利用数学运算（整除和取余）以及字符串乘法，把代码写得更加优雅和紧凑，这在面试中能展现出你对语言特性的熟练度。

1. class Solution:
   
2.     def largestInteger(self, n: int, s: int) -> int:
   
3.         # 特判：如果 s 为 0，直接返回 0
   
4.         if s == 0:
   
5.             return 0
   
6.         
   
7.         # 如果 s 超过了 n 位数能表示的最大和，无解
   
8.         if s > 9 * n:
   
9.             return -1
   
10.         
    
11.         # 计算需要多少个 '9'，以及最后一位非 '9' 的数字是什么
    
12.         # 例如 s = 20, 20 // 9 = 2 个 '9', 20 % 9 = 2
    
13.         count_9 = s // 9
    
14.         remainder = s % 9
    
15.         
    
16.         # 拼接字符串：先放满 '9'
    
17.         ans = "9" * count_9
    
18.         
    
19.         # 如果有余数，拼接到后面
    
20.         if remainder > 0:
    
21.             ans += str(remainder)
    
22.             
    
23.         # 剩下的位数，全部用 '0' 补齐
    
24.         ans += "0" * (n - len(ans))
    
25.         
    
26.         return int(ans)

复制代码

LC. 3502. Minimum Cost to Reach Every Position

You are given an integer array cost of size n. You are currently at position n (at the end of the line) in a line of n + 1 people (numbered from 0 to n).

You wish to move forward in the line, but each person in front of you charges a specific amount to swap places. The cost to swap with person i is given by cost[i].

You are allowed to swap places with people as follows:

If they are in front of you, you must pay them cost[i] to swap with them.
If they are behind you, they can swap with you for free.
Return an array answer of size n, where answer[i] is the minimum total cost to reach each position i in the line.



Example 1:

Input: cost = [5,3,4,1,3,2]

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

Explanation:

We can get to each position in the following way:

i = 0. We can swap with person 0 for a cost of 5.
i = 1. We can swap with person 1 for a cost of 3.
i = 2. We can swap with person 1 for a cost of 3, then swap with person 2 for free.
i = 3. We can swap with person 3 for a cost of 1.
i = 4. We can swap with person 3 for a cost of 1, then swap with person 4 for free.
i = 5. We can swap with person 3 for a cost of 1, then swap with person 5 for free.
Example 2:

Input: cost = [1,2,4,6,7]

Output: [1,1,1,1,1]

Explanation:

We can swap with person 0 for a cost of 1, then we will be able to reach any position i for free.



Constraints:

1 <= n == cost.length <= 100
1 <= cost[i] <= 100

核心本质（破局点）：
假设你想去位置 i，你有两种选择：

直接花钱：直接支付 cost[i] 和 i 交换。

“白嫖”策略（曲线救国）：你可以先花钱和位置更靠前的某个人 j（即 j < i）交换。交换完之后，你在位置 j，此时目标位置 i 就在你的后面了！根据规则，和后面的人换是免费的。所以，总共只需花费 cost[j]。

结论：到达位置 i 的最小成本，其实就是它前面所有人的成本以及它自己成本里的最小值。
数学表达：ans[i] = min(cost[0], cost[1], ..., cost[i])。

这也就是所谓的 前缀最小值 (Prefix Minimum) 模型。你的代码完美契合了这个模型！

1. class Solution:
   
2.     def minCosts(self, cost: List[int]) -> List[int]:
   
3.         leftSmallest = float('inf')
   
4. 
   
5.         ans = []
   
6. 
   
7.         for c in cost:
   
8.             if c >= leftSmallest:
   
9.                 ans.append(leftSmallest)
   
10.             else:
    
11.                 ans.append(c)
    
12.                 leftSmallest = c
    
13. 
    
14.         return ans

复制代码

一个简单的优化，用 min 来取代 if-else

1. class Solution:
   
2.     def minCosts(self, cost: List[int]) -> List[int]:
   
3.         min_cost = float('inf') # 维护当前遇到的最小代价
   
4.         ans = []
   
5.         
   
6.         for c in cost:
   
7.             # 更新当前的最小代价
   
8.             min_cost = min(min_cost, c)
   
9.             ans.append(min_cost)
   
10.             
    
11.         return ans

复制代码

LC. 3498. Reverse Degree of a String

简单题直接做

1. class Solution:
   
2.     def reverseDegree(self, s: str) -> int:
   
3.         ans = 0
   
4. 
   
5.         for i in range(len(s)):
   
6.             ans += ( i + 1) * (ord('z') - ord(s[i]) + 1)
   
7.         
   
8.         return ans
   
9.         

复制代码