算法知识点汇总

知识点

1. 求二进制中1的个数

int get_count(int x)//返回x的二进制有多少个1
int get_count(int x)
{
    int res = 0;
    while (x)
    {
        res ++ ;
        x -= x & -x;
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11

2. 建树，和树的DFS

记得初始化头节点

const int N = 1e5 + 10, M = N * 2;
int h[N], e[M], ne[M], idx;

void add(int a, int b)  //如果是无向图，加两条边
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dfs(int u)
{
	state[u] = true;
	for(int  i = h[u]; i != -1; i = ne[i])
	{
		int j = e[i];
		if(!state[j])
			dfs(j);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18