贪心算法和动态规划的区别
贪心算法，当局部最优可以递推到全局最优时这个可以使用这个贪心算法 动态规划， 带记忆状态的暴力递归
C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
// 解法一：动态规划 O(n²) 时间, O(n) 空间
int jumpDP(const vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, INT_MAX);
dp[0] = 0; for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (dp[j] != INT_MAX && j + nums[j] >= i) {
dp[i] = min(dp[i], dp[j] + 1);
}
}
}
return dp[n - 1];
}
// 解法二：贪心 O(n) 时间, O(1) 空间
int jumpGreedy(const vector<int>& nums) {
int jumps = 0;
int curEnd = 0; // 当前这一跳能到的最远边界
int farthest = 0; // 在当前范围内试探到的下一步最远点
for (int i = 0; i < (int)nums.size() - 1; ++i) {
farthest = max(farthest, i + nums[i]);
if (i == curEnd) { // 用尽当前跳的范围，必须再跳一次
++jumps;
curEnd = farthest;
}
}
return jumps;
}什么是动态规划？ 典型的动态规划问题有哪些？
动态规划问题是一种把大问题拆解成重叠子问题，通过记录子问题的解来避免重复计算的算法思想。 一个问题能用DP,通常要满足两个特征：
- 最优子结构：原问题的最优解可以子问题的最优解组合而来
- 重叠子问题：递归求解时会反复计算相同的子问题 DP 的核心时写出状态转移方程，解题套路： 定义状态：dp[i] 或dp[i] [j] 表示什么？ 状态转移方程： dp[i] 如何从之前的状态推导出来 初始化： 边界状态如和给值 遍历顺序：从前往后/从后往前/按照某种维度 典型题目： 斐波那契数列/爬楼梯 0-1 背包 完全背包 最长公共子序列 最长递增子序列 最长回文子串 编辑距离 打家劫舍 零钱兑换
常见的数据结构有哪些？各自适合什么场景
数据结构决定了数据在内存中怎么组织，也直接影响增删查的效率。面试里最基础的五种是数组、链表、栈、队列和树。
数组
元素在内存中连续存放，知道首地址和下标就能直接算出元素位置，所以按下标访问是 O(1)。 缺点是插入或删除中间元素时，后面的元素都要挪动，复杂度 O(n)。 适合：读多写少、需要按位置随机访问的场景。
链表
由一个个节点串起来，每个节点保存数据和指向下一个节点的指针，节点在内存中分散存放。 已知位置时插入、删除只需改指针，是 O(1)；但想找到第 k 个元素必须从头遍历，是 O(n)。 适合：频繁插入删除、元素数量变化大的场景。
栈
后进先出（LIFO），只能在栈顶压入和弹出。 典型应用：函数调用栈、括号匹配、表达式求值、浏览器后退。
队列
先进先出（FIFO），从队尾入队、从队头出队。 典型应用：任务排队、消息缓冲、广度优先搜索（BFS）。
树
非线性结构，由节点和边组成，一个节点可以有多个子节点，天然适合表达层级关系，比如文件目录、组织架构。 常见变种：
- 二叉搜索树：左小右大，查找平均 O(log n)。
- 红黑树：自平衡的二叉搜索树，Java 的 TreeMap 就用它。
- B+ 树：多叉、矮胖，减少磁盘 IO，是 MySQL 索引的底层结构。
- 堆：完全二叉树，用来快速取最大或最小值，实现优先队列。
对比一览
| 结构 | 访问 | 插入/删除 | 特点 |
|---|---|---|---|
| 数组 | O(1) | O(n) | 连续内存，随机访问快 |
| 链表 | O(n) | O(1)（已知位置） | 分散存储，增删灵活 |
| 栈 | 仅栈顶 | O(1) | 后进先出 |
| 队列 | 仅队头 | O(1) | 先进先出 |
| 平衡树 | O(log n) | O(log n) | 有序、层级 |
总结
没有万能的数据结构，选择取决于操作特点：随机读多用数组，增删多用链表，需要“撤销/回溯”用栈，需要排队处理用队列，需要有序或层级关系用树。
📮 联系方式
微信：BuZhiCoder ｜ QQ：1776418445 扫码添加，备注「求职」优先通过
