- C++面试&C++学习指南知识点整理
- 程序员应该如何写简历(附简历模板)
- 一线互联网公司技术面试的流程以及注意事项
- 究竟什么是时间复杂度,怎么求时间复杂度,看这一篇就够了
- 一文带你彻底理解程序为什么会超时
- 一场面试,带你彻底掌握递归算法的时间复杂度
- 算法分析中的空间复杂度,你真的会了么?
- 二分法其实很简单,为什么老是写不对!!
- 程序员算法面试中,必须掌握的数组理论知识
- 这五道数组相关的面试题,你一定要会!
- 关于哈希表,你该了解这些!
- 这六道哈希表相关的面试题,你一定要会!
- 关于链表,你该了解这些!
- 刷leetcode的时候,究竟什么时候可以使用库函数,什么时候不要使用库函数,过来人来说一说
- 精选链表相关的面试题
- 精选字符串相关的面试题
- 精选栈与队列相关的面试题
- 精选二叉树相关的面试题
- 精选递归与回溯面试题
(持续更新中....)
刷题顺序:建议先从同一类型里题目开始刷起,同一类型里再从简单到中等到困难刷起,题型顺序建议:数组-> 链表-> 哈希表->字符串->栈与队列->树。
这里我总结了各个类型的经典题目,初学者可以按照如下顺序来刷题,算法老手可以按照这个list查缺补漏!
-
数组经典题目
-
链表经典题目
-
哈希表经典题目
-
字符串经典题目
- 0344.反转字符串
- 0541.反转字符串II
- 剑指Offer05.替换空格
- 0151.翻转字符串里的单词
- 延伸左旋转字符串(剑指offer上的题目)
- 0028.实现strStr()
- 0459.重复的子字符串
-
栈与队列经典题目
-
二叉树经典题目
(持续补充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;
}
};
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;
}
可以直接解决如下题目:
-
0111.二叉树的最小深度(迭代法)
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)
题目 | 类型 | 难度 | 解题方法 |
---|---|---|---|
0001.两数之和 | 数组 | 简单 | 暴力 哈希 |
0015.三数之和 | 数组 | 中等 | 双指针 哈希 |
0018.四数之和 | 数组 | 中等 | 双指针 |
0020.有效的括号 | 栈 | 简单 | 栈 |
0021.合并两个有序链表 | 链表 | 简单 | 模拟 |
0026.删除排序数组中的重复项 | 数组 | 简单 | 暴力 快慢指针/快慢指针 |
0027.移除元素 | 数组 | 简单 | 暴力 双指针/快慢指针/双指针 |
0028.实现strStr() | 字符串 | 简单 | KMP |
0035.搜索插入位置 | 数组 | 简单 | 暴力 二分 |
0053.最大子序和 | 数组 | 简单 | 暴力 贪心 动态规划 分治 |
0059.螺旋矩阵II | 数组 | 中等 | 模拟 |
0083.删除排序链表中的重复元素 | 链表 | 简单 | 模拟 |
0094.二叉树的中序遍历 | 树 | 中等 | 递归 迭代/栈 |
0098.验证二叉搜索树 | 树 | 中等 | 递归 |
0100.相同的树 | 树 | 简单 | 递归 |
0101.对称二叉树 | 树 | 简单 | 递归 迭代/队列/栈 |
0102.二叉树的层序遍历 | 树 | 中等 | 广度优先搜索/队列 |
0104.二叉树的最大深度 | 树 | 简单 | 递归 迭代/队列/BFS |
0110.平衡二叉树 | 树 | 简单 | 递归 |
0111.二叉树的最小深度 | 树 | 简单 | 递归 队列/BFS |
0142.环形链表II | 链表 | 中等 | 快慢指针/双指针 |
0144.二叉树的前序遍历 | 树 | 中等 | 递归 迭代/栈 |
0145.二叉树的后序遍历 | 树 | 困难 | 递归 迭代/栈 |
0151.翻转字符串里的单词 | 字符串 | 中等 | 模拟/双指针 |
0155.最小栈 | 栈 | 简单 | 栈 |
0199.二叉树的右视图 | 二叉树 | 中等 | 广度优先遍历/队列 |
0202.快乐数 | 哈希表 | 简单 | 哈希 |
0203.移除链表元素 | 链表 | 简单 | 模拟 虚拟头结点 |
0205.同构字符串 | 哈希表 | 简单 | 哈希 |
0206.翻转链表 | 链表 | 简单 | 双指针法 递归 |
0209.长度最小的子数组 | 数组 | 中等 | 暴力 滑动窗口 |
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」「算法与数据结构」 等关键字就可以获得我多年整理出来的学习资料。