分类目录归档：编程

鸡蛋掉落问题

一、暴力递归法

首先，我们来看扔鸡蛋这个事儿本身，假设在N层的高楼中有K个鸡蛋，这个时候我们在n层扔了一个鸡蛋，那么这一次动作，把整个高楼其实就分成了两部分，一部分是1楼到n楼，这是一个层高为n的新楼，我们暂时叫它一号楼；另一部分是n+1到N楼，这是一栋新产生的层高为N-(n+1)+1=N-n的新楼，我们叫他二号楼。

继续阅读 →

TOP k

发表评论

继续阅读 →

排序算法

发表评论

堆排序继续阅读 →

树相关

发表评论

前缀树

继续阅读 →

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;
    }
}