废话
最近博客突然打不开了，看了一眼是PHP开始报莫名奇妙的错误。这个博客主题是当年随便从网上找的一个，历经多个PHP和wordpress大版本变化还凑合能正常展示已经非常不易了，中途历经多次魔改和打补丁。原计划是在10周年之前把所有文章彻底重写一次换掉wordpress，但以我这个鸽子的风格看了一眼还有1个月时间显然不现实，所以这次我直接放弃了，直接用官方的模板改了改css就成了现在这个样子。
看了一眼历史记录，我的第一篇博客还是在大学时候联系ubuntu linux搭建wodpress后写的，当时正好是大一的期末即将C语言考试，写了一系列的C语言教程当作期末复习。众所周知我的算法比较弱（相比于栋神或然妞），并且从未在算法上怎么努力过，就这么得过且过了10年，做深度算法的分析屈指可数。印象中比较清晰的只有KMP算法、Levenshtein距离、上班时为了优化聊天室pin消息new红点的算法、为了模仿outlook日程布局设计的排版算法。
前段时间在群里看到有人在讨论一个算法题，我简单分享了思路，但懒得动手。这次正好做个深度解析。顺带一提虽然现在ai编程非常的火，工作的话因为讲究效率优先有时候无需考虑原理，只要结果对就行。但长期来看我的态度还是要磨练下基本功，不然AI错了你根本纠正不回来，所以本次不会使用任何AI补全，完全一步步手动实现再逐步优化。
原题目
https://www.nowcoder.com/practice/294da7ea5f184655a31bf659035fc874?tab=note
视频版
https://www.bilibili.com/video/BV1cChqzqEh8
描述
假定小李有 m 个偏爱的字符，依次为c1,c2…cm，当小李看到一个长度为 n 的字符串 s 时，请你输出小李在进行全部替换操作后形成的字符串。
输入描述：
接下来一行输入m个字符c1,c2…cm，每两个字符之间用空格隔开，表示小李偏爱的字符。
1≤n≤1e5,1≤m≤26，保证题目中所有的字符均为大写字符，小李偏爱的字符互不相同，且偏爱字符至少出现一次。
输出描述：
输入：
|
0 1 2 3 |
12 4 Z G B A ZQWEGRTBYAAI |
输出：
|
0 1 |
ZZZGGGBBBAAA |
说明：
|
0 1 2 3 4 5 |
字符Q为非偏爱字符，且偏爱字符Z距离它最近，所以替换成Z；同理E距离G最近，替换成G； 对于字符W，偏爱字符Z和G与其距离相同，所以替换为左边的Z； ....... 对于字符 I ，右边没有偏爱字符，左边第一个偏爱字符是A，所以替换成字符A。 同一个偏爱字符可能会在字符串中出现多次。 |
题目分析
我做算法题因为没有限时，所以一般来说我都是先用暴力手段写正确结果，再逐步优化
题目里废话实在太多，翻译成人话就是把后续所有输入都改成指定的几个字母，以最近的为准，如果距离一样用左边的。
暴力版本
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; import java.util.stream.Collector; import java.util.stream.Collectors; public class Main { public static void main(String[] args) { //输入： //12 4 //Z G B A //ZQWEGRTBYAAI String inputStr = "ZQWEGRTBYAAI"; List<Character> inputStrChars = convert(inputStr); Set<Character> preferChars = new HashSet<>(4); preferChars.add('Z'); preferChars.add('G'); preferChars.add('B'); preferChars.add('A'); // System.out.println(inputStr); System.out.println(inputStrChars); // System.out.println(preferChars); String result = replaceChars(inputStrChars, preferChars); // String result = replaceChars1(inputStrChars, preferChars); // String result = replaceChars2(inputStrChars, preferChars); // String result = replaceChars3(inputStrChars, preferChars); System.out.println(result); //输出： //ZZZGGGBBBAAA } private static String replaceChars(List<Character> inputStrChars, Set<Character> preferChars) { List<Character> result = new ArrayList<>(inputStrChars.size()); // return "ZZZGGGBBBAAA"; // inputStrChars = convert("ZZZGGGBBBAAA"); for (int i = 0; i < inputStrChars.size(); i++) { Character currentChar = inputStrChars.get(i); if (preferChars.contains(currentChar)) { result.add(currentChar); } else { //find first preferChars in left int currentIndex = i; int leftDistance = findLeftPreferCharDistance(inputStrChars, currentIndex,preferChars); Character leftPreferChar = inputStrChars.get(currentIndex - leftDistance); //find first preferChars in right int rightDistance = findRightPreferCharDistance(inputStrChars, currentIndex,preferChars); Character rightPreferChar = inputStrChars.get(currentIndex + rightDistance); //compare distance Character replacedChar = 'A'; if (leftDistance <= rightDistance) { replacedChar = leftPreferChar; } else { replacedChar = rightPreferChar; } result.add(replacedChar); } } return convert(result); } private static int findLeftPreferCharDistance(List<Character> inputStrChars, int currentIndex, Set<Character> preferChars) { for (int i = currentIndex; i >=0; i--) { Character currentChar = inputStrChars.get(i); if (preferChars.contains(currentChar)) { return Math.abs(currentIndex - i); } } System.out.printf("find left prefer char error, currentIndex = %s\n", currentIndex); return -1; } private static int findRightPreferCharDistance(List<Character> inputStrChars, int currentIndex, Set<Character> preferChars) { for (int i = currentIndex; i < inputStrChars.size(); i++) { Character currentChar = inputStrChars.get(i); if (preferChars.contains(currentChar)) { return Math.abs(currentIndex - i); } } System.out.printf("find right prefer char error, currentIndex = %s\n", currentIndex); return -1; } private static String convert(List<Character> result) { String resultStr = result.stream().map(v -> v + "").collect(Collectors.joining("")); return resultStr; } private static List<Character> convert(String inputStr) { List<Character> result = new ArrayList<>(inputStr.length()); for (int i = 0; i < inputStr.length(); i++) { result.add(inputStr.charAt(i)); } return result; } } |
加一点优化
根据刚才的运行结果，如果尝试打印寻找过程
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
//0 find left prefer char, currentIndex = 1, distance = 1 find right prefer char, currentIndex = 1, distance = 3 find left prefer char, currentIndex = 2, distance = 2 find right prefer char, currentIndex = 2, distance = 2 find left prefer char, currentIndex = 3, distance = 3 find right prefer char, currentIndex = 3, distance = 1 //4 find left prefer char, currentIndex = 5, distance = 1 find right prefer char, currentIndex = 5, distance = 2 find left prefer char, currentIndex = 6, distance = 2 find right prefer char, currentIndex = 6, distance = 1 //7 find left prefer char, currentIndex = 8, distance = 1 find right prefer char, currentIndex = 8, distance = 1 //9 //10 find left prefer char, currentIndex = 11, distance = 1 find right prefer char error, currentIndex = 11 |
注意到每次左侧寻找的距离都是递增的，so优化思路就是不要每次都从头开始搜，如果还没出现新的偏爱字符，那上一次寻找的结果直接+1就是本次搜索的结果，如果距离右侧最新的偏爱字符过半了，那就是右侧的结果。因此之前循环的状态需要记录下左侧和右侧的距离或索引。
TODO 待编写代码
再加一点优化
按上面的思路，如果能提前知道哪些位置是偏爱字符，那么根本不需要逐个字符判断、搜索、替换，可以直接按偏爱字符的位置就能计算最终的结果。你会发现最终结果只和偏爱字符的位置有关，和其他输入的字符无关，你甚至都不需要读入其他字符也能计算出最终结果
TODO 待编写代码
另类思路
按上面所说既然结果和其他字符无关，只需要特殊字符和对应的位置+总字符串长度就能计算的话。实时处理也是可能的，这也是目前AI输入输出常见的表现形式，打字机效果。当输入一个字符后，实时输出最终结果，当发现前几个字符结果不对了，删除前n个字符后纠正回正确的字符。这种算法不需要预处理，但因为无法预知后续输入所以必须有纠正的过程出现。实际实现逻辑只需记录最后一次输入的偏爱字符和当前字符和最后一次输入的偏爱字符距离，即可知道是应该打印最后一次的偏爱字符，还是应该删除前n个距离当前输入的偏爱字符更近的字符。
TODO 待编写代码