算法面经
数组
88. 合并两个有序数组
经典 逆向双指针
void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) {
for (int i = m - 1, j = n - 1, k = m + n - 1; ~j; k--) {
nums1[k] = i >= 0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
}
}
4. 寻找两个正序数组的中位数
困难，hot100，必会题，重点是求两个数组中第k大的数
double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
int m = nums1.size(), n = nums2.size();
int a = getKth(0, 0, (m + n + 1) / 2, nums1, nums2);
int b = getKth(0, 0, (m + n + 2) / 2, nums1, nums2);
return (a + b) / 2.0;
}
int getKth(int i, int j, int k, vector<int> &nums1, vector<int> &nums2) {
int m = nums1.size(), n = nums2.size();
if (i >= m) {
return nums2[j + k - 1];
}
if (j >= n) {
return nums1[i + k - 1];
}
if (k == 1) {
return min(nums1[i], nums2[j]);
}
int p = k / 2;
int x = i + p - 1 < m ? nums1[i + p - 1] : INT_MAX;
int y = j + p - 1 < n ? nums2[j + p - 1] : INT_MAX;
return x < y ? getKth(i + p, j, k - p, nums1, nums2) : getKth(i, j + p, k - p, nums1, nums2);
}
15. 三数之和
两数之和升级版，方法完全不一样，还用hash的话，会有很多特殊情况需要考虑，推荐使用 排序+双指针 法。字节常考题，必会。
vector<vector<int>> threeSum(vector<int> &nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
int n = nums.size();
for (int i = 0; i < n - 2 && nums[i] <= 0; i++) {
if (i && nums[i] == nums[i - 1]) continue;
int j = i + 1, k = n - 1;
while (j < k) {
int x = nums[i] + nums[j] + nums[k];
if (x < 0) {
j++;
} else if (x > 0) {
k--;
} else {
ans.push_back({nums[i], nums[j++], nums[k--]});
while (j < k && nums[j] == nums[j - 1]) {
j++;
}
while (j < k && nums[k] == nums[k + 1]) {
k--;
}
}
}
}
return ans;
}
字符串
5. 最长回文子串
必须掌握，方法1:动态规划，方法2:中心扩展法
/* f[i][j] 即 s[i...j]是否为回文串
* if s[i]=s[j],f[i][j]=f[i-1][j+1] */
string longestPalindrome(string s) {
int n = s.size();
vector<vector<bool>> f(n, vector<bool>(n, true));
int k = 0, mx = 1;
for (int i = n - 2; i >= 0; i++) {
for (int j = i + 1; j < n; j++) {
f[i][j] = false;
if (s[i] == s[j]) {
f[i][j] = f[i + 1][j - 1];
if (f[i][j] && mx < j - i + 1) {
mx = j - i + 1;
k = i;
}
}
}
}
return s.substr(k, mx);
}
// 中心扩展发
class Solution1 {
public:
string palindrome(string s, int l, int r) {
int n = s.size();
while (l >= 0 && r < n && s[l] == s[r]) {
l--;
r++;
}
return s.substr(l + 1, r - l - 1);
}
string longestPalindrome(string s) {
string res = "";
for (int i = 0; i < s.length(); i++) {
string s1 = palindrome(s, i, i);
string s2 = palindrome(s, i, i + 1);
res = res.size() > s1.size() ? res : s1;
res = res.size() > s2.size() ? res : s2;
}
return res;
}
};
2的1000次方
字符串乘法，腾讯面试题
#include <iostream>
#include <string>
using namespace std;
string multiplyByTow(const string &num) {
string res;
int carry = 0;
for (int i = num.size() - 1; i >= 0; i--) {
int digit = num[i] - '0';
int product = digit * 2 + carry;
carry = product / 10;
res.insert(res.begin(), '0' + (product % 10));
}
while (carry > 0) {
res.insert(res.begin(), '0' + (carry % 10));
carry /= 10;
}
return res;
}
int main() {
string res = "1";
for (int i = 0; i < 1000; i++) {
res = multiplyByTow(res);
}
cout << "2^1000 = " << res << endl;
}
14. 最长公共前缀
字符串最常考的题，面试不会直接回家种田
string longestCommonPrefix(vector<string> &strs) {
for (int i = 0; i < strs[0].size(); i++) {
for (int j = 1; j < strs.size(); j++) {
if (i >= strs[j].size() || strs[j][i] != strs[0][i]) {
return strs[0].substr(0,i);
}
}
}
return strs[0];
}
哈希表
1. 两数之和 不必多言
3. 无重复字符的最长子串 双指针+哈希表
链表
翻转链表 🌟
迭代和递归双方法，这个都不会回家种田吧
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *pre = nullptr;
ListNode *cur = head;
for(;cur!= nullptr;){
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
环形链表
142. 环形链表 II 经典
ListNode *detectCycle(ListNode *head) {
ListNode *slow=head,*fast = head;
while(fast&& fast->next){
slow=slow->next;
fast=fast->next->next;
if(slow==fast){
slow=head;
while (slow!=fast){
slow=slow->next;
fast=fast->next;
}
return slow;
}
}
return nullptr;
}
栈
出栈合法性 典中典
#include <iostream>
#include <stack>
using namespace std;
int main() {
int n;
int nums[105];
while (cin >> n) {
if (n == 0) break;
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
stack<int> st;
int index = 0;
for (int i = 1; i <= n; i++) {
st.push(i);
while (!st.empty() && st.top() == nums[index]) {
st.pop();
index++;
}
}
if (st.empty() && index == n) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
}
堆
优先级队列 703. 数据流中的第 K 大元素
priority_queue<int> max_heap; // 默认为最大堆
priority_queue<int, vector<int>, greater<int>> min_heap; // 最小堆
// 比较函数是子与父比较
二叉树
遍历
层序遍历
102. 二叉树的层序遍历 必须掌握
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode *root) {
vector<vector<int>> res;
if (root == nullptr) return res;
queue<TreeNode *> q;
q.push(root);
while (!q.empty()) {
int n = q.size();
vector<int> temp;
for(int i=0;i<n;i++){
TreeNode* cur = q.front();
q.pop();
temp.push_back(cur->val);
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
}
res.push_back(temp);
}
return res;
}
};
扩展dfs方法 107. 二叉树的层序遍历 II
vector<vector<int>> levelOrderBottom(TreeNode *root) {
vector<vector<int>> ans;
dfs(ans, root, 0);
reverse(ans.begin(), ans.end());// 反转
return ans;
}
void dfs(vector<vector<int>> &ans, TreeNode *root, int level) {
if (root == nullptr)
return;
// 初始化下一层的集合
if (level == ans.size()) {
vector<int> tmp;
ans.emplace_back(tmp);
}
// 把节点的值添加到对应的集合中
ans[level].push_back(root->val);
// 递归左右子树
dfs(ans, root->left, level + 1);
dfs(ans, root->right, level + 1);
}
构造
重建二叉树_牛客题霸_牛客网 前中序构造二叉树， 太经典了
TreeNode *reConstructBinaryTree(vector<int> &preOrder, vector<int> &inOrder) {
unordered_map<int, int> idx;
int n = preOrder.size();
for (int i = 0; i < n; ++i) {
idx[inOrder[i]] = i;
}
function<TreeNode *(int, int, int)> dfs = [&](int i, int j, int n) -> TreeNode * {
if (n < 1) return nullptr;
int k = idx[preOrder[i]];
int l = k - j;
TreeNode *root = new TreeNode(preOrder[i]);
root->left = dfs(i + 1, j, l);
root->right = dfs(i + 1 + l, k + 1, n - l - 1);
return root;
};
return dfs(0, 0, n);
}
回溯
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
经典例题：46. 全排列 、51. N 皇后
排列、组合｜子集
// 78 子集
vector<vector<int>> subsets(vector<int> &nums) {
backtrace(nums, 0);
return res;
}
vector<vector<int>> res;
vector<int> track;
void backtrace(vector<int> &nums, int start) {
res.push_back(track);
for (int i = start; i < nums.size(); i++) {
track.push_back(nums[i]);
backtrace(nums, i + 1);
track.pop_back();
}
}
// 77 组合
vector<vector<int>> combine(int n, int k) {
backtrace(n, k, 0);
return res;
}
vector<vector<int>> res;
vector<int> track;
void backtrace(int n, int k, int start) {
if (track.size() == k) {
res.push_back(track);
return;
}
for (int i = start; i < n; i++) {
track.push_back(i + 1);
backtrace(n, k, i + 1);
track.pop_back();
}
}
// 46 全排列
vector<vector<int>> permute(vector<int> &nums) {
visited = vector<bool>(nums.size());
backtrace(nums);
return res;
}
vector<vector<int>> res;
vector<int> track;
vector<bool> visited;
void backtrace(vector<int> nums) {
if (nums.size() == track.size()) {
res.push_back(track);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (visited[i]) continue;
visited[i] = true;
track.push_back(nums[i]);
backtrace(nums);
track.pop_back();
visited[i] = false;
}
}
动态规划
70. 爬楼梯
唯一会的动态规划😅
class Solution {
public:
int climbStairs(int n) {
if (n <= 2) return n;
int dp[2] = {1, 2};
for (int i = 3; i <= n; i++) {
int next = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = next;
}
return dp[1];
}
};
数学与数字
排序与搜索
设计
208. 实现 Trie (前缀树)
非常重要，还有他的扩展 基数树
class Trie {
bool end;
Trie *next[26];
public:
Trie() : end(false) {
memset(next, 0, sizeof next);
}
void insert(string word) {
Trie *cur = this;
for (char c: word) {
if (cur->next[c - 'a'] == nullptr) {
cur->next[c - 'a'] = new Trie();
}
cur = cur->next[c - 'a'];
}
cur->end = true;
}
Trie *searchNode(string word) {
Trie *cur = this;
for (char c: word) {
if (cur->next[c - 'a'] == nullptr) {
return nullptr;
}
cur = cur->next[c - 'a'];
}
return cur;
}
bool search(string word) {
Trie *node = searchNode(word);
return node != nullptr && node->end;
}
bool startsWith(string prefix) {
return searchNode(prefix)!= nullptr;
}
};
模拟
2. 两数相加
常考题
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
ListNode *dummy = new ListNode();
int carry = 0;
ListNode *cur = dummy;
while (l1 || l2 || carry) {
int s = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
carry = s / 10;
cur->next = new ListNode(s % 10);
cur = cur->next;
l1 = l1?l1->next: nullptr;
l2 = l2?l2->next: nullptr;
}
return dummy->next;
}
奇技淫巧
for(;~j;) 等价于 for(;j>=0;) ~j = -j - 1