当前位置: 首页 > news >正文

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());
}
};

 

http://www.lryc.cn/news/583094.html

相关文章:

  • 【Linux】Rocky Linux 安装 Docker 与 Docker-Compose
  • 【vLLM 学习】Eagle
  • 多代理混战?用 PAC(Proxy Auto-Config) 优雅切换代理场景
  • 选哪个数据恢复软件?六款深度数据恢复软件介绍
  • 数据基础练习
  • 【Linux】权限的概念及理解
  • 进程于线程-3
  • 代码审计-springel表达式注入
  • JSP动态网页开发基础
  • 前后端集合如何传递
  • 主流大模型Agent框架 AutoGPT详解
  • thinkphp使用redis抢单实例
  • 如何将华为手机中的照片传输到电脑
  • 超越公有云:在裸金属服务器上构建低成本、高性能的静态资源服务
  • 【RK3568+PG2L50H开发板实验例程】FPGA部分 | Pango 的时钟资源——锁相环
  • 川翔云电脑:突破硬件极限,重构设计生产力范式
  • 使用DDR4控制器实现多通道数据读写(十九)
  • Amazon S3 对象存储服务深度解析:存储原理、应用场景与实战指南
  • 1.1 ARMv8/ARMv9安全扩展
  • ReactNative【实战】轮播图(含组件封装 ImageSlider)
  • 洛谷P1044 栈(学习向)
  • react16-react19都更新哪些内容?
  • clickhouse 各个引擎适用的场景
  • 【TCP/IP】2. 计算机网络与因特网体系结构
  • 手机文件夹隐藏工具,一键保护隐私
  • 数据库性能优化指南:解决ORDER BY导致的查询性能问题( SQL Server )
  • Dify 文本语意识别与自动补全工作流
  • MyBatisPlus-03-扩展功能
  • C#基础篇(11)泛型类与泛型方法详解
  • 1068.产品销售分析Ⅰ