資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學在給定的 HH:MM 格式時間內最大化缺失值
我們將得到一個長度為五的字串，它表示 HH:MM 格式的時間。字串中可能包含一些‘?’，我們必須用任何數字替換它們，使得結果是有效的時間，並且是可能的最大值。此外，給定的字串數字將是有效的，並且‘:’將出現在字串的精確位置。我們將使用兩種方法：第一種是暴力方法，另一種是有效的方法。
示例
輸入 1
Given string: 12:5? Output: 12:59
解釋
我們只有一個位置需要填充，我們可以獲得的最大時間是 12:59。
輸入 2
Given string: ?0:?9 Output: 20:59
解釋
這裡有兩個空位，首先，我們將關注小時部分，我們有三個選擇 0、1 和 2 來填充。對於分鐘部分，我們有 0 到 5 的選擇，為了最大化，我們可以填充 5。
方法
我們已經看到了示例，現在讓我們看看我們可以面臨的不同型別的案例：
字串有兩個部分：小時部分和分鐘部分。
小時部分的範圍是 0 到 23，分鐘部分的範圍是 0 到 59。
小時部分有以下幾種情況：
‘x?’，其中 x 可以是 0、1 和 2。對於 0，我們可以使用 0 作為最佳值；對於 1，我們可以選擇 9 作為最佳值；對於 2，我們可以使用 3 作為最佳值。
‘?x’，其中 x 的範圍是 0 到 9。如果 x 的範圍是 0 到 3，那麼我們可以用 2 替換它，否則 1 將是最佳值。
‘??’，因為我們必須最大化，所以我們將用 23 替換它。
分鐘部分有以下幾種情況：
‘x?’，其中 x 的範圍是 0 到 5。9 將是我們替換 ‘?’ 的最佳選擇。
‘?x’，其中 x 的範圍是 0 到 9。5 將是我們替換 ‘?’ 的最佳選擇。
‘??’，因為我們必須最大化，所以我們將用 59 替換它。
讓我們看看實現上述步驟的程式碼：
示例
#include <iostream>
using namespace std;
// function to replace hours
string replaceHours(string s){
if(s[0] == '?' && s[1] == '?'){
//Both hour characters are '?'
// replace with the maximum hour we can achieve
s[0] = '2';
s[1] = '3';
}
else if(s[0] == '?'){
// if the second number of hours is in the range 0 to 3
// replace by 2
if(s[1] < 4){
s[0] = '2';
}
else{
s[0] = '1'; // otherwise replace by one
}
}
else if(s[1] == '?'){
// if the first character is '2' we can go only upto 3
if(s[0] == '2'){
s[1] = '3';
}
else{
s[1] = '9'; // else we can go for 9
}
}
return s;
}
// function to replace minutes
string replaceMinutes(string s){
if(s[3] == '?' && s[4] == '?'){
// both minutes characters are '?'
// replace with maximum minutes we can acheive
s[3] = '5';
s[4] = '9';
}
else if(s[3] == '?'){
// we can maximum get 5 here
s[3] = '5';
}
else if(s[4] == '?'){
// we can get maximum 9 here
s[4] = '9';
}
return s;
}
int main(){
string str = "2?:3?"; // given string
// calling the function for updation of the minutes
str = replaceMinutes(str);
// calling to the function for updation of the hours
str = replaceHours(str);
// printing the final answer
cout<<"The maximum time we can get by replacing ? is: "<< str<<endl;
return 0;
}
輸出
The maximum time we can get by replacing ? is: 23:39
時間和空間複雜度
上述程式碼的時間複雜度是 O(1) 或常數，因為我們沒有使用任何迴圈或遞迴呼叫，只是檢查 if-else 條件。
上述程式碼的空間複雜度是 O(1)，因為我們沒有使用任何額外的空間。此外，對於函式，我們傳遞字串，但其大小始終為常數 5。
注意：為了使程式碼更美觀或更易讀，可以使用 switch 語句，它們不會影響時間或空間複雜度，並且會使程式碼更易於閱讀。
此外，回溯和重新檢查是一種解決方案，但這將檢查每種情況，並且在這裡實現效率不高。
結論
在本教程中，我們得到一個表示 24 小時制時間的字串。字串中有一些 ‘?’，我們必須用它們替換以獲得有效最大時間，並且保證字串中給定的字元始終導致有效時間。我們使用了 if-else 條件和兩個函式來用適當的情況替換 ‘?’。上述程式碼的時間和空間複雜度為常數，因為我們沒有使用任何迴圈或遞迴函式。
93 次瀏覽
