1. 題目

給定一個字符串 S 和一個字符 C。返回一個代表字符串 S 中每個字符到字符串 S 中的字符 C 的最短距離的數(shù)組。

示例 1:輸入: S = "loveleetcode", C = 'e' 輸出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shortest-distance-to-a-character
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 先掃描一遍，確定字符 C 的位置，存儲起來，再添加首位兩個"無窮遠"的虛擬位置
• 再掃一遍，對不為 C 的字符，計算其到前一個 C 和 后一個 C 的兩個距離的較小者存入答案
• 碰到 C 則，更新 前一個 C 和 后一個 C（left，right）
  
  

class Solution { public:vector<int> shortestToChar(string S, char C) {int i, j, left, right;vector<int> ans(S.size());vector<int> positionsC;for(i = 0; i < S.size(); ++i) {if(S[i] == C)positionsC.push_back(i);}positionsC.insert(positionsC.begin(),-20000);positionsC.push_back(300000);left = positionsC[0];right = positionsC[1];for(i = 0, j = 1; i < S.size(); ++i) {if(S[i] == C){ans[i] = 0;left = right;right = positionsC[++j];}else{ans[i] = min(i-left,right-i);}}return ans;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 821. 字符的最短距离的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。