資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中給定數字的最大時間
假設我們有一個包含 4 個數字的陣列，我們需要找到可以組成的最大的 24 小時制時間。我們知道最小的 24 小時制時間是 00:00，最大的時間是 23:59。從 00:00 開始，如果自午夜以來經過的時間更多，則時間更大。我們需要將答案作為長度為 5 的字串返回。如果沒有有效的時間需要返回，則返回空字串。
因此，如果輸入類似於 [1,2,3,4]，則輸出將為“23:41”
要解決此問題，我們將遵循以下步驟：
- 定義一個函式 isValid()，它將接收字串 a，
- 如果 a[0] > '2'，則：
- 返回 false
- 如果 a[0] 等於 '2' 且 a[1] > '3'，則：
- 返回 false
- 如果 a[3] > '5'，則：
- 返回 false
- 返回 true
- 定義一個函式 dfs()，它將接收一個數組 A、res、cur，
- 如果 cur 的大小等於 5，則：
- 如果 isValid(cur) 且 cur > res，則：
- res := cur
- 返回
- 如果 isValid(cur) 且 cur > res，則：
- 初始化 i := 0，當 i < 4 時，更新（將 i 增加 1），執行：
- 如果 A[i] 不等於 -1，則：
- tmp := A[i]
- cur := cur + A[i] + '0' 的 ASCII 碼
- 如果 cur 的大小等於 2，則：
- cur := cur 連線 ':'
- A[i] := -1
- dfs(A, res, cur)
- A[i] := tmp
- 從 cur 中刪除最後一個元素
- 如果 cur 的大小等於 2，則：
- 從 cur 中刪除最後一個元素
- 如果 A[i] 不等於 -1，則：
- 從主方法執行以下操作：
- res := 空字串，tmp := 空字串
- dfs(A, res, tmp)
- 返回 res
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void dfs(vector<int>& A, string& res, string& cur) {
if (cur.size() == 5) {
if (isValid(cur) && cur > res)
res = cur;
return;
}
for (int i = 0; i < 4; ++i) {
if (A[i] != -1) {
int tmp = A[i];
cur += A[i] + '0';
if (cur.size() == 2)
cur += ':';
A[i] = -1;
dfs(A, res, cur);
A[i] = tmp;
cur.pop_back();
if (cur.size() == 2)
cur.pop_back();
}
}
}
bool isValid(const string a) {
if (a[0] > '2')
return false;
if (a[0] == '2' && a[1] > '3')
return false;
if (a[3] > '5')
return false;
return true;
}
string largestTimeFromDigits(vector<int>& A) {
string res = "", tmp = "";
dfs(A, res, tmp);
return res;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,4};
cout << (ob.largestTimeFromDigits(v));
}輸入
{1,2,3,4}輸出
23:41
更新於： 2020-07-06
137 次檢視
廣告