代码实现

单例模式

懒汉式

public class Singleton {
    private static Singleton instance;

    private Singleton() {}

    public static synchronized Singleton getInstance() {
        if (instance == null) {
            instance = new Singleton();
        }
        return instance;
    }
}

饿汉式

public class SingleObject {
    private static SingleObject instance=new SingleObject();

    private SingleObject(){}

    public static SingleObject getInstance(){
        return instance;
    }
}

观察者模型

import java.util.ArrayList;
import java.util.List;

// 定义观察者的接口
interface Observer {
    void update(String message);
}

// 定义主题的接口
interface Subject {
    void registerObserver(Observer o);
    void removeObserver(Observer o);
    void notifyObservers(String message);
}

// 具体主题实现
class ConcreteSubject implements Subject {
    private List<Observer> observers = new ArrayList<>();
    private String state;

    @Override
    public void registerObserver(Observer o) {
        observers.add(o);
    }

    @Override
    public void removeObserver(Observer o) {
        observers.remove(o);
    }

    @Override
    public void notifyObservers(String message) {
        for (Observer observer : observers) {
            observer.update(message);
        }
    }

    public void setState(String state) {
        this.state = state;
        notifyObservers(state);
    }
}

// 具体观察者实现
class ConcreteObserver implements Observer {
    private String name;

    public ConcreteObserver(String name) {
        this.name = name;
    }

    @Override
    public void update(String message) {
        System.out.println(name + " received: " + message);
    }
}

public class ObserverPatternDemo {
    public static void main(String[] args) {
        ConcreteSubject subject = new ConcreteSubject();
        Observer observer1 = new ConcreteObserver("Observer 1");
        Observer observer2 = new ConcreteObserver("Observer 2");

        subject.registerObserver(observer1);
        subject.registerObserver(observer2);

        // 更新主题的状态
        subject.setState("State has changed.");
    }
}

排序算法

冒泡排序

 public static void sort(int[] str) {
        if (str == null || str.length == 0) {
            return;
        }

        for (int i = 0; i < str.length; i++) {
            for (int j = 0; j < str.length - 1 - i; j++) {
                if (str[j] > str[j + 1]) {
                    int temp = str[j];
                    str[j] = str[j + 1];
                    str[j + 1] = temp;
                }
            }
        }
    }

选择排序

平均时间复杂度为O(nlog2n) 且 最坏O(n²)

 public static void sort (int[] str) {

        if(str==null || str.length==0){
            return;
        }
        for (int i = 0; i < str.length; i++) {
            int min = i;
            for (int j = i; j < str.length; j++) {
                if(str[min]>str[j]){
                    min = j;
                }
            }
            // 将最小值放在索引为i的位置
            if(min!=i){
                int temp = str[i];
                str[i] = str[min];
                str[min] = temp;
            }
        }
    }

插入排序

最优时间复杂度为O(n),最坏的情况是O(n^2)

public static void sort(int[] str) {

    for (int i = 1; i < str.length; i++) {
        int temp = str[i];
        int j = i - 1;
        while (j >= 0) {
            if (str[j] > temp) {
                str[j + 1] = str[j];
                j--;
            } else {
                break;
            }
        }
        str[j + 1] = temp;
    }
}

希尔排序

public static void sort(int[] str) {

    if (str == null || str.length == 0) {
        return;
    }

    for (int temp = str.length / 2; temp >= 1; temp /= 2) {
        for (int i = temp; i < str.length; i++) {
            int flag = str[i];
            int j = i - temp;
            while (j >= 0) {
                if (str[j] > flag) {
                    str[j + temp] = str[j];
                    j -= temp;
                } else {
                    break;
                }
            }
            str[j + temp] = flag;
        }
    }
}

归并排序

public static int[] sort(int[] str) {
        if (str == null || str.length < 2) {
            return str;
        }
        int middle = str.length / 2;
        int[] left = Arrays.copyOfRange(str, 0, middle);
        int[] right = Arrays.copyOfRange(str, middle, str.length);
        return merge(sort(left), sort(right));
    }

    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        int m = 0;
        int n = 0;
        while (m < left.length && n < right.length) {
            if (left[m] < right[n]) {
                result[i++] = left[m++];
            } else {
                result[i++] = right[n++];
            }
        }
        while (m < left.length) {
            result[i++] = left[m++];
        }

        while (n < right.length) {
            result[i++] = right[n++];
        }
        return result;
    }

快速排序

平均时间复杂度为O(nlogn) 且 最坏O(n²)

public static void sort(int[] str, int left, int right) {
    // 递归到底的情况
    if (left >= right) {
        return;
    }

    // 递归操作
    int pivot = str[left];
    int i = left;
    int j = right;
    while (i < j) {
        // 从右边开始找第一个小于pivot的元素
        while (i < j && str[j] > pivot) {
            j--;
        }
        // 替换
        if (i < j) {
            str[i] = str[j];
            i++;
        }
        // 从左边开始找到第一个比pivot大的元素、
        while (i < j && str[i] < pivot){
            i++;
        }
        // 替换
        if(i < j){
            str[j] = str[i];
            j--;
        }
    }
    str[i] = pivot;
    sort(str, left, i-1);
    sort(str, i+1, right);
}

堆排序

public static void sort(int str[]) {
    if (str == null || str.length == 0) {
        return;
    }
    // 构建堆，将完全二叉树整理成堆
    heapify(str);

    // 排序
    for (int i = 0; i < str.length-1; i++) {
        // 将首位元素替换
        int temp = str[0];
        str[0] = str[i];
        str[i] = temp;

        // 整理成堆
        siftDown(0, str, i);
    }
}

public static void heapify(int[] str) {

    // 找到最后一个元素的父亲结点
    int parentIndex = getParentIndex(str.length - 1);

    // 从最后一个元素的父亲结点开始进行下沉操作，直到根结点
    for (; parentIndex >= 0; parentIndex--) {
        siftDown(parentIndex, str, str.length);
    }
}

// 获取堆的根结点，根结点一般都是最中间
public static int getParentIndex(int index) {
    if (index < 0) {
        throw new IllegalArgumentException("index is invalid!");
    }
    if (index == 0) { // 处理根结点
        return -1;
    }
    return (index - 1) / 2;
}

// 根据当前数组所在的索引获取左孩子结点的索引
private static int getLeftChileIndex(int index) {
    return index * 2 + 1;
}

// 下沉操作
private static void siftDown(int curIndex, int[] str, int length) {
    int leftChildIndex = getLeftChileIndex(curIndex);
    int changeIndex = leftChildIndex;
    while (leftChildIndex < length) {
        int rightChildIndex = leftChildIndex + 1;
        if (rightChildIndex < length && str[rightChildIndex] > str[leftChildIndex]) {
            changeIndex = rightChildIndex;
        }
        if(str[changeIndex]>str[curIndex]){
            // 交换操作
            int temp = str[curIndex];
            str[curIndex] = str[changeIndex];
            str[changeIndex] = temp;
            curIndex = changeIndex;
            leftChildIndex = getLeftChileIndex(curIndex);
            changeIndex = leftChildIndex;
        }else{
            break;
        }
    }
}

查找算法

二分查找

static int binarySearch2(int array[],int left,int right,int target){
    if(left<=right){
        int mid=(left+right)/2;
        /*搜索到对应元素*/
        if(array[mid]==target){
            return mid;
        }else if(array[mid]<target){
            /*array[mid]小于target，即要寻找的元素在右半边，所以需要设定左边界为mid+1，搜索右半边*/
            return binarySearch2(array,mid+1,right,target);
        }else{
            /*array[mid]大于target，即要寻找的元素在左半边，所以需要设定右边界为mid-1，搜索左半边*/
            return binarySearch2(array,left,mid-1,target);
        }
    }else{
        return -1;
    }
}

二叉树深度优先遍历

先序遍历

//先序遍历
public void startErgodic(TreeNode node) {
    //如果节点不是空节点就进行输出再进行递归
    if(node!=null) {
        System.out.print(node.val+" ");
        startErgodic(node.leftNode);
        startErgodic(node.rightNode);
    }
}

中序遍历

//中序遍历
public void midErgodic(TreeNode node) {
    if(node!=null) {
        midErgodic(node.leftNode);
        System.out.print(node.val+" ");
        midErgodic(node.rightNode);
    }
}

后序遍历

//后序遍历
public void endErgodic(TreeNode node) {
    if(node!=null) {
        endErgodic(node.leftNode);
        endErgodic(node.rightNode);
        System.out.print(node.val+" ");
    }
}

二叉树广度优先遍历

队列辅助

//广度优先遍历
public void Order() {
    //通过jdk的接口类创建一个链表创建的队列，泛型内填入的是二叉树节点类型
    LinkedList<TreeNode> queue=new LinkedList<>();
    //队列进行入队
    queue.push(root);
    //判断队列是否为空
    while(!queue.isEmpty()) {
        //记录出队的值
        TreeNode treeNode=queue.pop();
        //输出出队的值
        System.out.print(treeNode.val+" ");
        //先遍历每层的左节点元素，不是空接着压入队列
        if(treeNode.leftNode!=null) {
            queue.push(treeNode.leftNode);
        }
        //后遍历每层的右节点元素，不是空接着压入队列
        if(treeNode.rightNode!=null) {
            queue.push(treeNode.rightNode);
        }
    }
}