刷题日记 24.3.30

lc12. 整数转罗马数字（MD）

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

• I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
• X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
• C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给你一个整数，将其转为罗马数字。

示例 1:

输入: num = 3
输出: "III"

示例 2:

输入: num = 4
输出: "IV"

示例 3:

输入: num = 9
输出: "IX"

示例 4:

输入: num = 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例 5:

输入: num = 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

• 1 <= num <= 3999

---

贪心法+打表，非常简单

class Solution {
    public String intToRoman(int num) {
        int[] val = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] s = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        String res = "";
        while (num != 0) {
            for (int i = 0; i < 13; i++) {
                if (num >= val[i]) {
                    num -= val[i];
                    res += s[i];
                    break;
                }
            }
        }
        return res;
    }
}

---

lc135.分发糖果（HD）

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

提示：

• n == ratings.length
• 1 <= n <= 2 * 10^4
• 0 <= ratings[i] <= 2 * 10^4

---

又是一道不配被称为hard的hard题

双指针，左右两边分别遍历即可。对于糖果的具体分配，因为我们要求是最少糖果，所以对于符合条件的（相邻两个孩子评分更高的孩子会获得更多的糖果）就多给一个，不符合条件的只给一个糖（也就是贪心法）

class Solution {
    public int candy(int[] ratings) {
        int[] candies = new int[ratings.length];
        candies[0] = 1;
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            } else {
                candies[i] = 1;
            }
        }
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i + 1] + 1, candies[i]);
            }
        }
        int res = 0;
        for (int i = 0; i < ratings.length; i++) {
            res += candies[i];
        }
        return res;
    }
}

---

lc58. 最后一个单词的长度（EZ）

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例 1：

输入：s = "Hello World"
输出：5
解释：最后一个单词是“World”，长度为5。

示例 2：

输入：s = "   fly me   to   the moon  "
输出：4
解释：最后一个单词是“moon”，长度为4。

示例 3：

输入：s = "luffy is still joyboy"
输出：6
解释：最后一个单词是长度为6的“joyboy”。

提示：

• 1 <= s.length <= 10^4
• s 仅有英文字母和空格 ' ' 组成
• s 中至少存在一个单词

---

翻转计数，从最后一个下标开始往前倒推，推到出现第一个空格就终止倒推

最开始没注意到结尾也可能有空格，wa了一发

然后发现样例2结尾是有空格的，对结尾处空格做特判即可

class Solution {
    public int lengthOfLastWord(String s) {
        int res = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == ' ' && res != 0) {
                break;
            } else if (s.charAt(i) == ' ' && res == 0) {
                continue;
            }
            res++;
        }
        return res;
    }
}

---

lc14. 最长公共前缀（EZ）

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 仅由小写英文字母组成

---

最开始写的代码太丑陋了，时间复杂度偏高，今天重新写了个复杂度低一点的

其实，查找前缀这个问题，完全能用二分法。我们都知道，二分法首先计算区间的中间位置坐标，然后判断中间位置能否满足特定要求，然后根据返回的结果对区间进行缩小，最后得到精确的结果。

我们首先先定义一个新名词，前缀坐标，就是公共前缀的最后一个字符的下标值。前缀坐标必然大于0且小于字符串数组里面最短的字符串的字符串长度。我们要查找最长公共前缀，也就是最大的前缀坐标，那么我们就可以进行二分，左端点 l = 0，右端点 r = 字符串数组里面最短的字符串的字符串长度，此时我们计算出来的中间节点坐标值应该是 （r - l + 1 ) / 2 + l。

我们只需要进行特判——中间节点坐标对应的字符是否和其他字符串中该坐标对应的字符相等——如果相等，说明我们需要的最大前缀坐标应该在中间节点的右边或者就是在中间节点；如果不等，说明我们需要的最大前缀坐标应该在中间节点的左边。根据这个情况去调整区间长度，最后就能得到最大前缀坐标，也能得到最长公共前缀

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int minLength = Integer.MAX_VALUE;
        for (String str : strs) {
            minLength = Math.min(minLength, str.length());
        }
        int l = 0, r = minLength;
        while (l < r) {
            int mid = (r - l + 1) / 2 + l;
            if (isCommonPrefix(mid, strs)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return strs[0].substring(0, l);
    }

    private boolean isCommonPrefix(int length, String[] strs) {
        String str0 = strs[0].substring(0, length);
        int count = strs.length;
        for (int i = 0; i < count; i++) {
            String str = strs[i];
            for (int j = 0; j < length; j++) {
                if (str0.charAt(j) != str.charAt(j)) {
                    return false;
                }
            }
        }
        return true;
    }
}

---

lc151. 反转字符串中的单词（MD）

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

• 1 <= s.length <= 10^4
• s 包含英文大小写字母、数字和空格 ' '
• s 中 至少存在一个 单词

---

首先要说明的是，原题中还追加了一个进阶要求：使用空间复杂度为$O(1)$ 的原地算法完成这道题。实际上，Java语言因为 String 的不可变性，所以不可能实现$O(1)$ 的空间复杂度，以下给出的代码的空间复杂度为$O(n)$

对于这道题，我们很明显能想到一类数据结构 栈/队列，栈先进先出，队列后进后出，能满足我们反转单词的要求。我们只需要提取出单词，然后存进这类数据结构，然后再把这些单词弹出来，就能实现反转

class Solution {
    public String reverseWords(String s) {
        int l = 0, r = s.length() - 1;
        while (l <= r && s.charAt(l) == ' ') {
            l++;
        }
        while (l <= r && s.charAt(r) == ' ') {
            r--;
        }
        Deque<String> deq = new LinkedList<>();
        StringBuilder word = new StringBuilder();

        while (l <= r) {
            char c = s.charAt(l);
            if (word.length() != 0 && c == ' ') {
                deq.offerFirst(word.toString());
                word.setLength(0);
            } else if (c != ' ') {
                word.append(c);
            }
            l++;
        }

        deq.offerFirst(word.toString());
        return String.join(" ", deq);
    }
}