LC821.字符的最短距离

原题链接
image.png

思路1：两次遍历

  • 这是非常自然的思路
  • 从左往右扫描，记录每一个数字到左侧最近目标数字的距离。

  • 从右往左扫描，记录每一个数字到右侧最近目标数字的距离，同时和左边最近距离比较，取近的。

    代码1：

    1. class Solution {
    2. public:
    3.   vector<int> shortestToChar(string s, char c) {
    4.       int ns = s.size();
    5.       vector<int> ans(ns, 0);
    6.       for (int i = 0; i < ns; ) {
    7.           int cnt = 0;
    8.           if (s[i] == c) {
    9.               i += 1;
    10.               while (i < ns && s[i] != c) {
    11.                   cnt += 1;
    12.                   ans[i] = cnt;
    13.                   i += 1;
    14.               }
    15.           } else {
    16.               i += 1;
    17.           }
    18.       }
    20.       for (int i = ns - 1; i >= 0; ) {
    21.           int cnt = 0;
    22.           if (s[i] == c) {
    23.               i -= 1;
    24.               while (i >= 0 && s[i] != c) {
    25.                   cnt += 1;
    26.                   if (ans[i] == 0) {
    27.                       ans[i] = cnt;
    28.                   } else {
    29.                       ans[i] = min(ans[i], cnt);
    30.                   }
    31.                   i -= 1;
    32.               }
    33.           } else {
    34.               i -= 1;
    35.           }
    36.       }
    38.       return ans;
    39.   }
    40. };

    思路2：BFS

  • vector<int> ans记录各个位置到目标位置的最近距离

  • 所有目标字母的位置，全部进入队列（多个root）
  • BFS遍历，将当前节点所记录位置cur_pos的左右两个位置next_pos分别进行检验，符合条件就入队。
  • 在入队的时候修改ans[next_pos]，ans[next_pos] = ans[cur_pos] + 1

  • 如何避免重复？可以提前把ans中所有位置全部置-1，然后在入队的时候，需满足两个条件

    • next_pos不能越界

    • ans[next_pos] == -1

      代码2：

      class Solution {
public:
vector<int> shortestToChar(string s, char c) {
   queue<int> q;
   int ns = s.size();
   vector<int> ans(ns, -1);

   // push root
   for (int i = 0; i < ns; i++) {
       if (s[i] == c) {
           q.push(i);
           ans[i] = 0;
       }
   }

   // bfs
   while (!q.empty()) {
       int cur_pos = q.front();
       q.pop();

       for (int i = 0; i < 2; i++) {
           int next_pos = 0;
           if (i == 0) {
               next_pos = cur_pos + 1;
           } else {
               next_pos = cur_pos - 1;
           }

           if (0 <= next_pos && next_pos < ns && ans[next_pos] == -1) {
               ans[next_pos] = ans[cur_pos] + 1;
               q.push(next_pos);
           }
       }
   }

   return ans;
}
};class Solution {
public:
vector<int> shortestToChar(string s, char c) {
   queue<int> q;
   int ns = s.size();
   vector<int> ans(ns, -1);

   // push root
   for (int i = 0; i < ns; i++) {
       if (s[i] == c) {
           q.push(i);
           ans[i] = 0;
       }
   }

   // bfs
   while (!q.empty()) {
       int cur_pos = q.front();
       q.pop();

       for (int i = 0; i < 2; i++) {
           int next_pos = 0;
           if (i == 0) {
               next_pos = cur_pos + 1;
           } else {
               next_pos = cur_pos - 1;
           }

           if (0 <= next_pos && next_pos < ns && ans[next_pos] == -1) {
               ans[next_pos] = ans[cur_pos] + 1;
               q.push(next_pos);
           }
       }
   }

   return ans;
}
};