查詢訊號到達字串中所有位置所需的時間 - C++


在本教程中,我們將編寫一個程式來計算訊號到達字串中所有位置所需的時間。讓我用一個例子來解釋。

我們將有一個字串,其中只包含**s**和**p**字元。**s**代表**訊號**,**p**代表字串中的**位置**。訊號從**s**開始,向左和向右兩個方向傳播。我們假設它需要一個單位時間來移動到字串中的下一個位置。我們的任務是計算將所有**位置**轉換為**訊號**所需的時間。

讓我們看一些例子。

**輸入** − pppppspss

**輸出** − 5

**輸入** − pspspsps

**輸出** − 1

**輸入** − ssssss

**輸出** − 0

讓我們看看解決這個問題的步驟。

  • 初始化一個字串和時間 (0)

  • 迭代字串。

    • 計算連續的**p**字元,並將計數儲存在一個變數中。

    • 如果當前字元是**s**並且**p**計數大於之前的時間,則檢查左側是否存在**s**。

    • 如果兩側都存在**s**,則將計數分成兩半,因為**s**可以向兩個方向傳播。

    • 重置**p**的計數。

示例

讓我們看看程式碼。

 線上演示

#include <bits/stdc++.h>
using namespace std;
int timeToConvertToSignalString(string sample_string, int string_len) {
   int p_count = 0, time = 0;
   for (int i = 0; i <= string_len; i++) {
      if (sample_string[i] == 'p') {
         p_count++;
      }
      else {
         if (p_count > time) {
            bool is_present_left_side = false;
            if (((i - p_count) > 0) && (sample_string[i - p_count - 1] == 's')) {
               is_present_left_side = 1;
            }
            if (is_present_left_side) {
               p_count = ceil((double)p_count / 2);
            }
            time = max(time, p_count);
         }
         p_count = 0;
      }
   }
   return time;
}
int main() {
   string sample_string = "pppppspss";
   int n = sample_string.size();
   cout << timeToConvertToSignalString(sample_string, n) << endl;
   return 0;
}

輸出

如果您執行上述程式,您將得到以下結果。

5

嘗試使用不同的情況執行程式並檢查它。

結論

如果您在本教程中有任何疑問,請在評論部分提出。

更新於:2020-12-29

94 次檢視

開啟你的職業生涯

透過完成課程獲得認證

開始
廣告