LeetCode 681.次に近い時間（java）
Leetcode 681 Next Closest Time Java
「HH：MM」の形式で表される時刻を指定して、現在の数字を再利用して次に近い時刻を作成します。 1桁を再利用できる回数に制限はありません。
指定された入力文字列は常に有効であると想定できます。たとえば、「01:34」、「12:09」はすべて有効です。 「1:34」、「12：9」はすべて無効です。
Example 1: Input: '19:34' Output: '19:39' Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later. It is not 19:33, because this occurs 23 hours and 59 minutes later. Example 2: Input: '23:59' Output: '22:22' Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. It may be assumed that the returned time is next day's time since it is smaller than the input time numerically.解決策1：最適な解決策、時間計算量はO（4 * 10）、空間計算量はO（10）、アイデア：疑似ハッシュテーブルを使用して指定された時間番号を格納し、4桁目から開始してハッシュに移動します指定された4桁よりも大きい有効な数値があるかどうかを確認するためのテーブル。そうでない場合は、この有効な数値を持つ新しい文字列がある場合は、4桁目をハッシュテーブルの最小値に設定します。類推すると、4桁目から1桁目まで、最初の桁にそれより大きい有効値がない場合、4桁はすべて最小値に設定されてから返されます。対応する状況は、example2の状況です。 、返されるのは翌日の最小時間です。このソリューションはシンプルで理解しやすく、非常に効率的で、リートコーダーの96％を上回っています。
public String nextClosestTime(String time) { char[] t = time.toCharArray(), result = new char[4] int[] list = new int[10] char min = '9' for (char c : t) { if (c == ':') continue list[c - '0']++ if (c for (int i = t[4] - '0' + 1 i <= 9 i++) { if (list[i] != 0) { t[4] = (char)(i + '0') return new String(t) } } t[4] = min for (int i = t[3] - '0' + 1 i <= 5 i++) { if (list[i] != 0) { t[3] = (char)(i + '0') return new String(t) } } t[3] = min int stop = t[0] <'2' ? 9 : 3 for (int i = t[1] - '0' + 1 i <= stop i++) { if (list[i] != 0) { t[1] = (char)(i + '0') return new String(t) } } t[1] = min for (int i = t[0] - '0' + 1 i <= 2 i++) { if (list[i] != 0) { t[0] = (char)(i + '0') return new String(t) } } t[0] = min return new String(t) } 解決策2：これら4つの数値の可能なすべての時間の組み合わせを見つけてから、指定された時間と比較し、差が最も小さいものを維持して、この文字列を返します。時間計算量はO（4 ^ 4）であり、空間計算量はO（4）です。
int diff = Integer.MAX_VALUE String result = '' public String nextClosestTime(String time) { Set set = new HashSet() set.add(Integer.parseInt(time.substring(0, 1))) set.add(Integer.parseInt(time.substring(1, 2))) set.add(Integer.parseInt(time.substring(3, 4))) set.add(Integer.parseInt(time.substring(4, 5))) if (set.size() == 1) return time List digits = new ArrayList(set) int minute = Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(3, 5)) dfs(digits, '', 0, minute) return result } private void dfs(List digits, String cur, int pos, int target) { if (pos == 4) { int m = Integer.parseInt(cur.substring(0, 2)) * 60 + Integer.parseInt(cur.substring(2, 4)) if (m == target) return int d = m - target > 0 ? m - target : 1440 + m - target if (d 0, 2) + ':' + cur.substring(2, 4) } return } for (int i = 0 i if (pos == 0 && digits.get(i) > 2) continue if (pos == 1 && Integer.parseInt(cur) * 10 + digits.get(i) > 23) continue if (pos == 2 && digits.get(i) > 5) continue if (pos == 3 && Integer.parseInt(cur.substring(2)) * 10 + digits.get(i) > 59) continue dfs(digits, cur + digits.get(i), pos + 1, target) } }