Android面试之基础算法总结

一、什么是 LRU 缓存？

LRU（Least Recently Used）即最近最少使用算法，是一种常用的缓存淘汰策略。其核心思想是：当缓存容量已满时，优先淘汰最久未被访问的数据，以保证缓存始终存储高频访问的热点数据。

LRU 缓存需要满足以下核心操作：

• get(key)：获取指定键的值，若存在则返回并更新其访问顺序
• put(key, value)：插入或更新键值对，若容量不足则淘汰最久未使用的键

二、LRU 缓存的两种实现方式

import java.util.HashMap;
import java.util.Map;// 实现 LRU 缓存机制的类
class LRUCache {// 双向链表节点类，用于存储键值对private class DLinkedNode {// 键int key;// 值int value;// 指向前一个节点的引用DLinkedNode prev;// 指向后一个节点的引用DLinkedNode next;// 无参构造函数DLinkedNode() {}// 带键值参数的构造函数DLinkedNode(int key, int value) {this.key = key;this.value = value;}}// 缓存的容量private int capacity;// 当前缓存中元素的数量private int size;// 哈希表，用于快速查找键对应的节点private Map<Integer, DLinkedNode> cache = new HashMap<>();// 双向链表的头节点，虚拟节点，不存储实际数据private DLinkedNode head;// 双向链表的尾节点，虚拟节点，不存储实际数据private DLinkedNode tail;// 构造函数，初始化缓存容量、大小、头节点、尾节点public LRUCache(int capacity) {this.capacity = capacity;this.size = 0;head = new DLinkedNode();tail = new DLinkedNode();// 初始化双向链表，头节点的下一个节点是尾节点head.next = tail;// 尾节点的前一个节点是头节点tail.prev = head;}// 根据键获取值，如果键存在则将对应的节点移到链表头部并返回值，不存在则返回 -1public int get(int key) {DLinkedNode node = cache.get(key);if (node == null) {return -1;}// 将访问的节点移动到链表头部moveToHead(node);return node.value;}// 插入或更新键值对public void put(int key, int value) {DLinkedNode node = cache.get(key);if (node == null) {// 若键不存在，创建新节点DLinkedNode newNode = new DLinkedNode(key, value);// 将新节点存入哈希表cache.put(key, newNode);// 将新节点添加到链表头部addToHead(newNode);// 缓存元素数量加 1++size;if (size > capacity) {// 若缓存元素数量超过容量，移除链表尾部节点DLinkedNode removed = removeTail();// 从哈希表中移除对应的键值对cache.remove(removed.key);// 缓存元素数量减 1--size;}} else {// 若键已存在，更新节点的值node.value = value;// 将该节点移动到链表头部moveToHead(node);}}// 将节点添加到双向链表头部private void addToHead(DLinkedNode node) {// 新节点的前一个节点指向头节点node.prev = head;// 新节点的下一个节点指向原头节点的下一个节点node.next = head.next;// 原头节点下一个节点的前一个节点指向新节点head.next.prev = node;// 头节点的下一个节点指向新节点head.next = node;}// 从双向链表中移除指定节点private void removeNode(DLinkedNode node) {// 该节点前一个节点的下一个节点指向该节点的下一个节点node.prev.next = node.next;// 该节点下一个节点的前一个节点指向该节点的前一个节点node.next.prev = node.prev;}// 将指定节点移动到双向链表头部private void moveToHead(DLinkedNode node) {// 先从链表中移除该节点removeNode(node);// 再将该节点添加到链表头部addToHead(node);}// 移除双向链表的尾部节点private DLinkedNode removeTail() {// 获取尾部节点的前一个节点（即实际要移除的节点）DLinkedNode res = tail.prev;// 从链表中移除该节点removeNode(res);return res;}
}    

三、合并k个有序链表

给定一个包含 K 个有序链表的数组，要求将这些链表合并为一个有序链表:

// 定义一个解决方案类
class Solution {/*** 合并多个有序链表* @param lists 包含多个有序链表的数组* @return 合并后的有序链表*/public ListNode mergeKLists(ListNode[] lists) {// 调用递归方法，从数组的第一个元素开始，到最后一个元素结束return mergeKLists(lists, 0, lists.length);}/*** 合并从 lists[i] 到 lists[j - 1] 的链表* @param lists 包含多个有序链表的数组* @param i 起始索引* @param j 结束索引（不包含）* @return 合并后的有序链表*/private ListNode mergeKLists(ListNode[] lists, int i, int j) {// 计算当前要合并的链表数量int m = j - i;// 如果要合并的链表数量为 0，说明输入的数组为空，返回 nullif (m == 0) {return null; }// 如果要合并的链表数量为 1，无需合并，直接返回该链表if (m == 1) {return lists[i]; }// 递归合并左半部分的链表ListNode left = mergeKLists(lists, i, i + m / 2); // 递归合并右半部分的链表ListNode right = mergeKLists(lists, i + m / 2, j); // 最后把左半和右半合并后的链表进行合并return mergeTwoLists(left, right); }/*** 合并两个有序链表* @param list1 第一个有序链表* @param list2 第二个有序链表* @return 合并后的有序链表*/private ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 创建一个哨兵节点，简化代码逻辑，避免处理头节点为空的情况ListNode dummy = new ListNode(); // cur 指针指向新链表的末尾，用于构建新链表ListNode cur = dummy; // 当两个链表都不为空时，比较两个链表当前节点的值while (list1 != null && list2 != null) {if (list1.val < list2.val) {// 如果 list1 的当前节点值较小，将其添加到新链表中cur.next = list1; // list1 指针后移list1 = list1.next; } else { // 相等的情况加哪个节点都是可以的，这里将 list2 的当前节点添加到新链表中cur.next = list2; // list2 指针后移list2 = list2.next; }// cur 指针后移，指向新链表的末尾cur = cur.next; }// 拼接剩余链表，将未遍历完的链表直接连接到新链表的末尾cur.next = list1 != null ? list1 : list2; // 返回哨兵节点的下一个节点，即合并后的链表的头节点return dummy.next; }
}// 定义链表节点类
class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

四、打印矩阵 

import java.util.ArrayList;
import java.util.List;public class ZigzagMatrixPrinter {/*** 以蛇形顺序打印矩阵元素* @param matrix 输入的二维矩阵* @return 包含蛇形顺序元素的列表*/public static List<Integer> zigzagOrder(int[][] matrix) {// 用于存储最终蛇形打印结果的列表List<Integer> result = new ArrayList<>();// 检查输入的矩阵是否为空或无效// 如果矩阵为空，或者矩阵没有行，或者矩阵的第一行没有元素，直接返回空列表if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return result;}// 获取矩阵的行数int rows = matrix.length;// 获取矩阵的列数int cols = matrix[0].length;// 遍历矩阵的每一行for (int i = 0; i < rows; i++) {// 判断当前行是否为偶数行（行索引从 0 开始，所以索引为偶数的行是偶数行）if (i % 2 == 0) {// 偶数行从左到右打印// 遍历当前行的每一列for (int j = 0; j < cols; j++) {// 将当前元素添加到结果列表中result.add(matrix[i][j]);}} else {// 奇数行从右到左打印// 从当前行的最后一列开始，逆序遍历到第一列for (int j = cols - 1; j >= 0; j--) {// 将当前元素添加到结果列表中result.add(matrix[i][j]);}}}// 返回存储蛇形打印结果的列表return result;}public static void main(String[] args) {// 定义一个示例矩阵int[][] matrix = {{1, 2, 3},{4, 5, 6},{7, 8, 9}};// 调用 zigzagOrder 方法进行蛇形打印，并将结果存储在 result 列表中List<Integer> result = zigzagOrder(matrix);// 打印蛇形打印的结果System.out.println(result);}
}

希望能对你有帮助！！！

感谢观看！！！