最短距离题库

题一、字符的最短距离

---

给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。两个下标 i 和 j 之间的 距离 为 abs(i - j) ，其中 abs 是绝对值函数。

示例1:

输入：s = "loveleetcode", c = "e"
输出：[3,2,1,0,1,0,0,1,2,2,1,0]
解释：字符 'e' 出现在下标 3、5、6 和 11 处（下标从 0 开始计数）。
距下标 0 最近的 'e' 出现在下标 3 ，所以距离为 abs(0 - 3) = 3 。
距下标 1 最近的 'e' 出现在下标 3 ，所以距离为 abs(1 - 3) = 2 。
对于下标 4 ，出现在下标 3 和下标 5 处的 'e' 都离它最近，但距离是一样的 abs(4 - 3) == abs(4 - 5) = 1 。
距下标 8 最近的 'e' 出现在下标 6 ，所以距离为 abs(8 - 6) = 2 。

示例2:

输入：s = "aaab", c = "b"
输出：[3,2,1,0]

方案A、两次遍历

思路: 问题可以转换成，对 s 的每个下标 i，求:

• s[i] 到其左侧最近的字符 c 的距离: 我们可以从左往右遍历 s，若 s[i]=c 则记录下此时字符 c 的的下标 idx。遍历的同时更新 answer[i]=i−idx。

• s[i] 到其右侧最近的字符 c 的距离: 我们可以从右往左遍历 s，若 s[i]=c 则记录下此时字符 c 的的下标 idx。遍历的同时更新 answer[i]=min(answer[i],idx−i)

代码实现时，在开始遍历的时候 idx 可能不存在，为了简化逻辑，我们可以用 −n 或 2n 表示，这里 n 是 s 的长度。

这两者的最小值。

实现

function shortestToChar(s,c){
    const length = s.length;
    const result = new Array(length).fill(0);
    for(let i=0,idx=-length; i<length; i++){
        if(s[i] === c){
            idx = i;
        }
        result[i] = i - idx;
    }
    for(let i=length-1,idx=2*length; i>=0; i--){
        if(s[i] === c){
            idx = i;
        }
        result[i] = Math.min(result[i],idx-i);
    }
    return result;
}

• 时间复杂度: O(n)
• 空间复杂度: O(1) 返回值不计入空间复杂度