题目

给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。

返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。

两个下标 i 和 j 之间的 距离 为 abs(i - j) ，其中 abs 是绝对值函数。

示例 1：

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

提示：

  • 1 <= s.length <= 104
  • s[i] 和 c 均为小写英文字母

  • 题目数据保证 c 在 s 中至少出现一次

    思路一：

  • 生成一个与c重复下标的数组：iArray

  • 遍历 iArray 然后用 strArray 每一个下标与iArray每一项进行比较
  • 如果 strArray 的下标小于等于 iArray第一项
  • 说明当前的距离只有离 iArray第一项最近，直接将距离push进去
  • 如果当前 strArray 的下标 大于等于 iArray[i + 1]
  • 说明 i 的区间需要改变位置了
  • 比较大小，取距离最小的

  • 判断边界，如果iArray[i + 1]超出了iArray 那就使用iArray[i]：当前i代表最后索引了

    1. const shortestToChar = function (s, c) {
    2. const strArray = s.split('');
    3. const iArray = []
    4. const res = []
    5. // 生成一个与c重复下标的数组：iArray
    6. strArray.forEach((item, index) => {
    7.   if (item === c) {
    8.     iArray.push(index)
    9.   }
    10. })
    11. // console.log(iArray)
    12. // console.log(strArray)
    13. // 遍历 iArray 然后用 strArray 每一个下标与iArray每一项进行比较
    14. for (let i = 0; i < iArray.length; i++) {
    15.   for (let j = 0; j < strArray.length; j++) {
    16.     // 如果 strArray 的下标小于等于 iArray第一项
    17.     // 说明当前的距离只有离 iArray第一项最近，直接将距离push进去
    18.     if (j <= iArray[0]) {
    19.       res.push(Math.abs(j - iArray[i]))
    20.     } else {
    21.       // 如果当前 strArray 的下标 大于等于 iArray[i + 1]
    22.       // 说明 i 的区间需要改变位置了
    23.       if (j >= iArray[i + 1]) {
    24.         i = i + 1
    25.       }
    26.       // 比较大小，取距离最小的
    27.       // 判断边界，如果iArray[i + 1]超出了iArray 那就使用iArray[i]：当前i代表最后索引了
    28.       const min = Math.min(Math.abs(j - iArray[i]), Math.abs((j - iArray[i + 1]) || j - iArray[i]))
    29.       res.push(min)
    30.     }
    31.   }
    32.   continue
    33. }
    34. return res
    35. };
    36. const res = shortestToChar("aaba", "b")
    37. console.log(res);

    思路二：

  • 把 C 看成分界线，如果没有左边或者右边用 Infinity 替代

  • 将 S 划分成一个个窗口。
  • 然后对每个窗口进行遍历，分别计算每个字符到窗口边界的距离最小值。

image.png

  1. const shortestToChar = function (s, c) {
  2.   let left = s[0] === c ? 0 : Infinity,
  3.       right = s.indexOf(c, 1) // 第一个重复的
  4.   const res = new Array(s.length)
  5.   console.log(left, right);
  6.   for (let i = 0; i < s.length; i++) {
  7.     if (right === i) {
  8.       left = right
  9.       // 下一个重复的
  10.       right = s.indexOf(c, i + 1)
  11.     }
  12.     // 从i开始与左右边界比较取绝对值，然后
  13.     res[i] = Math.min(Math.abs(i - left), Math.abs(i - right))
  14.   }
  15.   return res
  16. };
  17. const res = shortestToChar("aaba", "b")
  18. console.log(res)