1.冒泡排序
//冒泡排序public int[] MySort (int[] arr) {// write code herefor (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - i - 1; j++) {if (arr[j] > arr[j + 1]) {swap(arr, j, j + 1);}}}return arr;}public void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}
2.快速排序
public int[] MySort (int[] arr) {
// write code here
quickSort(arr,0,arr.length - 1);
return arr;
}
public void quickSort(int[] arr,int left,int right) {
if(left < right) {
int point = partition(arr,left,right);
quickSort(arr,left,point - 1);
quickSort(arr,point + 1,right);
}
}
public int partition(int[] arr,int left,int right) {
int first = arr[left];
while(left < right) {
while(left < right && arr[right] >= first) {
right--;
}
swap(arr,left,right);
while(left < right && arr[left] <= first) {
left++;
}
swap(arr,left,right);
}
return left;
}
public void swap(int[] arr,int i,int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
3.归并排序
public int[] MySort (int[] arr) {
// write code here
mergeSort(arr,0,arr.length - 1);
return arr;
}
public void mergeSort(int[] arr,int l,int r) {
if(l == r) {
return;
}
int mid = l + ((r - l) >> 1);
mergeSort(arr,l,mid);
mergeSort(arr,mid + 1,r);
merge(arr,l,mid,r);
}
public void merge(int[] arr,int l,int mid,int r) {
int[] help = new int[r - l + 1];
int p1 = l;
int p2 = mid + 1;
int i = 0;
while(p1 <= mid && p2 <= r) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while(p1 <= mid) {
help[i++] = arr[p1++];
}
while(p2 <= r) {
help[i++] = arr[p2++];
}
for(int j = 0;j < help.length;j++) {
arr[l + j] = help[j];
}
}
4.堆排序
public void swap(int[] arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//对有一定顺序的堆，当前第i个结点取根左右的最大值（这个操作称heapfiy）
public void heapify(int[] tree,int n,int i) {
if(i >= n) return;
int l = 2 * i + 1;
int r = 2 * i + 2;
int max = i;
if(l < n && tree[l] > tree[max]) {
max = l;
}
if(r < n && tree[r] > tree[max]) {
max = r;
}
if(max != i) {//把最大值给父节点
swap(tree,max,i);
heapify(tree,n,max);
}
}
//建立大根堆，从树的倒数第二层第一个结点开始，对每个结点进行heapify操作，然后向上走
public void build_heap(int[] tree,int n) {
int last_node = n - 1;
int parent = (last_node - 1) / 2;//寻找最后一个节点的父节点
for(int i = parent;i >= 0;i--) {
heapify(tree,n,i);
}
}
//建立大根堆之后，每次交换最后一个结点和根节点（最大值），对交换后的根节点继续进行heapify
public void heap_sort(int[] tree,int n) {
build_heap(tree,n);
int i;
for(i = n - 1;i >= 0;i--) {
swap(tree,0,i);
heapify(tree,i,0);
}
}
5.优先级队列
PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>(){
public int compare(Integer a,Integer b){
return a.compareTo(b);
}
});
for(int i=0;i<arr.length;i++){
queue.add(arr[i]);
}
int[] newarr=new int[arr.length];
for(int i=0;i<arr.length;i++){
newarr[i]=queue.poll();
}
return newarr;
单例模式
//饿汉式
public class HungryMan {
private HungryMan() {
}
private final static HungryMan hungryMan =new HungryMan();
public static HungryMan getInstance() {
return hungryMan;
}
}
//双重校验锁实现对象单例
public class Singleton {
private volatile static Singleton singleton;//volatile关键字可以防止jvm指令重排优化，使用了volatile关键字可用来保证其线程间的可见性和有序性
private Singleton() {
}
public static Singleton getInstance() {
//第一次判断是在Synchronized同步代码块外，理由是单例模式只会创建一个实例，并通过getInstance方法返回singleton对象，
// 所以如果已经创建了singleton对象，就不用进入同步代码块，不用竞争锁，直接返回前面创建的实例即可，这样大大提升效率。
if(singleton == null) {
synchronized (Singleton.class) {
//第二次判断原因是为了保证同步，假若线程A通过了第一次判断，进入了同步代码块，但是还未执行，线程B就进来了（线程B获得CPU时间片），
// 线程B也通过了第一次判断（线程A并未创建实例，所以B通过了第一次判断），准备进入同步代码块，假若这个时候不判断，就会存在这种情况：
// 线程B创建了实例，此时恰好A也获得执行时间片，如果不加以判断，那么线程A也会创建一个实例，就会造成多实例的情况。
if(singleton == null) {
singleton = new Singleton();
}
}
}
return singleton;
}
}
//DCL懒汉式(双重检测模式的懒汉式单例)
public class LazyMan {
private LazyMan() {
}
private static volatile LazyMan lazyMan;
public static LazyMan getInstance() {
if(lazyMan == null) {
synchronized (lazyMan.getClass()) {
if(lazyMan == null) {
lazyMan = new LazyMan();//不是一个原子性操作
}
}
}
return lazyMan;
}
}
生产者和消费者模式
//可以使用Reentranclock
public class A {
public static void main(String[] args) {
Data data = new Data();
new Thread(()->{
for (int i = 0; i < 10; i++) {
try {
data.increment();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
},"A").start();
new Thread(()->{
for (int i = 0; i < 10; i++) {
try {
data.decrement();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
},"B").start();
// 判断等待，业务，通知
class Data{ // 数字 资源类
private int number = 0;
//+1
public synchronized void increment() throws InterruptedException {
while (number!=0){ //0
// 等待
this.wait();
}
number++;
System.out.println(Thread.currentThread().getName()+"=>"+number);
// 通知其他线程，我+1完毕了
this.notifyAll();
}
//-1
public synchronized void decrement() throws InterruptedException {
while (number==0){ // 1
// 等待
this.wait();
}
number--;
System.out.println(Thread.currentThread().getName()+"=>"+number);
// 通知其他线程，我-1完毕了
this.notifyAll();
}
}
二叉树
二叉树（Binary tree）是每个节点最多只有两个分支（即不存在分支度大于 2 的节点）的树结构。
二叉树 的分支通常被称作“左子树”或“右子树”。并且，二叉树 的分支具有左右次序，不能随意颠倒。
二叉树 的第 i 层至多拥有 2^(i-1) 个节点，深度为 k 的二叉树至多总共有 2^(k+1)-1 个节点（满二叉树的情况），至少有 2^(k) 个节点
判断图中是否有环的三种方法
- 拓扑排序
无向图：
使用拓扑排序可以判断一个无向图中是否存在环，具体步骤如下：
1）求出图中所有结点的度。
2）将所有度 <= 1 的结点入队。（独立结点的度为 0）
3）当队列不空时，弹出队首元素，把与队首元素相邻节点的度减一。如果相邻节点的度变为一，则将相邻结点入队。
4）循环结束时判断已经访问的结点数是否等于 n。等于 n 说明全部结点都被访问过，无环；反之，则有环。
有向图：
使用拓扑排序判断无向图和有向图中是否存在环的区别在于：
- 在判断无向图中是否存在环时，是将所有度 <= 1 的结点入队；
- 在判断有向图中是否存在环时，是将所有入度 = 0 的结点入队。
- DFS
使用 DFS 可以判断一个无向图和有向中是否存在环。深度优先遍历图，如果在遍历的过程中，发现某个结点有一条边指向已访问过的结点，并且这个已访问过的结点不是上一步访问的结点，则表示存在环。
我们不能仅仅使用一个 bool 数组来表示结点是否访问过。规定每个结点都拥有三种状态，白、灰、黑。开始时所有结点都是白色，当访问过某个结点后，该结点变为灰色，当该结点的所有邻接点都访问完，该节点变为黑色。
那么我们的算法可以表示为：如果在遍历的过程中，发现某个结点有一条边指向灰色节点，并且这个灰色结点不是上一步访问的结点，那么存在环。
- Union-Find Set
我们可以使用并查集来判断一个图中是否存在环：
对于无向图来说，在遍历边（u-v）时，如果结点 u 和结点 v 的“父亲”相同，那么结点 u 和结点 v 在同一个环中。
对于有向图来说，在遍历边（u->v）时，如果结点 u 的“父亲”是结点 v，那么结点 u 和结点 v 在同一个环中。
若有收获，就点个赞吧
0 人点赞
