Skip to content

Latest commit

 

History

History
659 lines (530 loc) · 14 KB

数据结构与算法.md

File metadata and controls

659 lines (530 loc) · 14 KB
Raw

说实话，算法这种东西没得快速提升，算法能力的提升需要日积月累慢慢累积而成的。

在互联网招聘中，不管是笔试还是面试中的手撕算法，可以考察的算法题简直不要太多。比如链表、树、数组、动态规划、回溯算法、贪心算法、甚至是拓扑都有可能考察到。

而一般说来笔试的难度是比面试稍微高一些的，面试中的手撕算法难度一般是力扣的 medium 水平，也有一些 easy 的，而笔试至少都是力扣 medium 难度以上的。

我仅在这章节中为大家盘点一下互联网大厂面试考察频率比较高的几道手撕算法题，希望我的整理对大家有一点点用处，那我就很高兴了！。

1、合并有序链表

将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的。

输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

力扣链接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/

#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;
    myList head(0);
    myList* node = &head;
    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;

    return head.next;

};

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、反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

第一种做法

#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* head = new node(1);
	node* node1 = new node(2);
	node* node2 = new node(3);
	node* node3 = new node(4);
	node* node4 = new node(5);

	head->next = node1;
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = nullptr;

	return head;
}

struct node* reverse(node* head) {
	struct node* pre = new node(-1);
	struct node* temp = new node(-1);
	pre = head;
	temp = head->next;
	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(){
	auto head = init();
	head = reverse(head);
	while (head != nullptr) {
		cout << head->data << endl;
		head = head->next;
	}

	return 0;
}

第二种做法

//头插法来做，将元素开辟在栈上，这样会避免内存泄露
ListNode* ReverseList(ListNode* pHead) {

	// 头插法
	if (pHead == nullptr || pHead->next == nullptr) return pHead;
	ListNode dummyNode = ListNode(0);
	ListNode* pre = &(dummyNode);
	pre->next = pHead;
	ListNode* cur = pHead->next;
	pHead->next = nullptr;
	//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* instance();

	class CG {
	public:
		~CG() {
			if (singlePattern::p != nullptr) {
				delete singlePattern::p;
				singlePattern::p = nullptr;
			}
		}
	};
};

singlePattern* singlePattern::p = new singlePattern();
singlePattern* singlePattern::instance() {
	return p;
}

update1: instance 手误写成 instacne，微信好友“卷轴”提出，已修正，感谢！- 20210407

懒汉模式

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缓存

设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。

它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

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

链接：https://leetcode-cn.com/problems/lru-cache-lcci

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;
	DoubleList* head, * tail;
	unordered_map<int, DoubleList*> memory;
public:
	LRU(int _capacity) {
		this->capacity = _capacity;
		head = new DoubleList(-1, -1);
		tail = new DoubleList(-1, -1);
		head->next = tail;
		tail->pre = head;
	}
	~LRU(){
		if (head != nullptr) {
			delete head;
			head = nullptr;
		}
		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
			int topKey = head->next->key;//取得key值，方便在后面删除
			removeNode(head->next);//移除头部的下一个
			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;
	}
};

8、重排链表

给定一个单链表 L：L0→L1→…→L**n-1→Ln ， 将其重新排列后变为： L0→L**n→L1→L**n-1→L2→L**n-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

力扣链接：https://leetcode-cn.com/problems/reorder-list/

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<unordered_map>

using namespace std;

struct ListNode {
	int val;
	ListNode * next;
	ListNode(int _val):val(_val),next(nullptr){}
};

ListNode* myReverseList(ListNode*head) {

	if (head == nullptr || head->next == nullptr) return head;
	ListNode dumyhead(0);
	ListNode* pre = &dumyhead;
	pre->next = head;
	ListNode* cur = head->next;
	head->next = nullptr;
	ListNode* node = new ListNode(-1);
	while (cur != nullptr) {
		node = cur;
		cur = cur->next;
		node->next = pre->next;
		pre->next = node;
	}

	return dumyhead.next;
}

ListNode* myMerge(ListNode* p1, ListNode* p2) {
	if (p1 == nullptr) return p2;
	if (p2 == nullptr) return p1;

	ListNode dumyhead(0);
	ListNode* pre = &dumyhead;
	while (p1 != nullptr && p2 != nullptr) {
		pre->next = p1;
		p1 = p1->next;
		pre = pre->next;
		pre->next = p2;
		p2 = p2->next;
		pre = pre->next;
	}
	if (p1 != nullptr) pre->next = p1;
	return dumyhead.next;

}

ListNode* myReverOrderList(ListNode *head) {
	if (head == nullptr || head->next == nullptr) return head;
	ListNode* slow = head, * fast = head->next;
	while (fast != nullptr && fast->next != nullptr) {
		slow = slow->next;
		fast = fast->next->next;
	}

	ListNode* second = slow->next;
	slow->next = nullptr;
	second = myReverseList(second);
	head = myMerge(head, second);
	return head;
}

int  main() {
	ListNode* head = new ListNode(1);
	ListNode* node1 = new ListNode(2);
	ListNode* node2 = new ListNode(3);
	ListNode* node3 = new ListNode(4);
	ListNode* node4 = new ListNode(5);
	ListNode* node5 = new ListNode(6);

	head->next = node1;
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = node5;
	node5->next = nullptr;


	head = myReverOrderList(head);
	while (head != nullptr) {
		cout << head->val << endl;
		head = head->next;
	}

	return 0;
}

9、奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
示例 2:
输入: 2->1->3->5->6->4->7->NULL 
输出: 2->3->6->7->1->5->4->NULL

说明:

应当保持奇数节点和偶数节点的相对顺序。 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

力扣链接：https://leetcode-cn.com/problems/odd-even-linked-list/

第一种解法

 ListNode* oddEvenList(ListNode* head) {
 if(head==NULL || head->next==NULL)
        {
            return head;
        }
        ListNode* first=head;//奇链表头结点
        ListNode* second=head->next;//偶链表头结点
        ListNode* cur=second;//保存偶链表头结点
        while(second != nullptr && second->next  != nullptr)
        {
            first->next=second->next;
            second->next=first->next->next;
            first=first->next;
            second=second->next;
        }
        first->next=cur;
        return head;
    }

第二种解法

ListNode* oddEvenList(ListNode* head) 
{
 if(head == NULL)
    {
        return head;
    }
    
     ListNode* p = head;
     ListNode* q = head->next;
     ListNode* evenhead = q;

    while(q != NULL &&  q->next != NULL)
    {
        p->next = p->next->next;
        p = p->next;
        q->next = q->next->next;
        q = q->next;
    }

    p->next =  evenhead;

    return head;
}