Question

1736. 替换隐藏数字得到的最晚时间

English Version

题目描述

给你一个字符串 time ，格式为 hh:mm（小时：分钟），其中某几位数字被隐藏（用 ? 表示）。

有效的时间为 00:00 到 23:59 之间的所有时间，包括 00:00 和 23:59 。

替换 time 中隐藏的数字，返回你可以得到的最晚有效时间。

 

示例 1：

输入：time = "2?:?0"
输出："23:50"
解释：以数字 '2' 开头的最晚一小时是 23 ，以 '0' 结尾的最晚一分钟是 50 。

示例 2：

输入：time = "0?:3?"
输出："09:39"

示例 3：

输入：time = "1?:22"
输出："19:22"

 

提示：

• time 的格式为 hh:mm
• 题目数据保证你可以由输入的字符串生成有效的时间

解法

方法一：贪心

我们依次处理字符串的每一位，处理的规则如下：

1. 第一位：若第二位的值已确定，且值落在区间 $[4, 9]$ 内，那么第一位只能取 $1$，否则第一位最大取 $2$；
2. 第二位：若第一位的值已确定，且值为 $2$，那么第二位最大取 $3$，否则第二位最大取 $9$；
3. 第三位：第三位最大取 $5$；
4. 第四位：第四位最大取 $9$。

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

class Solution:
  def maximumTime(self, time: str) -> str:
    t = list(time)
    if t[0] == '?':
      t[0] = '1' if '4' <= t[1] <= '9' else '2'
    if t[1] == '?':
      t[1] = '3' if t[0] == '2' else '9'
    if t[3] == '?':
      t[3] = '5'
    if t[4] == '?':
      t[4] = '9'
    return ''.join(t)

class Solution {
  public String maximumTime(String time) {
    char[] t = time.toCharArray();
    if (t[0] == '?') {
      t[0] = t[1] >= '4' && t[1] <= '9' ? '1' : '2';
    }
    if (t[1] == '?') {
      t[1] = t[0] == '2' ? '3' : '9';
    }
    if (t[3] == '?') {
      t[3] = '5';
    }
    if (t[4] == '?') {
      t[4] = '9';
    }
    return new String(t);
  }
}

class Solution {
public:
  string maximumTime(string time) {
    if (time[0] == '?') {
      time[0] = (time[1] >= '4' && time[1] <= '9') ? '1' : '2';
    }
    if (time[1] == '?') {
      time[1] = (time[0] == '2') ? '3' : '9';
    }
    if (time[3] == '?') {
      time[3] = '5';
    }
    if (time[4] == '?') {
      time[4] = '9';
    }
    return time;
  }
};

func maximumTime(time string) string {
  t := []byte(time)
  if t[0] == '?' {
    if t[1] >= '4' && t[1] <= '9' {
      t[0] = '1'
    } else {
      t[0] = '2'
    }
  }
  if t[1] == '?' {
    if t[0] == '2' {
      t[1] = '3'
    } else {
      t[1] = '9'
    }
  }
  if t[3] == '?' {
    t[3] = '5'
  }
  if t[4] == '?' {
    t[4] = '9'
  }
  return string(t)
}

/**
 * @param {string} time
 * @return {string}
 */
var maximumTime = function (time) {
  const t = Array.from(time);
  if (t[0] === '?') {
    t[0] = t[1] >= '4' && t[1] <= '9' ? '1' : '2';
  }
  if (t[1] === '?') {
    t[1] = t[0] == '2' ? '3' : '9';
  }
  if (t[3] === '?') {
    t[3] = '5';
  }
  if (t[4] === '?') {
    t[4] = '9';
  }
  return t.join('');
};