面试题——各种功能函数实现

实现自己的memcpy

void *my_memcpy(void *dest, void *src, int num){ assert(dest != NULL && src != NULL); char *pdest = (char *)dest; char *psrc = (char *)src; while(num--){ *pdest = *psrc; pdest++; psrc++; } return dest; }

实现LRU缓存机制 这个思路是维护一个hash用来快速查找，维护一个双向链表使得有序，新访问的元素放前面，若满了，pop_back删除最后元素

class LRUCache { list<pair<int, int>> cache; unordered_map<int, list<pair<int, int>>::iterator> map; int cap; public: LRUCache(int capacity) { cap = capacity; } int get(int key) { if (map.count(key) > 0){ //注意，这里一定要得到实体temp，而不是迭代器temp，因为后面erase会丢失 auto temp = *map[key]; cache.erase(map[key]); map.erase(key); cache.push_front(temp); map[key] = cache.begin(); return temp.second; } return -1; } void put(int key, int value) { if (map.count(key) > 0){ cache.erase(map[key]); map.erase(key); } else if (cap == cache.size()){ auto temp = cache.back(); cache.pop_back(); map.erase(temp.first); } cache.push_front(pair<int, int>(key, value)); map[key] = cache.begin(); } }; /** * Your LRUCache object will be instantiated and called as such: * LRUCache* obj = new LRUCache(capacity); * int param_1 = obj->get(key); * obj->put(key,value); */

实现平衡树旋转

#include <iostream> using namespace std; struct node { int val; struct node *left, *right; }; node *rotateLeft(node *root) { node *t = root->right; root->right = t->left; t->left = root; return t; } node *rotateRight(node *root) { node *t = root->left; root->left = t->right; t->right = root; return t; } node *rotateLeftRight(node *root) { root->left = rotateLeft(root->left); return rotateRight(root); } node *rotateRightLeft(node *root) { root->right = rotateRight(root->right); return rotateLeft(root); } int getHeight(node *root) { if(root == NULL) return 0; return max(getHeight(root->left), getHeight(root->right)) + 1; } node *insert(node *root, int val) { if(root == NULL) { root = new node(); root->val = val; root->left = root->right = NULL; } else if(val < root->val) { root->left = insert(root->left, val); if(getHeight(root->left) - getHeight(root->right) == 2) root = val < root->left->val ? rotateRight(root) : rotateLeftRight(root); } else { root->right = insert(root->right, val); if(getHeight(root->left) - getHeight(root->right) == -2) root = val > root->right->val ? rotateLeft(root) : rotateRightLeft(root); } return root; } int main() { int n, val; scanf("%d", &n); node *root = NULL; for(int i = 0; i < n; i++) { scanf("%d", &val); root = insert(root, val); } printf("%d", root->val); return 0; }

实现一个多态

#include <iostream> using namespace std; class Shape { protected: int width, height; public: Shape( int a=0, int b=0){ width = a; height = b; } virtual int area(){ cout << "Parent class area :" <<endl; return 0; } }; class Rectangle: public Shape{ public: Rectangle( int a=0, int b=0):Shape(a, b) { } int area (){ cout << "Rectangle class area :" <<endl; return (width * height); } }; class Triangle: public Shape{ public: Triangle( int a=0, int b=0):Shape(a, b) { } int area (){ cout << "Triangle class area :" <<endl; return (width * height / 2); } }; // 程序的主函数 int main( ) { Shape *shape; Rectangle rec(10,7); Triangle tri(10,5); // 存储矩形的地址 shape = &rec; // 调用矩形的求面积函数 area shape->area(); // 存储三角形的地址 shape = &tri; // 调用三角形的求面积函数 area shape->area(); //此时父类指针有了多种形态，这就是多态的本质 return 0; } //下面是输出结果 //Rectangle class area //Triangle class area

多线程与互斥锁简单实例

#include<windows.h> #include <iostream> #include <chrono> #include <thread> using namespace std; int number1 = 0; int number2 = 0; int sum = 0; mutex g_lock; int ThreadProc1(){ g_lock.lock(); number1 = rand() % 10; g_lock.unlock(); this_thread::sleep_for(chrono::milliseconds(10)); return 0; } int ThreadProc2(){ g_lock.lock(); number2 = rand() % 10; g_lock.unlock(); this_thread::sleep_for(chrono::milliseconds(10)); return 0; } int ThreadProc2(){ g_lock.lock(); sum = number1 + number2; g_lock.unlock(); this_thread::sleep_for(chrono::milliseconds(10)); return 0; } int main() { thread t1(ThreadProc1); thread t2(ThreadProc2); thread t3(ThreadProc2); t1.join();//阻塞直到线程执行完成 t2.join(); t3.join(); system("pause"); return 0; } //如果不想阻塞在这里就将join()换成使用线程的detach()方法，将线程与线程对象分离，线程就可以继续运行下去，并且不会造成影响。

生产者消费者模型简单实现 原理 存储的数据的区域可以用一个队列来模拟，然后我们通过C++11提供的条件变量来通知写入线程在数据不满的时候进行写入，在数据满的时候挂起，对读取线程也是同理。

#include <mutex> #include <condition_variable> #include <deque> #include <vector> #include <iostream> #include <thread> using namespace std; std::mutex g_mtxDeque; std::mutex g_mtxCout; std::condition_variable g_cv_not_empty; std::condition_variable g_cv_not_full; std::deque<int> g_deque; int g_itemIndex = 0; const int g_kItemSize = 30;//产品个数 const int g_kDequeSize = 10;//队列大小 void produceItem() { this_thread::sleep_for(chrono::seconds(1)); unique_lock<mutex> lock(g_mtxDeque);//队列加锁 g_cv_not_full.wait(lock, []() { return g_deque.size() < g_kDequeSize; });//直到队列满，此时wait就阻塞在这里 ++g_itemIndex; g_deque.push_back(g_itemIndex); { lock_guard<mutex> lock_guard(g_mtxCout); cout << "produce item " << g_itemIndex << endl; } lock.unlock(); g_cv_not_empty.notify_all();//通知线程 } void consumeItem() { this_thread::sleep_for(chrono::seconds(2)); unique_lock<mutex> lock(g_mtxDeque); g_cv_not_empty.wait(lock, []() { return !g_deque.empty(); });//队列为空只，此时wait将阻塞在这里 int itemIndex = g_deque.front(); g_deque.pop_front(); { lock_guard<mutex> lock_guard(g_mtxCout); cout << "consume item " << itemIndex << endl; } lock.unlock(); g_cv_not_full.notify_one(); } void produceTask() { int count = g_kItemSize; while (count--){ produceItem(); } } void consumeTask() { int count = g_kItemSize; while (count--){ consumeItem(); } } //单生产者单消费者模型 void consumeProduceTest(){ std::vector<std::thread> threads; thread thread1(produceTask); thread thread1(consumeTask); thread1.join(); thread2.join(); }

string类的实现

class my_string { public: my_string(char *str == nullptr); ~my_string(); my_string(const my_string& other); my_string& operator=(const my_string& other); private: char *m_data; }; my_string::my_string(char *str){ if (str == nullptr){ m_data = new char[1]; m_data = '\0'; } else{ int len = strlen(str); m_data = new char[len+1]; strcpy(m_data, str); } } my_string::my_string(const my_string& other){ int len = strlen(other.m_data); m_data = new char[len+1]; strcpy(m_data, other.m_data); } my_string& my_string::operator=(const my_string& other){ if (this == &other) return *this; delete[] m_data; int len = strlen(other.m_data); m_data = new char[len+1]; strcpy(m_data, other.m_data); return *this; } my_string::~my_string(){ if (m_data != nullptr){ delete[] m_data; m_data = nullptr; } }

抢红包算法 两倍均值法

#include <bits/stdc++.h> using namespace std; int main(){ double money; while (cin >> money){ int n = 10; for (int i=0; i<n; i++){ double max = money / n * 2;//区间 double randval = rand() / double(RAND_MAX);//生成0-1的浮点数 cout << randval * max << endl; money -= randval * max; } } return 0; }

另一种方法是先为每个人分配0.01元，然后开始随机抽取一个红包增加0.01元，直到总金额为0 真正随机的是第三种方法，线段法： 1、如何确定每一条子线段的长度呢？由“切割点”来决定。当N个人一起抢红包的时候，就需要确定N-1个切割点。 2、因此，当N个人一起抢总金额为M的红包时，我们需要做N-1次随机运算，以此确定N-1个切割点。随机的范围区间是（1， M）。 3、当所有切割点确定以后，子线段的长度也随之确定。这样每个人来抢红包的时候，只需要顺次领取与子线段长度等价的红包金额即可。

#include <bits/stdc++.h> using namespace std; int main(){ double money; while (cin >> money){ int n = 10; vector<double> arr(n-1, 0.01); for (int i=0; i<n-1; i++){ arr[i] += rand() / double(RAND_MAX) * (money-0.1);//生成0-1的浮点数 } sort(arr.begin(), arr.end()); cout << arr[0] << endl; for (int i=1; i<n-1; i++) cout << arr[i]-arr[i-1] << endl; cout << money-arr[arr.size()-1] << endl; } return 0; }

洗牌算法

#include <bits/stdc++.h> using namespace std; int main(){ double money; while (cin >> money){ vector<double> arr(10, 0); for (int i=0; i<10; i++) arr[i] = i; for (int i=0; i<10; i++){ int randval = rand() % (arr.size()-i); int temp = arr[randval]; arr.erase(arr.begin()+randval); arr.push_back(temp); } for (int i=0; i<10; i++) cout << arr[i] << endl; } return 0; }

实现单例模式

template <typename T> class singleInstance{ public: static singleInstance* instance; static singleInstance* getsingleInstance(){ if (instance == NULL){ pthread_mutex_t mutex;//mutex mlock; pthread_mutex_lock(&mutex);//mlock.lock(); if (instance == NULL){ instance = new singleInstance(); } pthread_mutex_unlock(&mutex);//mlock.unlock(); } return instance; }; private: singleInstance(){}; ~singleInstance(){}; singleInstance(const singleInstance<T>& other){}; singleInstance<T>& operator=(const singleInstance<T>& other){}; }; //饿汉式 singleInstance* singleInstance::instance = new singleInstance(); //懒汉式 static singleInstance* instance = singleInstance::getsingleInstance();

实现strcpy

char* Strcpy(char* dst, const char* source){ assert(dst != NULL && source != NULL); char* re = dst; while ((*dst++ == *source++) != '\0'); return re; }

shared共享指针实现

#include <iostream> #include <stdlib.h> using namespace std; template <typename T> class mysharedPtr { public: mysharedPtr(T* p = NULL); ~mysharedPtr(); mysharedPtr(const mysharedPtr<T>& other); mysharedPtr<T>& operator=(const mysharedPtr<T>& other); private: T* m_ptr; unsigned int* m_count; }; template <typename T> mysharedPtr<T>::mysharedPtr(T* p) { m_ptr = p; m_count = new unsigned int(0); ++(*m_count); cout << "Constructor is succeed!" << endl; } template <typename T> mysharedPtr<T>::~mysharedPtr() { --(*m_count); if ((*m_count) == 0) { delete[] m_ptr; m_ptr = NULL; delete[] m_count; m_count = NULL; cout << "Destructor is succeed!" << endl; } } template <typename T> mysharedPtr<T>::mysharedPtr(const mysharedPtr<T>& other) { m_ptr = other.m_ptr; m_count = other.m_count; ++(*m_count); cout << "Copy constructor is succeed!" << endl; } template <typename T> mysharedPtr<T>& mysharedPtr<T>::operator=(const mysharedPtr<T>& other) { // 《C++ primer》：“这个赋值操作符在减少左操作数的使用计数之前使other的使用计数加1， // 从而防止自身赋值”而导致的提早释放内存 ++(*other.m_count); --(*m_count); // 将左操作数对象的使用计数减1，若该对象的使用计数减至0，则删除该对象 if ((*m_count) == 0) { delete[] m_ptr; m_ptr = NULL; delete[] m_count; m_count = NULL; cout << "Left side object is deleted!" << endl; } m_ptr = other.m_ptr; m_count = other.m_count; cout << "Assignment operator overloaded is succeed!" << endl; return *this; } int main() { // Test Constructor and Assignment Operator Overloaded mysharedPtr<int> p1(new int(0)); p1 = p1; // Test Copy Constructor mysharedPtr<int> p2(p1); // Test Assignment Operator Overloaded mysharedPtr<int> p3(new int(1)); p3 = p1; system("Pause"); return 0; }

简单工程模式

//产品类（抽象类，不能实例化） class Product{ public: Product(){}; virtual void show()=0; //纯虚函数 }; class productA:public Product{ public: productA(){}; ~productA(){}; }; class productB:public Product{ public: productB(){}; ~productB(){}; }; class simpleFactory{ private: Product* m; public: simpleFactory(){}; Product* product(const string str){ if (str == "productA") m = new productA(); if (str == "productB") m = new productB(); return m; }; };

抽象工程模式

//产品类（抽象类，不能实例化） class Product{ public: Product(){} virtual void show()=0; //纯虚函数 }; //产品1 class Product_A:public Product{ public: Product_A(){} void show(){ cout<<"This is Product_A"<<endl; } }; //产品2 class Product_B:public Product{ public: Product_B(){} void show(){ cout<<"This is Product_B"<<endl; } }; class Factory{//抽象类 public: virtual Product* CreateProduct()=0; }; class Factor_A:public Factory{//工厂类A，只生产A产品 public: Product* CreateProduct(){ Product* _Product=nullptr; _Product=new Product_A(); return _Product; } }; class Factor_B:public Factory{//工厂类B，只生产B产品 public: Product* CreateProduct(){ Product* _Product=nullptr; _Product= new Product_B(); return _Product; } }; int main(){ Product* _Product=nullptr; auto MyFactory_A=new Factor_A(); _Product=MyFactory_A->CreateProduct();// 调用产品A的工厂来生产A产品 _Product->show(); delete _Product; auto MyFactory_B=new Factor_B(); _Product=MyFactory_B->CreateProduct();// 调用产品B的工厂来生产B产品 _Product->show(); delete _Product; getchar(); return 0; }

循环队列实现

class MyCircularQueue { private: vector<int> data; int head; int tail; int size; public: /** Initialize your data structure here. Set the size of the queue to be k. */ MyCircularQueue(int k) { data.resize(k); head = -1; tail = -1; size = k; } /** Insert an element into the circular queue. Return true if the operation is successful. */ bool enQueue(int value) { if (isFull()) { return false; } if (isEmpty()) { head = 0; } tail = (tail + 1) % size; data[tail] = value; return true; } /** Delete an element from the circular queue. Return true if the operation is successful. */ bool deQueue() { if (isEmpty()) { return false; } if (head == tail) { head = -1; tail = -1; return true; } head = (head + 1) % size; return true; } /** Get the front item from the queue. */ int Front() { if (isEmpty()) { return -1; } return data[head]; } /** Get the last item from the queue. */ int Rear() { if (isEmpty()) { return -1; } return data[tail]; } /** Checks whether the circular queue is empty or not. */ bool isEmpty() { return head == -1; } /** Checks whether the circular queue is full or not. */ bool isFull() { return ((tail + 1) % size) == head; } }; ** * Your MyCircularQueue object will be instantiated and called as such: * MyCircularQueue obj = new MyCircularQueue(k); * bool param_1 = obj.enQueue(value); * bool param_2 = obj.deQueue(); * int param_3 = obj.Front(); * int param_4 = obj.Rear(); * bool param_5 = obj.isEmpty(); * bool param_6 = obj.isFull(); */