力扣加加 - 努力做西湖区最好的算法题解
lucifer 的博客
Github
公众号
搜索文档…
introduction
第一章 - 算法专题
第二章 - 91 天学算法
第三章 - 精选题解
第四章 - 高频考题(简单)
面试题 17.12. BiNode
0001. 两数之和
0020. 有效的括号
0021. 合并两个有序链表
0026. 删除排序数组中的重复项
0053. 最大子序和
0160. 相交链表
0066. 加一
0088. 合并两个有序数组
0101. 对称二叉树
0104. 二叉树的最大深度
0108. 将有序数组转换为二叉搜索树
0121. 买卖股票的最佳时机
0122. 买卖股票的最佳时机 II
0125. 验证回文串
0136. 只出现一次的数字
0155. 最小栈
0167. 两数之和 II 输入有序数组
0169. 多数元素
0172. 阶乘后的零
0190. 颠倒二进制位
0191. 位 1 的个数
0198. 打家劫舍
0203. 移除链表元素
0206. 反转链表
0219. 存在重复元素 II
0226. 翻转二叉树
0232. 用栈实现队列
0263. 丑数
0283. 移动零
0342. 4 的幂
0349. 两个数组的交集
0371. 两整数之和
401. 二进制手表
0437. 路径总和 III
0455. 分发饼干
0504. 七进制数
0575. 分糖果
0665. 非递减数列
0661. 图片平滑器
821. 字符的最短距离
0874. 模拟行走机器人
1128. 等价多米诺骨牌对的数量
1260. 二维网格迁移
1332. 删除回文子序列
第五章 - 高频考题(中等)
第六章 - 高频考题(困难)
后序
由
GitBook
提供支持
821. 字符的最短距离
https://leetcode-cn.com/problems/shortest-distance-to-a-character
题目描述
1
给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。
2
3
示例 1:
4
5
输入: S = "loveleetcode", C = 'e'
6
输出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
7
说明:
8
9
- 字符串 S 的长度范围为 [1, 10000]。
10
- C 是一个单字符,且保证是字符串 S 里的字符。
11
- S 和 C 中的所有字母均为小写字母。
Copied!
前置知识
数组的遍历(正向遍历和反向遍历)
思路
这道题就是让我们求的是向左或者向右距离目标字符最近的距离。
我画了个图方便大家理解:
比如我们要找第一个字符 l 的最近的字符 e,直观的想法就是向左向右分别搜索,遇到字符 e 就停止,比较两侧的距离,并取较小的即可。如上图,l 就是 3,c 就是 2。
这种直观的思路用代码来表示的话是这样的:
Python Code:
1
class
Solution
:
2
def
shortestToChar
(
self
,
S
:
str
,
C
:
str
)
->
List
[
int
]:
3
ans
=
[]
4
5
for
i
in
range
(
len
(
S
)):
6
# 从 i 向左向右扩展
7
l
=
r
=
i
8
# 向左找到第一个 C
9
while
l
>
-
1
:
10
if
S
[
l
]
==
C
:
break
11
l
-=
1
12
# 向左找到第一个 C
13
while
r
<
len
(
S
):
14
if
S
[
r
]
==
C
:
break
15
r
+=
1
16
# 如果至死没有找到,则赋值一个无限大的数字,由于题目的数据范围是 [1, 10000],因此 -10000 或者 10000就够了。
17
if
l
==
-
1
:
l
=
-
10000
18
if
r
==
len
(
S
):
r
=
10000
19
# 选较近的即可
20
ans
.
append
(
min
(
r
-
i
,
i
-
l
))
21
return
ans
Copied!
复杂度分析
时间复杂度:$O(N^2)$
空间复杂度:$O(1)$
由于题目的数据范围是 $10^4$,因此通过所有的测试用例是没有问题的。
但是实际上,我们可以在线性的时间内解决。这里的关键点和上面的解法类似,也是两端遍历。不过不再是盲目的查找,因为这样做会有很多没有必要的计算。
我们可以使用空间换时间的方式来解,这里我使用类似单调栈的解法来解,大家也可以使用其他手段。关于单调栈的技巧,不在这里展开,感兴趣的可以期待我后面的专题。
1
class
Solution
:
2
def
shortestToChar
(
self
,
S
:
str
,
C
:
str
)
->
List
[
int
]:
3
ans
=
[
10000
]
*
len
(
S
)
4
stack
=
[]
5
for
i
in
range
(
len
(
S
)):
6
while
stack
and
S
[
i
]
==
C
:
7
ans
[
stack
.
pop
()]
=
i
-
stack
[
-
1
]
8
if
S
[
i
]
!=
C
:
stack
.
append
(
i
)
9
else
:
ans
[
i
]
=
0
10
for
i
in
range
(
len
(
S
)
-
1
,
-
1
,
-
1
):
11
while
stack
and
S
[
i
]
==
C
:
12
ans
[
stack
.
pop
()]
=
min
(
ans
[
stack
[
-
1
]],
stack
[
-
1
]
-
i
)
13
if
S
[
i
]
!=
C
:
stack
.
append
(
i
)
14
else
:
ans
[
i
]
=
0
15
16
return
ans
Copied!
复杂度分析
时间复杂度:$O(N)$
空间复杂度:$O(N)$
实际上,我们根本不需要栈来存储。原因很简单,那就是每次我们碰到目标字符 C 的时候, 我们就把栈
全部清空
了,因此我们用一个变量标识即可,具体参考后面的代码区。
如果碰到目标字符 C 的时候,不把栈清空,那么这个栈的空间多半是不能省的,反之可以省。
代码
代码支持:Python3,Java, CPP, Go, PHP
Python3 Code:
1
class
Solution
:
2
def
shortestToChar
(
self
,
S
:
str
,
C
:
str
)
->
List
[
int
]:
3
pre
=
-
10000
4
ans
=
[]
5
6
for
i
in
range
(
len
(
S
)):
7
if
S
[
i
]
==
C
:
pre
=
i
8
ans
.
append
(
i
-
pre
)
9
pre
=
20000
10
for
i
in
range
(
len
(
S
)
-
1
,
-
1
,
-
1
):
11
if
S
[
i
]
==
C
:
pre
=
i
12
ans
[
i
]
=
min
(
ans
[
i
],
pre
-
i
)
13
return
ans
Copied!
Java Code:
1
class
Solution
{
2
public
int
[]
shortestToChar
(
String
S
,
char
C
)
{
3
int
N
=
S
.
length
();
4
int
[]
ans
=
new
int
[
N
];
5
int
prev
=
-
10000
;
6
7
for
(
int
i
=
0
;
i
<
N
;
++
i
)
{
8
if
(
S
.
charAt
(
i
)
==
C
)
prev
=
i
;
9
ans
[
i
]
=
i
-
prev
;
10
}
11
12
prev
=
20000
;
13
for
(
int
i
=
N
-
1
;
i
>=
0
;
--
i
)
{
14
if
(
S
.
charAt
(
i
)
==
C
)
prev
=
i
;
15
ans
[
i
]
=
Math
.
min
(
ans
[
i
],
prev
-
i
);
16
}
17
18
return
ans
;
19
}
20
}
Copied!
CPP Code:
1
class
Solution
{
2
public
:
3
vector
<
int
>
shortestToChar
(
string S
,
char
C
)
{
4
vector
<
int
>
ans
(
S
.
size
(),
0
);
5
int
prev
=
-
10000
;
6
for
(
int
i
=
0
;
i
<
S
.
size
();
i
++
){
7
if
(
S
[
i
]
==
C
)
prev
=
i
;
8
ans
[
i
]
=
i
-
prev
;
9
}
10
prev
=
20000
;
11
for
(
int
i
=
S
.
size
()
-
1
;
i
>=
0
;
i
--
){
12
if
(
S
[
i
]
==
C
)
prev
=
i
;
13
ans
[
i
]
=
min
(
ans
[
i
],
prev
-
i
);
14
}
15
return
ans
;
16
}
17
};
Copied!
Go Code:
1
func
shortestToChar
(
S
string
,
C
byte
)
[]
int
{
2
N
:=
len
(
S
)
3
ans
:=
make
([]
int
,
N
)
4
5
pre
:=
-
N
// 最大距离
6
for
i
:=
0
;
i
<
N
;
i
++
{
7
if
S
[
i
]
==
C
{
8
pre
=
i
9
}
10
ans
[
i
]
=
i
-
pre
11
}
12
13
pre
=
N
*
2
// 最大距离
14
for
i
:=
N
-
1
;
i
>=
0
;
i
--
{
15
if
S
[
i
]
==
C
{
16
pre
=
i
17
}
18
ans
[
i
]
=
min
(
ans
[
i
],
pre
-
i
)
19
}
20
return
ans
21
}
22
23
func
min
(
a
,
b
int
)
int
{
24
if
a
<
b
{
25
return
a
26
}
27
return
b
28
}
Copied!
PHP Code:
1
class
Solution
2
{
3
4
/**
5
* @param String $S
6
* @param String $C
7
* @return Integer[]
8
*/
9
function
shortestToChar
(
$S
,
$C
)
10
{
11
$N
=
strlen
(
$S
);
12
$ans
=
[];
13
14
$pre
=
-
$N
;
15
for
(
$i
=
0
;
$i
<
$N
;
$i
++
)
{
16
if
(
$S
[
$i
]
==
$C
)
{
17
$pre
=
$i
;
18
}
19
$ans
[
$i
]
=
$i
-
$pre
;
20
}
21
22
$pre
=
$N
*
2
;
23
for
(
$i
=
$N
-
1
;
$i
>=
0
;
$i
--
)
{
24
if
(
$S
[
$i
]
==
$C
)
{
25
$pre
=
$i
;
26
}
27
$ans
[
$i
]
=
min
(
$ans
[
$i
],
$pre
-
$i
);
28
}
29
return
$ans
;
30
}
31
}
Copied!
复杂度分析
时间复杂度:$O(N)$
空间复杂度:$O(1)$
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:
https://github.com/azl397985856/leetcode
。 目前已经 37K star 啦。
大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
以前
0661. 图片平滑器
下一个
0874. 模拟行走机器人
最近更新
1yr ago
复制链接
内容
题目描述
前置知识
思路
代码