题目:
题解:
思路:类比接雨水,两次遍历求解最佳答案。
代码如下:
class Solution {
public:
// 思路:类比接雨水,两次遍历求距离的最小值
vector<int> shortestToChar(string s, char c) {
int n=s.size();
vector<int> res(n,0);
// 正向遍历:s[i]左边最近的c字符到位置i之间的距离,idx记录s[i]左边字符c出现的上一个位置
for(int i=0,idx=-n;i<n;++i){
if(s[i]==c){
idx=i;
}
res[i]=i-idx;
}
// 反向遍历:s[i]右边最近的c字符到位置i之间的距离,idx记录s[i]右边字符c出现的上一个位置
for(int i=n-1,idx=2*n;i>=0;--i){
if(s[i]==c){
idx=i;
}
res[i]=min(res[i],idx-i);
}
return res;
}
};
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)