苦逼的程序员,为了结婚,高位接盘买房,房子还没交付,背负了150万的房贷,工作被裁了,刚结婚的老婆,不到两个月跑了。。
刚看到个贴子,说一个程序员为了结婚,硬着头皮买了房,背上150万贷款,结果房子还没交付就被裁员,老婆也跑了。网友都在骂现实太狠,我看完也挺唏嘘。
程序员挣钱快,可风险也高,行业波动一来,连喘口气的机会都没有。网友有人说“别买房,租就行”,但说实话,到了结婚年龄,不买房很多人连婚都结不了。现实就是这么拧巴。
从我的角度看,问题不在买房,而在“孤注一掷”。工作、婚姻、贷款,全绑在一起,一崩全崩。人得有点“留白”的空间,不管是钱上还是心上。【备注:文末可领最新资料】
面试题:查找排列的下标
昨天晚上十一点多,在公司楼下啃着还凉着的肉夹馍,小李突然在群里问:“哥,那个…查找排列的下标怎么写来着?”我一愣,哦你说的是给你两个字符串 s 和 p,找出 s 里所有跟 p 由同样字母排列成的子串起始下标,对吧。就是常说的“异位词窗口”。别紧张,这玩意儿思路就一个字——滑。
先把场景想清楚:p 的字母构成是固定的,对吧。那我在 s 上滑一个和 p 等长的窗口,窗口里字母频率如果跟 p 一样,那窗口起点就是答案。问题是不能每次都重算频率,不然就超时。做法是这样的——我用两个长度 26 的数组(只考虑小写字母),一个记录 p 的频率,一个记录当前窗口的频率。窗口右边进一个字母就 +1,左边出一个就 -1。为了避免每次比较 26 位,我再维护一个“匹配计数”:当某个字母在窗口里的计数正好等于 p 的计数时,match++;当它从相等变成不相等时,match--。当 match==26,就说明两个频率完全一致,窗口起点记下来就完了。这样时间 O(n),空间 O(1)。
哦对了,细节总是绊人:如果 p 比 s 还长,直接空数组返回,别犹豫;还有只适用于 a–z 的情况,Unicode 就别这么玩了,用字典或 Counter。
我把刚才在地库里写的代码贴一下,能直接跑。没用花里胡哨的库,逻辑清楚,线上也扛得住。
from typing import List
deffind_anagram_indices(s: str, p: str) -> List[int]:
# 快速失败
if len(p) > len(s):
return []
# 仅处理小写字母
base = ord('a')
need = [0] * 26
window = [0] * 26
for ch in p:
need[ord(ch) - base] += 1
# 初始化首个窗口
for ch in s[:len(p)]:
window[ord(ch) - base] += 1
# 统计初始 match:有 26 个位置都相等才算完全匹配
match = 0
for i in range(26):
if window[i] == need[i]:
match += 1
res = []
if match == 26:
res.append(0)
# 滑动窗口:右进 left 从 0 开始,right 从 len(p) 开始
left = 0
for right in range(len(p), len(s)):
# 右边进一个
r_idx = ord(s[right]) - base
window[r_idx] += 1
if window[r_idx] == need[r_idx]:
match += 1
elif window[r_idx] - 1 == need[r_idx]:
# 刚从“相等”变为“不等”
match -= 1
# 左边出一个
l_idx = ord(s[left]) - base
window[l_idx] -= 1
if window[l_idx] == need[l_idx]:
match += 1
elif window[l_idx] + 1 == need[l_idx]:
match -= 1
left += 1
if match == 26:
res.append(left)
return res
# 小测一下
if __name__ == "__main__":
print(find_anagram_indices("cbaebabacd", "abc")) # [0, 6]
print(find_anagram_indices("abab", "ab")) # [0, 1, 2]
有人会说用 collections.Counter 不香吗?香,但要注意每次比较两个 Counter 代价不小;如果只是小写字母,数组版更快更省。还有个小坑,很多同学在移动窗口时只更新右边的字母,忘了把左边弹出去的字母从频率里减掉,结果匹配永远膨胀,找出来一堆假阳性…我见过,别笑。
顺带提一嘴,窗口思想你们用在日志扫描也一样好使。我们组上次排一个“偶发超时”的锅,我就是用类似的“定长窗口 + 计数”把可疑区间扣出来的。技术都是互通的,别死记公式。好了不说了,电梯来了我上楼开会,等会儿再看你们有没有把边界写崩。
-END-
我为大家打造了一份RPA教程,完全免费:songshuhezi.com/rpa.html
虎哥作为一名老码农,整理了全网最全《python高级架构师资料合集》,总量高达650GB,点击下方公众号回复关键字 python 全部免费领