j

jaryue

V1

2023/05/16阅读:8主题:默认主题

leetcode 821. 字符的最短距离

leetcode 821. 字符的最短距离.


题目描述

  1. 字符的最短距离

给你一个字符串 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]

提示: 1 <= s.length <= 104 s[i] 和 c 均为小写英文字母 题目数据保证 c 在 s 中至少出现一次

解题思路

法1

方法1:取最佳

我们来回遍历两次字符串,一次从左往右,一次从右往左,取最小的结果储存到数组中并返回数组的值

首先创建了一个与字符串 s 长度相同的整数数组 ans,用于存储每个位置到最近的字符 c 的距离。

接下来,代码使用两次遍历来计算距离。第一次遍历从左到右,维护一个变量 prev,表示最近的字符 c 的索引。如果当前位置的字符等于 c,则更新 prev 为当前索引,否则计算当前位置到 prev 的距离并存储到 ans 数组中。

第二次遍历从右到左,同样维护一个变量 prev,表示最近的字符 c 的索引。如果当前位置的字符等于 c,则更新 prev 为当前索引,然后计算当前位置到 prev 的距离,并与第一次遍历得到的距离比较,取较小值存储到 ans 数组中。

最后,返回计算得到的 ans 数组作为结果。

  • 时间复杂度(O(n))
  • 空间复杂度(O(1))

执行结果

法1

func shortestToChar(s string, c byte) []int {
    n := len(s)
    ans := make([]int, n)

    prev := -n
    for i := 0; i < n; i++ {
        if s[i] == c {
            prev = i
        }
        ans[i] = i - prev
    }

    prev = 2 * n
    for i := n-1; i >= 0; i-- {
        if s[i] == c {
            prev = i
        }
        ans[i] = min(ans[i], prev - i)
    }

    return ans
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

执行结果: 通过 显示详情 查看示例代码 添加备注

执行用时: 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗: 2.2 MB , 在所有 Go 提交中击败了 100.00% 的用户 通过测试用例: 76 / 76 炫耀一下:


分类:

后端

标签:

后端

作者介绍

j
jaryue
V1