AI 圈小这两天 KIMI K3 的权重开源又一次让 AI 圈热闹了起来。先是世界网红英伟达创始人黄仁勋在 X 开通个人账号首篇帖子表示要站台开源模型。这帖子后边得到了众多名人和企业家的点赞当中就包括了马斯克和小扎。这两位曾经线下约架的死对头在开源模型的意见上是一致的甚至马斯克还破天荒转载了小扎的帖子。另外一个重要的事件点是 OpenAI 的 CEO 奥特曼也公开表态无论是开源模型还是闭源模型他都会为 AI 感到开心。再联想到我这两天在脉脉看到的冷知识KIMI 的创始人杨植麟是智谱创始人唐杰的学生。国内开源模型除了 Qwen 有大厂基因剩下能打的也就是 GLM 和 KIMI 了但两者都师出清华。不知道这个冷知识有多少读者知道呢欢迎评论区交流。...回归主题来一道和「字节跳动」相关的算法题。题目描述平台LeetCode题号854对于某些非负整数k如果交换中两个字母的位置恰好k次能够使结果字符串等于则认为字符串和的 相似度为k。给你两个字母异位词和返回和的相似度k的最小值。示例 1输入s1 ab, s2 ba输出1示例 2输入s1 abc, s2 bca输出2提示s1和s2只包含集合{a, b, c, d, e, f}中的小写字母s2是s1的一个字母异位词AStar 算法由于题目确保了s1和s2互为字母异位词必然有解因此最好的求解方式是使用 AStar 算法。可直接根据本题规则来设计 AStar 的启发式函数: 对于两个状态a和b直接计算出「理论最小转换次数」:「不同字符串的转换成本之和由于每一次交换最多可减少两个不同的字符我们可计算a与b的不同字符数量对应的理论最小转换次数为。」需要注意的是「由于我们衡量某个字符str的估值是以目标字符串target为基准因此我们只能确保target出队时为「距离最短」而不能确保中间节点出队时「距离最短」因此我们不能单纯根据某个节点是否「曾经入队」而决定是否入队还要结合当前节点的「最小距离」是否被更新而决定是否入队。」❝一些细节在使用当前状态字符串poll拓展新状态字符串nstr时只拓展能够减少不同字符数量的方案从而收窄搜索空间。❞Java 代码classSolution{intn;String t;intf(String s){intans 0;for(inti 0; i n; i) ans s.charAt(i) ! t.charAt(i) ?1:0;returnans 11;}publicintkSimilarity(String s1, String s2){if(s1.equals(s2))return0;t s2;n s1.length();MapString, Integer map newHashMap();PriorityQueueString pq newPriorityQueue((a,b)-{intv1 f(a), v2 f(b), d1 map.get(a), d2 map.get(b);return(v1 d1) - (v2 d2);});map.put(s1,0);pq.add(s1);while(!pq.isEmpty()) {String poll pq.poll();intstep map.get(poll);char[] cs poll.toCharArray();intidx 0;while(idx n cs[idx] t.charAt(idx)) idx;for(inti idx 1; i n; i) {if(cs[i] ! t.charAt(idx) || cs[i] t.charAt(i))continue;swap(cs, idx, i);String nstr String.valueOf(cs);swap(cs, idx, i);if(map.containsKey(nstr) map.get(nstr) step 1)continue;if(nstr.equals(t))returnstep 1;map.put(nstr, step 1);pq.add(nstr);}}return-1;// never}voidswap(char[] cs,inti,intj){charc cs[i];cs[i] cs[j];cs[j] c;}}时间复杂度启发式搜索不分析时空复杂度空间复杂度启发式搜索不分析时空复杂度最后巨划算的 LeetCode 会员优惠通道目前仍可用 ~使用福利优惠通道leetcode.cn/premium/?promoChannelacoier年度会员有效期额外增加两个月季度会员有效期额外增加两周更有超大额专属 和实物 福利每月发放。我是宫水三叶每天都会分享算法知识并和大家聊聊近期的所见所闻。欢迎关注明天见。