《逆袭进大厂》第十弹之数据结构与算法 | 开放PDF编辑权限

1、合并有序链表

#include <iostream>
using namespace std;
struct myList {
int val;
myList* next;
myList(int _val) :val(_val), next(nullptr) {}
};
myList* merge(myList* l1, myList* l2) {
if (l1 == nullptr) return l2;
if (l2 == nullptr) return l1;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
node->next = l1;
l1 = l1->next;
}
else {
node->next = l2;
l2 = l2->next;
}
node = node->next;
}
if (l1 == nullptr)
node->next = l2;
if (l2 == nullptr)
node->next = l1;
};
int main(void) {
myList* node0 = new myList(0);
myList* node1 = new myList(1);
myList* node2 = new myList(2);
myList* node3 = new myList(3);
myList* node4 = new myList(1);
myList* node5 = new myList(4);
node0->next = node1;
node1->next = node2;
node2->next = node3;
node3->next = nullptr;
node4->next = node5;
node5->next = nullptr;
auto node = merge(node0, node4);
while (node != nullptr) {
cout << node->val << endl;
node = node->next;
}
return 0;
}

2、反转链表

#include<algorithm>
#include<unordered_map>
#include <iostream>
#include<vector>
using namespace std;
struct node {
int  data;
struct node* next;
node(int _data) :data(_data), next(nullptr) {
}
};
struct node* init() {
node* node1 = new node(2);
node* node2 = new node(3);
node* node3 = new node(4);
node* node4 = new node(5);
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = nullptr;
}
struct node* pre = new node(-1);
struct node* temp = new node(-1);
pre->next = nullptr;
struct node* cur = new node(-1);
cur = temp;
while (cur != nullptr) {
temp = cur;
cur = cur->next;
temp->next = pre;
pre = temp;
}
return pre;
}
int main(){
}
return 0;
}

//头插法来做，将元素开辟在栈上，这样会避免内存泄露
// 头插法
ListNode dummyNode = ListNode(0);
ListNode* pre = &(dummyNode);
//pre = cur;
ListNode* temp = nullptr;
while (cur != nullptr) {
temp = cur;
cur = cur->next;
temp->next = pre->next;
pre->next = temp;
}
return dummyNode.next;
}

3、单例模式

class singlePattern {
private:
singlePattern() {};
static singlePattern* p;
public:
static singlePattern* instacne();
class CG {
public:
~CG() {
if (singlePattern::p != nullptr) {
delete singlePattern::p;
singlePattern::p = nullptr;
}
}
};
};
singlePattern* singlePattern::p = new singlePattern();
singlePattern* singlePattern::instacne() {
return p;
}

class singlePattern {
private:
static singlePattern* p;
singlePattern(){}
public:
static singlePattern* instance();
class CG {
public:
~CG() {
if (singlePattern::p != nullptr) {
delete singlePattern::p;
singlePattern::p = nullptr;
}
}
};
};
singlePattern* singlePattern::p = nullptr;
singlePattern* singlePattern::instance() {
if (p == nullptr) {
return new singlePattern();
}
return p;
}

4、简单工厂模式

typedef enum productType {
TypeA,
TypeB,
TypeC
} productTypeTag;
class Product {
public:
virtual void show() = 0;
virtual ~Product() = 0;
};
class ProductA :public Product {
public:
void show() {
cout << "ProductA" << endl;
}
~ProductA() {
cout << "~ProductA" << endl;
}
};
class ProductB :public Product {
public:
void show() {
cout << "ProductB" << endl;
}
~ProductB() {
cout << "~ProductB" << endl;
}
};
class ProductC :public Product {
public:
void show() {
cout << "ProductC" << endl;
}
~ProductC() {
cout << "~ProductC" << endl;
}
};
class Factory {
public:
Product* createProduct(productType type) {
switch (type) {
case TypeA:
return new ProductA();
case TypeB:
return new ProductB();
case TypeC:
return new ProductC();
default:
return nullptr;
}
}
};

5、快排排序

void quickSort(vector<int>& data, int low, int high) {
//for_each(data.begin(), data.end(), [](const auto a) {cout << a << " "; });
//cout << endl;
if (low >= high) return;
int key = data[low], begin = low, end = high;
while (begin < end) {
while (begin<end && data[end]>key) {
end--;
}
if (begin < end) data[begin++] = data[end];
while (begin<end && data[begin]<= key) {
begin++;
}
if (begin < end) data[end--] = data[begin];
}
data[begin] = key;
quickSort(data, low, begin - 1);
quickSort(data, begin + 1,high);
}

6、归并排序

void mergeSort(vector<int>& data, vector<int>& copy, int begin, int end) {
if (begin >= end) return;
int mid = begin + (end - begin) / 2;
int low1 = begin, high1 = mid, low2 = mid + 1, high2 = end, index = begin;
mergeSort(copy, data, low1, high1);
mergeSort(copy, data, low2, high2);
while (low1 <= high1 && low2 <= high2) {
copy[index++] = data[low1] < data[low2] ? data[low1++] : data[low2++];
}
while (low1 <= high1) {
copy[index++] = data[low1++];
}
while (low2 <= high2) {
copy[index++] = data[low2++];
}
}
void mergeTest() {
vector<int> nums = { -5,-10,6,5,12,96,1,2,3 };
vector<int> copy(nums);
mergeSort(nums, copy, 0, nums.size() - 1);
nums.assign(copy.begin(), copy.end());
for_each(nums.begin(), nums.end(), [](const auto& a) {cout << a << " "; });
}

7、设计LRU缓存

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4
struct DoubleList {
int key, val;
DoubleList* pre, * next;
DoubleList(int _key,int _val):key(_key),val(_val),pre(nullptr),next(nullptr){ }
};
class LRU {
private:
int capacity;
unordered_map<int, DoubleList*> memory;
public:
LRU(int _capacity) {
this->capacity = _capacity;
tail = new DoubleList(-1, -1);
}
~LRU(){
}
if (tail != nullptr) {
delete tail;
tail = nullptr;
}
for (auto& a : memory) {
if (a.second != nullptr) {
delete a.second;
a.second = nullptr;
}
}
}
void set(int _key, int _val) {
if (memory.find(_key) != memory.end()) {
DoubleList* node = memory[_key];
removeNode(node);
node->val = _val;
pushNode(node);
return ;
}
if (memory.size() == this->capacity) {// 这里很重要，也很爱错，千万记得更新memory
memory.erase(topKey);//在memory中删除当前头部的值
}
DoubleList* node = new DoubleList(_key, _val);//新增node
pushNode(node);//放在尾部
memory[_key] = node;//记得在memory中添加进去
}
int get(int _key) {
if (memory.find(_key) != memory.end()) {
DoubleList* node = memory[_key];
removeNode(node);
pushNode(node);
return node->val;
}
return - 1;
}
void removeNode(DoubleList* node) {
node->pre->next = node->next;
node->next->pre = node->pre;
}
void pushNode(DoubleList* node) {
tail->pre->next = node;
node->pre = tail->pre;
node->next = tail;
tail->pre = node;
}
};

|
2月前
|
Web App开发 JavaScript 前端开发

847 0
|
2月前
|

57170 131
|
10天前
|

180 1
|
26天前
|

【CVPR2024】面向StableDiffusion的编辑算法FreePromptEditing，提升图像编辑效果

95615 22
|
27天前
|

【CVPR2024】阿里云人工智能平台PAI图像编辑算法论文入选CVPR2024

849 10
|
26天前
|

【调度算法】开放车间调度问题遗传算法
【调度算法】开放车间调度问题遗传算法
16 1
|
1月前
|
Java 数据安全/隐私保护
Java使用PDFBox开发包实现对PDF文档内容编辑与保存
Java使用PDFBox开发包实现对PDF文档内容编辑与保存
64 7
|
1月前
|

41 1
|
2月前
|
Python

47 5
|
1月前
|

23 0