5.17 note

反转链表

递归法
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head) return NULL;
if(!head->next) return head;

ListNode * newHead = reverseList(head->next); //走到最后，再实现翻转

head->next->next = head;
head->next = NULL; //置空
return newHead;
}
};

连通分量

#include <vector>
#include <unordered_map>
#include <functional>
using namespace std;

class Solution {
public:
int countCompleteComponents(int n, vector<vector<int>>& edges) {
vector<int> parent(n); // 节点数为n，初始化父数组大小为n
vector<int> size(n, 1); // 记录每个连通分量的节点数
unordered_map<int, int> edgeCount; // 记录每个连通分量的边数

// 初始化并查集
for (int i = 0; i < n; ++i) {
parent[i] = i;
}

function<int(int)> find = [&](int idx) {
if (parent[idx] != idx) {
parent[idx] = find(parent[idx]);
}
return parent[idx];
};

auto unionSet = [&](int x, int y) {
int root1 = find(x);
int root2 = find(y);
if (root1 != root2) {
// 合并时小集合并到大集合（按秩合并优化）
if (size[root1] < size[root2]) swap(root1, root2);
parent[root2] = root1;
size[root1] += size[root2]; // 合并后节点数累加
}
};

// 处理所有边，构建并查集并统计边数
for (const auto& e : edges) {
int u = e[0], v = e[1];
unionSet(u, v); // 合并节点
int root = find(u); // 找到共同根节点
edgeCount[root]++; // 根节点对应的边数+1（无向边每条会被处理两次，后续需除以2）
}

// 统计完全连通分量数量
int result = 0;
unordered_set<int> roots; // 记录所有根节点

// 先收集所有根节点
for (int i = 0; i < n; ++i) {
roots.insert(find(i));
}

// 检查每个根节点对应的连通分量是否为完全图
for (int root : roots) {
int componentSize = size[root];
int totalEdges = edgeCount[root]; // 无向边实际边数需除以2（每条边被记录两次）
// 完全图边数公式：n*(n-1)/2，其中n是节点数
if (componentSize * (componentSize - 1) / 2 == totalEdges) {
result++;
}
}

return result;
}
};

函数包装器 function

- function ：给函数贴一个“类型标签”，明确函数的输入输出格式。
- lambda ：快速写一个没有名字的小函数，随用随写。

- 作用：在 C++ 中实现类似 Python 嵌套函数的效果，让代码更模块化、更简洁。

可以简单记住：它们就是 “临时定义的小工具函数”，专门用来辅助解决当前问题，用完就“丢弃”，不用单独命名和管理。

复习并查集

#include <vector>
using namespace std;

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int cities = isConnected.size();
        vector<int> parent(cities);
        for (int i = 0; i < cities; ++i) { // 初始化父节点数组
            parent[i] = i;
        }

        function<int(int)> find = [&](int idx) { // 定义路径压缩的find函数
            if (parent[idx] != idx) {
                parent[idx] = find(parent[idx]);
            }
            return parent[idx];
        };

        auto unionSet = [&](int x, int y) { // 定义合并集合的union函数
            int root1 = find(x);
            int root2 = find(y);
            if (root1 != root2) {
                parent[root2] = root1; // 合并方式采用将root2的父节点设为root1
                //<---------
            }
        };

        // 遍历所有城市对，合并连通的城市
        for (int i = 0; i < cities; ++i) {
            for (int j = i + 1; j < cities; ++j) {
                if (isConnected[i][j] == 1) {
                    unionSet(i, j);
                }
            }
        }

        // 统计根节点数量（连通分量数）
        int provinces = 0;
        for (int i = 0; i < cities; ++i) {
            if (parent[i] == i) {
                provinces++;
            }
        }
        return provinces;
    }
};

连通图

无向图，所以可以写的很简单。

遍历i查找，!check[i]（因为无向所以一维标记），然后对未标记的dfs j check[j]查找连通，记录ret

class Solution {

vector<vector<int>> g;

vector<int> check;

int m,n,ret=0;

//利用了无向图

public:

int findCircleNum(vector<vector<int>>& isConnected)

{

this->g=isConnected;

m=isConnected.size();

n=isConnected[0].size();

check.resize(n);

for(int i=0;i<m;i++)

{

if(!check[i])

{

check[i]=true;

dfs(i);

ret++;

}

return ret;

}

void dfs(int i)

{

for(int j=0;j<n;j++)

{

if(g[i][j] && !check[j])

{

check[j]=true;

dfs(j);

}

};

完全连通分量建图

class Solution {
public:

vector<vector<int>> g;
vector<int> st;
int v, e;

int countCompleteComponents(int n, vector<vector<int>>& edges) {
g.resize(n);
st.resize(n);
for(vector<int>& edge : edges){
g[edge[0]].push_back(edge[1]);
g[edge[1]].push_back(edge[0]);
}
int ans = 0;
for(int i = 0; i < n; i ++){
if(!st[i]){
v = 0;
e = 0;
dfs(i);
ans += （e == v * (v - 1)）;
}
}
return ans;
}
void dfs(int x){
st[x] = true;
v ++;
e += g[x].size();
for(int& y : g[x]){
if(!st[y]) dfs(y);
}
}
};

图统计入度为0的点

class Solution {

public:

vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges)

{

vector<int> in(n,0);

vector<bool> check(n,false);

vector<int> ret;

for(auto e:edges)

{

int u=e[0];

int v=e[1];

in[v]++;

}

for(auto e:edges)

{

int u=e[0];

if(in[u]==0 && !check[u])

{

check[u]=true;

ret.push_back(u);

}

return ret;

}

};

并查集边和点的关系

找完全连通分量图

edge=n*(n-1)/2

class Solution {
public:
int countCompleteComponents(int n, vector<vector<int>>& edges) {
int ans = 0;
vector<set<int>> m(n + 1, set<int>());

// 构建并查集
for (int i = 0; i < n; i++) {
m[i].insert(i);
}
for (auto x : edges) {
m[x[0]].insert(x[1]);
m[x[1]].insert(x[0]);
}

map<set<int>, int> s;
for (int i = 0; i < n; i++) {
s[m[i]] ++; //相同联通量的集合数
}
for (auto &[x,y] : s) {
if (y == x.size()) {

//集合数==联通点数完全联通图
ans ++;
}
}
return ans;
}
};

模拟题

class Solution {
public:
int minFlips(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
int cnt1 = 0, cnt2 = 0;
for (int i = 0; i < n; i++) {
for (int j = 0, k = m - 1; j < k; j++, k--) {
if (grid[i][j] != grid[i][k]) cnt1++;
}
}
for (int i = 0; i < m; i++) {
for (int j = 0, k = n - 1; j < k; j++, k--) {
if (grid[j][i] != grid[k][i]) cnt2++;
}
}
return min(cnt1, cnt2);
}
};