常见面试算法总结

快排

时间复杂度 O（n*log(n)）

空间复杂度 O（1）

#pragma once
#include 
using namespace std;

static void exchnage_number(vector<int> &nums, int x, int y) {
	int tmp = nums[x];
	nums[x] = nums[y];
	nums[y] = tmp;
}

static int partition(vector<int> &nums, int begin, int end) {
	//随机一个元素，避免最差情况 1，2，3，4
	int x = begin + rand() % (end - begin + 1);
	exchnage_number(nums, x, end);
	//p1 始终指向第一个小于x的位置初始化为 -1
	//p2 用于遍历
	int p1 = begin - 1, p2 = begin;
	while (p2 < end)
	{
		if (nums[p2] < nums[end]) {//一旦发小了就让P1+1的位置为这个数字
			p1++;
			exchnage_number(nums, p1, p2);//原先p1 + 1 的位置一定大于x
		}
		p2++;
	}

	p1++; //p1此时为第一个大于等于x的位置
	exchnage_number(nums, p1, end);
	return p1;
}

void quick_sort(vector<int> &nums, int begin, int end) {
	if (begin < end) {
		int pos = partition(nums, begin, end);
		quick_sort(nums, begin, pos - 1);
		quick_sort(nums, pos + 1, end);
	}
}

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

归并

时间复杂度 O（n*log(n)）

空间复杂度 O（n）

static void merge_vec(vector<int> &nums, int p1, int p2, int len) {
	int cur = 0;
	int i = p1, j = p2;
	vector<int> tmpVec(len * 2);
	//j不能越界
	while (i < p1 + len && j < p2 + len && j < nums.size()) {
		tmpVec[cur++] = nums[i] < nums[j] ? nums[i++] : nums[j++];
	}

	while (i < p1 + len) {
		tmpVec[cur++] = nums[i++];
	}

	while (j < p2 + len && j < nums.size()) {
		tmpVec[cur++] = nums[j++];
	}

	for (int k = 0; k < cur; ++k) {
		nums[p1++] = tmpVec[k];
	}
}

void merge_sort(vector<int> &nums) {
	int len = 1;
	while (len < nums.size()) {
		int i = 0;
		while (i < nums.size()) {
			int fir = i;
			int sec = i + len;
			if (sec < nums.size()) {
				merge_vec(nums, fir, sec, len);
			}
			i += 2 * len;
		}
		len *= 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

KMP

时间复杂度 O（n + m）

空间复杂度 O（n）

aa b aa
前缀aa 和 后最aa 相等那么我们直接判断 aa 后面的下一个字符

int KMP(string haystack, string needle) {
	if (needle.empty()) {
		return 0;
	}
	//0 意味着你需要从第一个位置开始判断了
	vector<int> pre(needle.size(), 0);
	/*
	* 根据模式串来构建前缀表
	*/
	for (int i = 1, j = 0; i < needle.size(); ++i) {
		while (j > 0 && needle[j] != needle[i]) {
			//如果当前失败了 前缀数组指引我们应该从哪一个位置开始判断
			j = pre[j - 1];
		}

		if (needle[j] == needle[i]) {
			j++;
		}
		//needle[i] 和 needle[i] 相等，所以前缀表的第i个位置指向 j + 1
		//就是该位置的后一个位置期望是当前前缀的j + 1位置
		pre[i] = j;
	}

	for (int i = 0, p = 0; i < haystack.size(); i++) {
		while (p > 0 && haystack[i] != needle[p]) {
			//因为相对的P位置已经匹配不上
			//查询前缀表 我们当前位置最快可以和谁比较
			p = pre[p - 1];
		}

		if (haystack[i] == needle[p]) {
			p++;
		}
		//已经等于模式串的长度了，可以结束了
		if (p == needle.size()) {
			return i - needle.size() + 1;
		}
	}

	return -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

并查集

	int findFather(vector<int> &father, int i) {
		if (father[i] != i) {
			father[i] = findFather(father, father[i]);
		}

		return father[i];
	}

	bool uion(vector<int> &father, int i, int j) {
		int fatherI = findFather(father, i);
		int fatherJ = findFather(father, j);

		if (fatherI != fatherJ) {
			father[fatherI] = fatherJ;
			return true;
		}

		return false;
	}
//use....................
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (graph[i][j] == 1 && uion(father, i, j))
				ret--;
		}
	}
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

---

---

最大堆 和 最小堆

struct AA {
	int id;	

	bool operator< (const AA &a) const {
		return id < a.id;
	}
	bool operator> (const AA &a) const {
		return id > a.id;
	}

};

//less -> 最大堆；  greater -> 最小堆
	priority_queue<AA, vector<AA>, greater<AA>> mQ;

/ 最新
/ 用法
/ 想要小的在前就用大于号，比如按字母顺序输出，就要用大于号
/

	auto cmp = [](const pair<string, int> & x, const pair<string, int> & y) {
		return x.second == y.second ? x.first > y.first : x.second < y.second;
	};
	priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp) > q(cmp);

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

---

---

STL堆——通过map 找第一个大于x的元素

	map<int, int>::iterator it, p1, p2;
	//大于等于 x 的第一个元素
	p1 = mp.lower_bound(3);
	//大于 x 的第一个元素
	p2 = mp.upper_bound(3);
1
2
3
4
5

---

---

String 使用

	string s1 = "01234";
	auto s2 = s1.substr(1, 1); // "1"
	s1 = s1.erase(3);	//"012"
	s1.append(2, '#'); //"012##"
1
2
3
4

链表常用操作

	struct ListNode {
		int val;
		ListNode *next;
		ListNode() : val(0), next(nullptr) {}
		ListNode(int x) : val(x), next(nullptr) {}
		ListNode(int x, ListNode *next) : val(x), next(next) {}
		
	};
	/** ---------------- 反转链表 ---------------------**/
	ListNode* reverseList(ListNode* head) {
		ListNode *pre = NULL, *cur = head;
		while (cur != NULL) {
			ListNode *next = cur->next;
			cur->next = pre;
			pre = cur;
			cur = next;
		}

		return pre;
	}
	/** ---------------- 获取链表中位数 ---------------------**/
		//偶数时正好 奇书时前半段多一个
	ListNode* getMidList(ListNode* head) {
		ListNode dummy;
		dummy.next = head;

		ListNode *fast = &dummy, *slow = &dummy;
		while (fast != NULL && fast->next != NULL) {
			slow = slow->next;
			fast = fast->next;
			if (fast->next != NULL)
				fast = fast->next;
		}
		return slow->next;
	}
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

组合问题

整体思路都是围绕每一个位置的元素是选还是不选

	void serchSubsets(vector<vector<int>> &rets, vector<int> &cache, vector<int>& nums, int p) {
		if (p >= nums.size()) {
			rets.emplace_back(cache);
			return;
		}
		//不要
        serchSubsets(rets, cache, nums, p + 1);
		//要
		cache.push_back(nums[p]);
		serchSubsets(rets, cache, nums, p + 1);
		cache.pop_back();
	}
	/ 过滤重复元素 / 
	void dfs(vector<vector<int>> &rets, vector<int> &cache, vector<int>& candidates, int target, int p) {
		if (target == 0) {
			rets.emplace_back(cache);
		} else if (target > 0 && p < candidates.size()) {
		

			cache.push_back(candidates[p]);
			dfs(rets, cache, candidates, target - candidates[p], p + 1);
			cache.pop_back();

            dfs(rets, cache, candidates, target, getNext(candidates, p));
		}
	}

	int getNext(vector<int>& candidates, int index) {
		int next = index + 1;
		while (next < candidates.size() && candidates[index] == candidates[next]) {
			next++;
		}

		return next;
	}

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

排列问题

不含重复元素，我最早的构想，拿标记 递归 回溯

	#define USED 100

	void dfs(vector<vector<int>> &rets, vector<int> &cache, vector<int>& nums) {
		if (cache.size() == nums.size()) {
			rets.emplace_back(cache);
		}
		else {
			for (int i = 0; i < nums.size(); ++i) {
				if (USED != nums[i]) {
					cache.push_back(nums[i]);
					nums[i] = USED;
					dfs(rets, cache, nums);
					nums[i] = cache.back();
					cache.pop_back();
				}
			}
		}
	}

	vector<vector<int>> permute(vector<int>& nums) {
		vector<vector<int>> rets;
		vector<int> cache;

		dfs(rets, cache, nums);

		return rets;
	}
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

版本2

	void search(vector<vector<int>> &rets, vector<int>& nums, int i) {
		if (i == nums.size() - 1) {
			rets.emplace_back(nums);
		}
		else {
			for (int j = i; j < nums.size(); ++j) {
				int tmp = nums[j]; nums[j] = nums[i]; nums[i] = tmp;
				search(rets, nums, i + 1);
                tmp = nums[j]; nums[j] = nums[i]; nums[i] = tmp;
			}
		}
	}

	vector<vector<int>> permute(vector<int>& nums) {
		vector<vector<int>> rets;
		search(rets, nums, 0);

		return rets;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

包含重复元素

核心思想，如果排序后和前一个相等，且前一个已经推出搜索，我们直接跳过，因为会做重复的工作

	void dfs(vector<vector<int>> &rets, vector<int> &cache, vector<int>& nums, vector<int> &mark) {
		if (cache.size() == nums.size()) {
			rets.emplace_back(cache);
		}
		else {
			for (int i = 0; i < nums.size(); ++i) {
				if (mark[i] == 0) {
					if (i - 1 >= 0 && nums[i] == nums[i - 1] && mark[i - 1] == 0)
						continue;

					cache.push_back(nums[i]);
					mark[i] = 1;
					dfs(rets, cache, nums, mark);
					mark[i] = 0;
					cache.pop_back();
				}
			}
		}
	}

	vector<vector<int>> permuteUnique(vector<int>& nums) {
		vector<vector<int>> rets;
		vector<int> cache;
		vector<int> mark(nums.size(), 0);
		sort(nums.begin(), nums.end());
		dfs(rets, cache, nums, mark);

		return rets;
	}
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

版本2

	void ExChange(vector<int> &nums, int i, int j) {
		int tmp = nums[i];
		nums[i] = nums[j];
		nums[j] = tmp;
	}

	void searchPer(vector<vector<int>> &ret, vector<int>& nums, int p) {
		if (p == nums.size()) {
			ret.emplace_back(nums);
			return;
		}
		else {
			unordered_set<int> st;

			for (int i = p; i < nums.size(); ++i) {
				if (st.find(nums[i]) == st.end()) {
					st.insert(nums[i]);
					
					ExChange(nums, i, p);
					searchPer(ret, nums, p + 1);
					ExChange(nums, i, p);
				}
			}
		}
	}

	vector<vector<int>> permuteUnique(vector<int>& nums) {
		vector<vector<int>> ret;

		searchPer(ret, nums, 0);

		return ret;
	}
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

前缀树

每一步的时间复杂度都是 n（单词长度）

	struct Node {
		vector<Node*> chirds;
		bool isEnd;
		Node() :chirds(vector<Node*>(26, NULL)), isEnd(false) {
		};
	};

	void insertToTree(Node* root, const string& str) {
		Node* p = root;
		for (char c : str) {
			if (p->chirds[c - 'a'] == NULL) {
				p->chirds[c - 'a'] = new Node();
			}
			p = p->chirds[c - 'a'];
		}

		p->isEnd = true;
	}

	string findPre(Node* root, string &word) {
		string ret = "";
		Node* p = root;
		for (char c : word) {
			if (p->chirds[c - 'a'] == NULL)
				break;

			p = p->chirds[c - 'a'];
			ret.append(1, c);

			if (p->isEnd)
				break;
		}

		return p->isEnd ? ret : "";
	}
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

二分

右收敛 那么左可以相等
左收敛 那么右可以相等
根据题意

	int peakIndexInMountainArray(vector<int>& arr) {
		int i = 0, j = arr.size() - 1;

		while (i < j) {
			int mid = j - (j - i) / 2; 
			if (arr[mid] > arr[mid - 1]) {
				i = mid;
			}
			else {
				j = mid - 1;
			}
		}
		return i;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

滑动窗口

1.初始化 i = 0 ，j =0
2.j 向后扩展，记录满足条件的元素
3 i 弹出不满足的窗口前部
4. 窗口大小为 j - i + 1

	 int lengthOfLongestSubstringKDistinct(string s, int k) {
		 unordered_map<char, int> table;
		 int count = 0;

		 int ret = 0;

		 for (int i = 0, j = 0; j < s.size(); ++j) {
			 table[s[j]]++;
			 if (table[s[j]] == 1) {
				 count++;
			 }
		 
			 while (count > k) {
				 
				 table[s[i]]--;
				 if (table[s[i]] == 0) {
					 count--;
				 }
				 i++;
			 }

			 ret = max(ret, j - i + 1);
		 }

		 return ret;
	 }
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

水塘抽样

	int pick(int target) {
		int ans;
		for (int i = 0, cnt = 0; i < nums.size(); ++i) {
			if (nums[i] == target) {
				++cnt; // 第 cnt 次遇到 target
				if (rand() % cnt == 0) {
					ans = i;
				}
			}
		}
		return ans;
	}
1
2
3
4
5
6
7
8
9
10
11
12

除法不要比大小

6076. 表示一个折线图的最少线段数

本来我是用的是除法，但是一直ac不了，改成乘法后AC

	int minimumLines(vector<vector<int>>& stockPrices) {
		if (stockPrices.size() < 2)
			return 0;

		sort(stockPrices.begin(), stockPrices.end());

		long y = stockPrices[1][1] - stockPrices[0][1];
		long x = stockPrices[1][0] - stockPrices[0][0];

		int ret = 1;

		for (int i = 2; i < stockPrices.size(); ++i) {
			long _y = stockPrices[i][1] - stockPrices[i - 1][1];
			long _x = stockPrices[i][0] - stockPrices[i - 1][0];

			if (_x * y != _y * x) {
				y = _y;
				x = _x;
				ret++;
			}
		}

		return ret;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

最小栈

最小栈确定边界

TODO

前缀和

TODO