中兴校招薪资一览表
中兴校招薪水
写了几期薪资一览，只有 中兴 那一期有不少读者反映偏差较大，但实际上不是偏差大，而是倒挂情况严重。
同职级新员工可能要比老员工薪资高 30% 以上，如果算上蓝剑计划（允许发放薪资上限更高的 offer)，差值就更大了。
这里更新一下中兴近期的校招薪资：
-
研发： -
白菜（普通 offer）：12k~18.5k -
SP：19k~21.5k -
SSP（蓝剑计划）：22k~33k
-
-
IC： -
白菜（普通 offer）：15.5k~18.5k -
SP：19k~20.5k -
SSP（蓝剑计划）：21k~32k
-
-
算法： -
白菜（普通 offer）：16k~18.5k -
SP：19k~22k -
SSP（蓝剑计划）：25k~45k
-
-
职能： -
白菜（普通 offer）：14k~16k -
SP：17k~20k
-
中兴近几年校招特色是：同级 offer 薪资范围大，不同级 offer 薪资差值也大，蓝剑计划差别大上加大，这就导致存量员工的薪资水平差别巨大。
对此你怎么看？
...
回归主题。
1024，节日快乐，来道经典算法题。
题目描述
平台：LeetCode
题号：45
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: [2,3,0,1,4]
输出: 2
提示:
BFS
对于这一类问题，我们一般都是使用 BFS 进行求解。
本题的 BFS 解法的复杂度是 ，数据范围为 ，可以过。
Java 代码：
class Solution {
public int jump(int[] nums) {
int n = nums.length, ans = 0;
boolean[] st = new boolean[n];
Deque<Integer> d = new ArrayDeque<>();
st[0] = true;
d.addLast(0);
while (!d.isEmpty()) {
int size = d.size();
while (size-- > 0) {
int idx = d.pollFirst();
if (idx == n - 1) return ans;
for (int i = idx + 1; i <= idx + nums[idx] && i < n; i++) {
if (!st[i]) {
st[i] = true;
d.addLast(i);
}
}
}
ans++;
}
return ans;
}
}
C++ 代码：
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size(), ans = 0;
bool st[n];
memset(st, false, sizeof(st));
deque<int> d;
st[0] = true;
d.push_back(0);
while (!d.empty()) {
int size = d.size();
while (size-- > 0) {
int idx = d.front();
d.pop_front();
if (idx == n - 1) return ans;
for (int i = idx + 1; i <= idx + nums[idx] && i < n; i++) {
if (!st[i]) {
st[i] = true;
d.push_back(i);
}
}
}
ans++;
}
return ans;
}
};
Python 代码：
class Solution:
def jump(self, nums: List[int]) -> int:
n, ans = len(nums), 0
st = [False] * n
d = deque([0])
st[0] = True
while d:
size = len(d)
while size > 0:
idx = d.popleft()
if idx == n - 1:
return ans
for i in range(idx + 1, min(idx + nums[idx] + 1, n)):
if not st[i]:
st[i] = True
d.append(i)
size -= 1
ans += 1
return ans
-
时间复杂度：如果每个点跳跃的距离足够长的话，每次都会将当前点「后面的所有点」进行循环入队操作（由于 st 的存在，不一定都能入队，但是每个点都需要被循环一下）。复杂度为 -
空间复杂度：队列中最多有 个元素。复杂度为
双指针 + 贪心 + 动态规划
本题数据范围只有 ，所以 勉强能过。
如果面试官要将数据范围出到 ，又该如何求解呢？
我们需要考虑 的做法。
其实通过 这个数据范围，就已经可以大概猜到是道 DP 题。
我们定义 为到达第 个位置所需要的最少步数，那么答案是 。
学习过 路径 DP 专题 的同学应该知道，通常确定 DP 的「状态定义」有两种方法。
-
一种是根据经验猜一个状态定义，会结合题目给定的维度，和要求的答案去猜。
-
另外一种则是通过设计一个合理的
DFS方法签名来确定状态定义。
这里我是采用第一种方法。
至于如何确定「状态定义」是否可靠，关键是看使用这个状态定义能否推导出合理的「状态转移方程」，来覆盖我们所有的状态。
不失一般性的考虑 该如何转移：
我们知道最后一个点前面可能会有很多个点能够一步到达最后一个点。
也就是有 。
然后我们再来考虑集合 有何特性。
不然发现其实必然有 。
推而广之，不止是经过一步能够到达最后一个点的集合，其实任意连续的区间都有这个性质。
举个🌰，比如我经过至少 5 步到达第 个点，那么必然不可能出现使用步数少于 5 步就能达到第 个点的情况。到达第 个点的至少步数必然是 5 步或者 6 步。
搞清楚性质之后，再回头看我们的状态定义：* 为到达第 个位置所需要的最少步数。*
因此当我们要求某一个 的时候，我们需要找到最早能够经过一步到达 点的 点。
即有状态转移方程： 。
也就是我们每次都贪心的取离 点最远的点 来更新 。
而这个找 的过程可以使用双指针来找。
因此这个思路其实是一个「双指针 + 贪心 + 动态规划」的一个解法。
Java 代码：
class Solution {
public int jump(int[] nums) {
int n = nums.length;
int[] f = new int[n];
for (int i = 1, j = 0; i < n; i++) {
while (j + nums[j] < i) j++;
f[i] = f[j] + 1;
}
return f[n - 1];
}
}
C++ 代码：
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
vector<int> f(n, 0);
for (int i = 1, j = 0; i < n; i++) {
while (j + nums[j] < i) j++;
f[i] = f[j] + 1;
}
return f[n - 1];
}
};
Python 代码：
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
f = [0] * n
for i in range(1, n):
j = 0
while j + nums[j] < i:
j += 1
f[i] = f[j] + 1
return f[-1]
-
时间复杂度： -
空间复杂度：
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉