个人备案网站名称,校园网站建设特色,免费试用网站,网站维护一般怎么做 考试形式
笔试考了三道算法题#xff0c;笔试形式为阅读题目#xff0c;然后用中文给出算法思路#xff0c;最后给出算法例程#xff0c;分数各占一半#xff0c;简单#xff0c;中等#xff0c;复杂各一道题。我看9月份有人也是考这3道题#xff0c;一模一样。
第… 考试形式
笔试考了三道算法题笔试形式为阅读题目然后用中文给出算法思路最后给出算法例程分数各占一半简单中等复杂各一道题。我看9月份有人也是考这3道题一模一样。
第一题英文句子翻转
1.单词倒转简单 50 描述 将一个句子中的单词全部倒转如 i am a programmer. 倒转后为 programmer a am i. 每句话以.结尾只倒转每句话内的单词一个输入可能包含多句话。 输入为Char* 类型. 要求尽量使用空间复杂度最小的方法实现。 请用中文说明算法思想30 请给出算法例程可使用c/golang实现20 C代码 中文说明算法思想: 这个算法用于翻转句子中的单词并且保留句子末尾的句点。 逆序整个句子 首先计算句子的长度 len然后使用 std::reverse函数逆序整个句子但不包括句点。这一步将句子中的字符顺序全部反转。 逆序每个单词 接下来通过遍历句子中的字符找到单词的边界通过空格或句子末尾然后对每个单词进行逆序处理。逆序单词后将单词的起始位置start 更新为当前位置加一。 最后手动在输出末尾添加句点以保留原始句子的结尾标点符号。 这个算法通过反转整个句子和逆序每个单词来实现句子翻转同时保留了句子末尾的句点。 #include iostream
#include cstring // 包含cstring头文件以使用strlen函数
#include algorithmvoid reverseWords(char* s) {int len strlen(s); // 计算字符串长度if (len 1) {std::reverse(s, s len - 1); // // 逆序整个句子不包括末尾的句号.int start 0; // 记录单词的起始位置for (int i 0; i len - 1; i) { // 遍历字符串不处理句点if (s[i] || s[i] \0) { // 当遇到空格或字符串结束符时std::reverse(s start, s i); // 逆序单词start i 1; // 更新单词的起始位置为下一个字符}}}
}int main() {char str[] i am a programmer.;reverseWords(str); // 调用翻转单词的函数std::cout str std::endl; // 输出翻转后的句子return 0;
}这个例程的reverseWords函数实现了对单词的倒转。首先它翻转了整个句子然后再逐个翻转每个单词最终得到了所需的结果。
第二题二分查找
2.给一个非递减排序的数列非严格递增)请查找最后一个等于给定元素 x的数列元素的下标不存在则返回-1。 要求时间复杂度小于O(n) C代码 中文说明算法思想: 这段代码使用了二分查找算法来找到一个非递减排序的数组中最后一个等于给定元素 x 的数列元素的下标。具体步骤如下 初始化左右边界开始时将左边界 left 设为数组起始位置0右边界 right 设为数组末尾位置arr.size() - 1。 二分查找通过 while 循环执行二分查找算法。在每一次循环中 a. 计算中间位置 mid使用左右边界计算出中间位置。 b. 对比中间位置元素与给定元素 x - 如果中间位置的元素与 x 相等更新 result 为当前的中间位置 mid并向右侧继续寻找可能存在的更后面的元素因为要找最后一个等于 x 的位置。 - 如果中间位置的元素小于 x则将左边界 left 更新为 mid 1因为要在右半边继续寻找。 - 如果中间位置的元素大于 x则将右边界 right 更新为 mid - 1因为要在左半边寻找。 返回结果如果找到了等于 x 的元素则 result 中存储的即为最后一个等于 x 的元素下标如果没有找到则返回 -1。 这个算法的关键在于根据中间值与目标值的大小关系不断缩小搜索范围直到找到目标值或者确认数组中不存在该值。 #include iostream
#include vectorint lastIndexOfX(const std::vectorint arr, int x) {int left 0;int right arr.size() - 1;int result -1;while (left right) {int mid left (right - left) / 2;if (arr[mid] x) {result mid; // 更新结果left mid 1; // 继续向右寻找} else if (arr[mid] x) {left mid 1; // 向右边查找} else {right mid - 1; // 向左边查找}}return result;
}int main() {std::vectorint arr {1, 2, 2, 3, 4, 4, 4, 5, 6};int x 4;int lastIndex lastIndexOfX(arr, x);if (lastIndex ! -1) {std::cout 最后一个 x 的下标是: lastIndex std::endl;} else {std::cout x 不存在于数组中 std::endl;}return 0;
}第三题LRU缓存
第三道题是选做题leetcode上的LRU缓存使用双向链表。https://leetcode.cn/problems/lru-cache-lcci/solutions/491688/lruhuan-cun-by-leetcode-solution/
3.设计缓存复杂10选做 描述 设计一个缓存缓存大小为指定大小n最近最少使用的值应自动被缓存替换掉。 (类及类的方法已经定义好)
Class Cache {public:explict Cache(int n); bool put(int, int); int get(int);
}要求 1. 缓存支持键值对存取即支持插入键值对put(key, val)及读取某键对应的值 get(key)如果存在该键则返回其对应的值否则返回-1 2. 键值对可以支持整型。 要求尽量使用时间复杂度最小的方法实现。 请用中文说明算法思想5 请给出算法例程可使用c/golang实现5 C代码 中文说明算法思想: 这个算法使用了哈希表和双向链表来实现LRU缓存。具体思想如下 哈希表unordered_map用于快速查找键值对。键是缓存中的键值是指向双向链表中节点的指针。 双向链表用于维护键值对的访问顺序。链表的头部表示最近访问过的节点尾部表示最久未被访问的节点。 操作过程 插入操作 (put)当要插入新的键值对时先查看哈希表中是否已存在该键。如果存在更新其值并将该节点移动到链表头部表示最近访问。如果哈希表已满移除链表尾部节点最少使用的节点并在哈希表中删除相应的键值对然后将新节点插入链表头部并更新哈希表。 获取操作 (get)当要获取某个键对应的值时先在哈希表中查找。如果存在该键表示该节点被访问将其移动到链表头部并返回对应的值否则返回-1。 这种方法保证了对缓存的访问操作插入和获取都能在常数时间内完成因为哈希表的查找是常数时间而双向链表的插入和移动操作也是常数时间。 最近最少使用LRULeast Recently Used是一种常见的缓存淘汰策略。它的核心思想是当缓存达到其容量上限时移除最长时间未被使用的数据项来为新数据项腾出空间。这种策略基于一个假设最近经常使用的数据在不久的将来也很可能再次使用而长时间未被访问的数据在未来可能也不会被访问。
举例说明
假设我们有一个容量为3的LRU缓存以下是一系列的操作和缓存的状态变化
放入键值对 (1, ‘A’) 缓存状态1:A 放入键值对 (2, ‘B’) 缓存状态1:A, 2:B 放入键值对 (3, ‘C’) 缓存已满状态1:A, 2:B, 3:C 访问键为2的数据 (‘B’) 由于键2被访问它成为最近使用的数据移动到缓存的头部。缓存状态2:B, 1:A, 3:C 放入键值对 (4, ‘D’) 缓存已满需要移除最久未使用的数据在这个例子中是键3的数据。新数据 (4, ‘D’) 放入缓存头部。缓存状态4:D, 2:B, 1:A
在这个例子中每次访问或添加新数据时缓存都会根据数据的使用情况进行调整。最近被访问的数据总是被移动到缓存的头部而最久未被访问的数据则逐渐移动到缓存的尾部当需要移除数据以腾出空间时缓存尾部的数据即最久未使用的数据将被移除。
使用C设计一个缓存
当设计一个缓存你需要考虑一种数据结构能够以常数时间复杂度执行插入、删除和查找操作。一种优秀的选择是使用哈希表和双向链表实现一个LRULeast Recently Used缓存。
在这种方法中哈希表用于快速查找键值对而双向链表用于维护键值对的访问顺序。当有新的键值对被访问时它将会被移动到链表的头部而最近最少使用的元素将会位于链表的尾部以便于替换。
下面是一个用C实现LRU缓存的例程
#include unordered_map// 缓存节点类用于表示LRU缓存中的每个数据项
class CacheNode {
public:int key; // 缓存节点的键int value; // 缓存节点的值CacheNode* prev; // 指向前一个节点的指针CacheNode* next; // 指向后一个节点的指针// 构造函数用于创建一个新的缓存节点CacheNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};// LRU缓存类用于实现最近最少使用缓存机制
class Cache {
public:// 构造函数用于初始化缓存的大小和创建哨兵节点explicit Cache(int n) : capacity(n) {head new CacheNode(-1, -1); // 创建头哨兵节点tail new CacheNode(-1, -1); // 创建尾哨兵节点head-next tail; // 初始化双向链表tail-prev head;}// 析构函数用于释放链表中的所有节点~Cache() {CacheNode* current head;while (current) {CacheNode* next current-next;delete current;current next;}}// 从链表中移除一个节点的函数用于删除最久未使用的节点或移动节点void removeNode(CacheNode* node) {node-prev-next node-next;node-next-prev node-prev;}// 将节点添加到链表头部的函数用于添加新节点或将最近使用的节点移动到头部void addToFront(CacheNode* node) {node-next head-next;node-prev head;head-next-prev node;head-next node;}// 将节点移动到链表头部的函数当节点被访问时通过这个函数将其移动到头部void moveToHead(CacheNode* node) {removeNode(node);addToFront(node);}// 获取方法如果键存在返回对应的值并将该节点移至链表头部int get(int key) {if (cacheMap.find(key) ! cacheMap.end()) {CacheNode* node cacheMap[key];moveToHead(node);return node-value;}return -1;}// 插入方法将键值对存入缓存如果键已存在则更新其值并移动到头部如果不存在添加新节点bool put(int key, int value) {if (cacheMap.find(key) ! cacheMap.end()) {CacheNode* node cacheMap[key];node-value value;moveToHead(node);} else {if (cacheMap.size() capacity) {CacheNode* toRemove tail-prev;removeNode(toRemove);cacheMap.erase(toRemove-key);delete toRemove;}CacheNode* newNode new CacheNode(key, value);cacheMap[key] newNode;addToFront(newNode);}return true;}private:int capacity; // 缓存的最大容量std::unordered_mapint, CacheNode* cacheMap; // 键到节点的映射用于快速查找CacheNode* head; // 头哨兵节点CacheNode* tail; // 尾哨兵节点
};
这段代码实现了一个简单的LRU缓存其中使用了哈希表和双向链表。这种实现方式在put和get操作中都能以常数时间复杂度运行。 这个问题涉及到设计一个缓存系统这是计算机科学中常见的任务特别是在数据处理和系统设计领域。我将逐步解释任务的目的、要求和实现方法。
任务目的
缓存系统的主要目的是提高数据访问速度。当程序频繁访问某些数据时将这些数据存储在快速访问的缓存中可以减少从慢速存储如硬盘读取数据的次数从而提高效率。
任务要求
大小限制缓存的大小是固定的指定大小 n意味着它只能存储最多 n 个元素。键值对存储缓存通过键值对的方式存储数据。每个键对应一个唯一的值。可以使用 put(key, val) 方法插入键值对使用 get(key) 方法读取值。最近最少使用LRU策略当缓存达到最大容量时最近最少使用的数据将被新数据替换。这意味着缓存应跟踪数据的使用情况并且在需要空间时删除最久未使用的数据。
实现方法
数据结构
双向链表用于存储缓存中的数据。每个节点CacheNode包含一个键值对以及指向前一个和后一个节点的指针。链表的顺序反映了元素的使用情况——最近访问的元素被移到链表的头部而最久未使用的元素则接近尾部。哈希表使用一个 unordered_mapcacheMap以实现快速查找功能。哈希表存储键和指向相应链表节点的指针。
主要操作
插入put 方法 如果键已存在更新其值并将对应节点移动到链表头部表示最近使用。如果键不存在检查缓存是否已满。如果已满则删除最久未使用的元素链表尾部的元素然后将新元素添加到链表头部。 获取get 方法 如果键存在返回对应的值并将该节点移至链表头部。如果键不存在返回 -1。
操作细节
移动节点至头部moveToHead 方法当节点被访问时通过 get 或 put将其移动到链表的头部表示该节点是最近被使用过的。添加节点至头部addToFront 方法当插入一个新的元素时将其添加到链表的头部。移除节点removeNode 方法从链表中移除一个节点通常用于删除最久未使用的元素。
总结
这个缓存系统是一个典型的最近最少使用LRU缓存其通过双向链表和哈希表的结合实现了高效的插入、删除和访问操作。这种设计允许快速地添加和检索数据同时自动管理缓存的大小确保最常用的数据始终保留在缓存中。
验证LRU缓存实现
创建一个LRU缓存实例执行一些基本操作并验证预期行为。
#include iostream
#include cassert
#include unordered_map// 缓存节点类用于表示LRU缓存中的每个数据项
class CacheNode {
public:int key; // 缓存节点的键int value; // 缓存节点的值CacheNode* prev; // 指向前一个节点的指针CacheNode* next; // 指向后一个节点的指针// 构造函数用于创建一个新的缓存节点CacheNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};// LRU缓存类用于实现最近最少使用缓存机制
class Cache {
public:// 构造函数用于初始化缓存的大小和创建哨兵节点explicit Cache(int n) : capacity(n) {head new CacheNode(-1, -1); // 创建头哨兵节点tail new CacheNode(-1, -1); // 创建尾哨兵节点head-next tail; // 初始化双向链表tail-prev head;}// 析构函数用于释放链表中的所有节点~Cache() {CacheNode* current head;while (current) {CacheNode* next current-next;delete current;current next;}}// 从链表中移除一个节点的函数用于删除最久未使用的节点或移动节点void removeNode(CacheNode* node) {node-prev-next node-next;node-next-prev node-prev;}// 将节点添加到链表头部的函数用于添加新节点或将最近使用的节点移动到头部void addToFront(CacheNode* node) {node-next head-next;node-prev head;head-next-prev node;head-next node;}// 将节点移动到链表头部的函数当节点被访问时通过这个函数将其移动到头部void moveToHead(CacheNode* node) {removeNode(node);addToFront(node);}// 获取方法如果键存在返回对应的值并将该节点移至链表头部int get(int key) {if (cacheMap.find(key) ! cacheMap.end()) {CacheNode* node cacheMap[key];moveToHead(node);return node-value;}return -1;}// 插入方法将键值对存入缓存如果键已存在则更新其值并移动到头部如果不存在添加新节点bool put(int key, int value) {if (cacheMap.find(key) ! cacheMap.end()) {CacheNode* node cacheMap[key];node-value value;moveToHead(node);}else {if (cacheMap.size() capacity) {CacheNode* toRemove tail-prev;removeNode(toRemove);cacheMap.erase(toRemove-key);delete toRemove;}CacheNode* newNode new CacheNode(key, value);cacheMap[key] newNode;addToFront(newNode);}return true;}private:int capacity; // 缓存的最大容量std::unordered_mapint, CacheNode* cacheMap; // 键到节点的映射用于快速查找CacheNode* head; // 头哨兵节点CacheNode* tail; // 尾哨兵节点
};int main() {// 创建一个容量为3的LRU缓存Cache lruCache(3);// 插入一些键值对lruCache.put(1, 100);lruCache.put(2, 200);lruCache.put(3, 300);// 测试获取操作assert(lruCache.get(1) 100); // 应该返回100assert(lruCache.get(2) 200); // 应该返回200assert(lruCache.get(4) -1); // 不存在的键应该返回-1// 测试缓存替换lruCache.put(4, 400); // 这会导致键3被替换assert(lruCache.get(3) -1); // 键3被替换应返回-1assert(lruCache.get(4) 400); // 键4存在应返回400// 测试更新已存在的键lruCache.put(2, 250);assert(lruCache.get(2) 250); // 更新后的值应为250std::cout 所有测试通过 std::endl;return 0;
}这段测试代码做了以下几件事
创建LRU缓存初始化一个容量为3的缓存。插入数据向缓存中插入几个键值对。测试获取操作验证get方法能否正确返回值包括检查不存在的键。测试缓存替换插入新的数据以触发LRU替换机制并验证是否正确替换了最久未使用的数据。测试更新操作更新已存在的键的值并检查是否正确。
assert 函数用于验证条件是否为真。如果任何 assert 失败程序将终止执行这意味着缓存的行为与预期不符。
你可以将这段代码与前面的LRU缓存实现代码结合起来在C编译器中编译并运行来测试其功能。 在C中explicit 关键字用于构造函数的声明表明该构造函数是显式的。这意味着它防止了C中的隐式类型转换或隐式调用构造函数的行为。让我们通过一个例子来解释这一点。
explicit 关键字
explicit 关键字
explicit 关键字
不使用 explicit 关键字
假设有一个类 MyClass它有一个接受一个整数的构造函数但没有标记为 explicit
class MyClass {
public:MyClass(int n) { /*...*/ }
};在这种情况下C编译器允许隐式转换。这意味着你可以这样写代码
MyClass obj 5; // 隐式调用 MyClass(int)编译器会理解这条语句并且隐式地调用 MyClass 的构造函数。
使用 explicit 关键字
现在如果我们将构造函数标记为 explicit
class MyClass {
public:explicit MyClass(int n) { /*...*/ }
};这时编译器不再允许隐式转换。以下代码将导致编译错误
MyClass obj 5; // 错误: 不能隐式转换要创建 MyClass 的对象你必须显式地调用构造函数
MyClass obj(5); // 正确: 显式调用构造函数在这个LRU的例子中
在 Cache 类中使用 explicit 关键字意味着要创建 Cache 类的对象必须显式地指定其容量。这有助于避免潜在的错误如意外的隐式类型转换使代码的意图更加明确和安全。
例如
Cache myCache 3; // 错误如果构造函数是explicit
Cache myCache(3); // 正确必须这样调用使用 explicit 是良好的编程实践特别是对于只接受一个参数的构造函数以防止可能的隐式类型转换导致的错误。
