深圳Java外包这行情,已经不是卷了,是往回倒车。5到10年经验,开价还卡在13K、15K,乍一看像在招人,细一看像在测试谁还没断奶。
![]()
前几年大家还吐槽外包累、杂、没归属感,但钱起码还能撑住脸面。现在倒好,活一点没少,价倒先砍了。网友也很损,有人说这工资放深圳,房租和通勤先吃一半,剩下那点钱,连“多年经验”四个字都显得心酸。还有人说,企业现在不是招Java,是在淘性价比最高的老黄牛。
HR把需求写得天花乱坠,候选人点开一看,估计眼皮都跳一下。真要这个价,别聊什么发展了,先问问这班上着图啥。
算法题: 最短回文串
字符串一长,回文题最容易写成“能过样例,过不了大数据”。
“最短回文串”就是这种。题目要求很克制:给你一个字符串 s ,只能在 头部 添加字符,把它补成回文,而且补得越短越好。第一眼很多人会想到双指针,或者从头到尾试所有前缀是不是回文。思路不算错,就是一提交,长一点的字符串直接超时。
这题我一般先盯住一个地方: 到底哪一段是已经回文的 。 因为只能往前面补,所以本质不是“怎么拼”,而是“原串里最长的回文前缀是谁”。只要这个前缀找到了,后半截没进回文的部分反过来贴到前面就完了。
比如:
s = "aacecaaa"
它的最长回文前缀其实就是 "aacecaa" ,剩下一个 "a" 没进去,那答案就是前面补一个 "a" :
"aaacecaaa"
再看这个:
s = "abcd"
最长回文前缀只有 "a" ,那就把后面的 "bcd" 反过来放前面:
"dcbabcd"
很多人会先这么写:
defshortest_palindrome(s: str) -> str:
defis_pal(sub: str) -> bool:
return sub == sub[::-1]for i in range(len(s), -1, -1):
if is_pal(s[:i]):
return s[i:][::-1] + s
return s
这代码挺直,逻辑也没毛病。问题在于它一直切片、一直判回文,最坏情况接近 O(n^2) 。字符串一长,这种写法就开始冒汗了。
这题更稳的做法,是拿 KMP 前缀表 来找“最长回文前缀”。
做法不复杂,关键是这个拼接:
t = s + "#" + s[::-1]
为什么这么拼?因为我们想找的是: s 的前缀,和 s[::-1] 的后缀,最长能对齐多少。这个长度,恰好就是原串的最长回文前缀长度。
代码我给一版能直接交的:
defshortest_palindrome(s: str) -> str:
ifnot s:
return s
t = s + "#" + s[::-1]
lps = [0] * len(t)
j = 0
for i in range(1, len(t)):
while j > 0 and t[i] != t[j]:
j = lps[j - 1]
if t[i] == t[j]:
j += 1
lps[i] = jpal_prefix_len = lps[-1]
suffix = s[pal_prefix_len:]
return suffix[::-1] + s
拿 "abcd" 走一下,最后 pal_prefix_len = 1 ,说明只有首字母 "a" 是回文前缀。于是把 "bcd" 翻过来补到前面,得到 "dcbabcd" 。
这题真正要拎清的,不是 KMP 模板本身,而是这个判断转换: 最短回文串 = 原串前面补东西 = 找最长回文前缀。
特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.