树相关
发表评论
分类目录归档：编程
Java并查集问题
并查集是一种数据结构, 常用于描述集合,经常用于解决此类问题:某个元素是否属于某个集合,或者 某个元素 和 另一个元素是否同属于一个集合。可以用于点的分堆、判断点的互相可达性。
/**
* @Author: Sumail-Lee
* @Date: 2019/1/4 15:57
* @Description: 将一个集合内的点分堆，每个分好堆的点内都互相可达，公用同一个爹
*/
public class 并查集 {
private int[] parent;
private int size;
public 并查集(int size) {
this.size = size;
parent = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
}
}
public int findParent(int element) {
while (element != parent[element]) {
element = parent[element];
}
return element;
}
public boolean isConnected(int firstElement, int secondElement) {
return findParent(firstElement) == findParent(secondElement);
}
public void unionElements(int firstElement, int secondElement) {
int firstRoot = findParent(firstElement);
int secondRoot = findParent(secondElement);
if (firstRoot == secondRoot) {
return;
}
parent[firstRoot] = secondRoot;
}
}
单例模式线程安全的实现
大家的写法
public class Single {
private static class Holder {
static Single instance = new Single();
}
private Single() {
}
public Single getInstance() {
return Holder.instance;
}
}
皮一下的写法，优化后是上面的
public class Single {
private static Single instance;
static {
instance = new Single();
}
private Single() {
}
public Single getInstance() {
return instance;
}
}
黑群晖DSM6.2.1版本的安装（vmware虚拟机）
贪心算法的一些题目
活动安排问题
定义（活动） 设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，而在同一时间只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。
图相关算法
无向图判断是否存在闭环
01背包、多重背包、完全背包
一、01背包
【问题】有n 个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？并且假设背包容量为8。
|
i |
1 |
2 |
3 |
4 |
|
w(体积) |
2 |
3 |
4 |
5 |
|
v(价值) |
3 |
4 |
5 |
6 |
SpringCloud 微服务简介
一、概述
微服务：一系列微小的服务共同形成，每个服务跑在自己的进程里，每个服务为独立的业务开发。
- 一系列微小的服务共同组成
- 单独部署，跑在自己的进程里
- 每个服务为独立的业务开发
- 分布式的管理
Spring AOP简单讲解
幂等性保证
唯一ID+指纹码机制
- 唯一ID+指纹码机制，利用数据库主键去重
- SELECT COUNT(1) FROM T_ORDER WHERE ID=唯一ID+指纹码
- 好处：实现简单
- 坏处：高并发下有数据库写入的性能平静
- 解决方案：跟进ID进行分库分表进行算法路由
利用Redis原子性实现
- 使用Redis进行幂等。
- 是否要进行数据库入库，需要注意数据库与redis的一致性