查詢訊號到達字串中所有位置所需的時間 - 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
嘗試使用不同的情況執行程式並檢查它。
結論
如果您在本教程中有任何疑問,請在評論部分提出。
廣告