Coder Social home page Coder Social logo

lstarby / leetcode-master Goto Github PK

View Code? Open in Web Editor NEW

This project forked from youngyangyang04/leetcode-master

0.0 0.0 0.0 26.06 MB

LeetCode 刷题攻略：配思维导图，各个类型的经典题目刷题顺序、经典算法模板，以及详细图解和视频题解，每日一题，轻松学习算法！

leetcode-master's Introduction

目录：

算法面试思维导图

算法面试知识大纲

算法文章精选

（持续更新中....）

LeetCode 刷题攻略

刷题顺序：建议先从同一类型里题目开始刷起，同一类型里再从简单到中等到困难刷起，题型顺序建议：数组-> 链表-> 哈希表->字符串->栈与队列->树。

这里我总结了各个类型的经典题目，初学者可以按照如下顺序来刷题，算法老手可以按照这个list查缺补漏！

（持续补充ing）

算法模板

二分查找法

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); // 右
}

深度优先遍历（迭代法）

相关题解：0094.二叉树的中序遍历

前序遍历（中左右）

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

广度优先遍历（队列）

相关题解：0102.二叉树的层序遍历

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);
}

（持续补充ing）

LeetCode 最强题解:

题目 类型 难度 解题方法
0001.两数之和 数组 简单 暴力 哈希
0015.三数之和 数组 中等 双指针 哈希
0017.电话号码的字母组合 回溯 中等 回溯
0018.四数之和 数组 中等 双指针
0020.有效的括号 栈 简单 栈
0021.合并两个有序链表 链表 简单 模拟
0026.删除排序数组中的重复项 数组 简单 暴力 快慢指针/快慢指针
0027.移除元素 数组 简单 暴力 双指针/快慢指针/双指针
0028.实现strStr() 字符串 简单 KMP
0035.搜索插入位置 数组 简单 暴力 二分
0039.组合总和 数组/回溯 中等 回溯
0040.组合总和II 数组/回溯 中等 回溯
0046.全排列 回溯 中等 回溯
0047.全排列II 回溯 中等 回溯
0053.最大子序和 数组 简单 暴力 贪心 动态规划 分治
0059.螺旋矩阵II 数组 中等 模拟
0077.组合 回溯 中等 回溯
0078.子集 回溯/数组 中等 回溯
0083.删除排序链表中的重复元素 链表 简单 模拟
0093.复原IP地址 回溯 中等 回溯
0094.二叉树的中序遍历 树 中等 递归 迭代/栈
0098.验证二叉搜索树 树 中等 递归
0100.相同的树 树 简单 递归
0101.对称二叉树 树 简单 递归 迭代/队列/栈
0102.二叉树的层序遍历 树 中等 广度优先搜索/队列
0104.二叉树的最大深度 树 简单 递归 迭代/队列/BFS
0110.平衡二叉树 树 简单 递归
0111.二叉树的最小深度 树 简单 递归 队列/BFS
0131.分割回文串 回溯 中等 回溯
0142.环形链表II 链表 中等 快慢指针/双指针
0144.二叉树的前序遍历 树 中等 递归 迭代/栈
0145.二叉树的后序遍历 树 困难 递归 迭代/栈
0151.翻转字符串里的单词 字符串 中等 模拟/双指针
0155.最小栈 栈 简单 栈
0199.二叉树的右视图 二叉树 中等 广度优先遍历/队列
0202.快乐数 哈希表 简单 哈希
0203.移除链表元素 链表 简单 模拟 虚拟头结点
0205.同构字符串 哈希表 简单 哈希
0206.翻转链表 链表 简单 双指针法 递归
0209.长度最小的子数组 数组 中等 暴力 滑动窗口
0216.组合总和III 数组/回溯 中等 回溯
0219.存在重复元素II 哈希表 简单 哈希
0222.完全二叉树的节点个数 树 简单 递归
0225.用队列实现栈 队列 简单 队列
0226.翻转二叉树 二叉树 简单 递归 迭代
0232.用栈实现队列 栈 简单 栈
0237.删除链表中的节点 链表 简单 原链表移除 添加虚拟节点 递归
0239.滑动窗口最大值 滑动窗口/队列 困难 单调队列
0242.有效的字母异位词 哈希表 简单 哈希
0344.反转字符串 字符串 简单 双指针
0347.前K个高频元素 哈希/堆/优先级队列 中等 哈希/优先级队列
0349.两个数组的交集 哈希表 简单 哈希
0350.两个数组的交集II 哈希表 简单 哈希
0383.赎金信 数组 简单 暴力 字典计数 哈希
0450.删除二叉搜索树中的节点 树 中等 递归
0434.字符串中的单词数 字符串 简单 模拟
0454.四数相加II 哈希表 中等 哈希
0459.重复的子字符串 字符创 简单 KMP
0541.反转字符串II 字符串 简单 模拟
0575.分糖果 哈希表 简单 哈希
0617.合并二叉树 树 简单 递归 迭代
0654.最大二叉树 树 中等 递归
0700.二叉搜索树中的搜索 树 简单 递归 迭代
0701.二叉搜索树中的插入操作 树 简单 递归 迭代
0705.设计哈希集合 哈希表 简单 模拟
0707.设计链表 链表 中等 模拟
1047.删除字符串中的所有相邻重复项 栈 简单 栈
剑指Offer05.替换空格 字符串 简单 双指针

持续更新中....

关于作者

大家好，我是程序员Carl，ACM区域赛铜牌获得者，哈工大计算机硕士毕业，先后在腾讯和百度从事后端技术研发，CSDN博客专家。对算法和C++后端技术有一定的见解，利用工作之余重新刷leetcode。

我的微信：

我的公众号

更多精彩文章持续更新，微信搜索：「代码随想录」第一时间围观，关注后回复： 「简历模板」「java」「C++」「python」「算法与数据结构」 等关键字就可以获得我多年整理出来的学习资料。

leetcode-master's People

Contributors

youngyangyang04 avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.