# C++算法基础题解(第393场周赛)


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

## 题目

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

- 返回结果字符串。

## 测试案例

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

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

## 提示

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

## 解析：

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

## 代码示例

```c++
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 中下标的最大距离。

## 测试案例

> <font color=rad>示例 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。
> </font>

## 提示

{{< note info flat >}}
1 <= nums.length <= 3 \* 105 ， 1 <= nums[i] <= 100
输入保证 nums 中至少有一个质数。
{{< /note >}}

## 解析：

> <font><font>

## 代码示例

```c++
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;
    }
};

```

## 致谢

{{< note default flat >}}
思路来源：[茶灵山艾府](https://leetcode.cn/u/endlesscheng/)
{{< /note >}}