我最近参加了一次编码测试以在工作中升职。这是我真正挣扎的任务之一，并且想知道什么是最好的方法来做到这一点。我使用了大量 if 和 if else，不是最干净的解决方案，但完成了工作。
我被问到的问题是：
将 4 个数字格式化为 24 小时制 (00:00)，找到可能的最大（最新）时间，考虑到最大小时数为 23，最大分钟数为 59。如果不可能，则返回 NOT POSSIBLE。
例如：
6, 5, 2, 0 将是 20:56
3, 9, 5, 0 将是 09:53
7, 6, 3, 8 是不可能的
必须返回时间或字符串的示例函数如下所示，A、B、C、D 是与上面以逗号分隔的列表不同的数字：
function generate(A, B, C, D) {
// Your code here
}
人们将如何解决这个问题？
这是我想出的非蛮力解决方案。查看代码中的注释以了解它是如何工作的。如果有任何不清楚的，我可以帮助澄清。
function generate(A, B, C, D) {
vals = [A, B, C, D];
counts = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
for (i = 0; i < vals.length; i++) {
for (j = vals[i]; j < counts.length; j++) counts[j]++;
}
// counts is now populated with the number of values less than or equal to the index it belongs to
// so counts[2] is the total number of 0's, 1's and 2's
if (counts[2] === 0) return 'NOT POSSIBLE';
// if there are no 0's and 1's, then it must start with 2
mustStartWith2 = counts[1] === 0;
if (mustStartWith2 && counts[3] === 1) return 'NOT POSSIBLE';
// We want a count of the number of free digits that are 5 or less (for the minute digit)
numbersAvailableForMinute = counts[5] - (mustStartWith2 ? 2 : 1);
if (numbersAvailableForMinute === 0) return 'NOT POSSIBLE';
// we now know that it is a valid time
time = [0, 0, 0, 0];
// we also know if it starts with 2
startsWith2 = mustStartWith2 || (numbersAvailableForMinute >= 2 && counts[2] > counts[1]);
// knowing the starting digit, we know the maximum value for each digit
maxs = startsWith2 ? [2, 3, 5, 9] : [1, 9, 5, 9];
for (i = 0; i < maxs.length; i++) {
// find the first occurrence in counts that has the same count as the maximum
time[i] = counts.indexOf(counts[maxs[i]]);
// update counts after the value was removed
for (j = time[i]; j < counts.length; j++) counts[j]--;
}
// create the time
return time[0]+""+time[1]+":"+time[2]+""+time[3];
}
添加了可执行代码片段和一些测试用例
function generate(A, B, C, D) {
var combinations = []
arguments = Array.from(arguments)
for (var i = 0; i < 4; i++) {
for (var j = 0; j < 4; j++) {
if (i !== j) {
var num = +(arguments[i] + '' + arguments[j])
if (num <= 59 && combinations.indexOf(num) === -1)
combinations.push(num)
}
}
}
combinations.sort((a, b) => a - b);
var hours = combinations.filter(hour => hour <= 23);
for (var i = hours.length - 1; i >= 0; i--) {
for (var j = combinations.length - 1; j >= 0; j--) {
if (computeMax(hours[i], combinations[j], arguments))
return hours[i] + ':' + combinations[j]
}
}
return 'not possible'
}
function computeMax(maxHour, maxMinute, args) {
var minute = String(maxMinute)
var hour = String(maxHour)
for (var k = 0; k < minute.length; k++)
if (hour.indexOf(minute[k]) > -1 && args.indexOf(+minute[k]) === args.lastIndexOf(+minute[k]))
return false
return true
}
console.log('generate(1,7,2,7)', generate(1,7,2,7))
console.log('generate(6,5,2,0)', generate(6,5,2,0))
console.log('generate(3,9,5,0)', generate(3,9,5,0))
console.log('generate(7,6,3,8)', generate(7,6,3,8))
console.log('generate(0,1,2,3)', generate(0,1,2,3))
console.log('generate(1,1,1,2)', generate(1,1,1,2))
console.log('generate(1,1,1,1)', generate(1,1,1,1))
console.log('generate(5,6,7,8)', generate(5,6,7,8))
console.log('generate(2,9,3,1)', generate(2,9,3,1))一旦我了解到您可以将问题视为“生成一个小于 24 的数字和一个小于 60 的数字”而不是尝试使用单个数字这一事实，推理这个问题就变得容易多了。
这将遍历集合中的数字对，找到可以从那对数字中组成的最大有效小时，然后找到可以从剩余数字中组成的最大有效分钟。
var generate = function(a, b, c, d) {
var biggest = function(a, b, max) {
// returns largest of 'ab' or 'ba' which is below max, or false.
// I'm sure there's a more concise way to do this, but:
var x = '' + a + b;
var y = '' + b + a;
if (max > x && max > y) {
var tmp = Math.max(x,y);
return (tmp < 10) ? "0"+tmp : tmp;
}
if (max > x) return x;
if (max > y) return y;
return false;
}
var output = false;
var input = [].slice.call(arguments);
for (var i = 0; i < arguments.length; i++) {
for (var j = i + 1; j < arguments.length; j++) {
// for every pair of numbers in the input:
var hour = biggest(input[i], input[j], 24); // What's the biggest valid hour we can make of that pair?
if (hour) {
// do the leftovers make a valid minute?
var tmp = input.slice(); // copy the input
tmp.splice(j, 1);
tmp.splice(i, 1);
var minute = biggest(tmp[0], tmp[1], 60);
if (hour && minute) {
// keep this one if it's bigger than what we had before:
var nval = hour + ':' + minute;
if (!output || nval > output) output = nval;
}
}
}
}
return output || 'NOT POSSIBLE';
}
/* --------------- Start correctness test --------------------- */
var tests = ['0000', '1212', '1234', '2359', '2360','2362','2366', '1415', '1112', '1277', '9999', '0101'];
console.log('---');
for (var i = 0; i < tests.length; i++) {
console.log(
tests[i],
generate.apply(this, tests[i].split(''))
)
}
/* --------------- Start Speed Test --------------------- */
let startTime = Math.floor(Date.now());
let times = 10000; //how many generate call you want?
let timesHolder = times;
while (times--) {
let A = randNum();
let B = randNum();
let C = randNum();
let D = randNum();
generate(A, B, C, D);
if (times == 0) {
let totalTime = Math.floor(Date.now()) - startTime;
let msg = timesHolder + ' Call Finished Within -> ' + totalTime + ' ms <-';
console.log(msg);
// alert(msg);
}
}
function randNum() {
return Math.floor(Math.random() * (9 - 0 + 1)) + 0;
}
/* --------------- END Speed Test --------------------- */一种使用预计算字符串的方法，包含所有可能的排列。
function generate(A,B,C,D){
var isValidTime = /^(?:[01]\d|2[0-3]):(?:[0-5]\d)$/;
var pattern = "0123012 0132013 0213021 0231023 0312031 0321032".replace(/\d/g, i => arguments[+i]);
var max = "";
for(var i=pattern.length-4; i--; ){
var time = pattern.substr(i,2) + ":" + pattern.substr(i+2,2);
if(time > max && isValidTime.test(time))
max = time;
}
return max || "NOT POSSIBLE";
}
[
[6,5,0,2],
[3,9,5,0],
[7,6,3,8]
].forEach(arr => console.log(arr + ' -> ' + generate(...arr)));.as-console-wrapper{top:0;max-height:100%!important}但我们可以改进这一点，通过使用正则表达式只查找有效时间：
function generate(A,B,C,D){
var pattern = "0123012 0132013 0213021 0231023 0312031 0321032".replace(/\d/g, i => arguments[+i]);
console.log(pattern);
var matchValidTime = /([01]\d|2[0-3])([0-5]\d)/g, m, max = "";
while(m = matchValidTime.exec(pattern)){
var time = m[1] + ":" + m[2];
if(time > max) max = time;
console.log("index: %o time: %o max: %o", m.index, time, max);
matchValidTime.lastIndex = m.index+1; //to find intersecting matches
}
return max || "NOT POSSIBLE";
}
[
[1,2,3,4],
//[6,5,0,2],
//[3,9,5,0],
//[7,6,3,8]
].forEach(arr => console.log(arr + ' -> ' + generate(...arr)));.as-console-wrapper{top:0;max-height:100%!important}首先allCom将返回 4 个数字的所有组合（共 24 个组合）
然后对于 24 个数组（组合）调用.forEach检查每个数组是否是有效的时间格式。如果它是有效的时间格式，则计算时间值
如果时间是 AB:CD 那么值：
A = A * 10 小时 = A * 10 * 3600s = A * 36000s
B = B * 1 小时 = B * 3600s
C = C * 10s
D = D
总值 = A*36000 + B*3600 + C*10 + D
现在你得到了当前数组的值，与保存的 Max 进行比较，如果这个值更大，则替换 max。
在循环结束时确定是否找到最大值或它无效。
generate(6, 5, 2, 0);
generate(3, 9, 5, 0);
generate(7, 6, 3, 8);
generate(1, 7, 2, 7);
generate(1, 1, 1, 2);
// return all combination of 4 number (24 combination total)
function allCom(inputArray) {
var result = inputArray.reduce(function permute(res, item, key, arr) {
return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key + 1)).reduce(permute, []).map(function(perm) {
return [item].concat(perm);
}) || item);
}, []);
return result;
}
// core function to determine the max comb
function generate(A, B, C, D) {
let input = [A, B, C, D];
let allComb = allCom(input);
let max = '';
let maxA = [];
allComb.forEach(function(comb, index, arr) {
if (validCom(comb)) {
let temp = calValue(comb);
maxA = temp > max ? comb : maxA;
max = temp > max ? temp : max;
}
if (index == allComb.length - 1) {
if (max) {
return console.log('For ' + JSON.stringify(input) + ' found max comb: ' + maxA[0] + maxA[1] + ':' + maxA[2] + maxA[3]);
}
return console.log('Sorry ' + JSON.stringify(input) + ' is not valid');
}
});
}
// check if this array is valid time format, ex [1,2,9,0] false, [2,2,5,5] true
function validCom(ar) {
if (ar[0] <= 2 && ((ar[0] == 2 && ar[1] < 4) || (ar[0] != 2 && ar[1] <= 9)) && ar[2] <= 5 && ar[3] <= 9) {
return true;
}
return false;
}
// calculate the total value of this comb array
function calValue(ar) {
return +ar[0] * 36000 + +ar[1] * 3600 + +ar[2] * 10 + +ar[0];
}
$('button').on('click', function(e) {
let inp = $('select');
generate(inp[0].value, inp[1].value, inp[2].value, inp[3].value);
});
var s = $('<select />');
for(i=0;i<10;i++) {
$('<option />', {value: i, text: i}).appendTo(s);
}
s.clone().appendTo('#myform');
s.clone().appendTo('#myform');
s.clone().appendTo('#myform');
s.clone().appendTo('#myform');<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<form id="myform">
</form>
<br>
<button type="button">Submit</button>/* --------------- Start Speed Test --------------------- */
let startTime = Math.floor(Date.now());
let times = 10000; //how many generate call you want?
let timesHolder = times;
while (times--) {
let A = randNum();
let B = randNum();
let C = randNum();
let D = randNum();
generate(A, B, C, D);
if (times == 0) {
let totalTime = Math.floor(Date.now()) - startTime;
let msg = timesHolder + ' Call Finished Within -> ' + totalTime + ' ms <-';
console.log(msg);
alert(msg);
}
}
function randNum() {
return Math.floor(Math.random() * (9 - 0 + 1)) + 0;
}
/* --------------- END Speed Test --------------------- */
/* --------------- Start Speed Test --------------------- */
let startTime = Math.floor(Date.now());
let times = 10000; //how many generate call you want?
let timesHolder = times;
while (times--) {
let A = randNum();
let B = randNum();
let C = randNum();
let D = randNum();
generate(A, B, C, D);
if (times == 0) {
let totalTime = Math.floor(Date.now()) - startTime;
let msg = timesHolder + ' Call Finished Within -> ' + totalTime + ' ms <-';
console.log(msg);
alert(msg);
}
}
function randNum() {
return Math.floor(Math.random() * (9 - 0 + 1)) + 0;
}
/* --------------- END Speed Test --------------------- */
// return all combination of 4 number (24 combination total)
function allCom(inputArray) {
var result = inputArray.reduce(function permute(res, item, key, arr) {
return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key + 1)).reduce(permute, []).map(function(perm) {
return [item].concat(perm);
}) || item);
}, []);
return result;
}
// core function to determine the max comb
function generate(A, B, C, D) {
let input = [A, B, C, D];
let allComb = allCom(input);
let max = '';
let maxA = [];
allComb.forEach(function(comb, index, arr) {
if (validCom(comb)) {
let temp = calValue(comb);
maxA = temp > max ? comb : maxA;
max = temp > max ? temp : max;
}
if (index == allComb.length - 1) {
if (max) {
return 'For ' + JSON.stringify(input) + ' found max comb: ' + maxA[0] + maxA[1] + ':' + maxA[2] + maxA[3];
}
return 'Sorry ' + JSON.stringify(input) + ' is not valid';
}
});
}
// check if this array is valid time format, ex [1,2,9,0] false, [2,2,5,5] true
function validCom(ar) {
if (ar[0] <= 2 && ((ar[0] == 2 && ar[1] < 4) || (ar[0] != 2 && ar[1] <= 9)) && ar[2] <= 5 && ar[3] <= 9) {
return true;
}
return false;
}
// calculate the total value of this comb array
function calValue(ar) {
return +ar[0] * 36000 + +ar[1] * 3600 + +ar[2] * 10 + +ar[0];
}