替换字符可以得到的最晚时间

题目

  1. 给你一个字符串 s，表示一个 12 小时制的时间格式，其中一些数字（可能没有）被 “?” 替换。
  2. 12 小时制时间格式为 “HH:MM” ，其中 HH 的取值范围为 00 至 11，MM 的取值范围为 00 至 59。最早的时间为 00:00，最晚的时间为 11:59。
  3. 你需要将 s 中的 所有 “?” 字符替换为数字，使得结果字符串代表的时间是一个 有效 的 12 小时制时间，并且是可能的 最晚 时间。
  • 返回结果字符串。

测试案例

示例 1：
输入： s = “1?:?4”
输出： “11:54”
解释： 通过替换 “?” 字符，可以得到的最晚12小时制时间是 “11:54”。

示例 2：
输入： s = “0?:5?”
输出： “09:59”
解释： 通过替换 “?” 字符，可以得到的最晚12小时制时间是 “09:59”。

提示

s.length == 5，且s[2] 是字符 “:”，除 s[2] 外，其他字符都是数字或 “?”
输入保证在替换 “?” 字符后至少存在一个介于 “00:00” 和 “11:59” 之间的时间。

解析：

利用小时位范围（0-11）逐一遍历，优先置于最外层循环递减，并分层筛选特殊条件

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string findLatestTime(string s) {
        for (int h = 11; ; h--) {
            if (s[0] != '?' && s[0] - '0' != h / 10 || s[1] != '?' && s[1] - '0' != h % 10) {
                continue;
            }
            for (int m = 59; m >= 0; m--) {
                if (s[3] != '?' && s[3] - '0' != m / 10 || s[4] != '?' && s[4] - '0' != m % 10) {
                    continue;
                }
                char ans[6];
                sprintf(ans, "%02d:%02d", h, m);
                return string(ans);
            }
        }
    }
};

质数的最大距离

题目

  1. 给你一个整数数组 nums。
  2. 返回两个（不一定不同的）质数在 nums 中下标的最大距离。

测试案例

示例 1：
输入： nums = [4,2,9,5,3]
输出： 3
解释： nums[1]、nums[3] 和 nums[4] 是质数。因此答案是 |4 - 1| = 3。

示例 2：
输入： nums = [4,8,2,8]
输出： 0
解释： nums[2] 是质数。因为只有一个质数，所以答案是 |2 - 2| = 0。

提示

1 <= nums.length <= 3 * 105 ， 1 <= nums[i] <= 100
输入保证 nums 中至少有一个质数。

解析：

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    bool is_prime(int n) {
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return n >= 2;
    }

public:
    int maximumPrimeDifference(vector<int>& nums) {
        int i = 0;
        while (!is_prime(nums[i])) {
            i++;
        }
        int j = nums.size() - 1;
        while (!is_prime(nums[j])) {
            j--;
        }
        return j - i;
    }
};

致谢

思路来源：茶灵山艾府