LWC 51:681. Next Closest Time

LWC 51:681. Next Closest Time

传送门:681. Next Closest Time

Problem:

Given a time represented in the format “HH:MM”, form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused. You may assume the given input string is always valid. For example, “01:34”, “12:09” are all valid. “1:34”, “12:9” are all invalid.

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.

思路: 暴力遍历,下一个最近的时间点,只需要让时间一点点增大,并且找到第一个所有数字都被reused的情况跳出即可。

代码如下:

    public String nextClosestTime(String time) {
        String[] val = time.split(":");
        Set<Integer> set = new HashSet<>();
        int num1 = Integer.parseInt(val[0]);
        set.add(num1 / 10);
        set.add(num1 % 10);
        int num2 = Integer.parseInt(val[1]);
        set.add(num2 / 10);
        set.add(num2 % 10);

        int hour = num1;
        int minu = num2;

        minu ++;
        if (minu == 60) {
            hour ++;
            minu = 0;
            if (hour == 24) hour = 0;
        }

        while (!contains(hour, minu, set)) {
            minu++;
            if (minu == 60) {
                hour ++;
                minu = 0;
                if (hour == 24) hour = 0;
            }
        }
        String ans = "";
        if (hour >= 0 && hour <= 9) ans = "0" + hour;
        else ans += hour;
        ans += ":";
        if (minu >= 0 && minu <= 9) ans += "0" + minu;
        else ans += minu;
        return ans;
    }

    public boolean contains(int hour, int minu, Set<Integer> set) {
        return set.contains(hour / 10) && set.contains(hour % 10) && set.contains(minu / 10) && set.contains(minu % 10);
    }

优化一下:

    public String nextClosestTime(String time) {
        String[] val = time.split(":");
        Set<Integer> set = new HashSet<>();
        int hour = add(set, val[0]);
        int minu = add(set, val[1]);

        int[] times = new int[] {hour, minu};
        nxt(times);

        while (!contains(times[0], times[1], set)) {
            nxt(times);
        }
        return valid(times[0]) + ":" + valid(times[1]);
    }

    public void nxt(int[] time) {
        int hour = time[0];
        int minu = time[1];
        minu ++;
        if (minu == 60) {
            hour ++;
            minu = 0;
            if (hour == 24) hour = 0;
        }
        time[0] = hour;
        time[1] = minu;
    }

    public int add(Set<Integer> set, String timeStr) {
        int time = Integer.parseInt(timeStr);
        set.add(time / 10);
        set.add(time % 10);
        return time;
    }

    public String valid(int time) {
        if (time >= 0 && time <= 9) return "0" + time;
        else return time + "";
    }

    public boolean contains(int hour, int minu, Set<Integer> set) {
        return set.contains(hour / 10) && set.contains(hour % 10) && set.contains(minu / 10) && set.contains(minu % 10);
    }

当然,你也可以直接搜索,因为最多只有4个数字,所以总共有4 * 4 * 4 * 4种情况,在这些情况中找出diff最小的hour和minute即可。

代码如下:

    int diff = 0x3f3f3f3f;
    String result = "";
    int h;
    int m;
    public String nextClosestTime(String time) {
        int[] digit = new int[4];
        int tot = 0;
        String[] val = time.split(":");
        int hour = Integer.parseInt(val[0]);
        int minu = Integer.parseInt(val[1]);
        digit[tot++] = hour / 10;
        digit[tot++] = hour % 10;
        digit[tot++] = minu / 10;
        digit[tot++] = minu % 10;

        h = hour;
        m = minu;

        dfs(digit, 0, new int[4]);

        return result;
    }

    void dfs(int[] digit, int i, int[] ans) {
        if (i == 4) {
            int hour = 10 * ans[0] + ans[1];
            int minu = 10 * ans[2] + ans[3];
            if (hour >= 0 && hour <= 23 && minu >= 0 && minu <= 59) {
                int df = diff(hour, minu);
                if (df < diff) {
                    diff = df;
                    result = valid(hour) + ":" + valid(minu);
                }
            }
        }
        else {
            for (int j = 0; j < 4; ++j) {
                ans[i] = digit[j];
                dfs(digit, i + 1, ans);
                ans[i] = -1;
            }
        }
    }

    int diff(int hour, int minu) {
        int c2o = 60 * 60 - h * 60 - m;
        int n2o = 60 * 60 - hour * 60 - minu;
        return n2o < c2o ? c2o - n2o : c2o - n2o + 3600;
    }

    public String valid(int time) {
        if (time >= 0 && time <= 9) return "0" + time;
        else return time + "";
    }

剪枝优化:

    int diff = 0x3f3f3f3f;
    String result = "";
    int h;
    int m;
    public String nextClosestTime(String time) {
        int[] digit = new int[4];
        int tot = 0;
        String[] val = time.split(":");
        int hour = Integer.parseInt(val[0]);
        int minu = Integer.parseInt(val[1]);
        digit[tot++] = hour / 10;
        digit[tot++] = hour % 10;
        digit[tot++] = minu / 10;
        digit[tot++] = minu % 10;

        h = hour;
        m = minu;

        dfs(digit, 0, new int[4]);

        return result;
    }

    void dfs(int[] digit, int i, int[] ans) {
        if (i == 4) {
            int hour = 10 * ans[0] + ans[1];
            int minu = 10 * ans[2] + ans[3];
            int df = diff(hour, minu);
            if (df < diff) {
                diff = df;
                result = valid(hour) + ":" + valid(minu);
            }
        }
        else {
            for (int j = 0; j < 4; ++j) {
                ans[i] = digit[j];
                if (i == 1) {
                    int hour = 10 * ans[0] + ans[1];
                    if (hour >= 0 && hour <= 23) dfs(digit, i + 1, ans);
                }
                else if (i == 3) {
                    int minu = 10 * ans[2] + ans[3];
                    if (minu >= 0 && minu <= 59) dfs(digit, i + 1, ans);
                }
                else {
                    dfs(digit, i + 1, ans);
                }
            }
        }
    }

    int diff(int hour, int minu) {
        int c2o = 60 * 60 - h * 60 - m;
        int n2o = 60 * 60 - hour * 60 - minu;
        return n2o < c2o ? c2o - n2o : c2o - n2o + 3600;
    }

    public String valid(int time) {
        if (time >= 0 && time <= 9) return "0" + time;
        else return time + "";
    }      

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

3 条评论
登录 后参与评论

相关文章

来自专栏python3

习题6:字符串和文本

There are 10 types of people. Those who know binary and those who don't. I said:...

442
来自专栏计算机视觉与深度学习基础

Leetcode 171 Excel Sheet Column Number

Related to question Excel Sheet Column Title Given a column title as appear in...

18610
来自专栏ml

hdu1710(Binary Tree Traversals)(二叉树遍历)

Binary Tree Traversals Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 3...

2745
来自专栏ml

HDUOJ-------单词数

单词数 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

25810
来自专栏计算机视觉与深度学习基础

Leetcode 268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find ...

19110
来自专栏杨熹的专栏

【LEETCODE】模拟面试-39. Combination Sum

和subset区别:规定了子集的sum==target 注意,这里传递的起始位置是i,而不是position+1,but why??? helper(res, ...

2615
来自专栏机器学习入门

LWC 61:738. Monotone Increasing Digits

LWC 61:738. Monotone Increasing Digits 传送门:738. Monotone Increasing Digits Probl...

1837
来自专栏King_3的技术专栏

leetcode-496-Next Greater Element I

1406
来自专栏小樱的经验随笔

51 Nod 1029 大数除法【Java大数乱搞】

1029 大数除法 基准时间限制:4 秒 空间限制:131072 KB 分值: 160 难度:6级算法题 给出2个大整数A,B,计算A / B和A Mod B的...

2685
来自专栏前端说吧

CSS-背景渐变的兼容写法

3365

扫码关注云+社区