问题：
二进制手表Leetcode
周辰沛
我正在尝试使用回溯来解决LeetCode中的二进制手表问题。
我的代码在下面（不起作用）
public static void binaryWatchHelper(List<Integer>hours, List<Integer> mins,
int num , List<String> possibleTimes,int hoursSum,int minsSum) {
//System.out.println( num + " - " + hours + " - " + mins );
if(num==0) {
String m = minsSum <10?("0"+minsSum):""+minsSum;
possibleTimes.add(hoursSum +":"+m);
}
else {
for(int i=0;i<(hours.size()+mins.size());i++) {
if(i<hours.size()) {
int hr =hours.remove(i);
hoursSum+=hr;
if(hoursSum<=11)
binaryWatchHelper(hours, mins, num-1, possibleTimes, hoursSum, minsSum);
hours.add(i,hr);
hoursSum-=hr;
} else {
int mi =mins.remove(i-hours.size());
minsSum+=mi;
if(minsSum<=59)
binaryWatchHelper(hours, mins, num-1, possibleTimes, hoursSum, minsSum);
mins.add(i-hours.size(),mi);
minsSum-=mi;
}
}
}
}
我在leetcode讨论页面中找到了下面的代码（C），它运行良好。
void helper(vector<string>& res, pair<int, int> time, int num, int start_point) {
if (num == 0) {
res.push_back(to_string(time.first) + (time.second < 10 ? ":0" : ":") + to_string(time.second));
return;
}
for (int i = start_point; i < hour.size() + minute.size(); i ++)
if (i < hour.size()) {
time.first += hour[i];
if (time.first < 12) helper(res, time, num - 1, i + 1); // "hour" should be less than 12.
time.first -= hour[i];
} else {
time.second += minute[i - hour.size()];
if (time.second < 60) helper(res, time, num - 1, i + 1); // "minute" should be less than 60.
time.second -= minute[i - hour.size()];
}
}
上面的c algo和我写过的很像。但是我的代码不起作用。有人能解释一下我错过了什么吗？
我没有传递start Index，而是删除了该元素。但是为什么我的代码不起作用呢？
我尝试打印调用的堆栈跟踪，当然两者都非常不同。任何人都可以指出我错过了什么吗？
我得到了不正确的输出。
我的代码n=2的输出
[3:00, 5:00, 9:00, 1:01, 1:02, 1:04, 1:08, 1:16, 1:32, 3:00, 6:00, 10:00, 2:01, 2:02, 2:04, 2:08, 2:16, 2:32, 5:00, 6:00, 4:01, 4:02, 4:04, 4:08, 4:16, 4:32, 9:00, 10:00, 8:01, 8:02, 8:04, 8:08, 8:16, 8:32, 1:01, 2:01, 4:01, 8:01, 0:03, 0:05, 0:09, 0:17, 0:33, 1:02, 2:02, 4:02, 8:02, 0:03, 0:06, 0:10, 0:18, 0:34, 1:04, 2:04, 4:04, 8:04, 0:05, 0:06, 0:12, 0:20, 0:36, 1:08, 2:08, 4:08, 8:08, 0:09, 0:10, 0:12, 0:24, 0:40, 1:16, 2:16, 4:16, 8:16, 0:17, 0:18, 0:20, 0:24, 0:48, 1:32, 2:32, 4:32, 8:32, 0:33, 0:34, 0:36, 0:40, 0:48]
C代码输出：
[3:00, 5:00, 9:00, 1:01, 1:02, 1:04, 1:08, 1:16, 1:32, 6:00, 10:00, 2:01, 2:02, 2:04, 2:08, 2:16, 2:32, 4:01, 4:02, 4:04, 4:08, 4:16, 4:32, 8:01, 8:02, 8:04, 8:08, 8:16, 8:32, 0:03, 0:05, 0:09, 0:17, 0:33, 0:06, 0:10, 0:18, 0:34, 0:12, 0:20, 0:36, 0:24, 0:40, 0:48]
num=2的我的呼叫跟踪
2 - [1, 2, 4, 8] - [1, 2, 4, 8, 16, 32]
1 - [2, 4, 8] - [1, 2, 4, 8, 16, 32]
0 - [4, 8] - [1, 2, 4, 8, 16, 32]
0 - [2, 8] - [1, 2, 4, 8, 16, 32]
0 - [2, 4] - [1, 2, 4, 8, 16, 32]
0 - [2, 4, 8] - [2, 4, 8, 16, 32]
0 - [2, 4, 8] - [1, 4, 8, 16, 32]
0 - [2, 4, 8] - [1, 2, 8, 16, 32]
0 - [2, 4, 8] - [1, 2, 4, 16, 32]
0 - [2, 4, 8] - [1, 2, 4, 8, 32]
0 - [2, 4, 8] - [1, 2, 4, 8, 16]
1 - [1, 4, 8] - [1, 2, 4, 8, 16, 32]
0 - [4, 8] - [1, 2, 4, 8, 16, 32]
0 - [1, 8] - [1, 2, 4, 8, 16, 32]
0 - [1, 4] - [1, 2, 4, 8, 16, 32]
0 - [1, 4, 8] - [2, 4, 8, 16, 32]
0 - [1, 4, 8] - [1, 4, 8, 16, 32]
0 - [1, 4, 8] - [1, 2, 8, 16, 32]
0 - [1, 4, 8] - [1, 2, 4, 16, 32]
0 - [1, 4, 8] - [1, 2, 4, 8, 32]
0 - [1, 4, 8] - [1, 2, 4, 8, 16]
1 - [1, 2, 8] - [1, 2, 4, 8, 16, 32]
0 - [2, 8] - [1, 2, 4, 8, 16, 32]
0 - [1, 8] - [1, 2, 4, 8, 16, 32]
0 - [1, 2, 8] - [2, 4, 8, 16, 32]
0 - [1, 2, 8] - [1, 4, 8, 16, 32]
0 - [1, 2, 8] - [1, 2, 8, 16, 32]
0 - [1, 2, 8] - [1, 2, 4, 16, 32]
0 - [1, 2, 8] - [1, 2, 4, 8, 32]
0 - [1, 2, 8] - [1, 2, 4, 8, 16]
1 - [1, 2, 4] - [1, 2, 4, 8, 16, 32]
0 - [2, 4] - [1, 2, 4, 8, 16, 32]
0 - [1, 4] - [1, 2, 4, 8, 16, 32]
0 - [1, 2, 4] - [2, 4, 8, 16, 32]
0 - [1, 2, 4] - [1, 4, 8, 16, 32]
0 - [1, 2, 4] - [1, 2, 8, 16, 32]
0 - [1, 2, 4] - [1, 2, 4, 16, 32]
0 - [1, 2, 4] - [1, 2, 4, 8, 32]
0 - [1, 2, 4] - [1, 2, 4, 8, 16]
1 - [1, 2, 4, 8] - [2, 4, 8, 16, 32]
0 - [2, 4, 8] - [2, 4, 8, 16, 32]
0 - [1, 4, 8] - [2, 4, 8, 16, 32]
0 - [1, 2, 8] - [2, 4, 8, 16, 32]
0 - [1, 2, 4] - [2, 4, 8, 16, 32]
0 - [1, 2, 4, 8] - [4, 8, 16, 32]
0 - [1, 2, 4, 8] - [2, 8, 16, 32]
0 - [1, 2, 4, 8] - [2, 4, 16, 32]
0 - [1, 2, 4, 8] - [2, 4, 8, 32]
0 - [1, 2, 4, 8] - [2, 4, 8, 16]
1 - [1, 2, 4, 8] - [1, 4, 8, 16, 32]
0 - [2, 4, 8] - [1, 4, 8, 16, 32]
0 - [1, 4, 8] - [1, 4, 8, 16, 32]
0 - [1, 2, 8] - [1, 4, 8, 16, 32]
0 - [1, 2, 4] - [1, 4, 8, 16, 32]
0 - [1, 2, 4, 8] - [4, 8, 16, 32]
0 - [1, 2, 4, 8] - [1, 8, 16, 32]
0 - [1, 2, 4, 8] - [1, 4, 16, 32]
0 - [1, 2, 4, 8] - [1, 4, 8, 32]
0 - [1, 2, 4, 8] - [1, 4, 8, 16]
1 - [1, 2, 4, 8] - [1, 2, 8, 16, 32]
0 - [2, 4, 8] - [1, 2, 8, 16, 32]
0 - [1, 4, 8] - [1, 2, 8, 16, 32]
0 - [1, 2, 8] - [1, 2, 8, 16, 32]
0 - [1, 2, 4] - [1, 2, 8, 16, 32]
0 - [1, 2, 4, 8] - [2, 8, 16, 32]
0 - [1, 2, 4, 8] - [1, 8, 16, 32]
0 - [1, 2, 4, 8] - [1, 2, 16, 32]
0 - [1, 2, 4, 8] - [1, 2, 8, 32]
0 - [1, 2, 4, 8] - [1, 2, 8, 16]
1 - [1, 2, 4, 8] - [1, 2, 4, 16, 32]
0 - [2, 4, 8] - [1, 2, 4, 16, 32]
0 - [1, 4, 8] - [1, 2, 4, 16, 32]
0 - [1, 2, 8] - [1, 2, 4, 16, 32]
0 - [1, 2, 4] - [1, 2, 4, 16, 32]
0 - [1, 2, 4, 8] - [2, 4, 16, 32]
0 - [1, 2, 4, 8] - [1, 4, 16, 32]
0 - [1, 2, 4, 8] - [1, 2, 16, 32]
0 - [1, 2, 4, 8] - [1, 2, 4, 32]
0 - [1, 2, 4, 8] - [1, 2, 4, 16]
1 - [1, 2, 4, 8] - [1, 2, 4, 8, 32]
0 - [2, 4, 8] - [1, 2, 4, 8, 32]
0 - [1, 4, 8] - [1, 2, 4, 8, 32]
0 - [1, 2, 8] - [1, 2, 4, 8, 32]
0 - [1, 2, 4] - [1, 2, 4, 8, 32]
0 - [1, 2, 4, 8] - [2, 4, 8, 32]
0 - [1, 2, 4, 8] - [1, 4, 8, 32]
0 - [1, 2, 4, 8] - [1, 2, 8, 32]
0 - [1, 2, 4, 8] - [1, 2, 4, 32]
0 - [1, 2, 4, 8] - [1, 2, 4, 8]
1 - [1, 2, 4, 8] - [1, 2, 4, 8, 16]
0 - [2, 4, 8] - [1, 2, 4, 8, 16]
0 - [1, 4, 8] - [1, 2, 4, 8, 16]
0 - [1, 2, 8] - [1, 2, 4, 8, 16]
0 - [1, 2, 4] - [1, 2, 4, 8, 16]
0 - [1, 2, 4, 8] - [2, 4, 8, 16]
0 - [1, 2, 4, 8] - [1, 4, 8, 16]
0 - [1, 2, 4, 8] - [1, 2, 8, 16]
0 - [1, 2, 4, 8] - [1, 2, 4, 16]
0 - [1, 2, 4, 8] - [1, 2, 4, 8]
C代码调用跟踪：
2 - [1, 2, 4, 8] - [1, 2, 4, 8, 16, 32]
1 - [2, 4, 8] - [1, 2, 4, 8, 16, 32]
0 - [4, 8] - [1, 2, 4, 8, 16, 32]
0 - [8] - [1, 2, 4, 8, 16, 32]
0 - [] - [1, 2, 4, 8, 16, 32]
0 - [] - [2, 4, 8, 16, 32]
0 - [] - [4, 8, 16, 32]
0 - [] - [8, 16, 32]
0 - [] - [16, 32]
0 - [] - [32]
0 - [] - []
1 - [4, 8] - [1, 2, 4, 8, 16, 32]
0 - [8] - [1, 2, 4, 8, 16, 32]
0 - [] - [1, 2, 4, 8, 16, 32]
0 - [] - [2, 4, 8, 16, 32]
0 - [] - [4, 8, 16, 32]
0 - [] - [8, 16, 32]
0 - [] - [16, 32]
0 - [] - [32]
0 - [] - []
1 - [8] - [1, 2, 4, 8, 16, 32]
0 - [] - [2, 4, 8, 16, 32]
0 - [] - [4, 8, 16, 32]
0 - [] - [8, 16, 32]
0 - [] - [16, 32]
0 - [] - [32]
0 - [] - []
1 - [] - [1, 2, 4, 8, 16, 32]
0 - [] - [2, 4, 8, 16, 32]
0 - [] - [4, 8, 16, 32]
0 - [] - [8, 16, 32]
0 - [] - [16, 32]
0 - [] - [32]
0 - [] - []
1 - [] - [2, 4, 8, 16, 32]
0 - [] - [4, 8, 16, 32]
0 - [] - [8, 16, 32]
0 - [] - [16, 32]
0 - [] - [32]
0 - [] - []
1 - [] - [4, 8, 16, 32]
0 - [] - [8, 16, 32]
0 - [] - [16, 32]
0 - [] - [32]
0 - [] - []
1 - [] - [8, 16, 32]
0 - [] - [16, 32]
0 - [] - [32]
0 - [] - []
1 - [] - [16, 32]
0 - [] - [32]
0 - [] - []
1 - [] - [32]
0 - [] - []
1 - [] - []
谢谢
共有2个答案
巫马越彬
我同意上面的答案，我也用这种方式解决了这个问题。
我还有一个稍微不同的解决方案。你可以在这里找到它https://github.com/yan-khonski-it/leetcode/tree/master/src/main/java/com/yk/leetcode/binary_watch
这个想法是，您可以为每个小时数LED计算小时数组合。例如，0 个 led 表示 0 小时，1 个 led 表示 1、2、4、8 中的任何选项。更多详情 https://leetcode.com/problems/binary-watch/discuss/601642/C++-straight-solution-with-tables-of-hours-and-minutes
分钟也是如此。1 分钟表示 1、2、4、8、16、32 分钟之间的任何选项。
现在，您已经获得了手表上的led数量。nLeds = 小时Leds 分钟Leds。在这种情况下，您将拥有所有可能的小时组合和分钟组合，只需将它们加入即可。
现在，通过上面的链接，您可以找到具有定义值的表。您可以硬编码这些表，也可以自己构建它们。
// Hours combinations depending on leds number
private static final int[] hours0 = calculateLedsNumbers(0, 12);
private static final int[] hours1 = calculateLedsNumbers(1, 12);
private static final int[] hours2 = calculateLedsNumbers(2, 12);
private static final int[] hours3 = calculateLedsNumbers(3, 12);
private static final int[] hours4 = calculateLedsNumbers(4, 12);
// Minutes combinations depending on leds number
private static final int[] minutes0 = calculateLedsNumbers(0, 60);
private static final int[] minutes1 = calculateLedsNumbers(1, 60);
private static final int[] minutes2 = calculateLedsNumbers(2, 60);
private static final int[] minutes3 = calculateLedsNumbers(3, 60);
private static final int[] minutes4 = calculateLedsNumbers(4, 60);
private static final int[] minutes5 = calculateLedsNumbers(5, 60);
private static final int[] minutes6 = calculateLedsNumbers(6, 60);
然后你循环所有可能的小时和分钟组合，并将它们组合起来。
final List<String> result = new ArrayList<>(191);
for (int hoursLeds = 0; hoursLeds < 4; hoursLeds++) {
int[] possibleHours = getHoursFromLed(hoursLeds);
for (int minutesLeds = 0; minutesLeds < 6; minutesLeds++) {
if (hoursLeds + minutesLeds > nLeds) {
break;
}
if (hoursLeds + minutesLeds == nLeds) {
int [] possibleMinutes = getMinutesFromLed(minutesLeds);
combineHoursAndMinutes(possibleHours, possibleMinutes, result);
}
}
}
并结合
private static void combineHoursAndMinutes(int[] possibleHours, int[] possibleMinutes, List<String> result) {
for (int possibleHour : possibleHours) {
for (int possibleMinute : possibleMinutes) {
// Same as String.format("%d:%02d", possibleHour, possibleMinute), but faster.
result.add(hoursFormatted[possibleHour] + minutesFormatted[possibleMinute]);
}
}
}
凤安然
解决这个问题的回溯方法是多余的。您可以使用一些位操作技术来解决这个问题。
观察点
用于表示小时和表示分钟的设置位总数应等于传递的参数n。
然后你有 0 - 11 小时和 0 - 59 分钟。使用两个 for 循环，并且仅选择设置位之和等于 n 的小时 h 和分钟 m，则可以使解决方案更加优雅和快速。问题的目标也是测试您的位操作技能。
public List<String> readBinaryWatch(int n) {
List<String> ret = new ArrayList<>();
for(int h = 0; h < 12; h++) {
for(int m = 0; m < 60; m++) {
if(Integer.bitCount(h) + Integer.bitCount(m) == n) { // Checking whether the current h and m combination is a valid result.
//If the sum of their set bits is equal to n then the combination is a valid result and add that combination to result
ret.add(String.format("%d:%02d",h,m));
}
}
}
return ret;
}
类似资料：
-
本文向大家介绍Python中的十进制到二进制列表转换，包括了Python中的十进制到二进制列表转换的使用技巧和注意事项，需要的朋友参考一下 Python是一种通用语言，可以处理数据处理过程中提出的许多要求。当我们需要将十进制数转换为二进制数时，可以使用以下python程序。 使用格式 我们可以使用格式化程序中的字母来表示哪个数字基：十进制，十六进制，八进制或二进制，我们希望对数字进行格式化。在下面
-
我可以运行这个程序，但由于某些原因，它会显示/放置随机字符，而不是二进制的初始值，而且我似乎无法将程序从十进制运行回二进制。我该如何改进这些代码。要明确说明它不会将二进制转换为十进制，我将如何将其转换回十进制转换为二进制，如果有一些代码可以帮助我，将不胜感激。
-
我有一个严格按递减顺序排序的数组和一个元素；我想找到数组中最大元素的索引，该元素小于val（如果val已经存在，则为相等），并且我想在时间内完成此操作。和执行upper_bound()不是一个选项。 例如，如果数组为{10,5,3,1}而val为6，则函数应返回1。 我对迭代器是个新手，尝试过在upper_bound()中添加比较函数来使其工作，但失败了。我该怎么处理这件事。 注意：我检查了类似的
-
主要内容：二进制,八进制,十六进制我们平时使用的数字都是由 0~9 共十个数字组成的，例如 1、9、10、297、952 等，一个数字最多能表示九，如果要表示十、十一、二十九、一百等，就需要多个数字组合起来。 例如表示 5+8 的结果，一个数字不够，只能”进位“，用 13 来表示；这时”进一位“相当于十，”进两位“相当于二十。 因为逢十进一（满十进一），也因为只有 0~9 共十个数字，所以叫做 十进制（Decimalism）。十进
-
问题内容： 我正在使用python shell来解决print命令在python中的工作方式。 当我输入 打印01 1 打印010 8 打印0100 64 打印030 24 这里发生了什么？只是基数2？为什么第二个位置的“一个”打印为8？如果不是二进制，应该不是2吗？ 问题答案： 以0开头的数字在Python 2中将其标记为八进制。这被认为是令人困惑，令人惊讶且不一致的，因为以0x开头会将其标记为
-
本文向大家介绍python pip如何手动安装二进制包，包括了python pip如何手动安装二进制包的使用技巧和注意事项，需要的朋友参考一下 python中使用pip安装扩展包的时候，有时候会遇到如下类似报错： Running setup.py install for mysqlclient ... error ...(中间报错信息省略) building 'MySQLdb._mysql' ex