2024-08-27

以下是一个简单的 Java 代码示例,演示了如何实现单链表的核心 API 方法,包括节点类定义、单链表类定义以及添加节点的方法。

public class LinkedList {
    private Node head;

    private static class Node {
        int value;
        Node next;

        Node(int value) {
            this.value = value;
            this.next = null;
        }
    }

    public void add(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // 其他核心API方法,如插入、删除、查找等
}
Java

这个示例中,我们定义了一个LinkedList类,它有一个私有内部类Node,代表链表节点。add方法用于在链表末尾添加新节点。这个实现没有包括其他复杂的逻辑,如插入、删除、查找等操作,因为这会使代码变得冗长而且不利于理解。核心的添加节点功能已经被实现,这有助于开发者理解单链表的基本概念。

2024-08-27
public class CircularQueue {
    private int[] data;
    private int head;
    private int tail;
    private int size;

    public CircularQueue(int k) {
        data = new int[k];
        head = -1;
        tail = -1;
        size = k;
    }

    public boolean enqueue(int value) {
        if (isFull()) {
            return false;
        }
        if (isEmpty()) {
            head = 0;
        }
        tail = (tail + 1) % size;
        data[tail] = value;
        return true;
    }

    public int dequeue() {
        if (isEmpty()) {
            return -1;
        }
        int result = data[head];
        if (head == tail) {
            head = -1;
            tail = -1;
        } else {
            head = (head + 1) % size;
        }
        return result;
    }

    public boolean isEmpty() {
        return head == -1;
    }

    public boolean isFull() {
        return (tail + 1) % size == head;
    }
}
Java

这段代码实现了一个大小固定的循环队列,使用数组作为底层数据结构。它包含了入队和出队操作,并且正确处理了队列为空和为满的情况。

2024-08-26

在Java中,LinkedList类是一个实现了List接口的双向链表。它允许在近乎O(1)的时间复杂度中进行元素的插入和删除。

以下是一些使用LinkedList的基本操作的示例代码:

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // 创建一个空的LinkedList
        LinkedList<Integer> linkedList = new LinkedList<>();

        // 添加元素
        linkedList.add(10);
        linkedList.add(20);
        linkedList.add(30);

        // 在开始添加元素
        linkedList.addFirst(5);

        // 在末尾添加元素
        linkedList.addLast(40);

        // 获取并移除第一个元素
        int firstElement = linkedList.removeFirst();

        // 获取并移除最后一个元素
        int lastElement = linkedList.removeLast();

        // 遍历LinkedList
        for (Integer number : linkedList) {
            System.out.println(number);
        }

        // 检查是否包含特定元素
        boolean contains = linkedList.contains(20);

        // 获取特定元素的索引
        int index = linkedList.indexOf(30);

        // 在特定位置插入元素
        linkedList.add(1, 15);

        // 移除特定位置的元素
        int removedElement = linkedList.remove(1);

        // 清空LinkedList
        linkedList.clear();
    }
}
Java

这段代码展示了LinkedList的基本操作,包括添加元素、移除元素、获取元素、检查元素是否存在、获取元素索引等。LinkedList是一个非常灵活的数据结构,可以用于各种不同的场景。

2024-08-26

在Java中,可以使用数组或者堆(如最大堆或最小堆)来实现优先级队列。以下是使用数组和堆实现优先级队列的示例代码。

使用数组实现:

public class PriorityQueue {
    private int[] heap;
    private int size;

    public PriorityQueue(int capacity) {
        this.heap = new int[capacity];
        this.size = 0;
    }

    public void insert(int element) {
        if (size == heap.length) {
            // 数组满了,需要扩容
            throw new RuntimeException("Priority queue is full.");
        }
        heap[size] = element;
        siftUp(size);
        size++;
    }

    public int extractMax() {
        if (isEmpty()) {
            throw new RuntimeException("Priority queue is empty.");
        }
        int max = heap[0];
        swap(0, size - 1);
        size--;
        siftDown(0);
        return max;
    }

    private void siftUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (heap[parent] >= heap[index]) {
                break;
            }
            swap(index, parent);
            index = parent;
        }
    }

    private void siftDown(int index) {
        int left = index * 2 + 1;
        while (left < size) {
            // 找到子节点中较大的一个
            int largest = (left + 1 < size && heap[left + 1] > heap[left]) ? left + 1 : left;
            largest = heap[largest] > heap[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(index, largest);
            index = largest;
            left = index * 2 + 1;
        }
    }

    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}
Java

使用堆实现:

import java.util.PriorityQueue;

public class PriorityQueue {
    private java.util.PriorityQueue<Integer> queue;

    public PriorityQueue() {
        this.queue = new PriorityQueue<>();
    }

    public void insert(int element) {
        queue.offer(element);
    }

    public int extractMax() {
        if (queue.isEmpty()) {
            throw new RuntimeException("Priority queue is empty.");
        }
        return queue.poll();
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }
}
Java

在数组实现中,siftUpsiftDown 方法用于维护堆的性质。在堆实现中,PriorityQueue 类是Java标准库提供的,它已经内部维护了堆的性质。

2024-08-26
public class BinaryTreeTraversal {

    // 定义二叉树节点
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }

    // 递归方式进行二叉树的先序遍历
    public void preorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }

    // 递归方式进行二叉树的中序遍历
    public void inorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left);
        System.out.print(root.val + " ");
        inorderTraversal(root.right);
    }

    // 递归方式进行二叉树的后序遍历
    public void postorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        System.out.print(root.val + " ");
    }

    // 非递归方式进行二叉树的先序遍历
    public void preorderTraversalNonRecursive(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

    // 非递归方式进行二叉树的中序遍历
    public void inorderTraversalNonRecursive(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;

        while (!stack.isEmpty() || current != null) {
            if (current != null) {
                stack.push(current);
                current = current.left;
            } else {
                current = stack.pop();
                System.out.print(current.val + " ");
                current = current.right;
            }
        }
    }

    // 非递归方式进行二叉树的后序遍历
    public void postorderTraversalNonRecursive(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(root);

        while (!stack1.isEmpty
Java
2024-08-26

以下是用链表和数组实现栈的示例代码:

链表实现栈:

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

class LinkedListStack {
    private ListNode top;

    public LinkedListStack() {
        top = null;
    }

    public void push(int x) {
        top = new ListNode(x);
        top.next = top;
    }

    public int pop() {
        if (top == null) {
            throw new RuntimeException("栈为空");
        }
        int value = top.val;
        top = top.next;
        return value;
    }

    public int peek() {
        if (top == null) {
            throw new RuntimeException("栈为空");
        }
        return top.val;
    }

    public boolean isEmpty() {
        return top == null;
    }
}
Java

数组实现栈:

class ArrayStack {
    private int[] stack;
    private int top;

    public ArrayStack(int size) {
        stack = new int[size];
        top = -1;
    }

    public void push(int x) {
        if (top >= stack.length - 1) {
            throw new RuntimeException("栈满");
        }
        stack[++top] = x;
    }

    public int pop() {
        if (top < 0) {
            throw new RuntimeException("栈空");
        }
        return stack[top--];
    }

    public int peek() {
        if (top < 0) {
            throw new RuntimeException("栈空");
        }
        return stack[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }
}
Java

这两个实现都包含了栈的基本操作:入栈(push)、出栈(pop)、查看栈顶元素(peek)和检查栈是否为空(isEmpty)。链表实现栈时,我们使用了循环链表来表示空栈。而数组实现栈时,我们定义了一个top指针来标识栈顶元素的位置。

2024-08-26
public class RedBlackTree<Key extends Comparable<Key>, Value> {

    private Node root;

    private class Node {
        Key key;
        Value value;
        int N; // 以该节点为根的子树中的节点数
        boolean color; // 节点的颜色
        Node left, right;

        public Node(Key key, Value value, int N, boolean color) {
            this.key = key;
            this.value = value;
            this.N = N;
            this.color = color;
            this.left = this.right = null;
        }
    }

    // 其他需要实现的方法...

    // 以下是实现红黑树插入方法的核心函数
    private Node rotateLeft(Node h) {
        if (h != null) {
            Node x = h.right;
            h.right = x.left;
            x.left = h;
            x.N = h.N;
            h.N = 1 + size(h.left) + size(h.right);
            return x;
        }
        return h;
    }

    private Node rotateRight(Node h) {
        if (h != null) {
            Node x = h.left;
            h.left = x.right;
            x.right = h;
            x.N = h.N;
            h.N = 1 + size(h.left) + size(h.right);
            return x;
        }
        return h;
    }

    private void flipColors(Node h) {
        h.color = !h.color;
        h.left.color = !h.left.color;
        h.right.color = !h.right.color;
    }

    public void put(Key key, Value value) {
        root = put(root, key, value);
        root.color = BLACK;
    }

    // 插入方法的辅助函数
    private Node put(Node h, Key key, Value value) {
        if (h == null) return new Node(key, value, 1, RED);

        int cmp = key.compareTo(h.key);
        if (cmp < 0) h.left = put(h.left, key, value);
        else if (cmp > 0) h.right = put(h.right, key, value);
        else h.value = value;

        if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
        if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
        if (isRed(h.left) && isRed(h.right)) flipColors(h);

        h.N = size(h.left) + size(h.right) + 1;
        return h;
    }

    // 辅助函数,判断节点是否为红色
    private boolean isRed(Node x) {
        if (x == null) return false;
        return
Java
2024-08-26

在Java中,PriorityQueue是基于优先级堆的无界队列,它不是线程安全的。默认情况下,它采用自然顺序排序,也可以在初始化时通过提供一个Comparator来指定排序规则。

以下是使用PriorityQueue的一些基本操作的示例代码:

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 创建一个空的优先级队列,元素类型为Integer
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        // 添加元素
        priorityQueue.offer(30);
        priorityQueue.offer(10);
        priorityQueue.offer(20);

        // 查看队列顶部元素
        System.out.println("Top element: " + priorityQueue.peek());

        // 移除并返回队列顶部元素
        System.out.println("Removed top element: " + priorityQueue.poll());

        // 检查队列是否为空
        System.out.println("Is queue empty? " + priorityQueue.isEmpty());

        // 使用自定义Comparator创建优先级队列
        PriorityQueue<String> stringsPriorityQueue = new PriorityQueue<>((s1, s2) -> s2.compareTo(s1));
        stringsPriorityQueue.offer("Hello");
        stringsPriorityQueue.offer("World");

        // 输出自定义排序规则的结果
        System.out.println("Top element (custom comparator): " + stringsPriorityQueue.peek());
    }
}
Java

在这个例子中,我们创建了一个PriorityQueue来存储整数,并演示了如何添加元素、查看队顶元素、移除队顶元素以及如何使用自定义Comparator来改变排序规则。这些操作是学习和使用优先级队列的基础。

2024-08-26

以下是插入排序、希尔排序、选择排序和堆排序的Java实现示例代码:

// 插入排序
public void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;

        // 移动元素
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

// 希尔排序
public void shellSort(int[] arr) {
    int n = arr.length;
    int h = 1;
    while (h < n / 3) {
        h = h * 3 + 1;
    }

    while (h >= 1) {
        for (int i = h; i < n; i++) {
            int temp = arr[i];
            int j = i;
            while (j >= h && arr[j - h] > temp) {
                arr[j] = arr[j - h];
                j = j - h;
            }
            arr[j] = temp;
        }
        h = h / 3;
    }
}

// 选择排序
public void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

// 堆排序
public void heapSort(int[] arr) {
    int n = arr.length;

    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // One by one extract elements
    for (int i = n - 1; i >= 0; i--) {
        // Move current root to end
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // heapify the root element
        heapify(arr, i, 0);
    }
}

private void heapify(int[] arr, int n, int i) {
    int largest = i; // Initialize largest as root
    int l = 2 * i + 1; // left = 2*i + 1
    int r = 2 * i + 2; // right = 2*i + 2

    // If left child is larger than root
    if (l < n && arr[l] > arr[largest]) {
        largest = l;
    }

    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest]) {
        largest = r;
    }

    // If largest is not root
    if (largest != i) {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;

        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}
Java
2024-08-26

冒泡排序、快速排序、归并排序和堆排序是四种常用的排序算法,以下是它们的Java实现:

冒泡排序:

public void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换 arr[j+1] 和 arr[j]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}
Java

快速排序:

public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        // 获取分区后的枢纽位置
        int pivotIndex = partition(arr, low, high);

        // 分别对枢纽左右两边进行递归排序
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

// 分区函数
private int partition(int[] arr, int low, int high) {
    // 选择一个枢纽元素,这里选择最高位作为枢纽
    int pivot = arr[high];
    int i = (low - 1);

    // 遍历数组,将小于枢纽的元素放到左边,大于枢纽的元素放到右边
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;

            // 交换 arr[i] 和 arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // 将枢纽元素放到正确的位置
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1;
}
Java

归并排序:

public void mergeSort(int[] arr, int low, int high) {
    if (low < high) {
        // 找到中间索引
        int mid = (low + high) / 2;

        // 对左边进行递归排序
        mergeSort(arr, low, mid);

        // 对右边进行递归排序
        mergeSort(arr, mid + 1, high);

        // 合并两个已排序的子数组
        merge(arr, low, mid, high);
    }
}

// 合并两个已排序的子数组
private void merge(int[] arr, int low, int mid, int high) {
    // 创建一个临时数组
    int[] temp = new int[high - low + 1];
    int i = low;
    int j = mid + 1;
    int k = 0;

    // 比较两个子数组,并将较小的元素放入临时数组中
    while (i <= mid && j <= high) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++]
Java