一.哈希表
1.哈希表的简单介绍
哈希表（Hash Table），也称为散列表，是一种使用哈希函数组织数据，以支持快速插入和搜索的数据结构。哈希表的基本思想是通过哈希函数把键（Key）映射到表中一个位置来访问记录，以加快查找的速度。这个映射的函数称作哈希函数，存放记录的数组称作哈希表或散列表。
2.基本原理：
1.哈希函数设计：设计一个好的哈希函数是哈希表效率的关键。理想的哈希函数应该满足两个基本条件：一是尽量减少冲突，二是计算简单快速。哈希函数通常将输入（比如字符串、数字等）转换成一个整数，这个整数的范围通常是0到哈希表大小减一。
2.处理哈希冲突：由于不同的输入可能会被映射到同一个输出，因此必须有方法来处理这种"哈希冲突"（Hash Collision）。解决哈希冲突的方法主要有两种：开放寻址法（Open Addressing）和链表法（Chaining）。
（1）开放寻址法：当发生冲突时，探索表中的下一个空槽，并将元素插入其中。
（2）链表法：每个表格元素维护一个链表，所有映射到该位置的元素都存放在这个链表中。
3.动态扩容：为了保持哈希表的高效性，当哈希表中的元素过多，导致负载因子（即元素个数与表容量的比值）超过某个阈值时，通常需要进行扩容，即创建一个更大的哈希表，并将所有现有的元素重新映射到新表中。
3.优缺点
优点：
1.快速访问：理想情况下，哈希表的查找、插入和删除操作的时间复杂度都是O(1)。
2.灵活键值对应：可以直接通过键值对快速访问数据，非常适合需要频繁查找的场景。
缺点：
1.空间占用：为了减少哈希冲突，哈希表可能会预留大量空间，导致空间使用效率不高。
2.顺序遍历困难：由于数据是根据哈希值分布的，哈希表不支持高效的顺序访问。
3.哈希冲突：虽然有方法解决，但是在极端情况下，哈希冲突可能会导致性能大幅下降。
示例代码：
unordered_map 是C++标准模板库（STL）中的一个关联容器，提供了键值对的存储能力，其中每个键都是唯一的，并且可以通过键快速检索到值。
#include
#include
#include
using namespace std;
int main() {
// 创建一个unordered_map，键为string类型，值为int类型
std::unordered_map
// 插入键值对
ageMap["Alice"] = 30;
ageMap["Bob"] = 25;
ageMap["Charlie"] = 35;
// 通过键访问值
std::cout << "Alice's age: " << ageMap["Alice"] << std::endl;
// 检查键是否存在
if (ageMap.find("Diana") == ageMap.end()) {
std::cout << "Diana is not in the age map." << std::endl;
}
else {
std::cout << "Diana's age: " << ageMap["Diana"] << std::endl;
}
// 遍历unordered_map
std::cout << "All entries in the age map:" << std::endl;
for (const auto& pair : ageMap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
// 删除键值对
ageMap.erase("Bob");
std::cout << "After erasing Bob, we have:" << std::endl;
for (const auto& pair : ageMap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
return 0;
}
在 C++ 中，当使用 std::unordered_map 或任何基于哈希的容器时，容器自身会自动处理哈希冲突。但了解它是如何处理这些冲突的可以更好地理解哈希表的工作原理。一般来说，哈希冲突的处理方法包括链地址法（也称为分离链接法）和开放寻址法，其中链地址法是最常用的方法之一，且是许多标准库实现的选择。
在链地址法中，哈希表的每个桶（或称为槽）不直接存储键值对，而是存储指向键值对链表的指针。当多个键哈希到同一个桶时，这些键值对会被存储在同一个链表中，从而解决了冲突。查找、插入和删除操作会首先定位到桶，然后在链表中进行。
下面的示例代码不是使用 std::unordered_map 的标准处理方式，，展示了一个简化的哈希表实现，使用链地址法来处理哈希冲突：
#include
#include
#include
#include
class SimpleHashTable {
private:
static const int HASH_SIZE = 10; // 哈希表大小，简单起见设为一个小值
std::vector
public:
SimpleHashTable() : table(HASH_SIZE) {}
void insert(int key, const std::string& value) {
int index = hashFunction(key);
// 遍历链表以查找是否已存在相同的键
for (auto& pair : table[index]) {
if (pair.first == key) {
pair.second = value; // 如果键已存在，更新值
return;
}
}
// 如果键不存在，添加到链表的末尾
table[index].push_back(std::make_pair(key, value));
}
bool search(int key, std::string& value) {
int index = hashFunction(key);
for (const auto& pair : table[index]) {
if (pair.first == key) {
value = pair.second;
return true; // 找到键，返回true
}
}
return false; // 未找到键，返回false
}
bool remove(int key) {
int index = hashFunction(key);
for (auto it = table[index].begin(); it != table[index].end(); ++it) {
if (it->first == key) {
table[index].erase(it); // 找到键，删除
return true;
}
}
return false; // 未找到键，返回false
}
private:
int hashFunction(int key) {
return key % HASH_SIZE; // 简单的模运算哈希函数
}
};
int main() {
SimpleHashTable hashTable;
hashTable.insert(1, "Alice");
hashTable.insert(11, "Bob"); // 会产生哈希冲突并处理
std::string value;
if (hashTable.search(1, value)) {
std::cout << "Found key 1 with value: " << value << std::endl;
}
if (hashTable.search(11, value)) {
std::cout << "Found key 11 with value: " << value << std::endl;
}
return 0;
}
补充：
1)哈希表在使用层面上可以理解为一种集合结构
2)如果只有key，没有伴随数据value，可以使用HashSet结构(C++中叫Un0rderedSet)
3)如果既有key，又有伴随数据value，可以使用HashMap结构(C++中叫Un0rderedMap)
4)有无伴随数据，是HashMap和HashSet唯一的区别，底层的实际结构是一回事
5)使用哈希表增(put)、删(remove)、改(put)和查(get)的操作，可以认为时间复杂度为0(1)，但是常数时间比较大
6)放入哈希表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
7)放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是这个东西内存地址的大小。
二.有序表
有序表（Ordered List）是数据结构中的一种，它按照元素的某种特定顺序（如升序或降序）组织数据。这种数据结构支持高效的查找、插入和删除操作，因为元素的有序性使得可以使用比如二分查找等高效算法。有序表可以通过多种方式实现，包括数组、链表、平衡树（如AVL树、红黑树）、跳表等。下面是有序表的一些关键特点和常用实现方式：
1.关键特点
(1)有序性：有序表中的元素根据键（key）的值进行排序。这意味着元素在表中的位置是由其键的值决定的。
(2)动态操作：支持动态地插入和删除元素，同时保持元素的有序性。
(3)高效查找：由于元素是有序的，因此可以使用二分查找等高效算法，以对数时间复杂度进行查找操作。
(4)范围查询：有序表使得基于范围的查询变得简单和高效，如查找所有键在某个区间内的元素。
2.常用实现方式
1.数组
(1)静态数组：将元素存储在固定大小的数组中。插入和删除操作可能需要移动多个元素，因此效率较低。
(2)动态数组：可以调整大小的数组，以容纳更多元素。插入和删除操作的平均时间复杂度较好，但最坏情况下可能需要移动大量元素。
2.链表
单链表或双链表：元素通过指针相连，每个元素包含数据和指向下一个（和/或前一个）元素的指针。插入和删除操作可以在O(1)时间内完成，如果已经到达相应位置的话。但查找操作通常需要O(n)的时间复杂度。
3.平衡树
(1)二叉查找树（BST）的变体，如AVL树、红黑树：这些树结构通过旋转操作来保持平衡，确保最坏情况下的操作时间复杂度为O(log n)。
(2)B树和B+树：特别适用于存储系统中的数据索引，能够高效管理大量数据。
4.跳表
跳表是一个通过多层结构来实现快速查找的链表。它通过添加额外的"快速通道"链表，使得查找效率可以接近二分查找的效率，即O(log n)。
3.应用场景
有序表在很多领域都有广泛的应用，包括数据库索引、内存管理、文件系统以及各种需要快速查找和维护有序数据的场景。每种实现方式有其特定的适用场景和优缺点，选择哪一种取决于具体的应用需求，如操作的频率、数据量的大小以及是否需要支持快速的插入或删除操作。
示例代码：
在 C++ 中，有序表可以通过使用 std::map 来实现，这是一个基于红黑树的自平衡二叉搜索树，能够保持元素按照特定的顺序（通常是键的升序）进行排序。
#include
#include
#include
int main() {
// 创建一个std::map实例，键和值的类型都是string
std::map
// 向map中添加键值对
phoneBook["Alice"] = "555-1234";
phoneBook["Bob"] = "555-5678";
phoneBook["Charlie"] = "555-9999";
// 通过键访问值
std::cout << "Alice's phone number: " << phoneBook["Alice"] << std::endl;
// 检查键是否存在并访问
auto search = phoneBook.find("Diana");
if (search != phoneBook.end()) {
std::cout << "Diana's phone number: " << search->second << std::endl;
}
else {
std::cout << "Diana is not in the phone book." << std::endl;
}
// 遍历map
std::cout << "All entries in the phone book:" << std::endl;
for (const auto& entry : phoneBook) {
std::cout << entry.first << ": " << entry.second << std::endl;
}
// 删除键值对
phoneBook.erase("Bob");
std::cout << "After erasing Bob, the phone book contains:" << std::endl;
for (const auto& entry : phoneBook) {
std::cout << entry.first << ": " << entry.second << std::endl;
}
return 0;
}
补充：
有序表的固定操作 1)void put(K key，V value):将一个(key，value)记录加入到表中，或者将key的记录更新成value。 2)Vget(K key):根据给定的key，查询value并返回 3)void remove(K key):移除key的记录。 4)boolean containsKey(K key):询问是否有关于key的记录。 5)K firstKey():返回所有键值的排序结果中，最左(最小)的那个。6)KlastKey():返回所有键值的排序结果中，最右(最大)的那个。7)K floorKey(K key):如果表中存入过key，返回key;否则返回所有键值的排序结果中key的前一个。 8)KceilingKey(K key):如果表中存入过key，返回key;否则返回所有键值的排序结果中key的后一个。 以上所有操作时间复杂度都是0(I0gN)，N为有序表含有的记录数 有关有序表的原理，将在提升班“有序表详解”一章中讲叙原理
三.链表
链表是一种常用的数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针（在双向链表中还包含指向上一个节点的指针）。链表是一种动态的数据结构，可以在运行时动态添加或删除节点，这使得它在需要频繁插入和删除操作的场景下非常有用。链表的元素不像数组那样在内存中连续存储，因此它们的插入和删除操作不需要移动其他元素。
1.单向链表
每个节点只包含一个指向下一个节点的指针。这种结构使得遍历只能是单向的，从头节点开始到尾节点结束。
2.双向链表
每个节点包含两个指针，一个指向下一个节点，另一个指向上一个节点。这使得链表可以正向或反向遍历。
题目1：反转单向和双向链表 分别实现反转单向链表和反转双向链表的函数【要求】如果链表长度为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1)
（1）反转单向链表
#include
// 定义单向链表的节点结构
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 反转单向链表的函数
ListNode* reverseList(ListNode* head) {
ListNode *prev = nullptr;
ListNode *curr = head;
while (curr != nullptr) {
ListNode *nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev; // 新的头节点
}
// 用于打印链表，验证结果
void printList(ListNode* node) {
while (node != nullptr) {
std::cout << node->val << " ";
node = node->next;
}
std::cout << std::endl;
}
// 示例主函数
int main() {
// 创建示例链表：1 -> 2 -> 3 -> 4
ListNode *list = new ListNode(1);
list->next = new ListNode(2);
list->next->next = new ListNode(3);
list->next->next->next = new ListNode(4);
std::cout << "Original list: ";
printList(list);
ListNode *reversedList = reverseList(list);
std::cout << "Reversed list: ";
printList(reversedList);
// 释放链表内存（在实际应用中应该逐节点释放，此处为简化示例未包含）
return 0;
}
（2）反转双向链表
#include
// 定义双向链表的节点结构
struct DListNode {
int val;
DListNode *prev, *next;
DListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};
// 反转双向链表的函数
DListNode* reverseDList(DListNode* head) {
DListNode *temp = nullptr;
DListNode *current = head;
while (current != nullptr) {
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
if (temp != nullptr) {
head = temp->prev;
}
return head; // 新的头节点
}
// 用于打印双向链表，验证结果
void printDList(DListNode* node) {
while (node != nullptr) {
std::cout << node->val << " ";
node = node->next;
}
std::cout << std::endl;
}
// 示例主函数
int main() {
// 创建示例双向链表：1 <-> 2 <-> 3 <-> 4
DListNode *dlist = new DListNode(1);
dlist->next = new DListNode(2);
dlist->next->prev = dlist;
dlist->next->next = new DListNode(3);
dlist->next->next->prev = dlist->next;
dlist->next->next->next = new DListNode(4);
dlist->next->next->next->prev = dlist->next->next;
std::cout << "Original list: ";
printDList(dlist);
DListNode *reversedDList = reverseDList(dlist);
std::cout << "Reversed list: ";
printDList(reversedDList);
// 释放链表内存（在实际应用中应该逐节点释放，此处为简化示例未包含）
return 0;
}
注意：对于双向链表的反转，交换了每个节点的 prev 和 next 指针，并更新了头节点。在真实应用中，还需要适当管理内存，例如通过逐个删除链表中的节点来避免内存泄露。
题目2：打印两个有序链表的公共部分 给定两个有序链表的头指针head1和head2，打印两个链表的公共部分要求】如果两个链表的长度之和为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1)。
思路：
为了打印两个有序链表的公共部分，并满足时间复杂度为 O(N) 且额外空间复杂度为 O(1) 的要求，可以采用双指针遍历的方式。因为两个链表都是有序的，可以同时遍历这两个链表，比较当前遍历到的节点值：
（1）如果两个节点的值相等，那么这个值就是它们的公共部分之一，打印这个值，然后同时移动两个链表的指针。
（2）如果第一个链表的当前节点值小于第二个链表的当前节点值，那么移动第一个链表的指针，因为第一个链表的下一个节点可能与第二个链表的当前节点相等。
（3）反之，如果第二个链表的当前节点值小于第一个链表的当前节点值，那么移动第二个链表的指针。
这样做可以保证我们在 O(N) 时间内遍历完两个链表，并且因为只用到了几个额外的指针变量，所以额外空间复杂度为 O(1)。
#include
// 定义单向链表的节点结构
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 打印两个有序链表的公共部分
void printCommonPart(ListNode* head1, ListNode* head2) {
while (head1 != nullptr && head2 != nullptr) {
if (head1->val == head2->val) {
// 找到公共元素，打印
std::cout << head1->val << " ";
// 同时移动两个链表的指针
head1 = head1->next;
head2 = head2->next;
} else if (head1->val < head2->val) {
// 移动第一个链表的指针
head1 = head1->next;
} else {
// 移动第二个链表的指针
head2 = head2->next;
}
}
}
int main() {
// 创建两个示例有序链表
ListNode *list1 = new ListNode(1);
list1->next = new ListNode(2);
list1->next->next = new ListNode(3);
list1->next->next->next = new ListNode(4);
list1->next->next->next->next = new ListNode(6);
ListNode *list2 = new ListNode(2);
list2->next = new ListNode(4);
list2->next->next = new ListNode(6);
list2->next->next->next = new ListNode(8);
std::cout << "Common parts: ";
printCommonPart(list1, list2);
std::cout << std::endl;
// 释放链表内存（在实际应用中应该逐节点释放，此处为简化示例未包含）
return 0;
}
3.实际应用
1)对于笔试，不用太在乎空间复杂度，一切为了时间复杂度
2)对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法
重要技巧: 1)额外数据结构记录(哈希表等) 2)快慢指针
题目1：判断一个链表是否为回文结构 给定一个单链表的头节点head，请判断该链表是否为回文结构。【例子】1->2->1，返回true;1->2->2->1，返回true;15->6->15，返回true;1->2->3，返回false。 要求：如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。
思路：
1.找到链表的中点：使用快慢指针的方法，快指针一次走两步，慢指针一次走一步，当快指针到达链表末尾时，慢指针正好在链表的中间位置。
2反转链表的后半部分：从慢指针当前的位置开始，反转链表的后半部分。这样我们就可以轻易地从中间向两边比较链表的值来判断是否为回文。
3判断回文结构：将链表的前半部分和反转后的后半部分进行比较，如果每个对应位置的元素都相同，那么链表是回文的。比较完成后，需要恢复链表的后半部分到其原始状态，以保证链表的结构不被破坏（这一步是可选的，取决于是否需要保持原链表结构不变）。
4.恢复链表（可选）：如果需要保持原链表结构，可以再次反转后半部分的链表，恢复其原始顺序。
#include
// 定义链表的节点结构
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 反转链表函数
ListNode* reverseList(ListNode* head) {
ListNode *prev = nullptr, *curr = head;
while (curr != nullptr) {
ListNode *nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
// 寻找链表中点函数
ListNode* findMiddle(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast->next != nullptr && fast->next->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
// 判断链表是否为回文结构
bool isPalindrome(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return true;
}
ListNode* middle = findMiddle(head);
ListNode* secondHalfStart = reverseList(middle->next);
ListNode* p1 = head;
ListNode* p2 = secondHalfStart;
bool isPalindrome = true;
while (p2 != nullptr) { // 只需要比较后半部分
if (p1->val != p2->val) {
isPalindrome = false;
break;
}
p1 = p1->next;
p2 = p2->next;
}
// 恢复链表（如果需要）
middle->next = reverseList(secondHalfStart);
return isPalindrome;
}
int main() {
// 创建示例链表：1 -> 2 -> 2 -> 1
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(2);
head->next->next->next = new ListNode(1);
std::cout << "Is palindrome: " << isPalindrome(head) << std::endl;
// 释放链表内存（在实际应用中应该逐节点释放，此处为简化示例未包含）
return 0;
}
题目2：将单向链表按某值划分成左边小、中间相等、右边大的形式 【题目】给定一个单链表的头节点head，节点的值类型是整型，再给定一个整数pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。
#include
// 定义链表的节点结构
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 调整链表
void partition(ListNode* &head, int pivot) {
ListNode *lessHead = new ListNode(0), *equalHead = new ListNode(0), *greaterHead = new ListNode(0);
ListNode *lessTail = lessHead, *equalTail = equalHead, *greaterTail = greaterHead;
ListNode *current = head;
// 遍历链表，分配节点
while (current != nullptr) {
if (current->val < pivot) {
lessTail->next = current;
lessTail = lessTail->next;
} else if (current->val == pivot) {
equalTail->next = current;
equalTail = equalTail->next;
} else {
greaterTail->next = current;
greaterTail = greaterTail->next;
}
current = current->next;
}
// 连接三个部分
greaterTail->next = nullptr; // 最后一个部分的结尾要指向 nullptr
equalTail->next = greaterHead->next; // 等于部分连接大于部分
lessTail->next = equalHead->next; // 小于部分连接等于部分
head = lessHead->next; // 更新头节点
// 释放临时头节点
delete lessHead;
delete equalHead;
delete greaterHead;
}
// 打印链表
void printList(ListNode* node) {
while (node != nullptr) {
std::cout << node->val << " ";
node = node->next;
}
std::cout << std::endl;
}
int main() {
ListNode* head = new ListNode(9);
head->next = new ListNode(0);
head->next->next = new ListNode(4);
head->next->next->next = new ListNode(5);
head->next->next->next->next = new ListNode(1);
std::cout << "Original list: ";
printList(head);
partition(head, 3);
std::cout << "Partitioned list: ";
printList(head);
// 释放链表内存（在实际应用中应该逐节点释放，此处为简化示例未包含）
return 0;
}
【进阶】在实现原问题功能的基础上增加如下的要求
【要求】调整后所有小于pivot的节点之间的相对顺序和调整前一样
【要求】调整后所有等于pivot的节点之间的相对顺序和调整前一样
【要求】调整后所有大于pivot的节点之间的相对顺序和调整前一样
【要求】时间复杂度请达到O(N)，额外空间复杂度请达到O(1)
#include
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
void partition(ListNode*& head, int pivot) {
ListNode *lessHead = nullptr, *lessTail = nullptr;
ListNode *equalHead = nullptr, *equalTail = nullptr;
ListNode *greaterHead = nullptr, *greaterTail = nullptr;
ListNode *current = head;
while (current != nullptr) {
if (current->val < pivot) {
if (lessTail == nullptr) {
lessHead = lessTail = current;
} else {
lessTail->next = current;
lessTail = current;
}
} else if (current->val == pivot) {
if (equalTail == nullptr) {
equalHead = equalTail = current;
} else {
equalTail->next = current;
equalTail = current;
}
} else {
if (greaterTail == nullptr) {
greaterHead = greaterTail = current;
} else {
greaterTail->next = current;
greaterTail = current;
}
}
current = current->next;
}
// 连接三个部分
ListNode* newHead = nullptr;
if (lessHead) {
newHead = lessHead;
lessTail->next = equalHead ? equalHead : greaterHead;
}
if (equalHead) {
newHead = newHead ? newHead : equalHead;
equalTail->next = greaterHead;
}
if (greaterHead) {
newHead = newHead ? newHead : greaterHead;
greaterTail->next = nullptr;
}
head = newHead; // 更新头指针
}
void printList(ListNode* node) {
while (node) {
std::cout << node->val << " ";
node = node->next;
}
std::cout << std::endl;
}
int main() {
ListNode* head = new ListNode(9);
head->next = new ListNode(0);
head->next->next = new ListNode(4);
head->next->next->next = new ListNode(5);
head->next->next->next->next = new ListNode(1);
std::cout << "Original list: ";
printList(head);
partition(head, 4);
std::cout << "Partitioned list: ";
printList(head);
// 在实际应用中应该逐节点释放链表内存，此处为简化示例未包含释放代码
return 0;
}
好文链接
发表评论