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;
}
};
?
