949.给定数字能组成的最大时间

给定数字能组成的最大时间

给定一个由 4 位数字组成的数组，返回可以设置的符合 24 小时制的最大时间。24 小时格式为 “HH:MM” ，其中 HH 在 00 到 23 之间，MM 在 00 到 59 之间。

示例 1:

输入：arr = [1,2,3,4]
输出：”23:41”

提示:

• arr.length == 4
• 0 <= arr[i] <= 9

解析

枚举所有排列，筛选出符合时间格式的最大时间。

var largestTimeFromPermutation = function (arr) {
  let maxTime = -1;
  const perm = [0, 1, 2, 3];

  const swap = (i, j) => {
    [perm[i], perm[j]] = [perm[j], perm[i]];
  };

  const generate = (idx) => {
    if (idx === 4) {
      const [a, b, c, d] = perm.map((i) => arr[i]);
      const hour = a * 10 + b;
      const minute = c * 10 + d;
      if (hour < 24 && minute < 60) {
        maxTime = Math.max(maxTime, hour * 60 + minute);
      }
      return;
    }

    for (let i = idx; i < 4; i++) {
      swap(idx, i);
      generate(idx + 1);
      swap(idx, i);
    }
  };

  generate(0);

  if (maxTime === -1) return "";
  const hour = Math.floor(maxTime / 60);
  const minute = maxTime % 60;
  return `${hour.toString().padStart(2, "0")}:${minute.toString().padStart(2, "0")}`;
};

时间复杂度 O(1)，空间复杂度 O(1)。