力扣AC：字符的最短距离

题目链接

字符的最短距离

题目描述

实现代码

个人实现思路：

1. 首先遍历一次找到所有的c字符的位置存入数组cIndexes并记录其出现次数cLen；
2. 第二次遍历，对所有位置的元素与cindexes中的c位置进行逐一比较取小值得出最后结果；

注意的点：

1. 进行取小值对findC位置进行循环自增时判断是否已经到了最后一个；
2. 考虑如下情况

   s = “bbba” c = ‘b’

实现代码：

class Solution {
    public int[] shortestToChar(String s, char c) {
        int len = s.length();
        int[] results = new int[len];
        int[] cIndexed = new int[len];
        int cLen = 0;
        for(int i=0; i<len; i++) {
            if(s.charAt(i) == c) {
                cIndexed[cLen++] = i;
            }
        }
        int findC = 0;
        for(int i=0; i<len; i++) {
            char current = s.charAt(i);
            if(current == c) {
                continue;
            }
            if(findC == cLen-1) {
                results[i] = Math.abs(i - cIndexed[findC]);
            } else {
                while (Math.abs(i - cIndexed[findC]) >= Math.abs(i - cIndexed[findC + 1])) {
                    findC++;
                    if(findC == cLen - 1) {
                        break;
                    }
                }
                results[i] = Math.abs(i - cIndexed[findC]);
            }
        }
        return results;
    }
}

官方思路：

1. 分别找到每个位置从左看和从右看的最短距离，然后取最小

实现代码：

class Solution {
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] ans = new int[n];
        for (int i = 0, idx = -n; i < n; ++i) {
            if (s.charAt(i) == c) {
                idx = i;
            }
            ans[i] = i - idx;
        }
        for (int i = n - 1, idx = 2 * n; i >= 0; --i) {
            if (s.charAt(i) == c) {
                idx = i;
            }
            ans[i] = Math.min(ans[i], idx - i);
        }
        return ans;
    }
}