【刷题日记】821. 字符的最短距离
本次刷题日记的第 41 篇，力扣题为：821. 字符的最短距离 ，简单
一、题目描述：
来看看今天的题还是不是一个数学题？其实做很多的题都是和数学有关或者是有密切联系的
二、这道题考察了什么思想？你的思路是什么？
仔细瞅瞅这个题给了我们那么重点信息呢？
- 第一，题目给出的一个字符串，和一个字符，这个字符串中可能在多个索引上都会有这个指定的字符
- 题目要求我们计算每个字符到指定字符的距离，距离的计算，我们可以直接通过索引取差值
一起来思考一下这个题，我们如何知道每一个指定的字符的索引呢？
我们是否可以用一个数组或者切片来记录一下指定字符的索引位置的，默认从左遍历一下字符串，遇到指定字符串就记录一下索引，那么我们就可以得到一个指定字符的索引列表
对字符串进行第二次遍历的时候，我们直接就可以用当前字符的索引和索引列表里面的数字进行去差值即可，最终取最小的
这种方式是最好想到的，这样的时间复杂度是 O(n) ， 但是空间复杂度最大的时候会是 O(n) ，就是当字符串中全部都是指定的字符的时候
按照题目给出的示例效果会是这样的：
s = "loveleetcode", c = "e"
这样子的方式也是不错的，但是不够无脑，不够明确，不够傻瓜式，我们还要自己去用数字去到 helplist 里面比较，很麻烦 ， 我们可以尝试下面这种方式，左撸一下，然后右撸一下就可以了
可以看到，我们左->右遍历一遍，得到 left，右->左遍历一遍得到 right，那么我们最后合并一下，或者在从右遍历到左的时候，直接在 left 上面覆盖值，取最小值即可，得到结果
res = [3,2,1,0,1,0,0,1,2,2,1,0]
那么思路已经非常明确了，我们来实现一下第二种思路吧，傻瓜式的来撸一撸代码
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码，这里需要注意的是，从左到右，和从右到左的时候，咱们定义的指定字符索引的初始值是需要是一个不能影响结果的值即可
func shortestToChar(s string, c byte) []int { n := len(s) idx := -n res := make([]int,n) // 从左往右进行遍历 , 定义初始值 idx 为 -n，那么在未找到正确的 c 字符的时候，计算出来当前字符离指定字符的具体是最大的，这些值，后续从又比那里的时候，会被实际的最小值覆盖 for i:=0; i<n; i++{ if s[i] == c{ idx = i } res[i] = i - idx } idx = 2*n // 从右往左进行遍历，此处 idx 定义为 2n，是因为 i 是逐渐变小的，idx -i，如果idx 不是真实指定的 c 的索引，那么得到的会是一个大于 n 的值，则按照我们的计算方式，是取最小值，则这种较大的值是不会加入到结果集中的 for i:= n-1; i>=0; i--{ if s[i] == c{ idx = i } res[i] = min(res[i],idx-i) } return res } func min(a,b int)int{ if a<b{ return a } return b }
按照我们的实现思路，现在还会有疑问为什么从左向右遍历的时候， idx 初始值是 -n ，而从又右到左的时候，idx 初始值为 2n 吗？
其实原因都是，我们在从左到右，或者从右到左的时候，在还不知道指定字符的索引的时候，我们定义的一个值，只要这个只引入的结果不会影响我们真实的结果即可
因为我们计算的是最小距离，例如
从左到右， idx 初始值为 -n ，那么左边第一个字符距离目字符的距离就是 0 - (-n) = n ，那么这个值是一个不可能在数组中计算出来的值，因此当我们从右往左计算的时候，当前字符到指定字符串的距离，一定会小于 这个 n，我们会取最小值来加入到结果集
四、总结：
根据我们的实现方式来看，时间复杂度是多少呢？我们可以看到咱们的实现思路是从左到右遍历一次，然后又从右到左遍历一次，我们的时间时间复杂度是O(2n) 吗？ nono ， 是 O(n)
空间复杂呢？仔细看看，我们是没有引入其他额外空间消耗，因此是 O(1)
原题地址：821. 字符的最短距离
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
