算法面试思维导图

算法文章精选

LeetCode 刷题攻略

算法模板

二分查找法

class Solution {public:    int searchInsert(vector<int>& nums, int target) {        int n = nums.size();        int left = 0;        int right = n; // 我们定义target在左闭右开的区间里，[left, right)          while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间            int middle = left + ((right - left) >> 1);            if (nums[middle] > target) {                right = middle; // target 在左区间，因为是左闭右开的区间，nums[middle]一定不是我们的目标值，所以right = middle，在[left, middle)中继续寻找目标值            } else if (nums[middle] < target) {                left = middle + 1; // target 在右区间，在 [middle+1, right)中            } else { // nums[middle] == target                return middle; // 数组中找到目标值的情况，直接返回下标            }        }        return right;    }};

KMP

void kmp(int* next, const string& s){    next[0] = -1;    int j = -1;    for(int i = 1; i < s.size(); i++){        while (j >= 0 && s[i] != s[j + 1]) {            j = next[j];        }        if (s[i] == s[j + 1]) {            j++;        }        next[i] = j;    }}

二叉树

struct TreeNode {    int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : val(x), left(NULL), right(NULL) {}};

深度优先遍历（递归）

void traversal(TreeNode* cur, vector<int>& vec) {    if (cur == NULL) return;    vec.push_back(cur->val);    // 中 ，同时也是处理节点逻辑的地方    traversal(cur->left, vec);  // 左    traversal(cur->right, vec); // 右}

void traversal(TreeNode* cur, vector<int>& vec) {    if (cur == NULL) return;    traversal(cur->left, vec);  // 左    vec.push_back(cur->val);    // 中 ，同时也是处理节点逻辑的地方    traversal(cur->right, vec); // 右}

void traversal(TreeNode* cur, vector<int>& vec) {    if (cur == NULL) return;    vec.push_back(cur->val);    // 中 ，同时也是处理节点逻辑的地方    traversal(cur->left, vec);  // 左    traversal(cur->right, vec); // 右}

深度优先遍历（迭代法）

vector<int> preorderTraversal(TreeNode* root) {    vector<int> result;    stack<TreeNode*> st;    if (root != NULL) st.push(root);    while (!st.empty()) {        TreeNode* node = st.top();        if (node != NULL) {            st.pop();            if (node->right) st.push(node->right);  // 右            if (node->left) st.push(node->left);    // 左            st.push(node);                          // 中            st.push(NULL);                                  } else {            st.pop();            node = st.top();            st.pop();            result.push_back(node->val);            // 节点处理逻辑        }    }    return result;}

vector<int> inorderTraversal(TreeNode* root) {    vector<int> result; // 存放中序遍历的元素    stack<TreeNode*> st;    if (root != NULL) st.push(root);    while (!st.empty()) {        TreeNode* node = st.top();        if (node != NULL) {            st.pop();             if (node->right) st.push(node->right);  // 右            st.push(node);                          // 中            st.push(NULL);             if (node->left) st.push(node->left);    // 左        } else {            st.pop();             node = st.top();             st.pop();            result.push_back(node->val);            // 节点处理逻辑        }    }    return result;}

vector<int> postorderTraversal(TreeNode* root) {    vector<int> result;    stack<TreeNode*> st;    if (root != NULL) st.push(root);    while (!st.empty()) {        TreeNode* node = st.top();        if (node != NULL) {            st.pop();            st.push(node);                          // 中            st.push(NULL);            if (node->right) st.push(node->right);  // 右            if (node->left) st.push(node->left);    // 左        } else {            st.pop();            node = st.top();            st.pop();            result.push_back(node->val);            // 节点处理逻辑        }    }    return result;}

广度优先遍历（队列）

vector<vector<int>> levelOrder(TreeNode* root) {    queue<TreeNode*> que;    if (root != NULL) que.push(root);    vector<vector<int>> result;    while (!que.empty()) {        int size = que.size();        vector<int> vec;        for (int i = 0; i < size; i++) {// 这里一定要使用固定大小size，不要使用que.size()            TreeNode* node = que.front();            que.pop();            vec.push_back(node->val);   // 节点处理的逻辑            if (node->left) que.push(node->left);            if (node->right) que.push(node->right);        }        result.push_back(vec);    }    return result;}

二叉树深度

int getDepth(TreeNode* node) {    if (node == NULL) return 0;    return 1 + max(getDepth(node->left), getDepth(node->right));}

二叉树节点数量

int countNodes(TreeNode* root) {    if (root == NULL) return 0;    return 1 + countNodes(root->left) + countNodes(root->right);}

回溯算法

backtracking() {    if (终止条件) {        存放结果;    }    for (选择：选择列表（可以想成树中节点孩子的数量）) {        递归，处理节点;        backtracking();        回溯，撤销处理结果    }}

LeetCode 最强题解:

关于作者

我的公众号