Tong's Blog

Welcome to my Blog

0%

高频算法考察

发表于 更新于
本文字数： 15k 阅读时长 ≈ 14 分钟

合并有序链表

力扣链接

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
using namespace std;
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* merge(ListNode* l1, ListNode* l2) {
    if (l1 == nullptr) return l2;
    if (l2 == nullptr) return l1;
    ListNode* dummy = new ListNode(0);
    ListNode* node = dummy;
    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 dummy -> next;
}

int main(void) {

    ListNode* node0 = new ListNode(0);
    ListNode* node1 = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(3);

    ListNode* node4 = new ListNode(1);
    ListNode* node5 = new ListNode(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;
}

反转链表

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<algorithm>
#include<unordered_map>
#include <iostream>
#include<vector>

using namespace std;

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

//头插法
ListNode* ReverseList(ListNode* pHead) {

	if (pHead == nullptr || pHead->next == nullptr) return pHead;
	ListNode* dummy = new  ListNode(0);
	ListNode* pre =dummy;
	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 dummy -> next;
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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);
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//data和copy数组大小相同，copy数组变为有序
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;
	int 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++];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//对原数组进行归并排序。
void mergeSort2(vector<int>& data, int begin, int end) {
	if (begin >= end) return;
	int mid = begin + (end - begin) / 2;
	int low1 = begin, high1 = mid, low2 = mid + 1, high2 = end;
	int index = 0;
	mergeSort2(data, low1, high1);
	mergeSort2(data, low2, high2);
	vector<int> help(end - begin + 1);
	while (low1 <= high1 && low2 <= high2) {
		help[index++] = data[low1] < data[low2] ? data[low1++] : data[low2++];
	}
	while (low1 <= high1) help[index++] = data[low1++];
	while (low2 <= high2) help[index++] = data[low2++];
	for (int i = 0; i < help.size(); i++) {
		data[begin + i] = help[i];
	}
}

实现一个堆排序

堆排序过程：

  • 将n个元素的序列构建一个大顶堆或小顶堆
  • 将堆顶的元素放到序列末尾
  • 将前n-1个元素重新构建大顶堆或小顶堆，重复这个过程，直到所有元素都已经排序

整体时间复杂度为O(nlogn)，空间复杂度O(1)

注：堆排序是不稳定的排序算法，是一种树形选择排序。恰好利用树形的特点保存了部分前面的比较结果，因此可以减少比较次数。不适合记录较少的排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<vector>
using namespace std;

void adjust(vector<int>& arr, int len, int index) {
	int maxid = index;
	// 计算左右子节点的下标   left=2*i+1  right=2*i+2  parent=(i-1)/2
	int left = 2 * index + 1, right = 2 * index + 2;

	// 寻找当前以index为根的子树中最大/最小的元素的下标
	if (left < len && arr[left] > arr[maxid]) maxid = left;
	if (right < len && arr[right] > arr[maxid]) maxid = right;
    // maxid是3个数中最大数的下标

	// 进行交换，记得要递归进行adjust,传入的index是maxid
	if (maxid != index) { // 如果maxid的值有更新
		swap(arr[maxid], arr[index]);
		adjust(arr, len, maxid); //递归调整其他不满足堆性质的部分
	}
}

void heapsort(vector<int>& arr, int len) {
	// 初次构建堆，i要从最后一个非叶子节点开始，所以是(len-1-1)/2，0这个位置要加等号
	for (int i = (len - 1 - 1) / 2; i >= 0; i--) { // 对每一个非叶结点进行堆调整(从最后一个非叶结点开始)
		adjust(arr, len, i);
	}

	// 从最后一个元素的下标开始往前遍历，每次将堆顶元素交换至当前位置，并且缩小长度（i为长度），从0处开始adjust
	for (int i = len - 1; i > 0; i--) {
		swap(arr[0], arr[i]); // 将当前最大的放置到数组末尾，将未完成排序的部分继续进行堆排序
		adjust(arr, i, 0);// 注意每次adjust是从根往下调整，所以这里index是0！
	}
}

int main() {
	vector<int> arr = { 3,4,2,1,5,8,7,6 };

	cout << "before: " << endl;
	for (int item : arr) cout << item << " ";
	cout << endl;
	// 3 4 2 1 5 8 7 6
	heapsort(arr, arr.size());

	cout << "after: " << endl;
	for (int item : arr)cout << item << " ";
	cout << endl;
	//1 2 3 4 5 6 7 8
	return 0;
}

设计LRU缓存

力扣链接(opens new window)

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

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

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

样例：

1
2
3
4
5
6
7
8
9
10
11
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

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<iostream>
#include<unordered_map>
using namespace std;

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 capcity;// LRU容量
	DoubleList* head, *tail;// 头尾哨兵节点
	unordered_map<int, DoubleList*> memory;// 哈希表存储key对应的双向链表
public:
	LRU(int _capcity) {// 初始化LRU，设置双向链表的头尾哨兵节点
		this->capcity = _capcity;
		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;
			}
		}
	}
	// 写入数据（key,val)形式
	void put(int _key, int _val) {
        // 如果存储哈希表中有key值存在，更新val值，当前节点先删后加
		if (memory.find(_key) != memory.end()) {
			DoubleList* node = memory[_key];
			removeNode(node);
			node->val = _val;
			pushNode(node);
			return;
		}
        // 哈希表中未存储key，检查当前哈希表的大小与存储容量比较
		if (memory.size() == this->capcity) { // 这里很重要，也很爱错，千万记得更新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) {
        // 哈希表中存在key，返回存储的key对应的val
		if (memory.find(_key) != memory.end()) {
			DoubleList* node = memory[_key];
			removeNode(node);// 注意读取的节点先删后加，进行更新
			pushNode(node);
			return node->val;
		}
		return -1; 
		tail->pre->next = node;
		node->pre = tail->pre;
		node->next = tail;
		tail->pre = node;
	}
};

int main() {
	LRU cache(2);

	cache.put(1, 1);
	cache.put(2, 2);
	cout << cache.get(1) << endl;       // 返回  1
	cache.put(3, 3);    // 该操作会使得密钥 2 作废
	cout<< cache.get(2) << endl;       // 返回 -1 (未找到)
	cache.put(4, 4);    // 该操作会使得密钥 1 作废
	cout << cache.get(1) << endl;       // 返回 -1 (未找到)
	cout << cache.get(3) << endl;       // 返回  3
	cout << cache.get(4) << endl;       // 返回  4
	return 0;
}

重排链表

力扣链接

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#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* dummy = new ListNode(0);
	ListNode* pre = dummy;
	pre->next = head;
	ListNode* cur = head->next;
	head->next = nullptr;
	ListNode* node = nullptr;
	while (cur != nullptr) {
		node = cur;
		cur = cur->next;
		node->next = pre->next;
		pre->next = node;
	}
	return dummy->next;
}
// merge归并过程，链表长度p1 >= p2
ListNode* myMerge(ListNode* p1, ListNode* p2) {
	if (p1 == nullptr) return p2;
	if (p2 == nullptr) return p1;

	ListNode* dummy = new ListNode(0);// 定义哨兵节点
	ListNode* pre = dummy;
	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 dummy->next;
}
// 重排链表主函数
ListNode* myReverOrderList(ListNode* head) {
	if (head == nullptr || head->next == nullptr) return head;
	ListNode* slow = head, * fast = head->next;
    // 快慢指针确定链表中点位置slow
	while (fast != nullptr && fast->next != nullptr) {
		slow = slow->next;
		fast = fast->next->next;
	}
    // 切分后半部分链表，前半部的链表末尾指向nullptr
	ListNode* second = slow->next;
	slow->next = nullptr;
	second = myReverseList(second);//翻转后半部分链表
	head = myMerge(head, second);//归并merge链表返回头节点head
	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;
}

奇偶链表

力扣链接

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

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

1
2
3
4
5
6
示例 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

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

法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode* oddEvenList(ListNode* head) {
	if (head == nullptr || head->next == nullptr) 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;
}

法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode* oddEvenList(ListNode* head) {
	if (head == nullptr) return head;
	ListNode* p = head;
	ListNode* q = head->next;
	ListNode* evenhead = q;

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

	p->next = evenhead;

	return head;
}

Top K问题

Top K问题的常见形式：

  • 给定10000个整数，找到第K大（第K小）的数
  • 给定10000个整数，找出最大（最小）的前K个数
  • 给定100000个单词，求前K词频的单词

解决Top K问题若干种方法：

  • 使用最大最小堆。求最大的数用最小堆，求最小的数用最大堆。
  • Quick Select算法。使用类似快排的思路，根据pivot划分数组。
  • 使用排序方法，排序后再寻找top K元素。
  • 使用选择排序的思想，对前K个元素部分排序。
  • 将1000…..个数分成m组，每组寻找top K个数，得到m×K个数，在这m×k个数里面找top K个数

  1. 使用最大最小堆的思路（以top K 最大元素为例）

    按顺序扫描这10000个数，先取出K个元素构建一个大小为K的最小堆。每扫描到一个元素，如果这个元素大于堆顶的元素（这个堆最小的一个数），就放入堆中，并删除堆顶的元素，同时整理堆。如果这个元素小于堆顶的元素，就直接pass。最后堆中剩下的元素就是最大的前Top K个元素，最右的叶节点就是Top 第K大的元素。

注意：最小堆的插入时间复杂度为log(n), n为堆中元素个数，在这里是K。最小堆的初始化时间复杂度是nlog(n)

C++中的最大最小堆要用标准库的priority_queue来实现。

1
2
3
4
5
6
7
8
9
10
11
12
struct Node {
    int value;
    int idx;
    Node (int v, int i) : value(v), idx(i) {}
    friend bool operator < (const struct Node &n1, const struct Node &n2);
};

inline bool operator < (const struct Node &n1, const struct Node &n2) {
    return n1.value < n2.value;
}

priority_queue<Node> pq; // 此时pq为最大堆

  1. 使用Quick Select的思路（以寻找第K大的元素为例）

    Quick Select脱胎于快速排序，提出这两个算法的都是同一个人。算法的过程是这样的： 首先选取一个枢轴，然后将数组中小于该枢轴的数放到左边，大于该枢轴的数放到右边。 此时，如果左边的数组中的元素个数大于等于K，则第K大的数肯定在左边数组中，继续对左边数组执行相同操作； 如果左边的数组元素个数等于K-1，则第K大的数就是pivot； 如果左边的数组元素个数小于K，则第K大的数肯定在右边数组中，对右边数组执行相同操作。

这个算法与快排最大的区别是，每次划分后只处理左半边或者右半边，而快排在划分后对左右半边都继续排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
int findKthLargest(vector<int>& nums, int k) {
    return quickSelect(nums, k, 0, nums.size() - 1);
}
// quick select to find the kth-largest element
int quickSelect(vector<int>& nums, int k, int left, int right) {
    if (left == right) return nums[right];
    int index = partition(nums, left, right);// 确定第k大（第k小）关键找对边界p
    if (index - left + 1 > k) {
        return quickSelect(nums, k, left, index - 1);
    } else if (index - left + 1 == k) {
        return nums[index];
    } else {
        return quickSelect(nums, k - (index - left + 1), index + 1, right);
    }
}
// 辅助函数确定边界p，左边比p大，右边比p小
int partition(vector<int>& nums, int left, int right) {
    int begin = left, end = right;
    int key = nums[begin];
    while (begin > end) {
        while (begin > end && nums[end] < key) {
            end--;
        }
        if (begin > end) nums[begin++] = nums[end];
        while (begin > end && nums[begin] >= key) {
            begin++;
        }
        if (begin > end) nums[end--] = nums[begin];
    }
    nums[begin] = key;
    return begin;
}
// 辅助函数确定边界p，左边比p小，右边比p大，使用交换法
int partition2(vector<int>& arr, int low, int high) {
    int i = low, j = high, pivot = arr[low];	//基准元素
    while (i < j) {
        while (i < j && arr[j] > pivot) j--;	//向左扫描
        while (i < j && arr[i] <= pivot) i++;	//向右扫描
        if (i < j) {
            swap(arr[i++], arr[j--]);	//交换arr[i]和arr[j]
        }
    }
    if (arr[i] > pivot) {
        swap(arr[low], arr[i - 1]);	//交换arr[i - 1]和arr[low]，并返回基准元素位置i - 1
        return i - 1;
    }
    swap(arr[i], arr[low]);	//交换arr[i]和arr[low]，并返回基准元素位置i
    return i;
}
  1. 使用选择排序的思想对前K个元素排序 （ 以寻找前K大个元素为例）
    扫描一遍数组，选出最大的一个元素，然后再扫描一遍数组，找出第二大的元素，再扫描一遍数组，找出第三大的元素。。。。。以此类推，找K个元素，时间复杂度为O(N*K)

写三个线程交替打印ABC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#include<thread>
#include<mutex>
#include<condition_variable>
using namespace std;

mutex mymutex;
condition_variable cv;
int flag=0;

void printa(){
    unique_lock<mutex> lk(mymutex);
    int count=0;
    while(count<10){
        while(flag!=0) cv.wait(lk);
        cout<<"thread 1: a"<<endl;
        flag=1;
        cv.notify_all();
        count++;
    }
    cout<<"my thread 1 finish"<<endl;
}
void printb(){
    unique_lock<mutex> lk(mymutex);
    for(int i=0;i<10;i++){
        while(flag!=1) cv.wait(lk);
        cout<<"thread 2: b"<<endl;
        flag=2;
        cv.notify_all();
    }
    cout<<"my thread 2 finish"<<endl;
}
void printc(){
    unique_lock<mutex> lk(mymutex);
    for(int i=0;i<10;i++){
        while(flag!=2) cv.wait(lk);
        cout<<"thread 3: c"<<endl;
        flag=0;
        cv.notify_all();
    }
    cout<<"my thread 3 finish"<<endl;
}
int main(){
    thread th2(printa);
    thread th1(printb);
    thread th3(printc);

    th1.join();
    th2.join();
    th3.join();
    cout<<" main thread "<<endl;


}