7.15 窗口函数 | 二分 | 位运算 | 字符串dp
lc3316. 字符串dp
dp多开一行一列后，注意原字符串下标映射
dp[n][m] （ n 是source长度， m 是pattern长度）
两重循环填表
for i 1-n
for j 0-m
三种状态转移
1.不选 dp i j=dp i-1 j
2.不选if tag, dp[i][j]++
3.if(s i==p j) 选，dp i j=max(dp i j, dp i-1 j-1)
从原字符串中挑选字符组成目标模式，同时尽可能多地删除指定位置的字符，最终能删多少个指定位置的字符。
具体逻辑拆解：
1. 前提设定：
- 有一个原字符串 source 和一个目标模式 pattern
- 有一些指定位置 targetIndices ，删除这些位置的字符会被计分
2. 核心目标：
- 要从原字符串中选出字符，按顺序组成目标模式（字符顺序不能乱）
- 同时尽量多删 targetIndices 里的位置
- 最后返回最多能删掉多少个指定位置的字符
3. 具体做法（用表格记录状态）：
- 用一个表格 f[i][j] 表示：处理到原字符串第 i 个字符，已匹配到模式第 j 个字符时，最多能删掉多少个指定位置
- 两种选择：
- 不选当前字符：直接跳过原字符串第 i 个字符，如果这个位置是指定位置，就加1分
- 选当前字符：如果当前字符和模式第 j 个字符相同，就用它来匹配，分数沿用之前的状态
4. 最终结果：
- 处理完所有字符后，表格中 f[n][m] 的值就是答案（ n 是原字符串长度， m 是模式长度）
举个例子：
- 原字符串是"abcde"，模式是"ace"
- 指定位置是[0,2]（即第1个和第3个字符）
- 最优方案是选a、c、e组成模式，同时删掉位置0和2的字符，最终得2分
class Solution {
public:
int maxRemovals(string source, string pattern, vector<int>& targetIndices) {
int n = source.size(), m = pattern.size();
vector<bool> flag(n + 1, false);
for (int x : targetIndices)
flag[x + 1] = true;
const int INF = 1e9;
vector<vector<int>> f(n + 1, vector<int>(m + 1, -INF));
f[0][0] = 0; // 初始状态：处理0个字符，匹配0个模式字符，删除数为0
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
// 转移1：不使用source第i位，直接跳过
f[i][j] = f[i - 1][j];
if (flag[i]) { // 如果当前位置是指定删除位，删除数+1
f[i][j]++;
}
// 转移2：使用source第i位匹配pattern第j位（若字符相同）
if (j > 0 && source[i - 1] == pattern[j - 1]) {
f[i][j] = max(f[i][j],f[i - 1][j - 1]);
}
}
}
return f[n][m]; // 处理完所有字符且匹配完整个模式时的最大删除数
}
};
05.07
1.位运算
2.位图
class Solution {
public:
int exchangeBits(int num) {
bitset<33> bitNum(num);
for (int i = 0; i < 16; i++){
bitNum[32] = bitNum[2*i];
bitNum[2*i] = bitNum[2*i+1];
bitNum[2*i+1] = bitNum[32];
}
return (int)bitNum.to_ulong();
}
};
577.员工奖金
select e.name,b.bonus
from Employee e
left join Bonus b on e.empId = b.empId
where b.bonus <1000 or b.bonus is null;
游戏查询
select player_id,
min(event_date) as first_login
from Activity
group by player_id
lc1661
抽象后，计算查询
select
machine_id,
round(2*avg(if(activity_type = 'start',-1,1)*timestamp),3) as processing_time
from
Activity
group by
machine_id
lcr069.二分
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int size = arr.size();
int left = 0;
int right = size - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(arr[mid] < arr[mid + 1]){
left = mid + 1;
}else{
right = mid - 1;
}
}
return left;
}
};