第三章 图论 No.8最近公共祖先lca, tarjan与次小生成树

文章目录

    • lca
    • Tarjan
      • 板子题：1172. 祖孙询问
      • lca或tarjan：1171. 距离
      • 356. 次小生成树
      • 352. 闇の連鎖

image.png

lca

O ( m l o g n ) O(mlogn) O(mlogn)，n为节点数量，m为询问次数，lca是一种在线处理询问的算法
自己也是自己的祖先

倍增：
f a ( i , j ) fa(i, j) fa(i,j)表示从i开始，向上走 2 j 2^j 2j步走到的点
j = 0，走到父节点
j > 0，分两步走，先走到 2 j − 1 2^{j-1} 2j−1步再走 2 j − 1 2^{j-1} 2j−1步，那么一共就会走 2 j 2^j 2j步， f a ( i , j ) = f a ( f a ( i , j − 1 ) , j − 1 ) fa(i, j) = fa(fa(i, j-1), j-1) fa(i,j)=fa(fa(i,j−1),j−1)
d e p t h ( i ) depth(i) depth(i)表示层数

  1. 将两点跳到同一层
  2. 让两个点同时往上跳，直到跳到公共祖先的下一层

第一步：基于二进制的思想，x和y之间的层数差距为 d e p t h ( x ) − d e p t h ( y ) depth(x) - depth(y) depth(x)−depth(y)，假设y的层数小于x的层数，此时x要往上跳
若要跳k层，那么根据k的二进制表示将k拆分成多个2的幂相加，由于我们已经预处理了 f ( i , j ) f(i, j) f(i,j)，所以根据 f ( i , j ) f(i, j) f(i,j)的值往上跳即可
当 f ( x , k ) = f ( y , k ) f(x, k) = f(y, k) f(x,k)=f(y,k)时，即x往上跳k步和y往上跳k步后，位于同一个位置，此时找到了一个公共祖先，但不是最近公共祖先，所以这里要减小k的值，直到 f ( x , k ) ≠ f ( y , k ) f(x, k) ≠ f(y, k) f(x,k)=f(y,k)，此时才找到了最近公共祖先

规定 d e p t h ( 0 ) = 0 depth(0) = 0 depth(0)=0，0号点为哨兵，位于第0层，根节点位于第一层
向上跳 2 k 2^k 2k步后，若跳出了这颗树，那么 f ( i , k ) = 0 f(i, k) = 0 f(i,k)=0

image.png

预处理depth和fa的板子：

void bfs(int root)
{
	memset(dis, 0x3f, sizeof(dis));
	q[tt ++ ] = root;
	depth[root] = 1, depth[0] = 0;
	while (tt >= hh)
	{
		int x = q[hh ++ ];
		for (int i = h[x]; i != -1; i = ne[i])
		{
			int y = e[i];
			if (depth[y] > depth[x] + 1)
			{
				depth[y] = depth[x] + 1;
				q[tt ++ ] = y;
				fa[y][0] = x;
				for (int k = 1; k <= c; ++ k )
					fa[y][k] = fa[fa[y][k - 1]][k - 1];
			}
		}
	}
}

lca板子：

int lca(int x, int y)
{
	if (depth[x] < depth[y]) swap(x, y);
	for (int k = c; k >= 0; -- k )
		if (depth[fa[x][k]] >= depth[y])
			x = fa[x][k];
	if (x == y) return y;
	for (int k = c; k >= 0; -- k )
		if (fa[x][k] != fa[y][k])
		{
			x = fa[x][k];
			y = fa[x][k];
		}
	return fa[x][0];
}

Tarjan

O ( n + m ) O(n + m) O(n+m) ，n为节点数量，m为询问次数
tarjan是一种离线处理询问的算法，是向上标记法的优化
在深度优先遍历时，将所有点分成三大类

  1. 已经遍历过且已经回溯的点
  2. 已经遍历但正在搜索的分支
  3. 还未搜索到的点

image.png
将已经遍历且回溯的点标记成2，正在遍历的点标记成1，未遍历的点标记成0
对于正在回溯的点，需要处理所有有关该点的询问信息：若询问的另外一个点已经遍历过（回溯完成），那么该点将被分到一个集合中，集合的代表点就是两点的最近公共祖先
比如上图，当前正在遍历x这个点，已经遍历完的点为绿色部分，这些点所属集合的代表点位于红色分支上

模板：

// 用dfs维护dis数组
void dfs(int x, int fa)
{
	for (int i = h[x]; i != -1; i = ne[i])
	{
		int y = e[i];
		if (y != fa)
		{
			dis[y] = dis[x] + w[i];
			dfs(y, x);
		}
	}
}

// tarjan处理询问
void tarjan(int x)
{
	st[x] = 1; // 当前正在遍历该点
	for (int i = h[x]; i != -1; i = ne[i])
	{
		int y = e[i];
		if (!st[y]) // 当前为遍历ydian
		{
			tarjan(y);
			p[y] = u;
		}
	}
	for (auto item : query[x]) // 处理有关当前节点的询问
	{
		int y = item.first, id = item.first; // id为该询问的唯一编号
		if (st[y] == 2) // 询问的另一点已经遍历过
		{
			int anc = find(y); // 找到集合的代表点，公共祖先
			res[id] = dis[x] + dis[y] - 2 * dis[anc]; // 根据id将答案存储到数组中
		}
	}
	st[x] = 2; // 当前节点遍历完
}

板子题：1172. 祖孙询问

1172. 祖孙询问 - AcWing题库
image.png

由于树的层数最大有40000层，所以一个节点最多向上跳 l o g 400000 log400000 log400000层，大概是一个大于 2 15 2^{15} 215小于 2 16 2^{16} 216的数，所以最多跳 2 16 − 1 2^{16} - 1 216−1层，二进制位取15即可

#include <iostream>
#include <cstring>
using namespace std;

const int N = 4e4 + 10, M = 2 * N;
int h[N], e[M], ne[M], idx;
int q[N], hh, tt = -1;
int depth[N], fa[N][16]; // 最多跳2^16-1
int n;

void add(int x, int y)
{
    e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}

void bfs(int root)
{
    q[++ tt] = root;
    memset(depth, 0x3f, sizeof(depth));
    depth[0] = 0, depth[root] = 1;
    while (tt >= hh)
    {
        int x = q[hh ++ ];
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (depth[y] > depth[x] + 1)
            {
                depth[y] = depth[x] + 1;
                fa[y][0] = x;
                q[++ tt ] = y;
                for (int k = 1; k <= 15; ++ k )
                    fa[y][k] = fa[fa[y][k - 1]][k - 1];
            }
        }
    }
}

int lca(int x, int y)
{
    if (depth[x] < depth[y]) swap(x, y);
    for (int k = 15; k >= 0; -- k )
        if (depth[fa[x][k]] >= depth[y])
            x = fa[x][k];
    if (x == y) return y;
    for (int k = 15; k >= 0; -- k )
        if (fa[x][k] != fa[y][k])
        {
            x = fa[x][k];
            y = fa[y][k];
        }
    return fa[x][0];
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d", &n);
    int root;
    int a, b;
    for (int i = 0; i < n; ++ i )
    {
        scanf("%d%d", &a, &b);
        if (b == -1) root = a;
        else add(a, b), add(b, a);
    }
    
    bfs(root);
    int m;
    scanf("%d", &m);
    for (int i = 0; i < m; ++ i )
    {
        scanf("%d%d", &a, &b);
        int t = lca(a, b);
        if (t == a) puts("1");
        else if (t == b) puts("2");
        else puts("0");
    }
    return 0;
}

lca或tarjan：1171. 距离

1171. 距离 - AcWing题库
image.png

与上题一样，题目要处理很多询问，可以用lca或者离线tarjan解决
树的最短路问题可以从公共祖先的角度考虑，假设x和y的公共祖先为t， d i s ( t ) dis(t) dis(t)为根节点到t的距离，那么x和y之间的最短距离就是 d i s ( x ) + d i s ( y ) − 2 ∗ d i s ( t ) dis(x) + dis(y) - 2 * dis(t) dis(x)+dis(y)−2∗dis(t)

题目没有给定根节点，我们任意指定一个点为根节点即可

lca解法：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e4 + 10, M = 2 * N;
int h[N], e[M], ne[M], w[M], idx;
int depth[N], fa[N][16];
int q[N], hh, tt = -1;
int dis[N];

void add(int x, int y, int d)
{
    e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}

void dfs(int root)
{
    memset(depth, 0x3f, sizeof(depth));
    depth[0] = 0, depth[root] = 1;
    q[++ tt ] = root;
    while (tt >= hh)
    {
        int x = q[hh ++ ];
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (depth[y] > depth[x] + 1)
            {
                depth[y] = depth[x] + 1;
                dis[y] = dis[x] + w[i];
                fa[y][0] = x;
                q[++ tt ] = y;
                for (int k = 1; k <= 15; ++ k )
                    fa[y][k] = fa[fa[y][k - 1]][k - 1];
            }
        }
    }
}

int lca(int x, int y)
{
    if (depth[x] < depth[y]) swap(x, y);
    for (int k = 15; k >= 0; -- k )
        if (depth[fa[x][k]] >= depth[y])
            x = fa[x][k];
    if (x == y) return y;
    for (int k = 15; k >= 0; -- k )
        if (fa[x][k] != fa[y][k])
        {
            x = fa[x][k];
            y = fa[y][k];
        }
    return fa[x][0];
}

int main()
{
    memset(h, -1, sizeof(h));
    int n, m;
    scanf("%d%d", &n, &m);
    int x, y, d;
    for (int i = 0; i < n - 1; ++ i )
    {
        scanf("%d%d%d", &x, &y, &d);
        add(x, y, d), add(y, x, d);
    }
    dfs(1);
    
    for (int i = 0; i < m; ++ i )
    {
        scanf("%d%d", &x, &y);
        int t = lca(x, y);
        printf("%d\n", dis[x] + dis[y] - 2 * dis[t]);
    }
    return 0;
}

tarjan解法：

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int N = 1e4 + 10, M = 2 * N;
typedef pair<int, int> PII;
vector<PII> query[N];
int h[N], e[M], ne[M], w[M], idx;
int res[M], dis[N], st[N], p[N];
int n, m;

void add(int x, int y, int d)
{
    e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}

void dfs(int x, int fa)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if (y != fa)
        {
            dis[y] = dis[x] + w[i];
            dfs(y, x);
        }
    }
}

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void tarjan(int x)
{
    st[x] = 1;
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if (!st[y])
        {
            tarjan(y);
            p[y] = x;
        }
    }
    
    for (auto item : query[x])
    {
        int y = item.first, id = item.second;
        if (st[y] == 2)
        {
            int anc = find(y);
            res[id] = dis[x] + dis[y] - 2 * dis[anc];
        }
    }
    st[x] = 2;
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    int x, y, d;
    for (int i = 0; i < n - 1; ++ i )
    {
        scanf("%d%d%d", &x, &y, &d);
        add(x, y, d), add(y, x, d);
    }
    for (int i = 0; i < m; ++ i )
    {
        scanf("%d%d", &x, &y);
        query[x].push_back({y, i}); // 将查询的另一个点与查询编号保存
        query[y].push_back({x, i});
    }
    
    dfs(1, -1);
    for (int i = 1; i <= n; ++ i ) p[i] = i;
    tarjan(1);
    for (int i = 0; i < m; ++ i ) printf("%d\n", res[i]);
    
    return 0;
}

debug：维护的query信息要不同地插入两次

query[x].push_back({y, i});
query[y].push_back({x, i});

因为当前询问有关x的信息时，y可能没有遍历完，但是询问y有关的信息时，x是遍历完的

356. 次小生成树

356. 次小生成树 - AcWing题库
image.png

d 1 ( i , j ) d1(i, j) d1(i,j)表示从i往上跳 2 j 2^j 2j层后，路径上的最大边权
d 2 ( i , j ) d2(i, j) d2(i,j)表示从i往上跳 2 j 2^j 2j层后，路径上的次大边权
跳 2 j 2^j 2j步是一个类似分治的过程，分成两部分跳，这两部分依旧能分成两部分跳
路径上的最大值为每一段的最大值取max，次大值为所有子路径的最大值和次大值中的第二大，每次遍历子线段时维护信息即可

if (d > d1) d2 = d1, d1 = d; 
else if (d != d1 && d > d2) d2 = d;

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10, M = 3e5 + 10, INF = 0x3f3f3f3f;
struct Edge
{
    int x, y, w;
    bool f;
    bool operator<(const Edge& e) const 
    {
        return w < e.w;
    }
}edges[M];

int h[N], e[M], ne[M], w[M], idx;
int p[N], depth[N], fa[N][17];
int q[N], hh, tt = -1;
int d1[N][17], d2[N][17];
int d[M];
int n, m;

void add(int x, int y, int d)
{
    e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}

int find(int x)
{
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

LL kruskal()
{
    LL res = 0;
    sort(edges, edges + m);
    for (int i = 1; i <= n; ++ i ) p[i] = i;
    for (int i = 0; i < m; ++ i )
    {
        auto t = edges[i];
        int x = t.x, y = t.y, w = t.w;
        int px = find(x), py = find(y);
        if (px != py)
        {
            res += w;
            p[px] = py;
            edges[i].f = true;
            add(x, y, w), add(y, x, w);
        }
    }
    return res;
}

void bfs()
{
    q[++ tt ] = 1;
    memset(depth, 0x3f, sizeof(depth));
    depth[0] = 0, depth[1] = 1;
    while (tt >= hh)
    {
        int x = q[hh ++ ];
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (depth[y] > depth[x] + 1)
            {
                depth[y] = depth[x] + 1;
                fa[y][0] = x;
                d1[y][0] = w[i], d2[y][0] = -INF;
                q[++ tt ] = y;
                for (int k = 1; k <= 16; ++ k )
                {
                    int mid = fa[y][k - 1];
                    fa[y][k] = fa[mid][k - 1];
                    d1[y][k] = d2[y][k] = -INF;
                    int a[4] = { d1[mid][k - 1], d2[mid][k - 1], d1[y][k - 1], d2[y][k - 1] };
                    for (int i = 0; i < 4; ++ i )
                    {
                        if (a[i] > d1[y][k]) d2[y][k] = d1[y][k], d1[y][k] = a[i];
                        else if (a[i] != d1[y][k] && a[i] > d2[y][k]) d2[y][k] = a[i];
                    }
                }
            }
        }
    }
}


int lca(int x, int y, int w)
{
    int cnt = 0;
    if (depth[x] < depth[y]) swap(x, y);
    for (int k = 16; k >= 0; -- k )
        if (depth[fa[x][k]] >= depth[y])
        {
            d[cnt ++ ] = d1[x][k];
            d[cnt ++ ] = d2[x][k];
            x = fa[x][k];
        }
    if (x != y)
    {
        for (int k = 16; k >= 0; -- k )
        {
            if (fa[x][k] != fa[y][k])
            {
                d[cnt ++ ] = d1[x][k], d[cnt ++ ] = d2[x][k];
                d[cnt ++ ] = d1[y][k], d[cnt ++ ] = d2[y][k];
                x = fa[x][k], y = fa[y][k];
            }
            d[cnt ++ ] = d1[x][0], d[cnt ++ ] = d2[x][0];
            d[cnt ++ ] = d1[y][0], d[cnt ++ ] = d2[y][0];
        }
    }
    int dmax1 = -INF, dmax2 = -INF;
    for (int i = 0; i < cnt; ++ i )
    {
        if (d[i] > dmax1) dmax2 = dmax1, dmax1 = d[i];
        else if (d[i] != dmax1 && d[i] > dmax2) dmax2 = d[i];
    }
    
    if (w > dmax1) return w - dmax1;
    return w - dmax2;
}


int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++ i )
        scanf("%d%d%d", &edges[i].x, &edges[i].y, &edges[i].w);
        
    LL sum = kruskal(); // 最小生成树的权值
    bfs();
    
    LL res = 1e19;
    for (int i = 0; i < m; ++ i )
        if (!edges[i].f)
            res = min(res, sum + lca(edges[i].x, edges[i].y, edges[i].w));
    
    printf("%lld\n", res);
    return 0;
}

352. 闇の連鎖

352. 闇の連鎖 - AcWing题库
image.png

image.png

树上差分，将x到y的最短路径上所有的边加上c，若p为x和y的公共祖先，那么
d(x) += c, d(y) += c, d(p) -= 2c
如何计算某条边的权值？以这条边的子节点为根的子树中，所有边的权值相加为这条边的权值

在一颗树中，删除任意一条边，那么这颗树将被切成两个连通块
若向树中再添加一条边，那么这条非树边和树边就一定构成环，要向将此时的“树”切成两个连通块，就要删除环中的任意一条树边与这条非树边
题目限制只能先切树边，再切非树边，一共两次，两次过后还没有切成两个连通块，说明这个方案行不通
当切除树边，不用再切除非树边就得到两个连通块时，由于题目限制，还需要切除一条非树边，假设非树边有m条，那么此时可以选择m条边中的任意一条切除，此时的方案数为m
若切除树边后，还要再切除一条非树边，才能得到两个连通块时，此时的方案数为1，只能切除这条环中的非树边
若切除树边后，还要再切除大于一条的非树边，此时无法再切除，方案数为0

现在的问题是，如何知道切除某条树边后，还需要再切除几条非树边？
假设现在已经用树边建立了一棵树，此时再添加非树边将构成环，将环中的所有树边权值加1，假设初始权值为0，此时可以使用树上差分
然后遍历所有的树边，根据边权计算方案数

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][17];
int q[N], hh, tt = -1;
int d[N];
int n, m, ans;

void add(int x ,int y)
{
    e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}

void bfs()
{
    memset(depth, 0x3f, sizeof(depth));
    depth[0] = 0, depth[1] = 1;
    q[++ tt ] = 1;
    while (tt >= hh)
    {
        int x = q[hh ++ ];
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (depth[y] > depth[x] + 1)
            {
                depth[y] = depth[x] + 1;
                fa[y][0] = x;
                q[++ tt ] = y;
                for (int k = 1; k <= 16; ++ k )
                    fa[y][k] = fa[fa[y][k - 1]][k - 1];
            }
        }
    }
}

int lca(int x, int y)
{
    if (depth[x] < depth[y]) swap(x, y);
    for (int k = 16; k >= 0; -- k )
        if (depth[fa[x][k]] >= depth[y])
            x = fa[x][k];
    if (x == y) return x;
    for (int k = 16; k >= 0; -- k )
        if (fa[x][k] != fa[y][k])
        {
            x = fa[x][k];
            y = fa[y][k];
        }
    return fa[x][0];
}

int dfs(int x, int f)
{
    int res = d[x];
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if (f != y)
        {
            int t = dfs(y, x);
            if (t == 0) ans += m;
            else if (t == 1) ans ++;
            res += t;
        }
    }
    return res;
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    int x, y;
    for (int i = 0; i < n - 1; ++ i )
    {        
        scanf("%d%d", &x, &y);
        add(x, y), add(y, x);
    }
    
    bfs();
    int res = 0;
    for (int i = 0; i < m; ++ i)
    {
        scanf("%d%d", &x, &y);
        int p = lca(x, y);
        d[x] ++, d[y] ++, d[p] -= 2;
    }
    dfs(1, -1);
    printf("%d\n", ans);
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/69564.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Effective Java笔记（30）优先考虑泛型方法

Effective Java笔记（30）优先考虑泛型方法

正如类可以从泛型中受益一般 &#xff0c;方法也一样。静态工具方法尤其适合于泛型化 。 Collections 中的所有“算法”方法&#xff08;例如 binarySearch 和 sort &#xff09;都泛型化了 。 编写泛型方法与编写泛型类型相类似 。 例如下面这个方法&#xff0c;它返回两个集合…
阅读更多...
使用next.js编写TodoList(连接了数据库)(提供源码)

使用next.js编写TodoList(连接了数据库)(提供源码)

准备 安装next可以查看nextjs入门使用_姚*鸿的博客的博客-CSDN博客 安装Prisma可以查看 使用Prisma访问数据库_姚*鸿的博客的博客-CSDN博客 确保你前面两个步骤做完。 再提醒以下记得修改数据库的信息&#xff1a; 源码地址 next-todolist: nextjs的todolist例子 效果演示 开始…
阅读更多...
QT--崩溃原因分析

QT--崩溃原因分析

本文为学习记录&#xff0c;若有错误&#xff0c;请联系作者&#xff0c;谦虚受教。 文章目录 前言一、目的二、实现步骤1 add2line.exe2 分析文件3 crash文件 三、相关代码1 pro文件2.ccrashstack.h3.ccrashstack.cpp4.main.cpp 总结 前言 你从来来去自由&#xff0c;若你不想…
阅读更多...
Unity游戏源码分享-塔防游戏保卫兔子的食物CarrotFantasy

Unity游戏源码分享-塔防游戏保卫兔子的食物CarrotFantasy

Unity游戏源码分享-塔防游戏保卫兔子的食物CarrotFantasy 经典塔防游戏&#xff0c;可发布PC、Andoid、IOS、Web等 下载地址&#xff1a;https://download.csdn.net/download/Highning0007/88189987
阅读更多...
系统架构设计专业技能 · 软件工程（一）【系统架构设计师】

系统架构设计专业技能 · 软件工程（一）【系统架构设计师】

系列文章目录 系统架构设计高级技能 软件架构概念、架构风格、ABSD、架构复用、DSSA&#xff08;一&#xff09;【系统架构设计师】 系统架构设计高级技能 系统质量属性与架构评估&#xff08;二&#xff09;【系统架构设计师】 系统架构设计高级技能 软件可靠性分析与设计…
阅读更多...
​docker复现Nginx配置漏洞​

​docker复现Nginx配置漏洞​

目录 1.docker环境搭建 2.复现过程 2.1CRLF(carriage return/line feed)注入漏洞 ​编辑 2.2.目录穿越 2.3.add_header覆盖 1.docker环境搭建 1.安装docker Debian系列 apt-get update apt-get install docker.io Redhat系列 yum install docker.io 2.下载并解压dock…
阅读更多...
Do not access Object.prototype method ‘hasOwnProperty‘ from target object

Do not access Object.prototype method ‘hasOwnProperty‘ from target object

调用 hasOwnProperty 报错&#xff1a;不要使用对象原型上的方法&#xff0c;因为原型的方法可能会被重写 if (this.formData.selectFields.hasOwnProperty(selectField)) {delete this.formData.selectFields[selectField];} else {this.formData.selectFields[selectField] …
阅读更多...
Django快速入门

Django快速入门

文章目录 一、安装1.创建虚拟环境&#xff08;virtualenv和virtualenvwrapper&#xff09;2. 安装django 二、改解释器三、创建一个Django项目四、项目目录项目同名文件夹/settings.py 五、测试服务器启动六、数据迁移七、创建应用八、基本视图1. 返回响应 response2. 渲染模板…
阅读更多...
【01】基础知识：typescript安装及使用，开发工具vscode配置

【01】基础知识：typescript安装及使用，开发工具vscode配置

一、typescript 了解 typeScript 是由微软开发的一款开源的编程语言。 typeScript 是 javascript 的超级&#xff0c;遵循最新的 es6、es5规范。 typeScript 扩展了 javaScript 的语法。 typeScript 更像后端 java、C# 这样的面向对象语言&#xff0c;可以让 js 开发大型企…
阅读更多...
stm32项目（8）——基于stm32的智能家居设计

stm32项目（8）——基于stm32的智能家居设计

目录 一.功能设计 二.演示视频 三.硬件选择 1.单片机 2.红外遥控 3.红外探测模块 4.光敏电阻模块 5.温湿度检测模块 6.风扇模块 7.舵机 8.WIFI模块 9.LED和蜂鸣器 10.火焰传感器 11.气体传感器 四.程序设计 1.连线方式 2.注意事项 3.主程序代码 五.课题意义…
阅读更多...
ffmpeg+intel核显实现硬解码

ffmpeg+intel核显实现硬解码

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、前言二、检查方法1.图形法2.nvidia-smi3.intel-gpu-tools 三、安装使用1.libva-dev2.libva-utils3.编译安装4.测试1.vainfo2.ffmpeg测试解码 总结 前言 之…
阅读更多...
文档控件DevExpress Office File API v23.1新版亮点 - 支持.NET MAUI

文档控件DevExpress Office File API v23.1新版亮点 - 支持.NET MAUI

DevExpress Office File API是一个专为C#, VB.NET 和 ASP.NET等开发人员提供的非可视化.NET库。有了这个库&#xff0c;不用安装Microsoft Office&#xff0c;就可以完全自动处理Excel、Word等文档。开发人员使用一个非常易于操作的API就可以生成XLS, XLSx, DOC, DOCx, RTF, CS…
阅读更多...
LeetCode150道面试经典题-删除有序数组中的重复项(简单)

LeetCode150道面试经典题-删除有序数组中的重复项(简单)

1.题目 给你一个 升序排列 的数组 nums &#xff0c;请你 原地 删除重复出现的元素&#xff0c;使每个元素 只出现一次 &#xff0c;返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量为 k &#xff0c…
阅读更多...
工程英语翻译怎样做效果比较好

工程英语翻译怎样做效果比较好

我们知道&#xff0c;高质量的工程翻译可以有效指导工程项目操作的执行&#xff0c;但市场上专业的工程英语翻译人才严重不足。那么&#xff0c;工程英语翻译难吗&#xff0c;怎样翻译工程英语比较好&#xff1f; 业内人士指出&#xff0c; 工程翻译具有用词专业、涉及领域广、…
阅读更多...
stm32 cubemx ps2无线（有线）手柄

stm32 cubemx ps2无线（有线）手柄

文章目录 前言一、cubemx配置二、代码1.引入库bsp_hal_ps2.cbsp_hal_ps2.h 2.主函数 前言 本文讲解使用cubemx配置PS2手柄实现对手柄的按键和模拟值的读取。 很简单&#xff0c;库已经封装好了&#xff0c;直接就可以了。 文件 一、cubemx配置 这个很简单&#xff0c;不需要…
阅读更多...
Android Camera预览画面变形问题

Android Camera预览画面变形问题

csdn 问题 安卓camera1在预览时&#xff0c;预览画面看起来被拉伸了&#xff0e; 如图&#xff0c;圆形的盖子&#xff0c;变成椭圆形了&#xff0e; 代码 默认流程&#xff0c;如下为大致的打开摄像头并进行预览显示的代码 private Camera mCamera null; private Surfa…
阅读更多...
LeetCode算法递归类—验证二叉搜索树

LeetCode算法递归类—验证二叉搜索树

目录 98. 验证二叉搜索树 题解&#xff1a; 代码&#xff1a; 运行结果&#xff1a;​编辑 给你一个二叉树的根节点 root &#xff0c;判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下&#xff1a; 节点的左子树只包含 小于 当前节点的数。节点的右子树只包含…
阅读更多...
ChatGPT将会成为强者的外挂？—— 提高学习能力

ChatGPT将会成为强者的外挂？—— 提高学习能力

目录 前言 一、提高学习力 &#x1f9d1;‍&#x1f4bb; 1. 快速找到需要的知识 2. 组合自己的知识体系 3. 内化知识技能 二、提问能力❗ 三、思维、创新能力 &#x1f31f; 1. 批判性思维 1.1 八大基本结构进行批判性提问 1.2 苏格拉底的提问分类方法 2. 结构化思…
阅读更多...
【设计模式】责任链的基本概念及使用Predicate灵活构造校验链

【设计模式】责任链的基本概念及使用Predicate灵活构造校验链

文章目录 1. 概述1.1.背景1.2.责任链模式的概念 2.责任链的基本写法2.1.链表实现2.2.数组实现 3.Predicate校验链2.1.使用Predicate改写代码2.1.更丰富的条件拓展 4.总结 1. 概述 1.1.背景 在最近的开发中遇到了这么一个需求&#xff0c;需要对业务流程中的各个参数做前置校验…
阅读更多...
Nginx的优化和防盗链（面试高频！！!）

Nginx的优化和防盗链（面试高频！！!）

Nginx的优化和防盗链 全篇高能&#xff01;&#xff01;&#xff01;&#xff01;干货较多&#xff01;&#xff01;&#xff01;&#xff01;本篇含面试高频题&#xff1a; 修改配置文件时&#xff0c;先备份&#xff01;&#xff01;&#xff01;以便回滚&#xff01;&…
阅读更多...
最新文章

Copyright @ 2022~2023