算法面经

数组

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

热门相关:娇妻如云   妖夏   盛唐小园丁   锦桐   影帝偏要住我家