【基础篇 - Day 2】 2020-11-02 - 821. 字符的最短距离（01. 数组，栈，队列 ）

[patrickz93]

我的解法

public int[] shortestToChar(String S, char C) {
       Queue<Integer> cIndexQueue = new LinkedList<Integer>();
        char[] chars = S.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == C) {
                cIndexQueue.offer(i);
            }
        }

        int [] distance = new int[chars.length];

        Integer rightIndex = cIndexQueue.poll();
        for (int i = 0; i < rightIndex; i++) {
            distance[i] = rightIndex - i;
        }
        int leftIndex = rightIndex;

        while (!cIndexQueue.isEmpty()) {
            Integer rightIndex2 = cIndexQueue.poll();
            for (int i = leftIndex; i <= rightIndex2; i++) {
                int distanceDiff = (rightIndex2 - leftIndex)/2;
                if (i - leftIndex < distanceDiff) {
                    distance[i] = i - leftIndex;
                } else if (i - leftIndex == distanceDiff) {
                    distance[i] = distanceDiff;
                } else {
                    distance[i] = rightIndex2 - i;
                }
            }
            leftIndex = rightIndex2;
        }

        for (int i = leftIndex; i < chars.length; i++) {
            distance[i] = i - leftIndex;
        }

        return distance;
    }

[patrickz93]

官方解法

https://leetcode-cn.com/problems/shortest-distance-to-a-character/solution/zi-fu-de-zui-duan-ju-chi-by-leetcode/ 想法

对于每个字符 S[i]，试图找出距离向左或者向右下一个字符 C 的距离。答案就是这两个值的较小值。

算法

从左向右遍历，记录上一个字符 C 出现的位置 prev，那么答案就是 i - prev。

从右想做遍历，记录上一个字符 C 出现的位置 prev，那么答案就是 prev - i。

这两个值取最小就是答案。

public int[] shortestToChar(String S, char C) {
        int N = S.length();
        int[] ans = new int[N];
        int prev = Integer.MIN_VALUE / 2;

        for (int i = 0; i < N; ++i) {
            if (S.charAt(i) == C) prev = i;
            ans[i] = i - prev;
        }

        prev = Integer.MAX_VALUE / 2;
        for (int i = N-1; i >= 0; --i) {
            if (S.charAt(i) == C) prev = i;
            ans[i] = Math.min(ans[i], prev - i);
        }

        return ans;
    }