数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
广告