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