通过置换四个给定数字找到最大可能时间HH:MM

tut 发布于 2019-10-18 algorithm 最后更新 2019-10-18 13:45 100 浏览

我最近在工作中进行了升级的编码测试。这是我真正努力的任务之一,并且想知道做这件事的最佳方式是什么。我使用了if和if的其他负载,而不是最干净的解决方案,但完成了工作。 我被问到的问题是: 将4位数字格式化为24小时制(24小时制)(考虑到最大小时数为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
} 
人们将如何解决这个问题?
已邀请:

punde

赞同来自:

这是我的尝试。添加内联注释和解释。

// 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();

qodio

赞同来自:

一旦我了解到你可以将问题视为“生成小于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 --------------------- */

eut

赞同来自:

那么,从this suggestion about permutations in JavaScript开始,在给定一组值得到所有可能的唯一排列的情况下,我得到了这个解决方案:

  • 假设您拥有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));

oqui

赞同来自:

此解决方案在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

funde

赞同来自:

它不优雅或漂亮,但似乎可以做到这一点!

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

dsed

赞同来自:

一种使用预先计算的字符串的方法,包含所有可能的排列。

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}

xet

赞同来自:

嗯......我想如果你把它分解成更简单的问题真的很简单:例如找到所有有效时间(00-23),对于每个有效时间,使用剩余的数字来找到有效的分钟数(00-59),结合和排序。在伪代码中,如下所示

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

sit_et

赞同来自:

我将使用JavaScript的Date对象来确定特定时间是否有效,方法是将字符串解析为ISO日期时间字符串(如1970-01-01T62:87),然后测试!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';
}

taut

赞同来自:

我可以做大量的ifs和elses,但我很确定已经完成了。相反,我采用不同的方式。

  • 我们得到给定的4个数字的所有排列。在这里,我使用我的rotationPerm算法。我想这是one of the fastest ever in 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));

oalias

赞同来自:

添加了可执行代码段和一些测试用例

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

yeum

赞同来自:

这就是我提出的。非常优雅,我可能会试着整理一下,让它更有效率。我觉得蛮力方法是最干净,最有效的方法。这是一团糟。

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

mut

赞同来自:

想法:
  • 查找所有组合数组(共24个)
  • 过滤掉所有无效组合(时间格式)
  • 找到时间值
  • 输出具有最大时间值的数组

解决方案: 第一个allCom将返回4个数字的所有组合(共24个组合) 然后对于24个数组(组合)调用.forEach,检查每个数组,检查它是否是有效的时间格式。如果它是有效的时间格式,则使用计算时间值
If the time is AB:CD then the value: A = A * 10 hours = A * 10 * 3600s = A * 36000s B = B * 1 hour = B * 3600s C = C * 10s D = D Total value = 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>

我还邀请人们将此代码用于测试其算法的运行速度。 (使用@Diego ZoracKy的一些代码来制作它,谢谢!)。玩得开心!!!
/* --------------- 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];
}

dsed

赞同来自:

这是我提出的非暴力解决方案。查看代码中的注释,了解它是如何工作的。如果其中任何一个不清楚我可以帮助澄清。

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

menim

赞同来自:

我的方法是使用可用数字数组(stack)和另一个具有返回值(ret)的数字。起初我输入了无效值“-1”。然后我对堆栈降序和循环槽进行排序以尝试分配最大可能的数量以返回堆栈。

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

zquia

赞同来自:

派对真的很晚,但我认为这个问题有一个非常直接的解决方案(虽然比其他解决方案更慢,更丑)。只需通过从2359到0的所有整数值进行迭代(无硬编码,无排列),并检查它们是否包含提供的数字:

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

veos

赞同来自:

更新 只是尝试找到一些方法来改善性能,新想法的灵感来自于计算排序。 只需计算每个数字的数量,然后根据以下依赖链,粗暴找到最佳可能性。答案将是其中之一,优先级最高:

  1. 2 [最大数字< = 3]:[最大数字< = 5] [*]
  2. 1 [*]:[max digit< = 5] [*]
  3. 0 [*]:[max digit< = 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));

mest

赞同来自:

凭借较小的输入和输出空间,使用查找表始终是一种选择;但是,我发现在JavaScript中,表的大小对速度有着惊人的巨大影响。 如果我们首先对输入进行排序以获得规范版本,以便将4,3,2,13,1,4,2都转换为1,2,3,4,则导致有效结果的可能性少于400种。但是,只要我在查找表中添加了200多个条目,速度就会大幅下降(这可能与浏览器有关)。 但是,只有五种类型的数字:

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
在这些类型中,数字是可互换的;最佳排列将是相同的:
2,4,0,6  ->  20:46  (ACBD)
2,5,1,9  ->  21:59  (ACBD)
如果用数字类型“0”(0-1),“2”,“3”,“4”(4-5)和“6”(6-9)表示数字,则只有48种组合导致一个有效的解决方案,每个解决方案使用16种不同的排列之一。使用这些较小的查找表的代码变得更快:
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>");
}

wab

赞同来自:

对于地方,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

ksequi

赞同来自:

我认为这种方法叫做暴力。从@ Dummy的答案中测试样品。

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

xillum

赞同来自:

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