?
lcr148.棧
按放入順序推棧，能彈出的就及時彈出，最后棧空則符合要求。
判斷?takeOut?序列是否符合棧的操作邏輯，因為題目中“特殊的數據結構”其實就是棧（先進后出）。
思路如下：
1.?用一個棧來模擬圖書放入的過程。
2.?按?putIn?的順序依次將圖書推入棧中。
3.?每次推入后，檢查棧頂元素是否和?takeOut?當前待匹配的元素相同：
- 如果相同，就彈出棧頂元素，并移動?takeOut?的匹配指針。
- 重復此檢查，直到棧頂元素和待匹配元素不同。
4.?當?putIn?的元素全部處理完后，若棧為空，說明?takeOut?是正確的拿取序列，返回?true?；否則返回?false?。
class Solution {
public:
? ? bool validateBookSequences(vector<int>& putIn, vector<int>& takeOut)?
? ? {
? ? ? ? stack<int> st;
? ? ? ? int i=0;
? ? ? ? for(int& p:putIn)
? ? ? ? {
? ? ? ? ? ? st.push(p);
? ? ? ? ? ??
?while(!st.empty() && st.top()==takeOut[i])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? st.pop();
? ? ? ? ? ? ? ? i++;
? ? ? ? ? ? }
? ? ? ? ? ?
? ? ? ? }
? ? ? ? return st.empty();
? ? }
};
lc2316.dfs無向圖聯通塊計算
class Solution {
public:
long long countPairs(int n, vector<vector<int>> &edges) {
vector<vector<int>> g(n);
for (auto &e: edges) {
int x = e[0], y = e[1];
g[x].push_back(y);
g[y].push_back(x); // 建圖
}
? ? ? ? vector<int> vis(n);
function<int(int)> dfs = [&](int x) -> int {
vis[x] = true; // 避免重復訪問同一個點
int size = 1;
for (int y: g[x]) {
? if (!vis[y]) {
size += dfs(y);
}
}
return size;
};
? ? ? ? long long ans = 0;
for (int i = 0, total = 0; i < n; i++) {
? if (!vis[i]) { // 未訪問的點：說明找到了一個新的連通塊
int size = dfs(i);
ans += (long) size * total;
total += size;
}
}
return ans;
}
};
lc1042. 不領接植花
鄰接表涂色
給花園涂色：
1. 建鄰接表
2.?涂色時，先看它相鄰的用了什么顏色（記在?used?里）。
3.??找第一個沒被用過的顏色，給當前花園涂上。
最后返回所有花園的顏色數組
class Solution {
public:
vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
// 鄰接表存連接關系
vector<vector<int>> g(n);
for (auto& p : paths) {
// 花園編號轉成0開始（原是1開始）
int x = p[0] - 1, y = p[1] - 1;
g[x].push_back(y);
g[y].push_back(x);
}
? ? ? ? // 存每個花園的顏色（1-4）
vector<int> color(n);
for (int i = 0; i < n; i++)
? ? ? ? ? {
// 記錄鄰居用過的顏色
bool used[5] = {false};
for (int j : g[i]) {
used[color[j]] = true;
}
? ? ? ? ? ? // 找第一個沒被用過的顏色
int c = 1;
while (used[c]) {
c++;
}
color[i] = c;
}
return color;
}
};
?
lc3186.施咒
?
dp[i]?表示“考慮前i個不同數字時，能得到的最大總和”。
排好序后，對每個數字，要么跳過它，要么選它（同時只能搭配前面和它差≥3的數字），始終選總和最大的方案。
注意，就在于對于重復值的處理
1.?先整理數據：統計每個數字出現的次數（比如數字5出現3次，總和就是5×3），再把數字從小到大排序。
2.?動態規劃記錄最大和：用 dp[i]?表示“考慮前i個不同數字時，能得到的最大總和”。
3.?核心邏輯：
- 對每個數字?x?（帶次數?c?），先找最前面一個“和?x?的差小于3”的數字位置?j?（意味著?j?之前的數字都能和?x?共存）。
- 決策：要么不選?x?，總和就是?f[i]?（繼承前i-1個的結果）；要么選?x?，總和就是?f[j] + x×c?（?j?之前的最大和加上?x?的總貢獻），取兩者更大的那個。
4.?最終結果：?f[n]?就是考慮所有數字后能得到的最大總和。
class Solution {
public:
long long maximumTotalDamage(vector<int>& power) {
unordered_map<int, int> cnt;
for (int x : power) {
cnt[x]++;
}
? ? ? ? vector<pair<int, int>> a(cnt.begin(), cnt.end());? ? //hash轉化方法
sort(a.begin(),a.end());
? ? ? ? int n = a.size();
vector<long long> f(n + 1);
for (int i = 0, j = 0; i < n; i++)
? ? ? ? ? {
auto& [x, c] = a[i];
while (a[j].first < x - 2)
? ? ? ? ? ? {
? j++;? ?// 利用了單調性
}
?f[i + 1] = max(f[i], f[j] + (long long) x * c);
//選不選
}
return f[n];
}
};
?
?
lc2222. 狀態機dp
簡單dp:
?dp[k][j]? 記錄“選 ?k? 個字符、最后是 ?j?”的方案數，
class Solution {
typedef long long ll;
public:
long long numberOfWays(string s)
{
int n=s.size();
if(n<3) return 0;
vector<vector<ll>> dp(4,vector<ll>(2,0));
dp[0][1]=dp[0][0]=1;
for(int i=0;i<n;i++)? //遍歷子串，填表
{
//k要倒著加，要不然就多加了
for(int k=3;k>=1;k--)
{
if(s[i]=='0')
dp[k][0]+=dp[k-1][1];
else
dp[k][1]+=dp[k-1][0];
}
}
return dp[3][0]+dp[3][1];
}
};
k? 倒著遍歷是為了 確保狀態轉移時，?dp[k-1][...]? 用的是“上一輪”的舊值，避免當前輪更新的
?
lc442. 數組中重復的數據
模擬hash映射的原理? o(n)且不額外空間
“原地標記”
- 壓榨完num的價值，數組自身的下標和符號 代替哈希表，num遍歷查看完一個元素后，還原地通過符號標記修改。
- 利用了數也在1,n范圍的特性
找出數組里恰好出現兩次的數，返回這些數。
常規思路（哈希表，空間不夠好）
優化思路（原地標記，空間 O(1)）
?
利用數組下標和元素值的特殊關系：
- 數組長度是 n，元素值范圍是 ?[1, n]?，下標范圍是 ?[0, n-1]?。
- 可以把下標和元素值對應起來（比如值為?num?的數，對應下標?num-1? ），通過改元素正負，標記這個數是否出現過。
?
具體步驟（遍歷+標記）
1.?遍歷數組，對當前數?num?：
- 先取絕對值（因為可能被改過符號），算對應下標 ?index = |num| - 1?；
- 看?nums[index]?的符號：
- 若為正：說明?num?是第一次出現，把?nums[index]?改成負數（標記“已訪問”）；
- 若為負：說明?num?之前出現過，現在是第二次，把?num?加入結果（這就是重復的數）。
?
舉個例子
比如數組是 ?[4,3,2,7,8,2,3,1]?：
- 遍歷到?4?，對應下標?4-1=3?，?nums[3]?是?7?（正）→ 改成?-7?；
- 遍歷到?3?，對應下標?3-1=2?，?nums[2]?是?2?（正）→ 改成?-2?；
- ……
- 遍歷到?2?，對應下標?2-1=1?，?nums[1]?是?-3?（負）→ 說明?2?重復，加入結果；
- 最終找出所有重復兩次的數。
?
核心巧妙點
用數組自身的下標和符號代替哈希表，不用額外空間，完美解決“找重復兩次的數”的問題，時間 O(n)、空間 O(1) 。
?
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> duplicates;
int n = nums.size();
for (int i = 0; i < n; i++) {
int num = nums[i];
int index = abs(num) - 1;
? if (nums[index] > 0) {
nums[index] = -nums[index];
}
? ? ? ? ? else {
duplicates.push_back(index + 1);
}
}
return duplicates;
}
};
?
