广州seo服务公司,闸北网站优化公司,做旅游网站有前途吗,素材文章题目来源于leetcode#xff0c;解法学习了讨论去的解法。 问题#xff1a;有一种二进制LED表。上面的4个LED灯表示小时#xff0c;下面6个LED灯表示分钟。给定一个int值#xff0c;写出可能表示的时间。例如输入1#xff0c; Input: n 1 Return: [“1:00”, “2… 文章题目来源于leetcode解法学习了讨论去的解法。 问题有一种二进制LED表。上面的4个LED灯表示小时下面6个LED灯表示分钟。给定一个int值写出可能表示的时间。例如输入1 Input: n 1 Return: [“1:00”, “2:00”, “4:00”, “8:00”, “0:01”, “0:02”, “0:04”, “0:08”, “0:16”, “0:32”] 注意1输出结果的顺序无所谓2 小时不能有高位0例如”01:00”是错误的”1:00”是正确的3 分钟用两位数表示例如”1:1”是错误的”1:01”是正确的。 思路这是一道典型的深度优先搜索枚举各种情况就好了。枚举所有小时的可能性再枚举所有分钟的可能性。我确定我会做但是失败了。因为我同时在枚举小时和分钟。以前处理的都是单个的枚举。
// 每一步消耗一个数同时枚举小时和分钟结果错误有重复的情况。private void visit(int num, int countHour, int countMinute, int startHourIndex, int startMinuteIndex) {if (num 0) {if (countHour 12) {String str countHour : (countMinute 10 ? 0 countMinute : countMinute);if (!list.contains(str)) {list.add(str);}}} else {if (startMinuteIndex mininutes.length) {visit(num - 1, countHour, countMinute mininutes[startMinuteIndex], startHourIndex, startMinuteIndex 1);visit(num, countHour, countMinute, startHourIndex, startMinuteIndex 1);}if (startHourIndex hours.length) {visit(num - 1, countHour hours[startHourIndex], countMinute, startHourIndex 1, startMinuteIndex);visit(num, countHour, countMinute, startHourIndex 1, startMinuteIndex);}}}
收获 1 看了别人的解决方案后分别枚举小时、分钟最后再组合到一起。 2 还有一种方法更牛。提前把所有小时的可能组合、所有分钟可能的组合列出来。然后再把小时、分钟组合。参考链接。
private int[] hours new int[] { 1, 2, 4, 8 };private int[] mininutes new int[] { 1, 2, 4, 8, 16, 32 };private ListString list;public ListString readBinaryWatch(int num) {list new ArrayListString();for (int i 0; i num; i) {ListInteger hours visitHour(i);ListInteger minutes visitMinute(num - i);for (Integer h : hours) {if (h 12) {for (Integer m : minutes) {if (m 60) {list.add(h : (m 10 ? 0 m : m));}}}}}return list;}private ListInteger visitMinute(int num) {ListInteger list new ArrayListInteger();visit2(num,0,0,list,mininutes);return list;}private ListInteger visitHour(int num) {ListInteger list new ArrayListInteger();visit2(num,0,0,list,hours);return list;}private void visit(int num,int count, int startIndex, ListInteger list,int[] nums) {if(num0){list.add(count);return;}if(startIndexnums.length){return;}visit(num-1,countnums[startIndex],startIndex1,list,nums);visit(num,count,startIndex1,list,nums);}/*** visit的另外一种写法* param num* param count* param startIndex* param list* param nums*/private void visit2(int num,int count, int startIndex, ListInteger list,int[] nums) {if(num0){list.add(count);return;}for(int istartIndex;inums.length;i){visit2(num-1,countnums[i],i1,list,nums);}}
参考资料 1 [题目](https://leetcode.com/problems/binary-watch/#/description) 2 讨论1 3 讨论2
