微软的这个bug，2年都没有人发现

刚看到个新闻，说微软确认 Windows 系统一个存在了两年的 bug，“更新并关机”其实是“更新并重启”。听着挺离谱的吧，但想想也挺真实——两年没人发现，不是 bug 太隐蔽，而是大家都太“懂事”了。

我觉得这事反映了两个问题：一是微软内部确实有点官僚，人浮于事；二是普通用户太容易自我怀疑了。电脑一重启，第一反应是“是不是我点错了”“是不是驱动问题”，从没想过可能是微软的问题。久而久之，大厂的错也被我们自己“合理化”了。

算法题：重构字符串

兄弟们我刚下楼买豆浆，结果排队二十分钟…想起昨天小李问我一道题，嘴上念叨着“重构字符串那个…哎对，Reorganize String”，就顺手在本子上扒拉了两笔。你们知道吧，就是给你一串字母，要求“相邻不能相等”。有就返回新串，没法就返回空串。嗯…听起来像给同事排座位，不能把两个爱聊天的挨一起，差不多一个意思。

思路：贪

简单说，每次都挑当前剩得最多、且不等于上一个字符的那个字母放进去。为什么？因为“难以安置的家伙”要优先处理，不然后面全挤到一起就炸了。实现上用一个最大堆（优先队列）存 (频次, 字符)。每轮从堆里拿出两个不同的字母 A、B，先放一个，再放另一个，各自频次减一，减完还大于0就塞回堆里。这样相邻必不等。 还有个判定：如果最大频次 > (长度+1)/2，怎么摆都撞车，直接返回空串，省事儿。

import java.util.*;

classSolution{
staticclassNode{
char c;
int cnt;
        Node(char c, int cnt) { this.c = c; this.cnt = cnt; }
    }

public String reorganizeString(String s){
int n = s.length();
int[] freq = newint[26];
for (char ch : s.toCharArray()) freq[ch - 'a']++;

int max = 0;
for (int f : freq) max = Math.max(max, f);
if (max > (n + 1) / 2) return"";

        PriorityQueue<Node> pq = new PriorityQueue<>(
            (a, b) -> b.cnt - a.cnt
        );
for (int i = 0; i < 26; i++) {
if (freq[i] > 0) pq.offer(new Node((char) ('a' + i), freq[i]));
        }

        StringBuilder sb = new StringBuilder();
        Node hold = null; // 上一次没用完的字符，暂存，下一轮再塞回堆
while (!pq.isEmpty()) {
            Node cur = pq.poll();
// 保证不与上一个相同
if (sb.length() > 0 && sb.charAt(sb.length() - 1) == cur.c) {
if (pq.isEmpty()) return""; // 没得换
                Node next = pq.poll();
                pq.offer(cur);       // 先用 next，把 cur 放回去
                cur = next;
            }
            sb.append(cur.c);
            cur.cnt--;
if (cur.cnt > 0) {
                pq.offer(cur);
            }
        }
return sb.toString();
    }
}

复杂度&小坑

我昨晚十一点多在公司楼下抽烟的时候数了下，堆里最多 26 个元素，每次弹/压是 O(log 26)≈常数，总复杂度 O(n)。 坑点就两件： 1）极端频次，比如 "aaaaab"，直接用 (n+1)/2 判掉。 2）字符集不是只含 a-z？面试官有时候会皮…那就把 26 改成 Map<Character,Integer>，思路完全一样。

为啥这招稳

有人会问“为啥每次拿两个”？因为像排班，你把“最吵”的人分散到各天，再用第二吵的去填缝，冲突最小。堆保证“当前最难的人先安排”。如果某一刻连第二个都没有（堆空了），说明无解，收工睡觉，啊不对返回空串。

这个套路还能用在“整理任务避免相邻同类型”、“CPU 降温题（加冷却时间的那个）”。思路都像：计数 -> 选最大 -> 合理分散。 行了我先去把豆浆喝了，谁要是跑出来 AC 不了，丢我代码和测试用例，我看下是不是哪里打错字了，那个…算发，不是算法，困糊涂了。

-END-

我为大家打造了一份RPA教程，完全免费：songshuhezi.com/rpa.html