shelterofly

目标

给你一个整数数组 nums。

返回两个（不一定不同的）质数在 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 * 10^5
• 1 <= nums[i] <= 100
• 输入保证 nums 中至少有一个质数。

思路

找出数组中质数的最远距离（下标之差）。

知识点：

• 自然数：非负整数
• 质数：只能被1和它本身整除的大于1的自然数
• 合数：不是质数的大于1的自然数

如果 n 是一个合数，那么它可以分解为两个自然数 a、b 的乘积，即 n = a * b。设 a ≤ b ，如果 a ≥ √n ，那么 a * b ≥ n。 也就是说 a、b 要么同时等于 √n，要么一个大于一个小于 √n，不可能同时大于√n。于是判断一个数是否是质数，只需判断 n 是否能够整除 1 ~ √n 。

除了2的偶数都不是质数，因此自增的步长可以设为2。

更进一步分析，所有质数除了2和3外，都形如 6k - 1 或 6k + 1。考虑 n % 6 ：

• 余数为0，首先6不是质数，能被6整除的数也不是质数
• 余数为2、4，表明能够被2整除，不是质数
• 余数为3，表明能被3整除，不是质数
• 余数为5，6k - 1
• 余数为1，6k + 1

从5开始，步长可以设为6。

代码

/**
 * @date 2024-07-02 9:13
 */
public class MaximumPrimeDifference3115 {

    public int maximumPrimeDifference_v2(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (!isPrimeNumber(nums[i])) {
            i++;
        }
        while (!isPrimeNumber(nums[j])) {
            j--;
        }
        return j - i;
    }

    public boolean isPrimeNumber(int num) {
        if (num == 1) {
            return false;
        }
        if (num == 2) {
            return true;
        }
        if (num % 2 == 0) {
            return false;
        }
        for (int i = 3; i * i <= num; i += 2) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static boolean isPrimeNumber_v1(int num) {
        if (num <= 1) {
            return false;
        }
        if (num <= 3) {
            return true; 
        }
        if (num % 2 == 0 || num % 3 == 0) {
            return false; 
        }
        for (int i = 5; i * i <= num; i += 6) {
            // i = 6k - 1, i + 2 = 6k + 1
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
}

性能

目标

给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以完成以下行为：

• 选择 s 的任一非空子字符串，可能是整个字符串，接着将字符串中的每一个字符替换为英文字母表中的前一个字符。例如，'b' 用 'a' 替换，'a' 用 'z' 替换。

返回执行上述操作 恰好一次 后可以获得的 字典序最小 的字符串。

子字符串 是字符串中的一个连续字符序列。

现有长度相同的两个字符串 x 和 字符串 y ，在满足 x[i] != y[i] 的第一个位置 i 上，如果 x[i] 在字母表中先于 y[i] 出现，则认为字符串 x 比字符串 y 字典序更小 。

示例 1：

输入：s = "cbabc"
输出："baabc"
解释：我们选择从下标 0 开始、到下标 1 结束的子字符串执行操作。 
可以证明最终得到的字符串是字典序最小的。

示例 2：

输入：s = "acbbc"
输出："abaab"
解释：我们选择从下标 1 开始、到下标 4 结束的子字符串执行操作。
可以证明最终得到的字符串是字典序最小的。

示例 3：

输入：s = "leetcode"
输出："kddsbncd"
解释：我们选择整个字符串执行操作。
可以证明最终得到的字符串是字典序最小的。

说明：

• 1 <= s.length <= 3 * 10^5
• s 仅由小写英文字母组成

思路

求对一个字符串的 非空子串 进行操作后字典序最小的字符串，两个字符串 第一个不同的字母 在字母表 越先出现 其字典序就越小。字符串仅由小写字母组成，可进行的操作指将子串的每一个字母替换为其在字母表中的前一个字母，a 前面的字母定义为 z。

关键在于非空子串如何选，根据题意可知，如果子串不含字母 a 操作总能使字典序变小。字符串前面字符的字典序越小整个字符串的字典序就越小，因此可以从前向后遍历直到遇到字母 a 作为子串。如果字符串字母均为 a，操作总会使字典序变大，显然将最后一个 a 改为 z 可以使操作后的字符串字典序最小。

代码

/**
 * @date 2024-06-27 0:05
 */
public class SmallestString2734 {

    public String smallestString_v1(String s) {
        int i = 0;
        int n = s.length();
        char[] chars = s.toCharArray();
        while (i < n && chars[i] == 'a') {
            i++;
        }
        while (i < n && chars[i] != 'a') {
            chars[i++]--;
        }
        if (i == n && s.charAt(n - 1) == 'a') {
            chars[n - 1] = 'z';
        }
        return new String(chars);
    }

    public String smallestString_v2(String s) {
        int i = 0;
        int n = s.length();
        StringBuilder sb = new StringBuilder(s);
        while (i < n && s.charAt(i) == 'a') {
            i++;
        }
        if (i == n) {
            sb.setCharAt(n - 1, 'z');
            return sb.toString();
        }
        while (i < n && s.charAt(i) != 'a') {
            sb.setCharAt(i, (char) (s.charAt(i++) - 1));
        }
        return sb.toString();
    }
}

性能

使用 StringBuilder 显示用时更少，我试了一下与if判断的位置没关系，按道理来说直接数组访问比方法调用开销更小，new StringBuilder(s) 与 s.toCharArray 都进行了数组拷贝。我能想到的解释就是大家都用的StringBuilder，然后这段代码被JIT编译器优化。