标签： medium

目标

给你一个仅由小写英文字母组成的字符串 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();
    }

}

性能

目标

给你一个大小为 m x n 的矩阵 board 表示甲板，其中，每个单元格可以是一艘战舰 'X' 或者是一个空位 '.' ，返回在甲板 board 上放置的 战舰 的数量。

战舰 只能水平或者垂直放置在 board 上。换句话说，战舰只能按 1 x k（1 行，k 列）或 k x 1（k 行，1 列）的形状建造，其中 k 可以是任意大小。两艘战舰之间至少有一个水平或垂直的空位分隔 （即没有相邻的战舰）。

示例 1：

输入：board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
输出：2

示例 2：

输入：board = [["."]]
输出：0

说明：

• m == board.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] 是 '.' 或 'X'

进阶：你可以实现一次扫描算法，并只使用 O(1) 额外空间，并且不修改 board 的值来解决这个问题吗？

思路

这道题的描述很容易让人误解成只允许在'X'的位置上建造战舰，并且满足规则战舰不能相邻，问最多能造多少战舰。

但实际上题目的含义是，有一个棋盘，棋盘上放着战舰，每个战舰由k个'X'表示，战舰的形状是 1*k 或者 k*1，战舰的排放规则是不能相邻，让我们统计战舰数量。

刚开始想到的是使用一个二维数组保存是否访问过，从第一行开始从左到右访问，如果为'X'则向下延伸并将visited置为true。

后来看了题解，可以将原数组的'X'置为其它标记，这样就不用额外的空间了。

进阶的问题是不修改board，根据排列规则，仅统计战舰的起点，即上面与左边不能为'X'。

也有网友使用dfs来处理，子节点是下方与右侧的元素，如果是'X'则改为其它标记，否则返回。其实直接循环遍历更方便一些。

还有网友使用并查集计算连通分量，其实也没有必要。并查集主要用于快速判断元素是否属于同一个集合，统计集合中元素个数，集合元素的合并。这里仅需要连通分量个数，并且连通的关系很简单，纵向或横向，并不像图遍历那样复杂，直接计数即可。

代码

/**
 * @date 2024-06-11 8:40
 */
public class CountBattleships419 {

    /**
     * 网友题解
     * 一次扫描，不使用额外空间，不修改board
     * 统计左上顶点
     * 需满足条件：顶点左侧与上侧不能为'X'
     */
    public int countBattleships_v2(char[][] board) {
        int ans = 0;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == 'X' &&
                        (j == 0 || board[i][j - 1] != 'X') &&
                        (i == 0 || board[i - 1][j] != 'X')) {
                    ans++;
                }
            }
        }
        return ans;
    }

    /**
     * 看了题解，可以直接将board中的'X'置为'.'，这样就不需要额外的visited数组了
     * 一次扫描，但是修改了board
     */
    public int countBattleships_v1(char[][] board) {
        int res = 0;
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            int j = 0;
            while (j < n) {
                if (board[i][j] == 'X') {
                    res++;
                    int k = i + 1;
                    while (k < m && board[k][j] == 'X') {
                        board[k][j] = '.';
                        k++;
                    }
                    while (j < n && board[i][j] == 'X') {
                        board[i][j] = '.';
                        j++;
                    }
                } else {
                    j++;
                }
            }
        }

        return res;
    }

    /**
     * 一次扫描，但是使用了额外的空间
     */
    public int countBattleships(char[][] board) {
        int res = 0;
        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            int j = 0;
            while (j < n) {
                if (visited[i][j]) {
                    j++;
                    continue;
                }
                if (board[i][j] == 'X') {
                    res++;
                    int k = i;
                    while (k < m && board[k][j] == 'X') {
                        visited[k][j] = true;
                        k++;
                    }
                    while (j < n && board[i][j] == 'X') {
                        visited[i][j] = true;
                        j++;
                    }
                } else {
                    j++;
                }
            }
        }

        return res;
    }
}

性能

使用额外空间

不使用额外空间

目标

给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回 承载所有人所需的最小船数 。

示例 1：

输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)

示例 2：

输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)

示例 3：

输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)

说明：

• 1 <= people.length <= 5 * 10^4
• 1 <= people[i] <= limit <= 3 * 10^4

思路

给定一个数组，数组元素是待救援人员的体重，每条救生艇最多载两人且体重不超过限制，问最少需要多少救生艇。

尽可能多地让两人乘一艇，将体重轻的与重的搭配，如果都是轻的则造成运力浪费。

因此先按体重从小到大排序，然后使用双指针将重的与轻的搭配即可。

代码

/**
 * @date 2024-06-10 21:18
 */
public class NumRescueBoats881 {

    public int numRescueBoats(int[] people, int limit) {
        int n = people.length;
        Arrays.sort(people);
        int end = Arrays.binarySearch(people, limit);
        if (end < 0) {
            end = -end - 1;
        }
        // [end,n) 下标小于end的元素均比limit小，end 为0则可直接返回n
        int res = n - end;
        int start = 0;
        while (start < end) {
            // 如果start == end -1 即仅剩start一个元素 不再重复累加
            // start < end 防止end - 1为负即end==0
            // 由于取开区间，不包括end，因此从end-1开始
            while (start < end - 1 && people[start] + people[end - 1] > limit) {
                end--;
                res++;
            }
            start++;
            end--;
            res++;
        }
        return res;
    }
}

性能