最近刷 OfferShow，发现百度的校招薪资直接炸场了！年薪38w，还带8w签字费，T4级别。这待遇，属实“香”得不行了啊！再看看图里，这位同学居然说“有更好的选择”，直接婉拒了百度
这种薪资水平在互联网行业已经算“塔尖”了。别的不说，北京这种卷到头秃的地方，能拿到这个数，直接比绝大多数应届生高出好几个档位啊！不过话说回来，作为一个程序员，我觉得选工作还是得看长远价值。比如项目有多牛？团队够不够靠谱？发展方向能不能踩上风口？如果比百度还好的选择，那可能是阿里P7或者某家顶级独角兽了。虽然我这种普通社畜👨💻看看热闹就好，但不得不感叹，学算法确实“下饭”！小伙伴们，你们会选百度这种香饽饽吗？评论区聊聊呗～算法题：分发糖果
刷到一道挺有意思的算法题：青蛙过河，简单描述就是一只青蛙想过河，起点在第一块石头上，终点在最后一块石头上。青蛙每次可以跳一个步长（k），或者k-1，k，k+1的步长。不过，青蛙只能跳到河里的石头上，不能踩水。问题是：青蛙能不能成功跳到最后一块石头？解题思路
首先这题有点像一个动态规划的问题，但不是标准的DP表。我们需要存储每块石头上的“到达这块石头时，青蛙能跳的步长集合”，听起来有点拗口，其实核心思想是：- 从当前石头跳到下一块石头时，如果能到，就把步长记录下来；
- 最后看看终点石头有没有步长记录，空的话，青蛙到不了，非空说明它到了。
- 用一个
Map<Integer, Set<Integer>> 存每块石头的步长集合。
实现代码
import java.util.*;
public class FrogJump {
public boolean canCross(int[] stones) {
// 每块石头对应一个步长集合
Map<Integer, Set<Integer>> stoneSteps = new HashMap<>();
for (int stone : stones) {
stoneSteps.put(stone, new HashSet<>());
}
// 初始步长从0到1
stoneSteps.get(stones[0]).add(0);
for (int stone : stones) {
for (int step : stoneSteps.get(stone)) {
// 可能的步长
for (int jump = step - 1; jump <= step + 1; jump++) {
if (jump > 0 && stoneSteps.containsKey(stone + jump)) {
stoneSteps.get(stone + jump).add(jump);
}
}
}
}
// 终点是否有步长集合
return !stoneSteps.get(stones[stones.length - 1]).isEmpty();
}
public static void main(String[] args) {
FrogJump frogJump = new FrogJump();
int[] stones = {0, 1, 3, 5, 6, 8, 12, 17};
System.out.println(frogJump.canCross(stones)); // 输出 true
}
}
核心点解释
- 步长为0的初始条件：刚开始青蛙站在第一块石头上，步长是0，这很合理，因为它没有跳过。接下来它第一跳只能跳步长1。
- **步长范围是
k-1, k, k+1**：为啥 k-1 也行？因为有时候青蛙需要调整步伐，比如从 3 -> 5 可以用步长2跳上去，但下一跳 5 -> 6，就要缩回步长1。 - 用
Set 存储步长：有人可能会问，“每块石头的步长就一个，干嘛用 Set？”实际上，青蛙到达一块石头的路径不止一条！比如从 3 跳到 6，你既可以走 3 -> 5 -> 6（步长2），也可以直接 3 -> 6（步长3）。用 Set 就避免重复处理。
写到这我突然想到，要是青蛙也会发朋友圈，可能是这样的：- 青蛙1号：今天跳到终点了，成功上岸！这感觉就像刷完了公司面试所有的算法题，🤑。
- 青蛙2号：唉，跳到中途发现下一步无路可走，河太宽了💦，老板要求太高。
- 青蛙3号：建议把石头密度调高一点，不然不是逼我“踩水”吗？
不得不说，青蛙的职业生涯也太卷了！连过个河都被要求步长优化到极致。程序员看了沉默，裁员的老板看了流泪。扩展思路
这个问题延伸出来，可以拿来解决很多类似路径规划的问题，比如游戏里的角色跳跃路径设计。甚至在一些AI训练中，这种约束路径的计算模型也能派上用场。不过现实中呢，我觉得还是要让青蛙喘口气，别总给它这么难的条件。做人（蛙）嘛，开心就好，别把自己逼太紧。🍃你们有其他解法吗？欢迎评论区留言，我们一起为青蛙开辟新路！对编程、职场感兴趣的同学，可以链接我，微信：coder301 拉你进入“程序员交流群”。
