通过排列四个给定的数字来查找最大可能时间HH：MM

我最近在工作上进行了一次编码testing。 这是我真正努力的任务之一，并想知道什么是最好的方法来做到这一点。 我用了一些if和if，不是最干净的解决scheme，而是完成了工作。

我被问到的问题是：

将4位数字格式化为24小时制（24小时制），find可能的最大（最新）时间，考虑到最长时间为23分钟，最长分钟数为59分钟。如果不可能，则返回NOT POSSIBLE。

举个例子：

6,5,2,0将是20:56

3，9，5，0将是09:53

7，6，3，8将是不可能的

必须返回时间或string的示例函数看起来像这样，A，B，C，D是与上面逗号分隔列表不同的数字：

function generate(A, B, C, D) { // Your code here } 

人们将如何解决这个问题？

Answer 1

这是一个非暴力解决scheme，我想出了。 查看代码中的注释，了解它是如何工作的。 如果有任何不清楚，我可以帮忙澄清。

 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]; } 

Answer 2

增加了可执行代码片段和一些testing用例

 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)) 

Answer 3

一旦我提出这样一个事实，你可以把这个问题看作是“产生小于24的数字，小于60的数字”，而不是试图用个人数字处理，这样的推理就变得容易多了。

通过集合中的数字对，find可以从这两位数字中产生的最大有效小时数，然后find剩余的最大有效分钟数。

 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 --------------------- */ 

Answer 4

一种使用预先计算的string的方法，包含所有可能的排列。

 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} 

Answer 5

这个想法：

• 查找所有组合数组（共24个）
• 滤除所有无效组合（时间格式）
• find时间值
• 以最大时间值输出数组

解：

首先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进行比较，如果这个值更大，则将其replace成max。

在循环结束时确定是否find最大值或者无效。

 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> 

Answer 6

我会使用JavaScript的Date对象来判断一个特定的时间是否有效，通过parsingstring为ISOdate时间string（如1970-01-01T62:87 ），然后testing!isNaN( aDateInstance.getTime() )并比较具有较早保存的最大Date实例的Date实例（如果适用）：

 // permutator() borrowed from https://stackoverflow.com/a/20871714 function permutator( inputArr ) { var results = []; function permute( arr, memo ) { var cur, memo = memo || []; for( var i = 0; i < arr.length; i++ ) { cur = arr.splice( i, 1 ); if( arr.length === 0 ) { results.push( memo.concat( cur ) ); } permute( arr.slice(), memo.concat( cur ) ); arr.splice( i, 0, cur[ 0 ] ); } return results; } return permute( inputArr ); } function generate( A, B, C, D ) { var r = null; permutator( [ A, B, C, D ] ).forEach( function( p ) { var d = new Date( '1970-01-01T' + p[ 0 ] + '' + p[ 1 ] + ':' + p[ 2 ] + '' + p[ 3 ] ); if( !isNaN( d.getTime() ) && d > r ) { r = d; } } ); var h, m; return r ? ( ( h = r.getHours() ) < 10 ? '0' + h : h ) + ':' + ( ( m = r.getMinutes() ) < 10 ? '0' + m : m ) : 'NOT POSSIBLE'; } 

Answer 7

这是我想出来的。 非常优雅，我可以试着整理它，使它更有效率。 我有一个感觉，暴力方法将是最干净和最有效的方式来做到这一点。 这是一团糟。

 // w: highest value 2 or less // UNLESS: 1 of b, c, or d are less than 3 while the other two are greater than 7 // x: highest value // UNLESS: last was 2 then highest value less than 2 // y: highest value less than 5 // z: highest remaining value function findhighestwhere(array, condition) { let res = null let val = -1 let i = 0 for (let x of array) { if (x !== null && condition(x) && x > val) { res = i val = x } i++ } // console.log(`Test index: ${res} \n Test value: ${val}`) return res } function generate(a,b,c,d) { // console.log(`Testing: ${a}${b}${c}${d}`) let array = [a,b,c,d] let wi = findhighestwhere(array, x => x <= 2) // That one pain in the conditional edge-case if ( array[wi] == 2 ) { // console.log(`Encountered First Position 2 Checking for Edge Case`) let i = 0 let lowcount = 0 let highcount = 0 for (let x of array) { if ( i != wi && x <= 3 ) lowcount++ if ( i != wi && x >= 6 ) highcount++ i++ } if ( lowcount == 1 && highcount == 2 ) { // console.log(`Edge Case Encountered`) wi = findhighestwhere(array, x => x <= 1) } } if ( wi === null ) return false let w = array[wi] // console.log(`W: ${w}`) array[wi] = null if ( w == 2 ) { var xi = findhighestwhere(array, x => x <= 3) } else { var xi = findhighestwhere(array, x => true) } if ( xi === null ) return false let x = array[xi] // console.log(`X: ${x}`) array[xi] = null let yi = findhighestwhere(array, x => x <= 5) if ( yi === null ) return false let y = array[yi] // console.log(`Y: ${y}`) array[yi] = null let zi = findhighestwhere(array, x => true) if ( zi === null ) return false let z = array[zi] // console.log(`Z: ${z}`) array[zi] = null return `${w}${x}:${y}${z}` } console.log(`6520: ${generate(6,5,2,0)}`) // 6520: 20:56 console.log(`3950: ${generate(3,9,5,0)}`) // 3950: 09:53 console.log(`7638: ${generate(7,6,3,8)}`) // 7638: false console.log(`1727: ${generate(1,7,2,7)}`) // 1727: 17:27 

Answer 8

 function pickN(arr, clause){ const index = arr.findIndex(clause); if(index >= 0){ return arr.splice(index, 1)[0]; } } function getMaxTime(args, tryN1 = 2){ let paramsArray = Array.from(args).sort((a , b) => a < b); let n1 = pickN(paramsArray, n => n <= tryN1); let n2 = pickN(paramsArray, n => n1 === 2 ? n <= 3 : n); let n3 = pickN(paramsArray, n => n <= 5); let n4 = paramsArray.pop(); if([n1,n2,n3,n4].some(n => typeof(n) === `undefined`)){ return tryN1 > 0 && getMaxTime(args, --tryN1); } return `${n1}${n2}:${n3}${n4}`; } function generate(A, B, C, D) { let maxTime = getMaxTime(arguments); if(maxTime){ return maxTime; } return `NOT POSSIBLE`; } //////////////////////// // TESTING MANY TIMES // //////////////////////// let times = 100; while(times--){ let paramA = randomNumbers(); let paramB = randomNumbers(); let paramC = randomNumbers(); let paramD = randomNumbers(); let result = generate(paramA, paramB, paramC, paramD); console.log(`${paramA},${paramB},${paramC},${paramD} = ${result}`); } function randomNumbers(){ return Math.floor(Math.random() * (9 - 0 + 1)) + 0; } 

Answer 9

对于地方， AB:CD ，

 If at any point a condition cannot be fulfilled: return NOT POSSIBLE If there are two numbers greater than 5: place the larger in B, smaller in D for non-filled places from left to right: if B > 3: place a 1 in A else: place the largest number smaller than 3 in A if A is 2: place the largest number smaller than 4 in B else: place the largest number in B place the largest number smaller than 6 in C place the remaining number in D 

Answer 10

我可以做很多if s和else s，但我很确定这已经完成。 相反，我以一种不同的方式去。

• 我们得到给定的4个数字的所有排列组合。 在这里我使用我的rotationPermalgorithm。 我想这是有史以来最快的JS之一 。
• 过滤出无效的时间
• 从剩下的价值中选出最大的
• 格式为时间。

 function getMaxTime(...a){ function perm(a){ var r = [[a[0]]], t = [], s = []; if (a.length <= 1) return a; for (var i = 1, la = a.length; i < la; i++){ for (var j = 0, lr = r.length; j < lr; j++){ r[j].push(a[i]); t.push(r[j]); for(var k = 1, lrj = r[j].length; k < lrj; k++){ for (var l = 0; l < lrj; l++) s[l] = r[j][(k+l)%lrj]; t[t.length] = s; s = []; } } r = t; t = []; } return r; } function isValidTime(a){ return 10*a[0]+a[1] < 24 && 10*a[2]+a[3] < 60; } var time = perm(a).filter(t => isValidTime(t)) // filter out the invalids .map(t => t.reduce((p,c) => 10*p+c)) // convert them into 4 digit integer .reduce((p,c) => p > c ? p : c, -1); // get the biggest return time >= 0 ? ("0" + ~~(time/100)).slice(-2) + ":" + time%100 : "No way..!"; } console.log(getMaxTime(6, 5, 2, 0)); console.log(getMaxTime(3, 9, 5, 0)); console.log(getMaxTime(7, 6, 3, 8)); 

Answer 11

更新

试图find一些提高性能的方法，新的想法是受计数sorting的启发。

只要计算每个数字的数量，然后根据下面的依赖链，暴力发现最佳的可能性。 答案将是其中之一，最高优先级：

1. 2 [最大数字<= 3]：[最大数字<= 5] [*]
2. 1 [*]：[最大数字<= 5] [*]
3. 0 [*]：[最大数字<= 5] [*]

 /* --------------- Start Speed Test --------------------- */ var startTime = Math.floor(Date.now()); var times = 10000; //how many generate call you want? var timesHolder = times; while (times--) { var A = randNum(); var B = randNum(); var C = randNum(); var D = randNum(); generate(A, B, C, D); if (times == 0) { var totalTime = Math.floor(Date.now()) - startTime; var 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 cnt = [0,0,0,0,0,0,0,0,0,0], ans = ['', '']; cnt[A]++; cnt[B]++; cnt[C]++; cnt[D]++; function gen(part, max){ for(var i=max; i>=0; i--) if(cnt[i]){ ans[part] += i; cnt[i]--; return 1; } return 0; } function rollback(first){ cnt[first]++; for(var i in ans[0]) cnt[ans[0][i]]++; for(var i in ans[1]) cnt[ans[1][i]]++; ans[0] = ans[1] = ''; } /*** Main logic, based on the chain of dependencies ***/ if(cnt[2]){ cnt[2]--; if(!gen(0, 3) || !gen(1,5) || !gen(1,9)) rollback(2); else return '2' + ans[0] + ':' + ans[1]; } if(cnt[1]){ cnt[1]--; if(!gen(0, 9) || !gen(1,5) || !gen(1,9)) rollback(1); else return '1' + ans[0] + ':' + ans[1]; } if(cnt[0]){ cnt[0]--; if(!gen(0, 9) || !gen(1,5) || !gen(1,9)) rollback(0); else return '0' + ans[0] + ':' + ans[1]; } return 'NOT POSSIBLE'; } console.log(generate(1,7,2,7)); console.log(generate(0,0,2,9)); console.log(generate(6,5,2,0)); console.log(generate(3,9,5,0)); console.log(generate(7,6,3,8)); console.log(generate(0,0,0,0)); console.log(generate(9,9,9,9)); console.log(generate(1,2,3,4)); 

Answer 12

这是我的尝试。 添加内联评论与解释。

 // think of the result of the form {h1}{h2}:{ms} function generate(a, b, c, d) { const digits = [a, b, c, d]; // extract possible starting digits const possibleH1s = [2, 1, 0].filter(digit => digits.includes(digit)); // check result, starting from the highest possible h1 digit // if digits doesn't contains any of [2,1,0], we're done for (const h1 of possibleH1s) { // extract the remaining digits after h1 const withoutH1 = removeFrom(digits, h1); // determine all possible h2 digits based on the h1 digit const possibleH2s = h1 === 2 ? [3,2,1,0] : [9,8,7,6,5,4,3,2,1,0]; // find the highest possible h2 digit (works because array of possible digits above is in descending order) // if none exist, loop iteration is done const h2 = possibleH2s.find(d => withoutH1.includes(d)); if (typeof h2 !== 'number') { continue; } // remove h2 so we can search for the remaining ms digits const [possibleMS1, possibleMS2] = removeFrom(withoutH1, h2); // build the two possible combinations for ms const possibleMs = [ Number(`${possibleMS1}${possibleMS2}`), Number(`${possibleMS2}${possibleMS1}`) ]; // determine the min and max ms value const maxMs = Math.max(...possibleMs); const minMs = Math.min(...possibleMs); // find the largest valid ms value // if none exist, loop iteration is done const ms = maxMs < 60 ? maxMs : minMs < 60 ? minMs : undefined; if (typeof ms !== 'number') { continue; } // yay, time return `${h1}${h2}:${padWithZero(ms)}`; } return 'NOT POSSIBLE'; } // returns a new array by removing a single element // that is equal to `val` from the given array // (performs better than splice cause if doesn't do array shift) function removeFrom(arr, val) { const newArr = []; for (let i = 0, l = arr.length, found = false; i < l; i++) { if (arr[i] !== val || found) { newArr.push(arr[i]); } else { found = true; } } return newArr; } function padWithZero(digit) { return digit < 10 ? `0${digit}` : `${digit}`; } /* --------------- Tests --------------------- */ const speedTest = (times = 10000) => { let counter = times; const start = performance.now(); while (counter--) { const A = randNum(); const B = randNum(); const C = randNum(); const D = randNum(); generate(A, B, C, D); if (counter == 0) { const ms = performance.now() - start; console.log(`${times} times to run generate took ${ms} ms`); } } } const randNum = () => Math.floor(Math.random() * (9 - 0 + 1)) + 0; const accuracyTest = () => { console.assert(generate(1,7,2,7) === '17:27'); console.assert(generate(0,0,2,9) === '20:09'); console.assert(generate(6,5,2,0) === '20:56'); console.assert(generate(3,9,5,0) === '09:53'); console.assert(generate(7,6,3,8) === 'NOT POSSIBLE'); console.assert(generate(0,0,0,0) === '00:00'); console.assert(generate(9,9,9,9) === 'NOT POSSIBLE'); console.assert(generate(1,2,3,4) === '23:41'); console.log('All good!'); } speedTest(); accuracyTest(); 

Answer 13

我认为这种方法被称为蛮力。 从@ Dummy的答案拿了testing样本。

 <script> function generate(A, B, C, D) { var result = -1 var v = [A, B, C, D] for (i = 0; i < 4; i++) { for (j = 0; j < 4; j++) if (j != i) { for (k = 0; k < 4; k++) if (k != j && k != i) { for (m = 0; m < 4; m++) if (m != k && m != j && m != i) { if (v[i]*10 + v[j] < 24 && v[k]*10 + v[m] < 60) { //legal time if (v[i]*1000 + v[j]*100 + v[k]*10 + v[m] > result) { result = v[i]*1000 + v[j]*100 + v[k]*10 + v[m] } } } } } } return result >= 0? Math.floor(result/100) + ':' + result%100: 'NOT POSSIBLE' } 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)) </script> 

Answer 14

那么，从这个关于JavaScript排列的build议开始，在给定一组值的情况下，可以得到所有可能的独特排列，我得到了这个解决scheme：

• 假设你有所有可能的4位数组合，
• 并假设正确的小时值在00-23的范围内
• 并假设正确的分钟值在00-59的范围内

您可以使用这个简单的代码来执行操作：

 function maxTime(a, b, c, d) { var ps = Array.from(uniquePermutations([a, b, c, d])); while (maxHour = ps.pop()) { var timing = maxHour.join('').replace(/([0-9]{2})([0-9]{2})/, '$1:$2'); if (/([0-1][0-9]|2[0-3])\:[0-5][0-9]/.test(timing)) { return timing; } } return false; } 

 function swap(a, i, j) { const t = a[i]; a[i] = a[j]; a[j] = t; } function reverseSuffix(a, start) { if (start === 0) { a.reverse(); } else { let left = start; let right = a.length - 1; while (left < right) swap(a, left++, right--); } } function nextPermutation(a) { // 1. find the largest index `i` such that a[i] < a[i + 1]. // 2. find the largest `j` (> i) such that a[i] < a[j]. // 3. swap a[i] with a[j]. // 4. reverse the suffix of `a` starting at index (i + 1). // // For a more intuitive description of this algorithm, see: // https://www.nayuki.io/page/next-lexicographical-permutation-algorithm const reversedIndices = [...Array(a.length).keys()].reverse(); // Step #1; (note: `.slice(1)` maybe not necessary in JS?) const i = reversedIndices.slice(1).find(i => a[i] < a[i + 1]); if (i === undefined) { a.reverse(); return false; } // Steps #2-4 const j = reversedIndices.find(j => a[i] < a[j]); swap(a, i, j); reverseSuffix(a, i + 1); return true; } function* uniquePermutations(a) { const b = a.slice().sort(); do { yield b.slice(); } while (nextPermutation(b)); } function maxTime(a, b, c, d) { var ps = Array.from(uniquePermutations([a, b, c, d])); while (maxHour = ps.pop()) { var timing = maxHour.join('').replace(/([0-9]{2})([0-9]{2})/, '$1:$2'); if (/([0-1][0-9]|2[0-3])\:[0-5][0-9]/.test(timing)) { return timing; } } return false; } console.log(maxTime(6, 5, 2, 0)); console.log(maxTime(3, 9, 5, 0)); console.log(maxTime(7, 6, 3, 8)); 

Answer 15

嗯…..我想这很简单，如果你把它分解成简单的问题：例如find所有有效的小时（00-23），对于这些有效小时中的每一个使用其余的数字find有效的分钟（00-59），组合和sorting。 伪代码如下所示

  valid_times = [] function get_max(digits[]) { for each d1 in digits[] for each d2 in (digits[] except d1) res = is_valid_hour(d1, d2) if(res > 0) { if(res == 2) swap(d1, d2) d3 = one of the rest in (digits except d1 and d2) d4 = digit left in digits[] res = is_valid_minute(d3, d4) if(res > 0) if(res == 2) swap(d3, d4) add (d1, d2, d3, d4) to valid_times; } sort(valid_times) print valid_times[0] } function is_valid_hour(a, b) { if (a*10+b<24) return 1 if (b*10+a<24) return 2 return 0; } function is_valid_minute(a, b) { if (a*10+b<60) return 1 if (b*10+a<60) return 2 return 0; } 

Answer 16

这不是优雅或漂亮，但它似乎是伎俩！

 const NOT_POSSIBLE = 'NOT POSSIBLE'; function generate(A, B, C, D) { var args = [A, B, C, D]; var idx = -1; var out = NOT_POSSIBLE; var firstN, secondN; MAIN: { args.sort(NUMERIC_ASCENDING); // number has to start with 0, 1 or 2 if (args[0] > 2) break MAIN; while (args[++idx] < 3) {} // take the higest 2, 1, or 0 firstN = args[--idx]; args = pop(args, idx); if (firstN === 2) { // make sure that the first number doesn't exceed 23 and // the second number 59 if (args[0] > 3 || args[0] > 1 && args[1] > 5) break MAIN; // advance to the first number < 3 or the length idx = 0; while (args[++idx] < 3){} } else { // much simpler if we have a 0 or 1, take the biggest n remaining idx = args.length; } secondN = args[--idx]; args = pop(args, idx); // if minutes number is too large, swap if (args[0] > 5) { out = '' + secondN + args[1] + ':' + firstN + args[0]; } else { // if bottom number is low enough, swap for more minutes out = '' + firstN + secondN + (args[1] < 6 ? ':' + args[1] + args[0] : ':' + args[0] + args[1]); } } return out; } // numeric comparator for sort function NUMERIC_ASCENDING(x, y) { return x > y ? 1 : y > x ? -1 : 0; } // specialized "array pop" I wrote out longhand that's very optimized; might be cheating =D function pop(arr, target) { switch (arr.length) { case 3: switch (target) { case 0: return [arr[1], arr[2]]; case 1: return [arr[0], arr[2]]; default: return [arr[0], arr[1]]; } case 4: switch (target) { case 0: return [arr[1], arr[2], arr[3]]; case 1: return [arr[0], arr[2], arr[3]]; case 2: return [arr[0], arr[1], arr[3]]; default: return [arr[0], arr[1], arr[2]]; } } } /* --------------- Start Speed Test --------------------- */ let startTime = Math.floor(Date.now()); let times = 10000; 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); } } function randNum() { return Math.floor(Math.random() * (9 - 0 + 1)) + 0; } /* --------------- END Speed Test --------------------- */ 

Answer 17

My approach is to have array of available numbers ( stack ) and another with return value ( ret ). At first I put in ret invalid values "-1". Then I sort stack descending and loop trough to try to assign biggest possible number to return stack.

 function swap(a, b, p1, p2) { var temp = a[p1]; a[p1] = b[p2]; b[p2] = temp; } function t(a, b, c, d) { var stack = [a, b, c, d]; var ret = [-1, -1, -1, -1]; stack.sort().reverse(); var change = true; var i = 0; // this while is assigning HOURS while(change === true || i < 4) { change = false; // Assigning at first position (Hh:mm), so number must be lower or equal to 2 if(stack[i] <= 2 && ret[0] < stack[i]) { swap(ret, stack, 0, i); change = true; i = 0; } // Assigning at second position (hH:mm), so number must be <= 4 if number // at first position is 2, otherwise just make sure valid number // (0 to 1) is assigned at first position else if(((ret[0] === 2 && stack[i] <= 4) || ret[0] < 2 && ret[0] >= 0) && ret[1] < stack[i]) { swap(ret, stack, 1, i); change = true; i = 0; } else i++; } stack.sort().reverse(); change = true; i = 0; // This while is assigning minutes while(change === true || i < 4) { change = false; if(stack[i] <= 5 && ret[2] < stack[i]) { swap(ret, stack, 2, i); change = true; i = 0; } else if(stack[i] <= 9 && ret[3] < stack[i]) { swap(ret, stack, 3, i); change = true; i = 0; } else i++; } // If return stack contains -1, invalid combination was entered return Math.min.apply(Math, ret) > -1 ? ret[0] + "" + ret[1] + ":" + ret[2] + "" + ret[3] : "NOT POSSIBLE"; } console.log(t(6, 5, 2, 0)); // 20:56 console.log(t(3, 9, 5, 0)); // 09:53 console.log(t(2, 5, 6, 8)); // NOT POSSIBLE 

Answer 18

Really late for the party, but I think there a quite straightforward solution to the problem (slower and uglier than other solutions, though). Just iterate (no hardcoding, no permutations) through all integer values from 2359 to 0 and check if they contain provided digits:

 Number.prototype.pad = function(size) { var s = String(this); while (s.length < (size || 2)) {s = "0" + s;} return s; } getHHMM = (val) => `${Math.floor(val / 100).pad(2)}:${(val % 100).pad(2)}`; isValidDate = value => !isNaN(new Date(`1970-01-01T${getHHMM(value)}`).getTime()); isFit = function(a, b, c, d, value) { var valStr = value.pad(4).split("").sort().join(""); var digStr = [a, b, c, d].sort().join(""); return valStr === digStr; } generate = function(a, b, c, d) { for (var i = 2359; i >= 0; i--) { if (isFit(a, b, c, d, i) && isValidDate(i)) return getHHMM(i); } return "NOT POSSIBLE"; } 

Answer 19

This solution is in Swift 3.0.

 func returnValue (_ value :inout Int, tempArray : [Int] , compareValue : Int) -> Int { for i in tempArray { if value <= i && i <= compareValue { value = i } } return value } func removeValue(_ value : Int, tempArr : inout [Int]) -> Bool { let index = tempArr.index(of: value) tempArr.remove(at: index ?? 0) return index != nil ? true : false } public func solution(_ A : Int, _ B : Int, _ C : Int, _ D : Int) -> String { var tempArray = [A, B, C, D] let mainArray = [A, B, C, D] var H1 : Int = -1, H2: Int = -1, M1 : Int = -1, M2 : Int = -1; H1 = returnValue(&H1, tempArray: tempArray, compareValue: 2) if !removeValue(H1, tempArr: &tempArray) { return "NOT POSSIBLE" } for value in tempArray { if H1 < 2 { if H2 <= value && value <= 9 { H2 = value } } else { if H2 <= value && value <= 3 { H2 = value } } } if !removeValue(H2, tempArr: &tempArray) { return "NOT POSSIBLE" } M1 = returnValue(&M1, tempArray: tempArray, compareValue: 5) if M1 >= 0 { if !removeValue(M1, tempArr: &tempArray) { return "NOT POSSIBLE" } } else if mainArray.contains(0) || mainArray.contains(1) { H1 = -1 H1 = returnValue(&H1, tempArray: mainArray, compareValue: 1) for value in mainArray { if H1 < 2 { if H2 <= value && value <= 9 { H2 = value } } else { if H2 <= value && value <= 3 { H2 = value } } } tempArray.removeAll() for value in mainArray { tempArray.append(value) } var index = tempArray.index(of: H1) tempArray.remove(at: index!) index = tempArray.index(of: H2) tempArray.remove(at: index!) M1 = -1 M1 = returnValue(&M1, tempArray: tempArray, compareValue: 5) if !removeValue(M1, tempArr: &tempArray) { return "NOT POSSIBLE" } } else { return "NOT POSSIBLE" } // Now last we have M2 = temp.last if let lastValue = tempArray.last { M2 = lastValue } if M2 < 0 { return "NOT POSSIBLE" } return "\(H1)\(H2):\(M1)\(M2)" } print(solution(1,7,2,7)) print(solution(0,0,2,9)) print(solution(6,5,2,0)) print(solution(3,9,5,0)) print(solution(7,6,3,8)) print(solution(0,0,0,0)) print(solution(9,9,9,9)) print(solution(1,2,3,4)) 17:27 20:09 20:56 09:53 NOT POSSIBLE 00:00 NOT POSSIBLE 23:41 

Answer 20

With a small input and output space, using a look-up table is always an option; however, I found that in JavaScript the size of the table has a surprisingly large impact on the speed.

If we start by sorting the input to get a canonical version, so that 4,3,2,1 and 3,1,4,2 are both transformed into 1,2,3,4 , there are less than 400 possibilities that lead to a valid result. But as soon as I added more than 200 entries to the look-up table, the speed dropped considerably (which is probably browser-dependent).

However, there are only five types of digits:

 0,1 <- can be first digit of hours followed by any digit 2 <- can be first digit of hours followed by 0-3 3 <- can be second digit of hours after a 2 to form 23 hours 4,5 <- can be first digits of minutes 6-9 <- can only be second digit of hours or minutes 

Within these types, the digits are interchangeable; the optimal permutation will be the same:

 2,4,0,6 -> 20:46 (ACBD) 2,5,1,9 -> 21:59 (ACBD) 

If you represent the digits by digit types "0" (0-1), "2", "3", "4" (4-5), and "6" (6-9), there are only 48 combinations that lead to a valid solution, each using one of 16 different permutations. Code with these smaller look-up tables turns out to be much faster:

 function generate(A, B, C, D) { var swap; // sorting network if (A > B) { swap = A; A = B; B = swap; } if (C > D) { swap = C; C = D; D = swap; } if (A > C) { swap = A; A = C; C = swap; } if (B > D) { swap = B; B = D; D = swap; } if (B > C) { swap = B; B = C; C = swap; } var table = {"0000":15, "0002":15, "0003":14, "0004":14, "0006":14, "0022":15, "0023":14, "0024":13, "0026":12, "0033":11, "0034":11, "0036":11, "0044":11, "0046":11, "0066":10, "0222":15, "0223":14, "0224":13, "0226":12, "0233":11, "0234": 9, "0236": 8, "0244": 7, "0246": 6, "0266": 4, "0333": 5, "0334": 5, "0336": 5, "0344": 5, "0346": 5, "0366": 4, "0444": 5, "0446": 5, "0466": 4, "2222":15, "2223":14, "2224":13, "2226":12, "2233":11, "2234": 9, "2236": 8, "2244": 7, "2246": 6, "2333": 5, "2334": 3, "2336": 2, "2344": 1, "2346": 0}; var type = ['0','0','2','3','4','4','6','6','6','6']; var key = type[A] + type[B] + type[C] + type[D]; var permutation = table[key]; if (permutation == undefined) return "NOT POSSIBLE"; var digits = [[2,3,C,D], [2,3,D,C], [2,3,3,D], [2,3,D,3], [A,D,B,C], [A,D,C,B], [2,A,C,D], [2,A,D,C], [2,3,A,D], [2,3,D,A], [B,D,A,C], [B,D,C,A], [2,B,A,D], [2,B,D,A], [C,D,B,A], [D,C,B,A]]; var time = digits[permutation]; return "" + time[0] + time[1] + ':' + time[2] + time[3]; } function rndDigit() { return Math.floor(Math.random() * 10); } for (var tests = 0; tests < 11; tests++) { var d = [rndDigit(), rndDigit(), rndDigit(), rndDigit()]; document.write(d + " &rarr; " + generate(d[0],d[1],d[2],d[3]) + "<BR>"); }