7.9 note| dfs
dfs判断联通块
邻接表建图
class Solution {
public:
int countCompleteComponents(int n, vector<vector<int>>& edges)
{
vector<vector<int>> g(n);
for(auto& e:edges)
{
g[e[0]].push_back(e[1]);
g[e[1]].push_back(e[0]);
}
vector<int> vis(n);
int ans=0,e,v;
function<void(int)> dfs=[&](int x)
{
vis[x]=true;
v++;
e+=g[x].size();
for(auto y:g[x])
{
if(!vis[y])
dfs(y);
}
};
for(int i=0;i<n;i++)
{
if(!vis[i])
{
v=0;
e=0;
dfs(i);
ans+=(e==v*(v-1));
}
}
return ans;
}
};
lc841. 钥匙和房间
class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
int n = rooms.size();
vector<int> vis(n,false);
auto dfs = [&](this auto&& dfs,int x)->void
{
//递归出口
if(vis[x]) return;
vis[x] = true;
vector<int> keys = rooms[x];
for(int k : keys)
{
dfs(k);
}
};
dfs(0);
for (int i : vis)
{
if (i == false) return false;
}
return true;
}
};
lc432.路径总和
深搜,前缀和,hash
前题回顾,lc560.和为k的子数组
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
//子数组:连续的
int n=nums.size();
vector<int> dp(n+1);
unordered_map<int,int> count;
count[0]=1;//dp[i]==k
int ret=0;
for(int i=1;i<=n;i++)
{
dp[i]=dp[i-1]+nums[i-1];
if(count[dp[i]-k])
ret+=count[dp[i]-k];
count[dp[i]]++;
}
return ret;
}
};
lc40.组合总和
关键在于去重,无论是选不选,或者是枚举做,都要好好画出决策树,理清楚各种情况~
选或不选
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
int n = candidates.size();
vector<vector<int>> ans;
vector<int> path;
sort(candidates.begin(), candidates.end());
auto dfs = [&](auto&& dfs, int i, int left)->void
{
if (left == 0)
{
ans.push_back(path);
return;
}
if (i == n) return;
if (left-candidates[i] < 0) return;
path.push_back(candidates[i]);
dfs(dfs, i + 1, left - candidates[i]);
path.pop_back();
//不选的时候,要注意重复逻辑的去除
int j = i + 1;
while (j < n&&candidates[j] == candidates[i]) j++;
if (j == n) return;
dfs(dfs, j, left);
return;
};
dfs(dfs, 0, target);
return ans;
}
};
枚举,符合条件的选择
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
int n=candidates.size();
sort(candidates.begin(),candidates.end());
vector<vector<int>> ans;
vector<int> path;
auto dfs=[&](auto&& dfs,int i,int left)->void
{
if(left==0){
ans.push_back(path);
return;
}
if(i==n) return;
for(int j=i;j<n&&left-candidates[j]>=0;j++)
{
if(j!=i&&candidates[j]==candidates[j-1]) continue;
path.push_back(candidates[j]);
dfs(dfs,j+1,left-candidates[j]);
path.pop_back();
}
};
dfs(dfs,0,target);
return ans;
}
};
lc739.每日温度
单调栈
一眼望去,只有更好的山峰,和无尽的低落
栈存储索引,比存储温度好
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures)
{
int n = temperatures.size();
vector<int> ret(n, 0);
stack<int> st; // 栈存储索引,而非温度值
for (int i = 0; i < n; i++)
{
int a = temperatures[i];
// 当前温度大于栈顶索引对应的温度时,弹出栈顶并计算天数
while (!st.empty() && a > temperatures[st.top()])
{
int topIdx = st.top();
st.pop();
ret[topIdx] = i - topIdx; // 天数差即为结果
}
st.push(i); // 压入当前索引
}
return ret; // 返回结果数组
}
};
lc128.鲁棒性
循环结束后,最后一组也要注意比较
class Solution {
public:
int longestConsecutive(vector<int>& nums)
{
if(nums.empty()) return 0;
sort(nums.begin(),nums.end());
int ret=1;
int cnt=1;
int n=nums.size();
for(int i=1;i<n;i++)
{
if(nums[i-1]==nums[i])
continue;
else if(nums[i-1]+1==nums[i])
cnt++;
else
{
ret=max(ret,cnt);
cnt=1;
}
}
ret=max(ret,cnt);
return ret;
}
};
lc189.轮转数组
三次翻转,stl源码中有类似思想
class Solution {
public:
void rotate(vector<int>& nums, int k) {
k %= nums.size(); // 轮转 k 次等于轮转 k % n 次
reverse(nums.begin(),nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
}
};