内蒙古高等级公路建设开发有限责任公司网站城阳网站设计

内蒙古高等级公路建设开发有限责任公司网站,城阳网站设计,域名邮箱免费注册,网站建设yuue字符的最短距离 问题描述 给你一个字符串 s 和一个字符 c#xff0c;其中 c 在 s 中至少出现一次。 返回一个整数数组 answer#xff0c;其中 answer[i] 是字符串 s 中下标 i 处的字符到最近的字符 c 的最短距离。 两个下标 i 和 j 之间的距离为 abs(i - j)。 示例…字符的最短距离问题描述给你一个字符串s和一个字符c其中c在s中至少出现一次。返回一个整数数组answer其中answer[i]是字符串s中下标i处的字符到最近的字符c的最短距离。两个下标i和j之间的距离为abs(i - j)。示例输入: s loveleetcode, c e 输出: [3,2,1,0,1,0,0,1,2,2,1,0] 解释: 字符 e 在下标 3、5、6、11 处出现。 对于下标 0最近的 e 在下标 3距离为 |0-3| 3。 对于下标 1最近的 e 在下标 3距离为 |1-3| 2。 ...算法思路核心最近距离对于任意位置 i最近的字符 c 要么在 i 的左边要么在 i 的右边两次遍历第一次从左到右记录每个位置到左边最近 c 的距离第二次从右到左记录每个位置到右边最近 c 的距离取两次遍历结果的最小值方法两次遍历时间复杂度 O(n)空间复杂度 O(1)预处理位置先找到所有 c 的位置然后对每个位置二分查找最近的 c暴力对每个位置遍历整个字符串找最近的 c效率低代码实现方法一两次遍历classSolution{/** * 使用两次遍历计算每个字符到最近目标字符的最短距离 * * param s 输入字符串 * param c 目标字符 * return 每个位置到最近c的最短距离数组 */publicint[]shortestToChar(Strings,charc){intns.length();int[]resultnewint[n];// 初始化为一个很大的值大于可能的最大距离// 最大距离不会超过n所以用n作为初始值for(inti0;in;i){result[i]n;}// 第一次遍历从左到右计算到左边最近c的距离intprev-n;// 记录上一个c的位置初始化为-n确保第一次更新for(inti0;in;i){if(s.charAt(i)c){previ;}result[i]Math.min(result[i],i-prev);}// 第二次遍历从右到左计算到右边最近c的距离prev2*n;// 记录下一个c的位置初始化为2*n确保第一次更新for(intin-1;i0;i--){if(s.charAt(i)c){previ;}result[i]Math.min(result[i],prev-i);}returnresult;}}方法二预处理位置 二分查找importjava.util.*;classSolution{/** * 先预处理所有目标字符的位置然后对每个位置二分查找最近的位置 */publicint[]shortestToChar(Strings,charc){// 预处理找到所有c的位置ListIntegerpositionsnewArrayList();for(inti0;is.length();i){if(s.charAt(i)c){positions.add(i);}}int[]resultnewint[s.length()];// 对每个位置找到最近的cfor(inti0;is.length();i){result[i]findMinDistance(positions,i);}returnresult;}/** * 在有序位置列表中找到距离target最近的位置 */privateintfindMinDistance(ListIntegerpositions,inttarget){// 二分查找插入位置intleft0,rightpositions.size();while(leftright){intmidleft(right-left)/2;if(positions.get(mid)target){leftmid1;}else{rightmid;}}intminDistInteger.MAX_VALUE;// 检查left位置第一个target的位置if(leftpositions.size()){minDistMath.min(minDist,positions.get(left)-target);}// 检查left-1位置最后一个target的位置if(left0){minDistMath.min(minDist,target-positions.get(left-1));}returnminDist;}}方法三暴力classSolution{/** * 暴力对每个位置遍历整个字符串 */publicint[]shortestToChar(Strings,charc){intns.length();int[]resultnewint[n];for(inti0;in;i){intminDistn;// 最大可能距离for(intj0;jn;j){if(s.charAt(j)c){minDistMath.min(minDist,Math.abs(i-j));}}result[i]minDist;}returnresult;}}算法分析时间复杂度两次遍历O(n) - 三次线性扫描初始化两次遍历预处理二分查找O(n log k) - k是字符c的出现次数暴力O(n²)空间复杂度两次遍历O(1) - 只使用常数额外空间预处理二分查找O(k) - 存储c的位置暴力O(1)算法过程1s “loveleetcode”, c “e”字符e的位置[3, 5, 6, 11]两次遍历第一次遍历左到右i0: prev-12, dist0-(-12)12i1: prev-12, dist13i2: prev-12, dist14i3: s[3]‘e’, prev3, dist0i4: prev3, dist1i5: s[5]‘e’, prev5, dist0i6: s[6]‘e’, prev6, dist0i7: prev6, dist1…继续到i11中间结果[12,13,14,0,1,0,0,1,2,3,4,0]第二次遍历右到左i11: s[11]‘e’, prev11, distmin(0, 0)0i10: prev11, distmin(4, 1)1i9: prev11, distmin(3, 2)2i8: prev11, distmin(2, 3)2i7: prev11, distmin(1, 4)1i6: s[6]‘e’, prev6, distmin(0, 0)0i5: s[5]‘e’, prev5, distmin(0, 0)0i4: prev5, distmin(1, 1)1i3: s[3]‘e’, prev3, distmin(0, 0)0i2: prev3, distmin(14, 1)1i1: prev3, distmin(13, 2)2i0: prev3, distmin(12, 3)3最终结果[3,2,1,0,1,0,0,1,2,2,1,0]测试用例publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例1标准示例int[]result1solution.shortestToChar(loveleetcode,e);System.out.println(Test 1: Arrays.toString(result1));// [3,2,1,0,1,0,0,1,2,2,1,0]// 测试用例2目标字符在开头int[]result2solution.shortestToChar(aaab,b);System.out.println(Test 2: Arrays.toString(result2));// [3,2,1,0]// 测试用例3目标字符在结尾int[]result3solution.shortestToChar(baaa,b);System.out.println(Test 3: Arrays.toString(result3));// [0,1,2,3]// 测试用例4所有字符都是目标字符int[]result4solution.shortestToChar(eeee,e);System.out.println(Test 4: Arrays.toString(result4));// [0,0,0,0]// 测试用例5只有一个目标字符int[]result5solution.shortestToChar(abcdefg,d);System.out.println(Test 5: Arrays.toString(result5));// [3,2,1,0,1,2,3]// 测试用例6单字符字符串int[]result6solution.shortestToChar(a,a);System.out.println(Test 6: Arrays.toString(result6));// [0]// 测试用例7两个字符int[]result7solution.shortestToChar(ab,b);System.out.println(Test 7: Arrays.toString(result7));// [1,0]// 测试用例8目标字符多次出现int[]result8solution.shortestToChar(abccba,c);System.out.println(Test 8: Arrays.toString(result8));// [2,1,0,0,1,2]// 测试用例9长字符串int[]result9solution.shortestToChar(abcdefghijklmnopqrstuvwxyz,m);System.out.println(Test 9: Arrays.toString(result9));// [12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13]// 测试用例10目标字符在中间int[]result10solution.shortestToChar(abcde,c);System.out.println(Test 10: Arrays.toString(result10));// [2,1,0,1,2]}关键点两次遍历单次遍历无法同时考虑左右两边的最近字符两次遍历分别处理左边界和右边界情况初始化使用足够大的初始值确保正确更新避免使用Integer.MAX_VALUE防止溢出距离计算左到右i - prevprev ≤ i右到左prev - iprev ≥ i保证距离为正数边界处理字符串开头只有右边的字符可选字符串结尾只有左边的字符可选常见问题为什么不能用一次遍历一次遍历只能知道已遍历部分的信息无法预知右边是否有更近的字符