【算法通关村Day5】Hash和队列的经典问题

hash和队列青铜挑战 hash和队列基本知识 hash

 哈希（Hash）是将任意长度的输入（通常是字符串）通过哈希函数映射为固定长度的输出（哈希值）。它广泛应用于数据存储、数据查找、密码学等领域。在Java中，常见的哈希相关类包括HashMap、HashSet以及Hashtable等。

哈希的基本原理

哈希函数的作用是将输入数据映射到一个固定大小的值。理想情况下，哈希函数应该：

不同的输入应该尽量映射到不同的哈希值（减少哈希冲突）。输入数据的微小变化应该导致哈希值的大幅度变化。

Java中HashMap的基本使用

在Java中，HashMap是基于哈希表实现的，它提供了一个存储键值对的容器，通过哈希值定位存储位置，通常具有很快的查找和插入速度。

下面是一个简单的HashMap使用示例：

import java.util.HashMap; public class HashMapExample { public static void main(String[] args) { HashMap<String, Integer> map = new HashMap<>(); map.put("apple", 1); map.put("banana", 2); map.put("cherry", 3); //获取值 System.out.println("The value for 'apple' is " + map.get("apple")); //遍历HashMap for(String key : map.keySet()){ System.out.println(key + " => " + map.get(key)); } //判断HashMap是否包含某个键 if (map.containsKey("banana")) { System.out.println("Banana exists."); } //删除键值对 map.remove("cherry"); System.out.println("'cherry' exists? " + map.containsKey("cherry")); } } 哈希存储

哈希存储（或哈希表存储）是利用哈希函数将数据映射到一个固定大小的表格中。在哈希表中，数据被存储在“桶”（bucket）中，每个桶有一个对应的索引，这个索引是由哈希函数生成的。 哈希函数：哈希函数将一个输入（例如，一个字符串）映射为一个固定大小的输出（哈希值）。这个哈希值通常是整数类型，作为数组或链表的索引。

例如：

输入 apple，哈希函数可能返回值 3，表示将 apple 存储在数组的第3个位置。输入 banana，哈希函数可能返回值 5，表示将 banana 存储在数组的第5个位置。

哈希表的基本操作：

插入： 哈希函数会根据键计算出对应的索引，然后将值存储在该索引处。查找： 查找时，哈希函数根据键计算索引，然后直接访问该索引位置的值。删除： 删除时，哈希函数计算索引并删除该位置的值。 哈希冲突

哈希冲突发生在两个不同的键经过哈希函数计算后，得到了相同的哈希值。这意味着它们被映射到了哈希表中的相同位置（桶），但是每个位置只能存放一个值，因此就产生了冲突。

假设我们有如下的哈希表，大小为5（索引范围为0到4）：

[ ] [ ] [ ] [ ] [ ]

我们要插入两个不同的键：apple 和 banana。假设哈希函数将 apple 映射到索引 2，将 banana 映射到索引 2（由于哈希函数的特性，它们得到了相同的哈希值），此时就会发生哈希冲突。

为了解决哈希冲突，我们通常采用以下几种常见的解决方法。

解决哈希冲突的方法 1. 链式法（Chaining）

链式法是最常见的解决哈希冲突的方式。它为每个哈希表的桶（索引位置）创建一个链表或其他容器，所有映射到同一位置的键值对都保存在该链表中。

示例： 假设我们使用链表存储冲突的元素，当发生冲突时，apple 和 banana 将被存储在索引 2 的链表中：

[ ] [ ] [apple -> banana] [ ] [ ]

apple 和 banana 都被存储在索引为 2 的链表中，链表中的节点可以存储多个键值对。查找时，如果两个键哈希到同一个位置，程序会遍历该位置的链表查找正确的键值对。 2. 开放地址法（Open Addressing）

开放地址法是将冲突的元素存储到哈希表的其他位置。它的关键思想是，如果发生冲突，哈希表会寻找下一个空的桶来存储数据。

开放地址法有几种具体的实现方式，最常见的是线性探测和二次探测。

线性探测： 如果当前位置已经被占用，程序就尝试下一个位置（即 index + 1），直到找到空位。

例如，如果apple哈希到索引2，并且该位置已经被占用（banana），那么程序会尝试将apple存放到3，如果3也被占用，则尝试4，以此类推。

二次探测： 与线性探测不同，二次探测会按照固定的步长（通常是平方数）来寻找下一个空桶。例如，如果冲突发生在位置 i，那么下一个查找的位置会是 i+1^2，如果仍然冲突，再尝试 i+2^2。

示例： 假设哈希表大小为 5，我们有以下两个键：

apple 哈希到位置 2。banana 哈希到位置 2（发生冲突）。

使用开放地址法时，如果位置 2 已经被 apple 占用，程序就会查找下一个空位置来存储 banana，例如位置 3 或 4。

3. 再哈希法（Rehashing）

再哈希法是指，当哈希表中的元素超过某个负载因子（比如 0.75）时，重新调整哈希表的大小，并将所有现有元素重新计算哈希值并放入新表中。这通常用于动态扩展哈希表。

4. Java中的哈希冲突处理

在Java的HashMap中，哈希冲突是通过链式法来解决的。如果多个键的哈希值相同，HashMap会将这些键值对存储在同一个桶的链表中。通常，HashMap会将链表转换为红黑树（如果链表的长度超过一定阈值），从而提高查找效率。

总结 哈希存储是通过哈希函数将数据映射到固定大小的数组（或桶）中，使得查找和插入操作的时间复杂度接近O(1)。哈希冲突是指两个或更多的键经过哈希计算后，得到相同的哈希值，导致它们被存储在相同的位置。

队列

队列（Queue）是一种典型的线性数据结构，遵循先进先出（FIFO, First In First Out）的原则。也就是说，最先插入队列的元素会最先被移除。队列在许多场景中都有广泛的应用，比如任务调度、进程管理、网络缓冲区等。

队列的基本操作

队列主要有以下几个基本操作：

入队（enqueue）： 向队列的尾部添加元素。出队（dequeue）： 从队列的头部移除元素。查看队头元素（peek/front）： 获取队列头部的元素，但不移除它。判断队列是否为空（isEmpty）： 检查队列是否包含元素。获取队列的大小（size）： 获取队列中元素的个数。 队列的特点 FIFO（先进先出）： 队列中的元素按顺序排队，最早进入队列的元素会最先出队。动态增长或固定大小： 队列可以是动态大小的（例如通过链表实现），也可以是固定大小的（例如通过数组实现）。 队列的实现方式 数组实现： 利用数组来实现队列，可以通过索引来管理队头和队尾。链表实现： 使用链表来实现队列，节点之间通过指针连接。 Java中的队列

在Java中，队列通常由Queue接口来定义，常用的实现类有LinkedList、ArrayDeque等。Java还提供了线程安全的队列实现类，例如ConcurrentLinkedQueue。

以下是一个简单的队列实现示例，使用LinkedList来实现队列：

import java.util.LinkedList; import java.util.Queue; public class QueueExample { public static void main(String[] args) { //创建一个队列 Queue<String> queue = new LinkedList<>(); //入队 queue.offer("apple"); queue.offer("banana"); queue.offer("cherry"); //查看队头元素 System.out.println("Front element: " + queue.peek()); //出队 System.out.println("Dequeued: " + queue.poll()); //打印 System.out.println(queue); //判断是否为空 if (!queue.isEmpty()) { System.out.println("Not empty."); } //获取队列大小 System.out.println("Queue size: " + queue.size()); } } hash和队列白银挑战 队列的经典问题 用两个栈实现队列 leetcode232

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空，返回 true ；否则，返回 false

解法：

栈1（stackIn）：用来处理 push 操作，将元素推入栈的顶部。栈2（stackOut）：用来处理 pop 和 peek 操作。为了保持队列的先进先出特性，我们从栈2中弹出元素。但是栈2中的元素顺序是后进先出，为了实现队列的先进先出，需要先将栈1中的所有元素倒入栈2。 详细步骤 push(x)：直接将元素 x 推入 stackIn。pop()： 如果 stackOut 为空，则将 stackIn 中的所有元素逐个弹出并推入 stackOut。这样，栈1中的元素倒入栈2时，顺序就会反转，从而模拟队列的先进先出。然后从 stackOut 中弹出并返回元素。 peek()：返回 stackOut 的顶部元素。如果 stackOut 为空，则先将 stackIn 中的元素倒入 stackOut，再返回 stackOut 的顶部元素。empty()：检查 stackIn 和 stackOut 是否都为空。如果两个栈都为空，则队列为空。 import java.util.Stack; public class MyQueue { private Stack<Integer> stackIn; private Stack<Integer> stackOut; public MyQueue(){ stackIn = new Stack<>(); stackOut = new Stack<>(); } //1. 直接将元素推入stackIn，将元素推到队列的末尾 public void push(int x){ stackIn.push(x); } //2. 将 stackIn 中的所有元素转移到 stackOut，然后从 stackOut 弹出栈顶元素并返回 public int pop(){ if (stackOut.isEmpty()) { while (!stackIn.isEmpty()) { stackOut.push(stackIn.pop()); } } return stackOut.pop(); } //3. 返回栈顶元素但不弹出 public int peek(){ if (stackOut.isEmpty()) { while (!stackIn.isEmpty()) { stackOut.push(stackIn.pop()); } } return stackOut.peek(); } //4. 判断队列是否为空 public boolean empty(){ return stackIn.isEmpty() && stackOut.isEmpty(); } } 用两个队列实现栈 leetcode225

要使用两个队列来实现一个后入先出（LIFO）的栈，我们需要通过队列的先进先出（FIFO）特性来模拟栈的后进先出行为。队列是先进先出，而栈是后进先出，所以我们可以通过在 push 和 pop 操作中对队列的操作顺序进行巧妙安排来实现栈的行为。

队列1（queueIn）：用来处理 push 操作，存储元素。队列2（queueOut）：用来处理 pop 和 top 操作。 详细步骤

push(x)：

将元素 x 放入 queueIn。这个操作时间复杂度是 O(1)。

pop()：

将 queueIn 中的元素逐个转移到 queueOut 中，直到 queueIn 中只剩下一个元素，这个元素就是栈顶元素。弹出 queueIn 中的最后一个元素。然后交换 queueIn 和 queueOut，使得 queueIn 继续保存新的元素。这个操作的时间复杂度是 O(n)，因为可能需要将所有元素从 queueIn 移动到 queueOut。

top()：

类似于 pop()，我们将 queueIn 中的元素逐个转移到 queueOut 中，直到只剩下一个元素。返回该元素，但不移除它。然后交换 queueIn 和 queueOut。这个操作的时间复杂度也是 O(n)。

empty()：

直接检查 queueIn 和 queueOut 是否都为空。如果都为空，则栈为空，返回 true，否则返回 false。这个操作是 O(1) 时间复杂度。 import java.util.LinkedList; import java.util.Queue; public class MyStack { private Queue<Integer> queueIn; private Queue<Integer> queueOut; public MyStack(){ queueIn = new LinkedList<>(); queueOut = new LinkedList<>(); } //将元素推入栈顶 public void push(int x){ queueIn.offer(x); } //移除并返回栈顶元素 public int pop(){ while (queueIn.size() > 1) { queueOut.offer(queueIn.poll()); } // 返回栈顶元素，即 queueIn 中剩下的那个元素 int topElement = queueIn.poll(); Queue<Integer> temp = queueIn; queueIn = queueOut; queueOut = temp; return topElement; } //返回栈顶元素，不移除 public int top(){ while (queueIn.size() > 1) { queueOut.offer(queueIn.poll()); } // 返回栈顶元素，即 queueIn 中剩下的那个元素 int topElement = queueIn.peek(); // 将剩余的那个元素再次放回 queueOut queueOut.offer(queueIn.poll()); Queue<Integer> temp = queueIn; queueIn = queueOut; queueOut = temp; return topElement; } //判断栈是否为空 public boolean empty(){ return queueIn.isEmpty() && queueOut.isEmpty(); } } hash和队列黄金挑战 LRU的设计与实现

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类： LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存。

int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

解法：

为了设计一个满足 LRU (最近最少使用) 缓存的类，可以使用 双向链表 和 哈希表 的组合来确保以下几点：

双向链表：可以支持 O(1) 时间复杂度的插入和删除操作。哈希表：可以支持 O(1) 时间复杂度的查找操作。

具体思路：

使用双向链表来维护缓存的顺序，链表的头部表示最近使用的元素，尾部表示最久未使用的元素。使用哈希表存储 key 和链表节点的映射，以便 O(1) 查找。 具体步骤 get(key)：查找哈希表中的键。如果找到，返回值并将该节点移到链表头部。如果未找到，返回 -1。put(key, value)：如果键存在，更新值并将节点移到链表头部。如果键不存在，创建一个新节点，插入到链表头部，并检查是否超过容量，如果超过则移除尾部节点（即最久未使用的节点）。 import java.lang.classfile ponents.ClassPrinter.Node; import java.util.HashMap; import java.util.Map; public class LRUCache { private final int capacity; private final Map<Integer, Node> map = new HashMap<>(); private Node head = null; private Node tail = null; public LRUCache(int capacity){ this.capacity = capacity; } public int get(int key){ if (!map.containsKey(key)) { return -1; } Node node = map.get(key); // 移除该节点，因为它即将被移动到链表头部 removeNode(node); //调用 setHead(node) 将该节点放到链表的头部 setHead(node); return node.value; } public void put(int key, int value){ // 如果已存在，则更新其值并移到头部 if (map.containsKey(key)) { Node node = map.get(key); node.value = value; removeNode(node); setHead(node); } else { // 否则创建新的节点 if (map.size() >= capacity) { // 超过容量时移除尾部节点 map.remove(tail.key); removeNode(tail); } Node newNode = new Node(key, value); map.put(key, newNode); setHead(newNode); } } public void removeNode(Node node){ if (node.prev != null) { //将前驱节点的 next 指向 node 的后继节点 node.prev.next = node.next; } else { head = node.next; // 如果是头节点，则更新头指针 } if (node.next != null) { //将后继节点的 prev 指向 node 的前驱节点 node.next.prev = node.prev; } else { tail = node.prev; // 如果是尾节点，则更新尾指针 } } public void setHead(Node node){ //使 node 成为新的头节点 node.next = head; node.prev = null; //如果原头节点 head 不为空，则将其 prev 指向 node if (head != null) { head.prev = node; } //更新 head 为 node head = node; //如果 tail 为 null（链表为空），则将 tail 设置为 head，表示链表只有一个节点 if (tail == null) { tail = head; } } private static class Node { int key; int value; Node prev; Node next; public Node(int key, int value) { this.key = key; this.value = value; } } }