果然,秋招会惩罚每一个本末倒置的应届生
秋招建议
随着秋招的白热化,有不少同学又开始了内耗和焦虑。
过去一周,有不少同学在后台私信我,聊一些关于秋招的话题。
其中有一类同学,是想找我当"树洞"的:
-
这当中,有一部分是向我倾诉自己投递了多家公司,但都是石沉大海,0 约面 -
还有一些同学,学历比较好,有不少面试机会,但大多挂在了一面二面中,0 Offer
这里面有一位同学比较特别,既没有给我交代自己的基本情况,留言内容也只有"三叶姐,秋招不顺,不知道咋办"、"宿友都上岸了,只剩下自己没着落,很痛苦"、"秋招想摆烂了"...这样的空洞内容,而且基本上每隔几个小时就留言一次,持续了好几天。
不是说不能找我,但是这个频率的留言,我很难相信你除了在做「向我求助」这件事情以外,还有做其他对秋招有益的事情。
相信同样处境的同学不在少数,这里统一给一些秋招建议:
-
抓紧时间:大多数秋招上岸的同学,都是做「时间管理」的好手,之前我就说过,没有一家公司能够将 HC 均匀分配在整个秋招时间窗口,所以越到后面难度越大,因此越早投递,成功率越高;
-
转换思维:校招是应届生的求职优势,因为有个特殊身份(应届生),拦掉了绝大多数的求职者,但不代表应届生只能参与校招,要学会转换思维,校招这条路堵死了,要学会留意社招这条路,可能会有别的收获
-
注重复盘:很多大厂的秋招几乎都是同时开启的,因此应届生会在短时间集中性地进行大量面试,此时复盘就显得十分重要,那些频繁在一面二面倒下的同学,或许只是在重复犯同样的错误;
-
快速学习:如果复盘下来,发现自己是某个必考知识点缺失导致的频繁失败,正确的做法就是快速学习,建立知识谱图(技能树),有的放矢进行查漏补缺;
-
整合资源:如果顺利拿到多个 Offer,要善于利用一切资源来帮助自己决策,包括找身边已经入职该公司的师兄师姐咨询(ta 们最清楚该公司的实际情况),以及针对性逛各种论坛和职场 App(牛客网、脉脉),问人是直接,但人家清楚的未必就是你要去的那个部门,利用好广大网民,帮助自己更加全面了解该公司;
...
回归主题。
来一道和「秋招」相关的算法原题。
题目描述
平台:LeetCode
题号:91
一条包含字母 A-Z
的消息通过以下映射进行了 编码 :
'A' -> 1
'B' -> 2
...
'Z' -> 26
要解码已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。
例如,"11106"
可以映射为:
-
"AAJF"
,将消息分组为(1 1 10 6)
-
"KJF"
,将消息分组为(11 10 6)
注意,消息不能分组为 (1 11 06)
,因为 "06"
不能映射为 "F"
,这是由于 "6"
和 "06"
在映射中并不等价。
给你一个只含数字的非空字符串 s
,请计算并返回解码方法的总数。
题目数据保证答案肯定是一个 32
位的整数。
示例 1:
输入:s = "12"
输出:2
解释:它可以解码为 "AB"(1 2)或者 "L"(12)。
示例 2:
输入:s = "226"
输出:3
解释:它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
示例 3:
输入:s = "0"
输出:0
解释:没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于没有字符,因此没有有效的方法对此进行解码,因为所有数字都需要映射。
示例 4:
输入:s = "06"
输出:0
解释:"06" 不能映射到 "F" ,因为字符串含有前导 0("6" 和 "06" 在映射中并不等价)。
提示:
-
-
s
只包含数字,并且可能包含前导零。
基本分析
我们称一个解码内容为一个 item
。
为根据题意,每个 item
可以由一个数字组成,也可以由两个数字组成。
数据范围为 100,很具有迷惑性,可能会有不少同学会想使用 DFS 进行爆搜。
我们可以大致分析一下这样的做法是否可行:不失一般性的考虑字符串 s
中的任意位置 i
,位置 i
既可以作为一个独立 item
,也可以与上一位置组成新 item
,那么相当于每个位置都有两种分割选择(先不考虑分割结果的合法性问题),这样做法的复杂度是
的,当 n
范围是 100 时,远超我们计算机单秒运算量(
)。即使我们将「判断分割结果是否合法」的操作放到爆搜过程中做剪枝,也与我们的单秒最大运算量相差很远。
递归的方法不可行,我们需要考虑递推的解法。
动态规划
「这其实是一道字符串类的动态规划题,不难发现对于字符串 s
的某个位置 i
而言,我们只关心「位置 i
自己能否形成独立 item
」和「位置 i
能够与上一位置(i-1
)能否形成 item
」,而不关心 i-1
之前的位置。」
有了以上分析,我们可以从前往后处理字符串 s
,使用一个数组记录以字符串 s
的每一位作为结尾的解码方案数。即定义
为考虑前
个字符的解码方案数。
对于字符串 s
的任意位置 i
而言,其存在三种情况:
-
只能由位置 i
的单独作为一个item
,设为a
,转移的前提是a
的数值范围为 ,转移逻辑为 。 -
只能由位置 i
的与前一位置(i-1
)共同作为一个item
,设为b
,转移的前提是b
的数值范围为 ,转移逻辑为 。 -
位置 i
既能作为独立item
也能与上一位置形成item
,转移逻辑为 。
因此,我们有如下转移方程:
其他细节:由于题目存在前导零,而前导零属于无效 item
。可以进行特判,但个人习惯往字符串头部追加空格作为哨兵,追加空格既可以避免讨论前导零,也能使下标从 1 开始,简化 f[i-1]
等负数下标的判断。
Java 代码:
class Solution {
public int numDecodings(String s) {
int n = s.length();
s = " " + s;
char[] cs = s.toCharArray();
int[] f = new int[n + 1];
f[0] = 1;
for (int i = 1; i <= n; i++) {
// a : 代表「当前位置」单独形成 item
// b : 代表「当前位置」与「前一位置」共同形成 item
int a = cs[i] - '0', b = (cs[i - 1] - '0') * 10 + (cs[i] - '0');
// 如果 a 属于有效值,那么 f[i] 可以由 f[i - 1] 转移过来
if (1 <= a && a <= 9) f[i] = f[i - 1];
// 如果 b 属于有效值,那么 f[i] 可以由 f[i - 2] 或者 f[i - 1] & f[i - 2] 转移过来
if (10 <= b && b <= 26) f[i] += f[i - 2];
}
return f[n];
}
}
C++ 代码:
class Solution {
public:
int numDecodings(string s) {
int n = s.length();
s = " " + s;
vector<int> f(n + 1, 0);
f[0] = 1;
for (int i = 1; i <= n; i++) {
int a = s[i] - '0', b = (s[i - 1] - '0') * 10 + (s[i] - '0');
if (1 <= a && a <= 9) f[i] += f[i - 1];
if (10 <= b && b <= 26) f[i] += f[i - 2];
}
return f[n];
}
};
Python 代码:
class Solution:
def numDecodings(self, s: str) -> int:
n = len(s)
s = " " + s
f = [0] * (n + 1)
f[0] = 1
for i in range(1, n + 1):
a = ord(s[i]) - ord('0')
b = (ord(s[i - 1]) - ord('0')) * 10 + a
if 1 <= a <= 9:
f[i] += f[i - 1]
if 10 <= b <= 26:
f[i] += f[i - 2]
return f[n]
TypeScript 代码:
function numDecodings(s: string): number {
const n: number = s.length;
s = " " + s;
const f: number[] = new Array(n + 1).fill(0);
f[0] = 1;
for (let i: number = 1; i <= n; i++) {
const a: number = parseInt(s.charAt(i));
const b: number = parseInt(s.charAt(i - 1)) * 10 + a;
if (1 <= a && a <= 9) f[i] += f[i - 1];
if (10 <= b && b <= 26) f[i] += f[i - 2];
}
return f[n];
};
-
时间复杂度:共有 n
个状态需要被转移,复杂度为 -
空间复杂度:
空间优化
不难发现,我们转移 f[i]
时只依赖 f[i-1]
和 f[i-2]
两个状态。
因此我们可以采用与「滚动数组」类似的思路,只创建长度为 3 的数组,通过取余的方式来复用不再需要的下标。
Java 代码:
class Solution {
public int numDecodings(String s) {
int n = s.length();
s = " " + s;
char[] cs = s.toCharArray();
int[] f = new int[3];
f[0] = 1;
for (int i = 1; i <= n; i++) {
f[i % 3] = 0;
int a = cs[i] - '0', b = (cs[i - 1] - '0') * 10 + (cs[i] - '0');
if (1 <= a && a <= 9) f[i % 3] = f[(i - 1) % 3];
if (10 <= b && b <= 26) f[i % 3] += f[(i - 2) % 3];
}
return f[n % 3];
}
}
C++ 代码:
class Solution {
public:
int numDecodings(string s) {
int n = s.length();
s = " " + s;
vector<int> f(3, 0);
f[0] = 1;
for (int i = 1; i <= n; i++) {
f[i % 3] = 0;
int a = s[i] - '0', b = (s[i - 1] - '0') * 10 + (s[i] - '0');
if (1 <= a && a <= 9) f[i % 3] = f[(i - 1) % 3];
if (10 <= b && b <= 26) f[i % 3] += f[(i - 2) % 3];
}
return f[n % 3];
}
};
Python 代码:
class Solution:
def numDecodings(self, s: str) -> int:
n = len(s)
s = " " + s
f = [1, 0, 0]
for i in range(1, n + 1):
f[i % 3] = 0
a = ord(s[i]) - ord('0')
b = (ord(s[i - 1]) - ord('0')) * 10 + a
if 1 <= a <= 9:
f[i % 3] = f[(i - 1) % 3]
if 10 <= b <= 26:
f[i % 3] += f[(i - 2) % 3]
return f[n % 3]
TypeScript 代码:
function numDecodings(s: string): number {
const n: number = s.length;
s = " " + s;
const f: number[] = [1, 0, 0];
for (let i: number = 1; i <= n; i++) {
f[i % 3] = 0;
const a: number = parseInt(s.charAt(i));
const b: number = parseInt(s.charAt(i - 1)) * 10 + a;
if (1 <= a && a <= 9) f[i % 3] = f[(i - 1) % 3];
if (10 <= b && b <= 26) f[i % 3] += f[(i - 2) % 3];
}
return f[n % 3];
};
-
时间复杂度:共有 n
个状态需要被转移,复杂度为 -
空间复杂度:
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier,年度会员 有效期额外增加两个月,季度会员 有效期额外增加两周,更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶,每天都会分享算法知识,并和大家聊聊近期的所见所闻。
欢迎关注,明天见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉