大家好,我是毛毛。ヾ(´∀ ˋ)ノ
废话不多说开始今天的解题Day~
Given a string s
and a character c
that occurs in s
, return an array of integers answer where answer.length == s.length
and answer[i]
is the distance from index i
to the closest occurrence of character c
in s
.
The distance between two indices i
and j
is abs(i - j)
, where abs
is the absolute value function.
Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]
Explanation: The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed).
The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3.
The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2.
For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1.
The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.
Input: s = "aaab", c = "b"
Output: [3,2,1,0]
1 <= s.length <= 10^4
s[i]
and c
are lowercase English letters.c
occurs at least once in s
.首先先简单的翻译一下题目
给一个字串和字元,要先找出这个字元在字串的哪些位置上,最後回传每个位置跟该字元的最短距离。
作法大致上是这样
c
在s
的哪些位置上(这边存在indices
的list中),再来用Binary Search
去找s
的每一个index应该插在indices
的哪个位置上。class Solution:
def shortestToChar(self, s: str, c: str) -> List[int]:
indices = [index for index, value in enumerate(s) if value == c]
# print(indices)
# print(len(s))
ans = []
for index in range(len(s)):
if index in indices:
ans.append(0)
continue
# binary Search
low = 0
upper = len(indices)-1
mid = 0
while low <= upper:
mid = int(round( ((low + upper) / 2), 0))
if indices[mid] < index:
low = mid + 1
elif indices[mid] > index:
upper = mid - 1
else:
ans.append(abs(indices[mid]-index))
# If it doesn't contain in indices, we need to find where it would be inserted.
if indices[mid] < index:
if mid+1 <= len(indices)-1:
ans.append(min(abs(indices[mid]-index), abs(indices[mid+1]-index)))
else:
ans.append(abs(indices[mid]-index))
else:
if mid-1 >= 0:
ans.append(min(abs(indices[mid-1]-index), abs(indices[mid]-index)))
else:
ans.append(abs(indices[mid]-index))
return ans
Python
大家明天见
<<: [DAY-23] 有声 无声 在不同模式下 有效沟通
>>: 【Day26】[演算法]-快速排序法Quick Sort
...为什麽 PHP 的变数宣告要使用 $ 符号?...PHP 在变数前使用 $ 的用意是提醒开发...
今天来简单介绍关於物件的一些基本概念 物件的结构 我们可以利用 {} 中括号 来建立一个物件,物件内...
您的订阅是我制作影片的动力 订阅点这里~ 若内容有误,还请留言指正,谢谢您的指教 ...
在测试一个网页时,时常会有需要等待的时候,可能是等待网页载入、等待 UI 显示或等待搜寻结果等 pa...
HTTP 与Web 请求 HTTP,超文本传输协定(HyperText Transfer Proto...