刷题记录帖子

LC 175. Combine Two Tables

1. # Write your MySQL query statement below
   
2. select
   
3.     p.firstName,
   
4.     p.lastName,
   
5.     a.city,
   
6.     a.state
   
7. from Person p
   
8. left join Address a
   
9. on a.personId = p.personId
   

复制代码

LC. 2669. Count Artist Occurrences On Spotify Ranking List

Table: Spotify

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| id          | int     |
| track_name  | varchar |
| artist      | varchar |
+-------------+---------+
id is the primary key (column with unique values) for this table.
Each row contains an id, track_name, and artist.
Write a solution to find how many times each artist appeared on the Spotify ranking list.

Return the result table having the artist's name along with the corresponding number of occurrences ordered by occurrence count in descending order. If the occurrences are equal, then it’s ordered by the artist’s name in ascending order.

The result format is in the following example​​​​​.



Example 1:

Input:
Spotify table:
+---------+--------------------+------------+
| id      | track_name         | artist     |  
+---------+--------------------+------------+
| 303651  | Heart Won't Forget | Sia        |
| 1046089 | Shape of you       | Ed Sheeran |
| 33445   | I'm the one        | DJ Khalid  |
| 811266  | Young Dumb & Broke | DJ Khalid  |
| 505727  | Happier            | Ed Sheeran |
+---------+--------------------+------------+
Output:
+------------+-------------+
| artist     | occurrences |
+------------+-------------+
| DJ Khalid  | 2           |
| Ed Sheeran | 2           |
| Sia        | 1           |
+------------+-------------+

Explanation: The count of occurrences is listed in descending order under the column name "occurrences". If the number of occurrences is the same, the artist's names are sorted in ascending order.

1. # Write your MySQL query statement below
   
2. select artist, count(id) AS occurrences
   
3. from Spotify
   
4. group by artist
   
5. order by occurrences DESC, artist

复制代码

LC. 2943. Maximize Area of Square Hole in Grid

1. class Solution:
   
2.     def maximizeSquareHoleArea(
   
3.         self, n: int, m: int, hBars: List[int], vBars: List[int]
   
4.     ) -> int:
   
5.         hBars.sort()
   
6.         vBars.sort()
   
7.         hmax, vmax = 1, 1
   
8.         hcur, vcur = 1, 1
   
9.         for i in range(1, len(hBars)):
   
10.             if hBars[i] == hBars[i - 1] + 1:
    
11.                 hcur += 1
    
12.             else:
    
13.                 hcur = 1
    
14.             hmax = max(hmax, hcur)
    
15.         for i in range(1, len(vBars)):
    
16.             if vBars[i] == vBars[i - 1] + 1:
    
17.                 vcur += 1
    
18.             else:
    
19.                 vcur = 1
    
20.             vmax = max(vmax, vcur)
    
21.         side = min(hmax, vmax) + 1
    
22.         return side * side

复制代码

LC 228. Summary Ranges
不难就是比较繁琐，需要 Dry-run 来 debug。一定切记切记！

1. class Solution:
   
2.     def summaryRanges(self, nums: List[int]) -> List[str]:
   
3.         res = []
   
4.         if len(nums) == 0: return []
   
5.         if len(nums) == 1: return [str(nums[0])]
   
6.         if len(nums) == 2:
   
7.             if nums[0]+1 == nums[1]: return [str(nums[0])+"->"+str(nums[1])]
   
8.             else: return [str(nums[0]), str(nums[1])]
   
9. 
   
10.         i = 0
    
11.         while i <= len(nums) - 1:
    
12.             start = i
    
13.             while i < len(nums) -1 and nums[i]+1 == nums[i+1]:
    
14.                 i += 1
    
15.             if i == start:
    
16.                 # signle index
    
17.                 res.append(str(nums[start]))
    
18.                 i += 1
    
19.             else:
    
20.                 res.append(str(nums[start])+"->"+str(nums[i]))
    
21.                 i += 1
    
22.         return res
    
23.                
    
24. 
    
25. 
    

复制代码

LC 163. Missing Ranges
Solved
Easy
Topics
conpanies icon
Companies
You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are within the inclusive range.

A number x is considered missing if x is in the range [lower, upper] and x is not in nums.

Return the shortest sorted list of ranges that exactly covers all the missing numbers. That is, no element of nums is included in any of the ranges, and each missing number is covered by one of the ranges.





Example 1:

Input: nums = [0,1,3,50,75], lower = 0, upper = 99
Output: [[2,2],[4,49],[51,74],[76,99]]
Explanation: The ranges are:
[2,2]
[4,49]
[51,74]
[76,99]
Example 2:

Input: nums = [-1], lower = -1, upper = -1
Output: []
Explanation: There are no missing ranges since there are no missing numbers.


Constraints:

-109 <= lower <= upper <= 109
0 <= nums.length <= 100
lower <= nums[i] <= upper
All the values of nums are unique.

其实这题目很有意思，考察了，你需要抽象出一个 函数 addRange，如果抽象出 addRange，后面的答案就很容易。

这道题目虽然是 easy 但是是很哈的锻炼思维的一种题目。

简单高效的解决问题。

不然你需要写一大堆边界条件。

同时，一个简化是，把 upper 和 lower 当成两个数，插入数组其实就可以直接简化code 了。

1. class Solution:
   
2.     def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[List[int]]:
   
3. 
   
4.         result = []
   
5.         prev = lower - 1
   
6.         
   
7.         for curr in nums + [upper + 1]:
   
8.             if curr - prev >= 2:
   
9.                 result.append([prev + 1, curr - 1])
   
10.             prev = curr
    
11.         
    
12.         return result

复制代码

1. class Solution:
   
2.     def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[List[int]]:
   
3. 
   
4.         result = []
   
5.         
   
6.         # 辅助函数：添加缺失范围
   
7.         def addRange(start, end):
   
8.             if start <= end:
   
9.                 result.append([start, end])
   
10.         
    
11.         # 1. 处理 lower 到第一个数之前
    
12.         if not nums:
    
13.             addRange(lower, upper)
    
14.             return result
    
15.         
    
16.         # lower 到 nums[0] 之间的缺失
    
17.         addRange(lower, nums[0] - 1)
    
18.         
    
19.         # 2. 处理相邻元素之间的缺失
    
20.         for i in range(1, len(nums)):
    
21.             addRange(nums[i-1] + 1, nums[i] - 1)
    
22.         
    
23.         # 3. 处理最后一个数到 upper
    
24.         addRange(nums[-1] + 1, upper)
    
25.         
    
26.         return result
    
27. 
    
28.         

复制代码

LC 57 Insert Intervals 和 LC 56. Merge Intervals 对照起来看

1. class Solution:

复制代码

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:

        intervals = sorted(intervals, key = lambda x: (x[0]))

        merged = []

        for interval in intervals:
            if not merged or merged[-1][1] < interval[0]:
                # process empty merged and non-overlapping cases
                merged.append(interval)
            else:
                merged[-1][1] = max(merged[-1][1], interval[1])
        return merged

LC 57. Insert Interval

三段处理：
1. 左边不重叠 → 直接添加
2. 中间重叠 → 合并成一个
3. 右边不重叠 → 直接添加

1. class Solution:
   
2.     def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
   
3.         result = []
   
4.         i = 0
   
5.         n = len(intervals)
   
6.         
   
7.         # 阶段1：添加所有在 newInterval 左边的区间
   
8.         while i < n and intervals[i][1] < newInterval[0]:
   
9.             result.append(intervals[i])
   
10.             i += 1
    
11.         
    
12.         # 阶段2：合并所有与 newInterval 重叠的区间
    
13.         while i < n and intervals[i][0] <= newInterval[1]:
    
14.             # 更新 newInterval 为合并后的区间
    
15.             newInterval[0] = min(newInterval[0], intervals[i][0])
    
16.             newInterval[1] = max(newInterval[1], intervals[i][1])
    
17.             i += 1
    
18.         result.append(newInterval)
    
19.         
    
20.         # 阶段3：添加所有在 newInterval 右边的区间
    
21.         while i < n:
    
22.             result.append(intervals[i])
    
23.             i += 1
    
24.         
    
25.         return result

复制代码

LC 135. Candy

🎯 一句话总结
两次贪心遍历：左→右处理左侧约束，右→左处理右侧约束并取max，保证每个孩子比相邻评分低的多糖且总数最少。

🔑 核心要点
1. 为什么需要两次遍历？
约束是双向的：
- 评分高要比左边的孩子糖多
- 评分高要比右边的孩子糖多

一次遍历只能处理一个方向
两次遍历分别处理，取max同时满足

1. class Solution:
   
2.     def candy(self, ratings: List[int]) -> int:
   
3.         n = len(ratings)
   
4.         candies = [1] * n  # 每人至少1颗
   
5.         
   
6.         # 从左往右：保证比左边rating高的孩子糖更多
   
7.         for i in range(1, n):
   
8.             if ratings[i] > ratings[i-1]:
   
9.                 candies[i] = candies[i-1] + 1
   
10.         
    
11.         # 从右往左：保证比右边rating高的孩子糖更多
    
12.         # 用max保证同时满足左右约束
    
13.         for i in range(n-2, -1, -1):
    
14.             if ratings[i] > ratings[i+1]:
    
15.                 candies[i] = max(candies[i], candies[i+1] + 1)
    
16.         
    
17.         return sum(candies)

复制代码

LC. 1653. Minimum Deletions to Make String Balanced

经典的题目，这道题目最好的 dp 但是你用 stack 也是可以做的。甚至我可以说，用了 stack 其实更加程序员的思维，你通过一个数据结构轻松的解决了一个复杂的问题。

方法1：Stack 方法🎯 核心思想不平衡的根源 = "ba"模式（b在a前面）
解决方案 = 遇到"ba"就消除
消除次数 = 最少删除数

1. class Solution:
   
2.     def minimumDeletions(self, s: str) -> int:
   
3.         stack = []
   
4.         delete_count = 0
   
5.         
   
6.         for char in s:
   
7.             # 检查是否形成"ba"配对
   
8.             if stack and stack[-1] == 'b' and char == 'a':
   
9.                 stack.pop()  # 删除'b'
   
10.                 delete_count += 1  # 'a'也被消除
    
11.             else:
    
12.                 stack.append(char)
    
13.         
    
14.         return delete_count

复制代码

### 🔑 关键理解

1. 栈维护"已处理的平衡部分"

2. 遇到字符：
   - 能与栈顶配对成"ba" → 消除（两个都删）
   - 不能配对 → 入栈

3. 为什么正确？
   每次消除"ba"都是局部最优
   → 累积起来就是全局最优（贪心）
```

### ⚠️ 注意事项

✅ 检查栈是否为空：if stack and ...
✅ 同时检查栈顶和当前字符
✅ 弹出后delete_count++，当前'a'不入栈

DP 方法（优化版）

### 🎯 核心思想

DP状态定义：
min_deletions = 前面已处理字符的最少删除数
b_count = 前面'b'的数量

关键决策（遇到'a'时）：
方案1：删除这个'a' → min_deletions + 1
方案2：删除前面所有'b' → b_count
取最小值

1. class Solution:
   
2.     def minimumDeletions(self, s: str) -> int:
   
3.         min_deletions = 0  # 当前最少删除数
   
4.         b_count = 0        # 前面'b'的数量
   
5.         
   
6.         for char in s:
   
7.             if char == 'b':
   
8.                 b_count += 1
   
9.             else:  # char == 'a'
   
10.                 # 删除这个'a' vs 删除前面所有'b'
    
11.                 min_deletions = min(min_deletions + 1, b_count)
    
12.         
    
13.         return min_deletions

复制代码

🔑 关键理解

1. 状态转移方程：
   遇到'b': b_count++（只记录，不改变删除数）
   遇到'a': min_deletions = min(min_deletions+1, b_count)

2. 两种策略：
   删a：保持前面的平衡，代价+1
   删b：保留这个'a'，删除前面所有'b'

3. 为什么正确？
   每一步都选择局部最优
   → 保证全局最优（DP性质）

### ⚠️ 注意事项

✅ 遇到'b'只增加计数，不更新min_deletions
✅ 遇到'a'才做决策（两种方案取min）
✅ 只需两个变量，空间O(1)

不优化，使用 dp 数组的解法如下
class Solution:
    def minimumDeletions(self, s: str) -> int:
        n = len(s)
        dp = [0] * (n + 1)  # dp[i] 表示前i个字符的最少删除数
        b_count = 0         # 前面'b'的数量

        for i in range(n):
            if s[i] == 'b':
                # 遇到'b'：不影响平衡
                dp[i + 1] = dp[i]
                b_count += 1
            else:  # s[i] == 'a'
                # 遇到'a'：删除这个'a' vs 删除前面所有'b'
                dp[i + 1] = min(dp[i] + 1, b_count)

        return dp[n]

1. class Solution:

复制代码

LC

虽然前几天做过这道题目了，知道是求高度的同时做判断，但是写代码的时候还是卡了一下。还是要继续练习，熟能生巧。

平衡条件 ：
左子树平衡
                计算左子树高度，如果 == -1，左子树不平衡，提前终止；否则返回左子树高度
右子树平衡
                类似左子树，检查是不是平衡，不平衡提前终止；否则返回右子树高度
左右子树差值不超过 1
                判断左右高度差是不是 < 1；> 1，返回 -1； <1， 返回当前树高 max(left, right)  + 1

1. # Definition for a binary tree node.
   
2. # class TreeNode:
   
3. #     def __init__(self, val=0, left=None, right=None):
   
4. #         self.val = val
   
5. #         self.left = left
   
6. #         self.right = right
   
7. class Solution:
   
8.     def isBalanced(self, root: Optional[TreeNode]) -> bool:
   
9.         if not root: return True
   
10. 
    
11.         def getHeightAndBalanced(node):
    
12.             if not node: return 0
    
13. 
    
14.             leftHeight = getHeightAndBalanced(node.left)
    
15.             if leftHeight == -1: return -1
    
16.             else:
    
17.                 leftHeight += 1
    
18.             rightHeight = getHeightAndBalanced(node.right)
    
19.             
    
20.             if rightHeight == -1:
    
21.                 return -1
    
22.             else:
    
23.                 rightHeight += 1
    
24. 
    
25.             if abs(leftHeight - rightHeight) > 1:
    
26.                 return -1
    
27.             else:
    
28.                 return max(leftHeight, rightHeight)
    
29.         
    
30.         if getHeightAndBalanced(root) == -1:
    
31.             return False
    
32.         else:
    
33.             return True
    

复制代码

LC 3833. Count Dominant Indices

简单周赛题目，从右到左，逐项计算统计。

1. class Solution:
   
2.     def dominantIndices(self, nums: List[int]) -> int:
   
3.         n = len(nums)
   
4.         sum_to_right = nums[n-1]
   
5.         ans = 0
   
6.         count = 1
   
7. 
   
8.         for i in range(n-2, -1, -1):
   
9.             if nums[i] > (sum_to_right * 1.0 / count):
   
10.                 ans += 1
    
11.             sum_to_right += nums[i]
    
12.             count += 1
    
13.         return ans
    
14.         

复制代码