返回目录

题目描述

警察在侦破一个案件时，得到了线人给出的可能犯罪时间，形如 “HH:MM” 表示的时刻。

根据警察和线人的约定，为了隐蔽，该时间是修改过的，

解密规则为：利用当前出现过的数字，构造下一个距离当前时间最近的时刻，则该时间为可能的犯罪时间。

每个出现数字都可以被无限次使用。

输入描述

形如HH:SS字符串，表示原始输入。

输出描述

形如HH:SS的字符串，表示推理处理的犯罪时间。

备注

1.可以保证现任给定的字符串一定是合法的。

例如，“01:35”和“11:08”是合法的，“1:35”和“11:8”是不合法的。

2.最近的时刻可能在第二天。

示例：

题目解析

解密规则为：利用当前出现过的数字，构造下一个距离当前时间最近的时刻，则该时间为可能的犯罪时间。

Python算法源码

import itertools
import re

def get_result(hour, minute):
    # 创建字符集合
    char_set = set(hour + minute)
    char_list = list(char_set)
  
    # 生成排列组合
    perms = itertools.permutations(char_list, len(char_list))
  
    # 过滤符合条件的时间格式
    res = []
    for perm in perms:
        time_str = ''.join(perm)
        if re.match(r"(([01][0-9])|([2][0-3]))[0-5][0-9]", time_str):
            res.append(time_str)
  
    # 排序并获取最近的时间
    res.sort()
    index = res.index(hour + minute)
  
    recent_time = res[(index + 1) % len(res)]
  
    # 格式化时间
    recent_time = recent_time[:2] + ":" + recent_time[2:]
    return recent_time

def dfs(arr, path, res):
    if len(path) == 4:
        time_str = ''.join(path)
        if re.match(r"(([01][0-9])|([2][0-3]))[0-5][0-9]", time_str):
            res.append(time_str)
        return
  
    for c in arr:
        path.append(c)
        dfs(arr, path, res)
        path.pop()

def main():
    user_input = input().split(":")
    hour = user_input[0]
    minute = user_input[1]
  
    char_set = set(hour + minute)
    char_list = list(char_set)
  
    res = []
    dfs(char_list, [], res)
  
    res.sort()
    index = res.index(hour + minute)
  
    recent_time = res[(index + 1) % len(res)]
    recent_time = recent_time[:2] + ":" + recent_time[2:]
  
    print(recent_time)

if __name__ == "__main__":
    main()

C算法源码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char res[256][5] = {'\0'};
int res_size = 0;

typedef struct Point {
    int x;
    int y;
} Point;

//计算两个点的距离
int distance(Point p1, Point p2) {
    return abs(p1.x - p2.x) + abs(p1.y - p2.y);
}

// 合法的 HHMM 时间格式判断
int isValidTime(const char time[]) {
    // HH判断
    if (time[0] == '0' || time[0] == '1') {
        if (time[1] < '0' || time[1] > '9') return 0;
    } else if (time[0] == '2') {
        if (time[1] < '0' || time[1] > '3') return 0;
    } else {
        return 0;
    }

    // MM判断
    if (time[2] >= '0' && time[2] <= '5') {
        if (time[3] >= '0' && time[3] <= '9') {
            return 1;
        } else {
            return 0;
        }
    } else {
        return 0;
    }
}

// 使用 DFS 算法进行遍历
void dfs(char arr[], int arr_size, char path[], int path_size) {
    if (path_size == 4) {
        if (isValidTime(path)) {
            strcpy(res[res_size++], path);
        }
        return;
    }

    int i = 0;
    while (arr[i] != '\0') {
        char c = arr[i];

        path[path_size] = c;
        dfs(arr, arr_size, path, path_size + 1);
        path[path_size] = '\0';

        i++;
    }
}

//比较函数，用于排序
int cmp(const void *a, const void *b) {
    return strcmp((char *) a, (char *) b);
}

// ，计算两个数的和
int sum(int x, int y) {
    return x + y;
}

// 主函数
int main() {
    char s[6];
    gets(s);

    // arr记录后面求解排列的（去重）可用字符
    char arr[5] = {'\0'};
    int arr_size = 0;

    int set[128] = {0}; // 记录哪些字符已使用过，初始都未使用过
    for (int i = 0; i < 5; i++) {
        char c = s[i];

        if (c == ':' || set[c]) continue;

        set[c] = 1;
        arr[arr_size++] = c;
    }

    // 记录排列
    char path[5] = {'\0'};
    int path_size = 0;

    // 求排列
    dfs(arr, arr_size, path, path_size);

    // 对所有合法排列进行字典序升序
    qsort(res, res_size, sizeof(res[0]), cmp);

    // （原始输入）当前时间
    char curTime[5] = {'\0'};
    strncat(curTime, s, 2);
    strncat(curTime, s + 3, 2);

    // 找到当前时间在所有排列中的位置 i
    int i = 0;
    while (strcmp(res[i], curTime) != 0) {
        i++;
    }

    // i + 1 位置就是当前时间的下一个时间，如果 i + 1 越界，则循环到开头位置
    char *ans;
    if (i == res_size - 1) {
        ans = res[0];
    } else {
        ans = res[i + 1];
    }

    // 打印结果
    char hour[3] = {'\0'};
    strncpy(hour, ans, 2);

    char minute[3] = {'\0'};
    strncpy(minute, ans + 2, 2);

    printf("%s:%s\n", hour, minute);

    return 0;
}

Java算法源码

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        String[] split = line.split(":");
        String hour = split[0];
        String minute = split[1];
        System.out.println(getResult(hour, minute));
    }

    public static String getResult(String hour, String minute) {
        HashSet<Character> set = new HashSet<>();
        for (char c : hour.toCharArray()) set.add(c);
        for (char c : minute.toCharArray()) set.add(c);
        Character[] arr = set.toArray(new Character[0]);

        ArrayList<String> res = new ArrayList<>();
        dfs(arr, new StringBuilder(), res);

        res.sort(String::compareTo);

        int index = res.indexOf(hour + minute);
        String recentTime;
        if (index == res.size() - 1) {
            recentTime = res.get(0);
        } else {
            recentTime = res.get(index + 1);
        }

        StringBuilder ans = new StringBuilder(recentTime);
        ans.insert(2, ":");
        return ans.toString();
    }

    public static void dfs(Character[] arr, StringBuilder path, ArrayList<String> res) {
        if (path.length() == 4) {
            String timeStr = path.toString();
            if (isValidTime(timeStr)) {
                res.add(timeStr);
            }
            return;
        }

        for (Character c : arr) {
            path.append(c);
            dfs(arr, path, res);
            path.deleteCharAt(path.length() - 1);
        }
    }

    public static boolean isValidTime(String timeStr) {
        return timeStr.matches("(([01][0-9])|([2][0-3]))[0-5][0-9]");
    }
}