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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PPV课数据科学社区

走近 Python (类比 JS)

Python 是一门运用很广泛的语言,自动化脚本、爬虫,甚至在深度学习领域也都有 Python 的身影。作为一名前端开发者,也了解 ES6 中的很多特性借鉴自 ...

37910
来自专栏机器学习入门

挑战程序竞赛系列(74):4.3强连通分量分解(1)

挑战程序竞赛系列(74):4.3强连通分量分解(1) 传送门:POJ 2186: Popular Cows 题意: 每头牛都想成为牛群中的红人。给定N头牛的牛...

1908
来自专栏Albert陈凯

2018-06-13 关于Java集合的小抄

1263
来自专栏Danny的专栏

【J2SE快速进阶】——递归算法

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

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

getline函数(精华版)

在我的印象中,getline函数经常出现在自己的视野里,模糊地记得它经常用来读取字符串 。但是又对它的参数不是很了解,今天又用到了getline函数,现在来细细...

2834
来自专栏大闲人柴毛毛

贪心算法(五)——迪杰斯特拉算法

问题描述 给一个有向无环带权图,并给一个起点,求出该原点到所有顶点的最短路径。 ? 数据结构 dis: Map<String,Integer> dis; ...

3539
来自专栏文武兼修ing——机器学习与IC设计

分离链接的散列散列代码实现

散列 散列为一种用于以常数平均时间执行插入,删除和查找的技术。一般的实现方法是使通过数据的关键字可以计算出该数据所在散列中的位置,类似于Python中的字典。关...

3538
来自专栏加米谷大数据

Scala语言:既存类型

Scala既存类型语法: ? 既存类型具有 T forSome {Q}的形式,Q 是一个类型声明的序列。设t1[tps1]>:L1<:U1,...,tn[tps...

3496
来自专栏蓝天

汇编指令: VERW、WAIT、WBINVD、WRSHR、WRMSR、XADD、XBTS、XCHG、

632
来自专栏mathor

导入:什么是数据结构,为什么要学习数据结构,约瑟夫环的数组实现

1255

扫码关注云+社区