211以下就别天天想着进大厂了～

刚看到个贴子，有网友吐槽说“211以下就别天天想着进大厂了包”，言下之意就是学历不行别做梦。我觉得这事吧，作为程序员真的感触挺多。

网友们的回复我看了看，有的说学历真重要，大厂筛简历门槛高；也有不少人不服气，觉得技术牛照样能进大厂。怎么说呢，站在程序员的角度，学历确实是敲门砖，尤其是校招那一波，很多公司HR直接用学校一刀切，属实扎心💔。但你说没希望吗？未必，能力、项目经验、内推资源都能破圈，身边确实有非211靠实力卷进大厂的哥们。

我的看法是，学历是门票，但不是全部。技术圈最终还是看输出，能写好代码、会解决问题、懂协作，机会就多。说到底，大厂岗位是有限，但市场和机会很大。不要被学历卡死，更不要自我设限。学历重要，但持续提升自己才是王道，别让一纸文凭成为你止步的理由。【备注:文末可领最新资料】

面试题：滑动谜题

哎，前两天在家那边，晚上十一点多，正准备睡觉，突然我妹她问我，东哥，你以前不是搞算法的吗？你会不会那个滑动谜题，就是那种小方块，挪来挪去拼顺序的那个。我一听这不就是LeetCode上那种“Sliding Puzzle”嘛？不过说实话我大学时候玩那种物理玩具还挺溜，后来全都用Python写算法了。

说实话，这玩意看起来很简单，就是一个5格的棋盘，通常是2行3列，里面数字摆乱了，你要一步步把它恢复成123450这种顺序。每次只能挪0旁边的数字和0交换。刚开始我也觉得简单啊，后来写代码才发现...卧槽，剪枝不好做就TLE（超时）得飞起。

其实整个过程用的就是BFS，没啥玄学。为啥不能用DFS？你想嘛，BFS找的是最短路径，DFS一旦走远了，万一死循环，回头再剪枝，肯定慢成狗。

我一般写的时候，喜欢把棋盘状态压成字符串，这样方便哈希嘛，你直接把二维数组转成"123450"这种，反正操作也简单。每次找0的位置，看它能不能往上下左右挪一下，然后换完位置新的状态放到队列里。最关键的是你得有个set或者dict，存一下已经访问过的状态，不然你反复横跳，时间复杂度就炸了。

前两天我在公司楼下抽烟还跟小李说，其实这种题一旦状态数爆炸，BFS也吃不消，所以有时候A可以上场，启发式估价加一点，速度能快不少。可惜LeetCode这道原题BFS就能过，懒得整花的。你要是真想写A，就用曼哈顿距离做估价函数，也不难。

代码我那天刚撸了一个，凑合能跑：

from collections import deque

defslidingPuzzle(board):
    start = ''.join(str(num) for row in board for num in row)
    target = '123450'
    neighbor = {
0: [1,3], 1: [0,2,4], 2: [1,5],
3: [0,4], 4: [1,3,5], 5: [2,4]
    }
    queue = deque()
    queue.append((start, 0))
    visited = set()
    visited.add(start)
while queue:
        cur, step = queue.popleft()
if cur == target:
return step
        idx = cur.index('0')
for adj in neighbor[idx]:
            lst = list(cur)
            lst[idx], lst[adj] = lst[adj], lst[idx]
            nxt = ''.join(lst)
if nxt notin visited:
                visited.add(nxt)
                queue.append((nxt, step + 1))
return-1

对了，我顺便说一句哈，你们别小看这BFS，真正面试的时候问原理也别瞎扯，核心点其实就俩：状态压缩和去重。有的人喜欢用元组存状态，我觉得字符串更直观。之前有个实习生非得存list...面试官直接说你这个list不能哈希，查重效率太低。直接凉了。

而且，这题如果你搞成N*N版本，状态空间直接爆炸，就得用位运算压缩了。2x3还好，上面这样写没啥毛病。

哦对，还有一点，有时候你会发现这题根本无解。比如两个奇偶不一样的排列，永远拼不回去。你要是面试，记得顺嘴提一句“其实可以先判断下逆序数，奇偶性不一致就直接返回-1”。不过2x3的版本就那几个状态，直接搜也无所谓。

反正就这样，滑动谜题这题写起来其实没啥花活，重点是BFS，字符串状态压缩，访问去重，A*可以加速。