面試常用基礎算法

- - 快速排序
  - 歸并排序
  - 堆排序
  - $n$ 皇后問題
  - 最大和子數組
  - 爬樓梯
  - 中心擴展法求最長回文子序列
  - 分割回文串
  - 動態規劃求最長回文子序列
  - 最長回文子串
  - 單調棧
  - 雙指針算法
  - 修改 + 分割回文串
  - 滑動窗口
  - 棧

快速排序

#include <iostream>
#include <algorithm>using namespace std;const int N = 1e5 + 10;int n;
int arr[N];void quick_sort(int l, int r) {if (l >= r) return;int mid = l + r >> 1;int val = arr[mid];int p1 = l - 1, p2 = r + 1;while (p1 < p2) {while (arr[++p1] < val);while (arr[--p2] > val);if (p1 < p2) swap(arr[p1], arr[p2]);}quick_sort(l, p2);quick_sort(p2 + 1, r);
}int main() {cin >> n;for (int i = 0; i < n; ++i) cin >> arr[i];quick_sort(0, n - 1);for (int i = 0; i < n; ++i) cout << arr[i] << " ";cout << "\n";return 0;
}

歸并排序

#include <iostream>
#include <algorithm>using namespace std;const int N = 1e5 + 10;int n;
int arr[N], tmp[N];void merge_sort(int l, int r) {if (l >= r) return;int mid = l + r >> 1;merge_sort(l, mid);merge_sort(mid + 1, r);int i = l, j = mid + 1, k = 0;while (i <= mid && j <= r) {if (arr[i] <= arr[j]) tmp[k++] = arr[i++];else tmp[k++] = arr[j++];}while (i <= mid) tmp[k++] = arr[i++];while (j <= r) tmp[k++] = arr[j++];for (i = l; i <= r; ++i) arr[i] = tmp[i - l];
}int main() {cin >> n;for (int i = 0; i < n; ++i) cin >> arr[i];merge_sort(0, n - 1);for (int i = 0; i < n; ++i) cout << arr[i] << " ";cout << "\n";return 0;
}

堆排序

#include <iostream>
#include <algorithm>using namespace std;const int N = 1e5 + 10;int n, k;
int heap[N], sz;void down(int u) {int t = u;int ls = u << 1;int rs = u << 1 | 1;if (ls <= sz && heap[ls] <= heap[t]) t = ls;if (rs <= sz && heap[rs] <= heap[t]) t = rs;if (t != u) {swap(heap[u], heap[t]);down(t);}
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> k;for (int i = 1; i <= n; ++i) cin >> heap[i];sz = n;for (int i = n >> 1; i >= 1; --i) down(i);while (k--) {int res = heap[1];cout << res << " ";swap(heap[1], heap[sz--]);down(1);}return 0;
}

$n$ 皇后問題

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 10;int n;
char g[N][N];bool is_valid(int x, int y) {for (int i = 0; i < n; ++i) if (g[i][y] == 'Q') return false;for (int i = 0; i < n; ++i) if (g[x][i] == 'Q') return false;int nx = x, ny = y;while (nx >= 0 && ny >= 0) {if (g[nx][ny] == 'Q') return false;nx--, ny--;}nx = x, ny = y;while (nx < n && ny >= 0) {if (g[nx][ny] == 'Q') return false;nx++, ny--;}nx = x, ny = y;while (nx >= 0 && ny < n) {if (g[nx][ny] == 'Q') return false;nx--, ny++;}nx = x, ny = y;while (nx < n && ny < n) {if (g[nx][ny] == 'Q') return false;nx++, ny++;}return true;
}void dfs(int row, int k) {if (k == 0) {for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {cout << g[i][j];}cout << "\n";}cout << "\n";return;}// 枚舉列for (int i = 0; i < n; ++i) {if (is_valid(row, i)) {g[row][i] = 'Q';dfs(row + 1, k - 1);g[row][i] = '.';}}
}int main() {cin >> n;for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {g[i][j] = '.';}}dfs(0, n);return 0;
}

最大和子數組

53.最大和子數組

class Solution {
public:int maxSubArray(vector<int>& nums) {const int N = 1e5 + 10;int arr[N];int f[N];int n = nums.size();for (int i = 0; i < n; ++i) {arr[i + 1] = nums[i];}memset(f, -0x3f, sizeof f);int res = -0x3f3f3f3f;arr[0] = 0;for (int i = 1; i <= n; ++i) {f[i] = max(arr[i], f[i - 1] + arr[i]);res = max(res, f[i]);}return res;}
};

爬樓梯

class Solution {
public:int climbStairs(int n) {const int N = 46;int f[N] = {0};f[0] = 1;f[1] = 1;for (int i = 2; i <= n; ++i) f[i] = f[i - 1] + f[i - 2];return f[n];}
};

中心擴展法求最長回文子序列

516. 最長回文子序列

采用中心擴展法, 分別枚舉所有可能的回文串的中心位置
然后再將回文串長度的類別分為奇數和偶數, 分別統計答案

#include <string>
using namespace std;class Solution {
public:int countSubstrings(string s) {int res = 0;int n = s.size();for (int i = 0; i < n; ++i) {int l = i, r = i;while (l >= 0 && r < n && s[l--] == s[r++]) res++;l = i, r = i + 1;while (l >= 0 && r < n && s[l--] == s[r++]) res++;}return res;}
};

分割回文串

131.分割回文串

先用DP預處理所有合法的子串, 然后DFS所有分割方式

#include <iostream>
#include <vector>
#include <cstring>using namespace std;class Solution {
public:const int N = 20;bool f[20][20];void dfs(string &str, vector<vector<string>> &res, vector<string> &tmp, int u) {if (u >= str.size()) {res.push_back(tmp);return;}for (int v = u; v < str.size(); ++v) {if (f[u][v]) {tmp.push_back(str.substr(u, v - u + 1));dfs(str, res, tmp, v + 1);tmp.pop_back();}}}vector<vector<string>> partition(string s) {memset(f, false, sizeof f);int n = s.size();// 預處理回文子串for (int i = 0; i < n; ++i) {f[i][i] = true;if (i + 1 < n && s[i] == s[i + 1]) {f[i][i + 1] = true;}}for (int len = 3; len <= n; ++len) {for (int i = 0; i + len - 1 < n; ++i) {int j = i + len - 1;if (s[i] == s[j] && f[i + 1][j - 1]) {f[i][j] = true;}}}vector<vector<string>> res;vector<string> tmp;dfs(s, res, tmp, 0);return res;}
};

動態規劃求最長回文子序列

516.最長回文子序列

class Solution {
public:int longestPalindromeSubseq(string s) {const int N = 1010;int f[N][N] = {0};int n = s.size();for (int i = 0; i < n; ++i) f[i][i] = 1;for (int len = 2; len <= n; ++len) {for (int i = 0; i + len - 1 < n; ++i) {int j = i + len - 1;if (s[i] == s[j]) f[i][j] = f[i + 1][j - 1] + 2;else f[i][j] = max(f[i + 1][j], f[i][j - 1]);}}return f[0][n - 1];}
};

最長回文子串

5.最長回文子串

動態規劃預處理每個狀態是否是合法的, 同時記錄最長的回文字符串

class Solution {
public:string longestPalindrome(string s) {const int N = s.size() + 10;bool f[N][N];memset(f, false, sizeof f);int n = s.size();for (int i = 0; i < n; ++i) f[i][i] = true;int start = 0, sz = 1;for (int i = 0; i < n; ++i) {int j = i + 1;if (s[i] == s[j]) {f[i][j] = true;start = i, sz = 2;}}for (int len = 3; len <= n; ++len) {for (int i = 0; i + len - 1 < n; ++i) {int j = i + len - 1;if (s[i] == s[j] && f[i + 1][j - 1]) {f[i][j] = true;if (j - i + 1 > sz) {sz = j - i + 1;start = i;}}}}string res = "";for (int i = start; i < start + sz; ++i) res += s[i];return res;}
};

單調棧

42.接雨水

棧底到棧頂的存儲的柱子高度是遞減的, 當新加入的柱子高度大于當前棧頂的高度的時候, 說明能夠形成凹槽, 然后邊彈棧邊計算積水面積

class Solution {
public:int trap(vector<int>& height) {const int N = height.size() + 10;int stack[N], top = 0;int res = 0;for (int i = 0; i < height.size(); ++i) {int val = height[i];while (top && val > height[stack[top]]) {int pre = stack[top--];if (!top) break;// 計算兩個柱子之間的距離int d = i - stack[top] - 1;// 減去凹槽的高度int h = min(height[stack[top]], height[i]) - height[pre];res += h * d;}stack[++top] = i;}return res;}
};

雙指針算法

C - Shortest Duplicate Subarray

問題陳述
給你一個正整數
$N$ 和一個長度為 $N$ 的整數序列
請判斷 $A$ 是否存在一個非空(連續)子數組，它有一個重復值，多次出現在 $A$ 中。如果存在這樣的子數組，求最短的子數組的長度。

維護滑動窗口, 使用 $se t$ 記錄是否有重復元素, 如果有重復元素縮短左側窗口, 直到沒有重復元素, 然后遞增右側窗口

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>using namespace std;const int N = 2e5 + 10, INF = 0x3f3f3f3f;int n, arr[N];
unordered_set<int> s;int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n;for (int i = 0; i < n; ++i) cin >> arr[i];int res = INF;int l = 0;for (int r = 0; r < n; ++r) {while (s.count(arr[r])) {res = min(res, r - l + 1);s.erase(arr[l++]);}s.insert(arr[r]);}if (res == INF) res = -1;cout << res << endl;return 0;
}

11. 盛最多水的容器

貪心策略: 定義兩個指針指向兩側, 每次移動高度較小的那個指針, 這樣能夠圍成的面積有可能變大

class Solution {
public:int maxArea(vector<int>& height) {int res = 0;int l = 0, r = height.size() - 1;while (l < r) {int h = min(height[l], height[r]);res = max(res, h * (r - l));height[l] < height[r] ? l++ : r--;}return res;}
};

LCR 179. 查找總價格為目標值的兩個商品

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int l = 0, r = price.size() - 1;vector<int> res;while (l < r) {int sum = price[l] + price[r];if (sum == target) {res.push_back(price[l]);res.push_back(price[r]);break;}else if (sum < target) l++;else r--;}return res;}
};

鏈表中的中間節點

class Solution {
public:ListNode* middleNode(ListNode* head) {//		定義快慢指針, 快指針走到終點, 慢指針走到中間ListNode *u = head;ListNode *v = head;while (u != nullptr) {if (u->next == nullptr) break;u = (u->next)->next;v = v->next;}return v;}
};

判斷鏈表中是否含有環

class Solution {
public:bool hasCycle(ListNode *head) {ListNode *u = head;ListNode *v = head;while (u != nullptr && v != nullptr) {if (u->next == nullptr) break;u = u->next->next;v = v->next;if (u == v) return true;}return false;}
};

尋找鏈表中倒數第k個位置

class Solution {
public:ListNode* trainingPlan(ListNode* head, int cnt) {ListNode *u = head;ListNode *v = head;cnt--;while (cnt--) u = u->next;while (u->next != nullptr) {u = u->next;v = v->next;}return v;}
};

392. 判斷子序列

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>using namespace std;class Solution {
public:bool isSubsequence(string s, string t) {int i = 0, j = 0;int n = s.size(), m = t.size();if (n == 0) return true;while (i < n && j < m) {if (s[i] == t[j]) {if (i == n - 1) {cout << i << endl;return true;}i++;}j++;}return false;}
};

將所有0移動到數組末尾, 同時保證剩余元素相對位置不變

class Solution {
public:void moveZeroes(vector<int>& nums) {int n = nums.size();
//		i是處理好的下一個位置, j遍歷整個數組int i = 0, j = 0;while (j < n) {if (nums[j]) {swap(nums[i], nums[j]);i++;}j++;}}
};

修改 + 分割回文串

1278. 分割回文串 III

$f [i] [j]$ 代表考慮前 $i$ 個字符并且已經分割了 $j$ 個回文子串的所有方案的集合

屬性: 修改的最少字符

如何進行集合劃分/狀態轉移
考慮第 $j$ 個回文子串的起始位置 $i_0$
$f[i][j] = min(f[i_0][j - 1] + cost(S, i_0 + 1, i))$
時間復雜度: $O(n ^ 3k)$

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>using namespace std;const int N = 110;int n;
//f[i][j]考慮前i個字符, 已經分割了j個子串的最小修改字符次數
int f[N][N];class Solution {
public:
//	計算將l到r修改為回文串需要的最小代價int cost(string &s, int l, int r) {int res = 0;for (int i = l, j = r; i < j; ++i, --j) {if (s[i] != s[j]) res++;}return res;}int palindromePartition(string s, int k) {n = s.size();memset(f, 0x3f, sizeof f);f[0][0] = 0;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= min(i, k); ++j) {
//				如果只分割了一個子串, 那么就是從開頭到當前位置if (j == 1) f[i][j] = cost(s, 0, i - 1);
//				枚舉最后一個回文子串的起始位置else {for (int l = j - 1; l < i; ++l) {f[i][j] = min(f[i][j], f[l][j - 1] + cost(s, l, i - 1));}}}}return f[n][k];}
};

滑動窗口

1004. 最大連續1的個數 III

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n = nums.size();int l = 0, r = 0;int res = 0;int cnt = 0;while (r < n) {if (nums[r] == 0) cnt++;while (cnt > k) {if (nums[l] == 0) cnt--;l++;}res = max(res, r - l + 1);r++;}return res;}
};

替換后最長重復字符

class Solution {
public:int characterReplacement(string s, int k) {int n = s.size();int l = 0, r = 0;
//		記錄每個字符出現的次數int cnt[26] = {0};int max_cnt = 0;int res = 0;while (r < n) {cnt[s[r] - 'A']++;max_cnt = max(max_cnt, cnt[s[r] - 'A']);if (r - l + 1 - max_cnt > k) {cnt[s[l] - 'A']--;l++;}res = max(res, r - l + 1);r++;}return res;}
};

2024. 考試的最大困擾度

class Solution {
public:int get(char c) {if (c == 'F') return 0;return 1;}int maxConsecutiveAnswers(string answerKey, int k) {int n = answerKey.size();int l = 0, r = 0;int cnt[2] = {0};int max_cnt = 0;int res = 0;while (r < n) {int &val = cnt[get(answerKey[r])];val++;max_cnt = max(max_cnt, val);if (r - l + 1 - max_cnt > k) {cnt[get(answerKey[l])]--;l++;}res = max(res, r - l + 1);r++;}return res;}
};

395. 至少有 K 個重復字符的最長子串

外層枚舉的是不同字符的種類

class Solution {
public:int longestSubstring(string s, int k) {int n = s.size();int res = 0;for (int i = 1; i <= 26; ++i) {int cnt[26] = {0};int l = 0, r = 0;int type_cnt = 0;int tmp = 0;while (r < n) {
//				當前窗口中字符類型數量小于等于iif (type_cnt <= i) {int u = s[r] - 'a';if (cnt[u] == 0) type_cnt++;cnt[u]++;if (cnt[u] == k) tmp++;r++;}
//				當前窗口字符數量大于i, 縮小窗口else {int u = s[l] - 'a';if (cnt[u] == k) tmp--;cnt[u]--;if (cnt[u] == 0) type_cnt--;l++;}if (type_cnt == i && tmp == i) res = max(res, r - l);}}return res;}
};

713. 乘積小于 K 的子數組

class Solution {
public:int numSubarrayProductLessThanK(vector<int>& nums, int k) {if (k <= 1) return 0;int n = nums.size();int l = 0, r = 0;int res = 0;int curr = 1;while (r < n) {curr *= nums[r];while (curr >= k) {curr /= nums[l];l++;}
//			以r結尾的子數組的數量res += r - l + 1;r++;}return res;}
};

棧

刪除字符串中所有相鄰的重復項

class Solution {
public:string removeDuplicates(string s) {string res = "";for (char c : s) {if (!res.empty() && res.back() == c) res.pop_back();else res.push_back(c);}return res;}
};