LRU 的实现

使用. hashMap + Deque(ArrayDeque) 实现

public class LruJavaUtil {


    public static class LRUCache6<K, V> {
        private final int capacity;
        private final Map<K, V> cache;
        private final Deque<K> accessOrder;


        public LRUCache6(int capacity) {
            this.capacity = capacity;
            cache = new HashMap<>();
            this.accessOrder = new ArrayDeque<>();
        }

        public V get(K key) {
            if (!cache.containsKey(key)) {
                return null;
            }

            // 更新访问顺序
            updateAccess(key);
            return cache.get(key);
        }

        private void updateAccess(K key) {
            // 实际项目中可以使用更高效的数据结构
            accessOrder.remove(key); // O(n)
            accessOrder.addFirst(key);
        }

        public void put(K key, V value) {
            if (cache.containsKey(key)) {
                // 更新现有键值
                cache.put(key, value);
                updateAccess(key);
            } else {
                if (cache.size() >= capacity) {
                    // 移除最久未使用的
                    K oldestKey = accessOrder.removeLast();
                    cache.remove(oldestKey);
                }
                cache.put(key, value);
                accessOrder.addFirst(key);
            }
        }

        public void printCache() {
            System.out.println("访问顺序: " + accessOrder);
            System.out.println("缓存内容: " + cache);
        }
    }

    public static void main(String[] args) {
        LRUCache6<Integer, String> cache = new LRUCache6<>(3);

        cache.put(1, "A");
        cache.put(2, "B");
        cache.put(3, "C");
        cache.printCache();

        System.out.println();
        System.out.println();

        cache.get(2); // 访问 B
        cache.printCache();

        System.out.println();
        System.out.println();

        cache.put(4, "D"); // 添加 D，A 被移除
        cache.printCache();
    }
}

使用自定义链表实现

package other;

import java.util.HashMap;

class Node {
    Integer key;
    int value;
    Node prev;
    Node next;

    public Node() {
    }

    Node(Integer key, int value) {
        this.key = key;
        this.value = value;
    }

    public Integer getKey() {
        return key;
    }
}

class LRU {
    HashMap<Integer, Node> keyMap = new HashMap<Integer, Node>();
    int size;
    Node head;
    Node tail;

    int capacity;

    LRU(int size) {
        capacity = size;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    public int get(Integer key) {
        Node node = keyMap.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    public void put(Integer key, int value) {
        Node node = keyMap.get(key);
        if (node == null) {
            Node newNode = new Node(key, value);
            keyMap.put(key, newNode);
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                Node rev = removeTail();
                keyMap.remove(rev.getKey());
                --size;
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToHead(Node newNode) {
        newNode.prev = head;
        newNode.next = head.next;
        head.next.prev = newNode;
        head.next = newNode;
    }

    private Node removeTail() {
        Node node = tail.prev;
        removeNode(node);
        return node;
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }
}

public class Main {
    public static void main(String[] args) {
        LRU lru = new LRU(2);
        lru.put(1, 1);
        lru.put(2, 2);
        System.out.println(lru.get(1));
        lru.put(3, 3);
        lru.get(2);
        lru.put(4, 4);
        System.out.println(lru.get(1));
        System.out.println(lru.get(3));
        System.out.println(lru.get(4));
    }
}

二分查找法的实现

注意是在有序集合中查找时。

public class BinarySearch {
    /**
     * 二分查找（迭代版本）
     * @param arr 有序数组（升序）
     * @param target 目标值
     * @return 目标值的索引，如果不存在返回 -1
     */
    public static int binarySearch(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            // 防止整数溢出：使用 >>> 1 或 left + (right - left) / 2
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;  // 目标在右侧
            } else {
                right = mid - 1; // 目标在左侧
            }
        }
        
        return -1; // 未找到
    }

排序算法总结与几道排序题

插入排序，快排，堆排和归并排序

快速排序

public class QuickSort {
    
    // 版本1：基础快速排序（Lomuto分区方案）
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        quickSort(arr, 0, arr.length - 1);
    }
    
    private static 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);
        }
    }
    
    // Lomuto分区方案
    private static 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++;
                swap(arr, i, j);
            }
        }
   
        // 将基准放到正确位置
        swap(arr, i + 1, high);
        return i + 1;
    }  
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    // 测试
    public static void main(String[] args) {
        int[] arr1 = {10, 7, 8, 9, 1, 5};
        quickSort(arr1);
        System.out.println("快速排序结果: " + Arrays.toString(arr1));
        
        int[] arr2 = {3, 7, 8, 5, 2, 1, 9, 5, 4};
        quickSortHoare(arr2);
        System.out.println("Hoare分区结果: " + Arrays.toString(arr2));
        
        int[] arr3 = {3, 5, 2, 5, 1, 5, 4, 5, 3};
        quickSortThreeWay(arr3);
        System.out.println("三路快排结果: " + Arrays.toString(arr3));
    }
}

归并排序

public class MergeSort {
    
    // 自上而下的归并排序（递归）
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        int[] temp = new int[arr.length];  // 临时数组
        mergeSort(arr, 0, arr.length - 1, temp);
    }
    
    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            
            // 递归排序左右两半
            mergeSort(arr, left, mid, temp);
            mergeSort(arr, mid + 1, right, temp);
            
            // 合并已排序的两部分
            merge(arr, left, mid, right, temp);
        }
    }
    
    // 合并两个有序子数组
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;      // 左子数组起始索引
        int j = mid + 1;   // 右子数组起始索引
        int k = 0;         // 临时数组索引
        
        // 合并两个有序数组
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        
        // 复制左子数组剩余元素
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        
        // 复制右子数组剩余元素
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        
        // 将临时数组复制回原数组
        k = 0;
        while (left <= right) {
            arr[left++] = temp[k++];
        }
    }
    
    // 自底向上的归并排序（非递归）
    public static void mergeSortBottomUp(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        
        int n = arr.length;
        int[] temp = new int[n];
        
        // 子数组大小从1开始，每次翻倍
        for (int size = 1; size < n; size *= 2) {
            // 合并相邻的子数组
            for (int left = 0; left < n - size; left += 2 * size) {
                int mid = left + size - 1;
                int right = Math.min(left + 2 * size - 1, n - 1);
                merge(arr, left, mid, right, temp);
            }
        }
    }
    
    // 测试
    public static void main(String[] args) {
        int[] arr1 = {12, 11, 13, 5, 6, 7};
        mergeSort(arr1);
        System.out.println("递归归并排序: " + Arrays.toString(arr1));
        
        int[] arr2 = {38, 27, 43, 3, 9, 82, 10};
        mergeSortBottomUp(arr2);
        System.out.println("非递归归并排序: " + Arrays.toString(arr2));
    }
}

堆排序

public class HeapSort {
    
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        
        int n = arr.length;
        
        // 1. 构建最大堆（从最后一个非叶子节点开始）
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        
        // 2. 逐个提取堆顶元素
        for (int i = n - 1; i > 0; i--) {
            // 将当前堆顶（最大值）与末尾元素交换
            swap(arr, 0, i);
            
            // 对剩余元素重新堆化
            heapify(arr, i, 0);
        }
    }
    
    // 堆化：维护以i为根的子树满足最大堆性质
    private static void heapify(int[] arr, int heapSize, int i) {
        int largest = i;      // 假设当前节点最大
        int left = 2 * i + 1; // 左子节点索引
        int right = 2 * i + 2; // 右子节点索引
        
        // 如果左子节点存在且大于当前最大值
        if (left < heapSize && arr[left] > arr[largest]) {
            largest = left;
        }
        
        // 如果右子节点存在且大于当前最大值
        if (right < heapSize && arr[right] > arr[largest]) {
            largest = right;
        }
        
        // 如果最大值不是当前节点，交换并递归堆化
        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, heapSize, largest);
        }
    }
    
    // 辅助方法：交换数组元素
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    // 可选：最大堆类（完整实现）
    static class MaxHeap {
        private int[] heap;
        private int size;
        private int capacity;
        
        public MaxHeap(int capacity) {
            this.capacity = capacity;
            this.size = 0;
            this.heap = new int[capacity];
        }
        
        public MaxHeap(int[] arr) {
            this.capacity = arr.length;
            this.size = arr.length;
            this.heap = arr.clone();
            
            // 构建堆
            for (int i = size / 2 - 1; i >= 0; i--) {
                heapify(i);
            }
        }
        
        private void heapify(int i) {
            int largest = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            
            if (left < size && heap[left] > heap[largest]) {
                largest = left;
            }
            
            if (right < size && heap[right] > heap[largest]) {
                largest = right;
            }
            
            if (largest != i) {
                int temp = heap[i];
                heap[i] = heap[largest];
                heap[largest] = temp;
                heapify(largest);
            }
        }
        
        public int extractMax() {
            if (size == 0) throw new IllegalStateException("Heap is empty");
            
            int max = heap[0];
            heap[0] = heap[size - 1];
            size--;
            heapify(0);
            return max;
        }
    }
    
    // 测试
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        heapSort(arr);
        System.out.println("堆排序结果: " + Arrays.toString(arr));
        
        // 使用MaxHeap类测试
        int[] arr2 = {3, 2, 1, 5, 6, 4};
        MaxHeap heap = new MaxHeap(arr2);
        System.out.println("使用MaxHeap提取元素:");
        for (int i = 0; i < arr2.length; i++) {
            System.out.print(heap.extractMax() + " ");
        }
    }
}

插入排序

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        
        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--;
            }
            arr[j + 1] = key;  // 插入元素
        }
    }
    
    // 测试
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        insertionSort(arr);
        System.out.println("插入排序结果: " + Arrays.toString(arr));
    }
}

Java优先队列实现大顶堆和小顶堆

//默认为小顶堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a,b)->a-b);
 
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
           @Override
           public int compare(Integer a, Integer b) {
               return a - b;
           }
 });
 
//大顶堆
PriorityQueue<Integer> maxHeap4 = new PriorityQueue<>(Comparator.reverseOrder());

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, (a,b)->b-a);
 
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
           @Override
           public int compare(Integer a, Integer b) {
               return b - a;
           }
 });
自定义对象堆
class Student {
    String name;
    int score;
    
    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }
    
    @Override
    public String toString() {
        return name + ":" + score;
    }
}

public class CustomObjectHeap {
    public static void main(String[] args) {
        // 按分数的小顶堆（最低分优先）
        PriorityQueue<Student> minScoreHeap = new PriorityQueue<>(
            Comparator.comparingInt(s -> s.score)
        );
        
        // 按分数的大顶堆（最高分优先）
        PriorityQueue<Student> maxScoreHeap = new PriorityQueue<>(
            (s1, s2) -> s2.score - s1.score
        );
        
        // 按姓名字典序的小顶堆
        PriorityQueue<Student> nameHeap = new PriorityQueue<>(
            Comparator.comparing(s -> s.name)
        );

算法-贪心（Java实现）

• 剑指 Offer II 019. 最多删除一个字符得到回文

算法-并查集（Java实现）

• 剑指 Offer II 116. 省份数量

算法-排序（Java实现）

• 剑指 Offer II 074. 合并区间

算法-数学/模拟（Java实现）

• 剑指 Offer 44. 数字序列中某一位的数字
• 剑指 Offer 66. 构建乘积数组

算法-滑动窗口与前缀和

• 最长重复子数组（给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 ）
• 11.盛最多水的容器
• 剑指 Offer II 010. 和为 k 的子数组
• 剑指 Offer II 008. 和大于等于 target 的最短子数组
• 剑指 Offer II 009. 乘积小于 K 的子数组
• 剑指 Offer II 057. 值和下标之差都在给定的范围内
• 剑指 Offer II 012. 左右两边子数组的和相等

算法-二分查找（Java实现）

• 剑指 Offer 11. 旋转数组的最小数字
• 寻找重复数

数据结构专练-链表

• 剑指 Offer 35. 复杂链表的复制
• 剑指 Offer 25. 合并两个排序的链表
• 剑指 Offer II 025. 链表中的两数相加
• 剑指 Offer II 077. 链表排序
• 剑指 Offer II 022. 链表中环的入口节点
• 82.删除排序链表中的重复元素 II

算法-字典树（Java实现）

• 代码实现前缀树
• 212. 单词搜索 II
• 剑指 Offer II 063. 替换单词

数据结构专练-字符串

• 剑指 Offer 58 - I. 翻转单词顺序
• 求两个字符串的最大公共子串(一看到两个字符串的“最值”问题，一般想到二维dp)
• 剑指 Offer II 095. 最长公共子序列（类似的最长子序列等等都是DP的经典解法）
• 剑指 Offer II 063. 替换单词
• 剑指 Offer 45. 把数组排成最小的数
• 滑动窗口模板与思路
• 最小覆盖子串
• 剑指 Offer II 016. 不含重复字符的最长子字符串（里面有滑动窗口的具体实现）
• 剑指 Offer II 018. 有效的回文
• 5.最长回文子串

算法-搜索DFS与BFS（Java实现）

• 剑指 Offer 12. 矩阵中的路径
• 完全二叉树的节点个数
• 剑指 Offer 34. 二叉树中和为某一值的路径
• 剑指 Offer 38. 字符串的排列
• 括号生成
• N皇后的问题
• 数独问题
• 组合总和（给定数组和target，找所有实现）
• 剑指 Offer II 079. 所有子集
• 剑指 Offer II 084. 含有重复元素集合的全排列
  给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。

算法-动态规划（Java实现）

• 最小路径和
• 把数字翻译成字符串
• 带因子的二叉树
• 剑指 Offer 49. 丑数
• 爬楼梯
• 三角形最小路径和
• 乘积最大子数组
• 121 股票买卖序列
• 121 从始至终只能买卖一次股票系列
• 122 可同天，可以交易无数次的情况
• 最长递增子序列
• 剑指 Offer 42. 连续子数组的最大和
• 剑指 Offer II 103. 最少的硬币数目
• 剑指 Offer II 102. 加减的目标值

算法-位运算（Java实现）

• 位运算的一些技巧
• 剑指 Offer 56 - I. 数组中数字出现的次数
• 位1的个数
• 2 的幂 与 338. 比特位计数

算法-哈希表（Java实现）

1. 两数之和
2. 三数之和
   方法一：使用哈希表存储第三个数字，然后使用两数之和的思路
   方法二：夹逼法
3. 四数之和
4. 有效的字母异位词
5. 剑指 Offer II 004. 只出现一次的数字

算法-递归和分治（Java实现）

• 50 实现 pow(x, n) ，即计算 x 的 n 次幂函数
  思路一：快速幂 + 递归
  思路二：快速幂 + 迭代 + 位运算
• 169 求众数题目（剑指 Offer 39. 数组中出现次数超过一半的数字、169. 多数元素）

算法-树&二叉树&二叉搜索树（Java实现）

• 树的几种遍历方式
• 验证二叉搜索树
  思路：中序遍历如果是得到一个排序好的数组的话，那么肯定就是二叉搜索树
  思路：递归，如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。
• 最近公共祖先
• 求最小深度和最大深度
  思路：DFS 搜索
  思路：BFS 搜索
• 652.寻找重复的子树
• 剑指 Offer II 050. 向下的路径节点之和
• 二叉树的右视图
• 剑指 Offer 28. 对称的二叉树
• 剑指 Offer 27. 二叉树的镜像
• 1448.统计二叉树中好节点的数目
• 剑指 Offer 26. 树的子结构
• 450.删除二叉搜索树中的节点
• 对称二叉树：实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

算法-栈和队列（Java实现）

单调栈类型问题

• 剑指 Offer 59 - II. 队列的最大值（单调队列类问题）
• 739.每日温度

其他

栈和队列以及优先队列

• 栈的压入、弹出序列
• 返回滑动窗口中的最大值
  解法一：
  解法二：
• 返回数据流中的第K大元素
• 20.有效的括号
• 剑指 Offer II 037. 小行星碰撞

所有代码地址：Javastudy/algorithm/src/main/java