标签： medium

目标

给你一个整数数组 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编译器优化。

目标

句子 是由若干个单词组成的字符串，单词之间用单个空格分隔，其中每个单词可以包含数字、小写字母、和美元符号 '$' 。如果单词的形式为美元符号后跟着一个非负数值(A word represents a price if it is a sequence of digits preceded by a dollar sign.)，那么这个单词就表示一个 价格 。

• 例如 "$100"、"$23" 和 "$6" 表示价格，而 "100"、"$" 和 "$1e5 不是。

给你一个字符串 sentence 表示一个句子和一个整数 discount 。对于每个表示价格的单词，都在价格的基础上减免 discount% ，并 更新 该单词到句子中。所有更新后的价格应该表示为一个 恰好保留小数点后两位 的数字。

返回表示修改后句子的字符串。

注意：所有价格 最多 为 10 位数字。

示例 1：

输入：sentence = "there are $1 $2 and 5$ candies in the shop", discount = 50
输出："there are $0.50 $1.00 and 5$ candies in the shop"
解释：
表示价格的单词是 "$1" 和 "$2" 。 
- "$1" 减免 50% 为 "$0.50" ，所以 "$1" 替换为 "$0.50" 。
- "$2" 减免 50% 为 "$1" ，所以 "$1" 替换为 "$1.00" 。

示例 2：

输入：sentence = "1 2 $3 4 $5 $6 7 8$ $9 $10$", discount = 100
输出："1 2 $0.00 4 $0.00 $0.00 7 8$ $0.00 $10$"
解释：
任何价格减免 100% 都会得到 0 。
表示价格的单词分别是 "$3"、"$5"、"$6" 和 "$9"。
每个单词都替换为 "$0.00"。

说明：

• 1 <= sentence.length <= 105
• sentence 由小写英文字母、数字、' ' 和 '$' 组成
• sentence 不含前导和尾随空格
• sentence 的所有单词都用单个空格分隔
• 所有价格都是 正 整数且不含前导零
• 所有价格 最多 为 10 位数字
• 0 <= discount <= 100

思路

在许多脚本与命令中经常会使用 $+数字 形式的占位符来替换传入的参数。这个题就是要我们提取这个数字并进行一些操作然后再将处理后的数字替换回去。

知识点：

• 如何保留两位小数，可以使用String.format("%.2f", 浮点数); 类似C语言的字符串格式化。DecimalFormat df = new DecimalFormat("0.00"); df.format(浮点数);
• 如何判断是否为数字，Character.isDigit 该API处理了不同code point上的数字，这里我们只需处理ISO-LATIN-1字符集的数字即可。直接比较c >= '0' c <='9'即可。
• 正则表达式断言，非捕获匹配以及捕获组的替换。匹配到的字符串被保存在group(0)，group(1~n)可以获取正则表达式中的捕获组。值得注意的是断言并不会出现在匹配的字符串中，而非捕获匹配不能通过group(1~n) 访问，但还是会作为匹配字符被匹配到。appendReplacement会替换匹配到的字符串即group(0)。

需要注意防止数字的溢出，以及边界条件的处理。

官网是根据空格拆分为单词，然后再对单词进行处理，最后使用String.join将单词合并。

有网友使用JS直接用正则表达式匹配数字，并使用匿名函数计算折扣并替换。

leetcode 中Java不能用java.util.regex包，但是可以使用 splitWord.matches("(?<=(^|\\s)\\$)(\\d+)(?=\\s|$)") 判断是否是目标形式，也算是一种判断是否为数字的手段。当然我们也可以不判断数字，直接使用Long.parseLong解析并捕获异常，不处理异常即可。

代码

/**
 * @date 2024-06-18 0:39
 */
public class DiscountPrices2288 {

    /**
     * 遇到$就记录随后的数字，如果遇到非数字就将其append到buffer
     * 如果在遇到分隔符' '之前都是数字，那么计算折扣然后append到buffer
     * 里面需要特别主要在同一个单词内含有多个'$'导致多次开启记录数字
     * 只有开头以及前一个字符是' '的情况下才开启记录数字
     * 另外需要在循环外处理最后一个单词的数字，如果存在的话
     * 还要特别主要数字溢出
     */
    public String discountPrices(String sentence, int discount) {
        // BigDecimal不让用
//        BigDecimal mul = new BigDecimal((100 - discount) / 100.0);
        double mul = (100 - discount) / 100.0;
        DecimalFormat df = new DecimalFormat("0.00");
        int n = sentence.length();
        boolean skip = false;
        StringBuilder sb = new StringBuilder();
        StringBuilder num = new StringBuilder();
        for (int i = 0; i < n; i++) {
            char c = sentence.charAt(i);
            if (c != '$' || num.length() > 0) {
                if (!skip) {
                    sb.append(c);
                } else {
                    if (c >= '0' && c <= '9') {
                        num.append(c);
                    } else if (c == ' ' && num.length() > 0) {
                        // 这里应使用long
                        long origin = Long.parseLong(num.toString());
//                        BigDecimal discnt = new BigDecimal(origin).multiply(mul).setScale(2, BigDecimal.ROUND_HALF_UP);
                        double discnt = origin * mul;
                        sb.append(df.format(discnt)).append(c);
                        num = new StringBuilder();
                        skip = false;
                    } else {
                        sb.append(num).append(c);
                        num = new StringBuilder();
                        skip = false;
                    }
                }
            } else if (i == 0 || sentence.charAt(i - 1) == ' ') {
                // 这里不用else if(!skip)，因为num.length >0 说明skip 为true
                skip = true;
                sb.append(c);
            } else {
                // 处理 $$$0 的情况
                if (skip) {
                    skip = false;
                }
                sb.append(c);
            }
        }
        // 处理结尾没有空格的情况
        if (num.length() > 0) {
            long origin = Long.parseLong(num.toString());
            double discnt = origin * mul;
            sb.append(df.format(discnt));
        }
        return sb.toString();
    }

}

性能