解决我的代码中未通过测试用例的错误

Question

Leetcode上存在这个问题，问题的链接是：https://leetcode.com/problems/largest-time-for-given-digits/

我已经为这个问题编写了代码，据我说我的代码是正确的，但我的代码仍然没有通过所有测试用例，我被困在调试中的问题在哪里。

任何人都可以帮我吗？

class Solution {
public:

bool isValid(string s){
if(s[0] > '2') return false;
if(s[0] == '2'){
if(s[1] >= '4'){
return false ;
}
}

if(s[2] >=6) return false ;

return true ; 

}
vector<vector<int>> permute(vector<int> &nums)
{
vector<vector<int>> result;
//Base Case For The Problem:
if (nums.size() <= 1)
return {nums};
for (int i = 0; i < nums.size(); i++)
{
vector<int> v(nums.begin(), nums.end());
v.erase(v.begin() + i);
auto res = permute(v);
for (int j = 0; j < res.size(); j++)
{
vector<int> _v = res[j];
_v.insert(_v.begin(), nums[i]);
result.push_back(_v);
}
}
return result;


}


string largestTimeFromDigits(vector<int>& A) {
vector<vector<int>> res ;
vector<string> valid ; //For Only Storing the Valid Time Permutations

res = permute(A); 

//Now , Iterating Over All the Permutations:
for(int i=0 ; i<res.size() ; i++){
string curr = "";
for(int j=0 ; j<res[i].size() ; ++j){
curr += res[i][j];
}
if(isValid(curr)) valid.push_back(curr);

}
sort(valid.begin() , valid.end()); 

string ans = ""; //The Final Answer that we have to return at the end.

if(valid.size() > 0){
//Now , perform the Required Operations:
string temp = valid[valid.size() - 1];
ans = temp.substr(0,2) + ":" + temp.substr(2);
}

return ans; 



}
};

Answer 1

代码中的两个问题，都与int与char混合有关。第一个在这里：

if(s[2] >=6 ) {
return false ;
} 

由于这种情况，您的isValid总是false返回。范围内没有字符'0'...'9'小于整数6。将char与char进行比较：

if(s[2] >='6' ) {
return false ;
} 

接下来，这里

curr += res[i][j]; 

res[i][j]是一个整数，但您希望在字符串中添加一个字符：

curr += static_cast<char>(res[i][j]) + '0';

修复这两个后，我至少在输入{2,2,2,2}中获得了预期的输出，请参阅此处：https://godbolt.org/z/35r3f9。

我必须提到，如果您使用调试器，您会自己发现这些问题。在编码方面变得更好并不是为了减少错误，而是为了更好地发现和修复它们。调试器是执行此操作的重要工具。

Answer 2

C++

您可以先使用std::prev_permutation和排序：

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <string>
#include <vector>
#include <algorithm>
static const struct Solution {
static const std::string largestTimeFromDigits(std::vector<int>& A) {
std::sort(std::begin(A), std::end(A), std::greater<int>());
do if (
(A[0] < 2 || A[0] == 2 && A[1] < 4) &&
A[2] < 6
) {
return std::to_string(A[0]) + std::to_string(A[1]) + ":" + std::to_string(A[2]) + std::to_string(A[3]);
}
while (std::prev_permutation(std::begin(A), std::end(A)));
return "";
}
};

以下是 LeetCode 在 C++ 年的官方解决方案：

class Solution {
public:
string largestTimeFromDigits(vector<int>& A) {
int max_time = -1;
// prepare for the generation of permutations next.
std::sort(A.begin(), A.end());
do {
int hour = A[0] * 10 + A[1];
int minute = A[2] * 10 + A[3];
if (hour < 24 && minute < 60) {
int new_time = hour * 60 + minute;
max_time = new_time > max_time ? new_time : max_time;
}
} while(next_permutation(A.begin(), A.end()));
if (max_time == -1) {
return "";
} else {
std::ostringstream strstream;
strstream << std::setw(2) << std::setfill('0') << max_time / 60
<< ":" << std::setw(2) << std::setfill('0') << max_time % 60;
return strstream.str();
}
}
};

使用正则表达式的替代解决方案：

不过，这在C++中会很困难：

class Solution:
def largestTimeFromDigits(self, A: List[int]) -> str:
for i in range(2359, -1, -1):
if i < 1000:
i = format(i, '04')
if int(re.findall(r'd{2}$', str(i))[0]) > 59:
continue
l = list(map(int, str(i)))
for j in A:
if j in l:
l.remove(j)
if len(l) == 0:
hm = re.findall(r'.{2}', str(i))
return f'{hm[0]}:{hm[1]}'
return ""

在 Java 中使用三个循环的替代解决方案：

public final class Solution {
public static final String largestTimeFromDigits(
final int[] A
) {
String res = "";
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
for (int k = 0; k < 4; ++k) {
if (i == j || i == k || j == k) {
continue;
}
String hour = "" + A[i] + A[j];
String minute = "" + A[k] + A[6 - i - j - k];
String time = hour + ":" + minute;
if (
hour.compareTo("24") < 0 &&
minute.compareTo("60") < 0 &&
res.compareTo(time) < 0
) {
res = time;
}
}
}
}
return res;
}
}

<小时 />

参考资料

• 有关其他详细信息，请参阅讨论区，您可以在其中找到大量解释清楚的已接受解决方案，包括低复杂度算法和渐近运行时/内存分析^1、2。