刷题日记 24.3.29

lc380. O(1) 时间插入、删除和获取随机元素（MD）

实现RandomizedSet 类：

• RandomizedSet() 初始化 RandomizedSet 对象
• bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
• bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
• int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

示例：

输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]

解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

提示：

• -231 <= val <= 231 - 1
• 最多调用 insert、remove 和 getRandom 函数 2 * 10^5 次
• 在调用 getRandom 方法时，数据结构中 至少存在一个 元素。

---

其实这道题，唯一的难点就是在于，怎么获取一个随机数

元素的存储和查重很容易想到用什么集合

class RandomizedSet {
    List<Integer> nums;
    Map<Integer, Integer> indices;
    Random random;

    public RandomizedSet() {
        nums = new ArrayList<>();
        indices = new HashMap<>();
        random = new Random();
    }
    
    public boolean insert(int val) {
        if (indices.containsKey(val)) {
            return false;
        }
        int idx = nums.size();
        nums.add(val);
        indices.put(val, idx);
        return true;
    }
    
    public boolean remove(int val) {
        if (!indices.containsKey(val)) {
            return false;
        }
        int idx = indices.get(val);
        int last = nums.get(nums.size() - 1);
        nums.set(idx, last);
        indices.put(last, idx);
        nums.remove(nums.size() - 1);
        indices.remove(val);
        return true;
    }
    
    public int getRandom() {
        int randomIdx = random.nextInt(nums.size());
        return nums.get(randomIdx);
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

---

lc238. 除自身以外数组的乘积（MD）

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 **不要使用除法，**且在$O(n)$ 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

---

第一感觉, 类似于前缀和的前缀积. 但是如果真的那么想, 那么只会和正解相去甚远, 最后根本没法ac

所以这道题肯定不是简简单单的用一个数组算前缀乘积

正解如下: 类似于双指针的思想+前缀乘积

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] l = new int[nums.length];
        int[] r = new int[nums.length];
        int[] res = new int[nums.length];
        l[0] = 1;
        r[nums.length - 1] = 1;
        for (int i = 1; i < nums.length; i++) {
            l[i] = l[i - 1] * nums[i - 1];
        }
        for (int i = nums.length - 2; i >= 0; i--) {
            r[i] = r[i + 1] * nums[i + 1];
        }
        for (int i = 0; i < nums.length; i++) {
            res[i] = l[i] * r[i];
        }
        return res;
    }
}

---

lc134. 加油站(MD)

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

示例 1:

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

示例 2:

输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

提示:

• gas.length == n
• cost.length == n
• 1 <= n <= 10^5
• 0 <= gas[i], cost[i] <= 10^4

---

贪心 + 简单的模拟, 没有特别难的地方

可能最大的难处在于如何判断除了第一个之外其他索引是否为起始索引, 我们可以从最后索引开始倒推, 推出来最少油量 > 0 就是起始索引

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < gas.length; i++) {
            int rest = gas[i] - cost[i];
            curSum += rest;
            if (curSum < min) {
                min = curSum;
            }
        }
        if (curSum < 0) {
            return -1;
        }
        if (min >= 0) {
            return 0;
        }
        for (int i = gas.length - 1; i >= 0; i--) {
            int rest = gas[i] - cost[i];
            min += rest;
            if (min >= 0) {
                return i;
            }
        }
        return -1;
    }
}

(我今天做这道题的时候把min的初值设置成了 Integer.MIN_VALUE, 结果半天a不出来, 调了半天也没发现是这里出了问题, 最后还是看了以前做出来的题解代码才发现这里有问题)

---

lc13. 罗马数字转整数(EZ)

罗马数字包含以下七种字符: 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:

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

示例 2:

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

示例 3:

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

示例 4:

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

示例 5:

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

提示：

• 1 <= s.length <= 15
• s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
• 题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
• 题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
• IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
• 关于罗马数字的详尽书写规则，可以参考 罗马数字 - Mathematics 。

---

我相当早的时候就a出来这道题了, 大一上学期的时候, 还没学数据结构与算法. 贴一下那时候的题解

import java.util.*;

class Solution {
    public int romanToInt(String s) {
        int sum = 0;
        int preNum = getValue(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            int num = getValue(s.charAt(i));
            if(preNum < num) {
                sum -= preNum;
            } else {
                sum += preNum;
            }
            preNum = num;
        }
        sum += preNum;
        return sum;
    }
    private int getValue(char ch) {
        switch(ch) {
            case'I': return 1;
            case'V': return 5;
            case'X': return 10;
            case'L': return 50;
            case'C': return 100;
            case'D': return 500;
            case'M': return 1000;
        }
        return 0;
    }
}

我感觉这个题解, 就算给现在的我, 一时间也搞不明白在写什么

这道题没那么复杂, 就是个简单模拟, 从最后一位开始倒推模拟即可

适合新手入门的模拟题

class Solution {
    public int romanToInt(String s) {
        int len = s.length();
        int res = 0;
        for (int i = len - 1; i >= 0; i--) {
            if (s.charAt(i) == 'I') {
                res++;
            } else if (s.charAt(i) == 'V') {
                if (i != 0 && s.charAt(i - 1) == 'I') {
                    res += 4;
                    i--;
                } else {
                    res += 5;
                }
            } else if (s.charAt(i) == 'X') {
                if (i != 0 && s.charAt(i - 1) == 'I') {
                    res += 9;
                    i--;
                } else {
                    res += 10;
                }
            } else if (s.charAt(i) == 'L') {
                if (i != 0 && s.charAt(i - 1) == 'X') {
                    res += 40;
                    i--;
                } else {
                    res += 50;
                }
            } else if (s.charAt(i) == 'C') {
                if (i != 0 && s.charAt(i - 1) == 'X') {
                    res += 90;
                    i--;
                } else {
                    res += 100;
                }
            } else if (s.charAt(i) == 'D') {
                if (i != 0 && s.charAt(i - 1) == 'C') {
                    res += 400;
                    i--;
                } else {
                    res += 500;
                }
            } else if (s.charAt(i) == 'M') {
                if (i != 0 && s.charAt(i - 1) == 'C') {
                    res += 900;
                    i--;
                } else {
                    res += 1000;
                }
            }
        }
        return res;
    }
}

简单易懂, 3岁小孩看了都会写

---

lc42. 接雨水(HD)

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

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

---

本栏目开设以来碰到的第一个hard题, 也是最简单的hard题, 也是面试中最常见的hard题. 简单到什么程度? 思维上完全没有深度, 就是纯纯双指针; 码量也很少, 熟悉的人完全可以直接默写出来.个人感觉这道题不应该评为hard, 最多就mid, 甚至部分mid题的思维深度都比这道题要深

上面说了解法了, 双指针, 直接给代码

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int l = 0, r = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (l < r) {
            leftMax = Math.max(leftMax, height[l]);
            rightMax = Math.max(rightMax, height[r]);
            if (height[l] < height[r]) {
                ans += leftMax - height[l];
                l++;
            } else {
                ans += rightMax - height[r];
                r--;
            }
        }
        return ans;
    }
}

非常简单, 十五分钟不到就能a出来, 最菜hard题非本题莫属

当然, 对双指针不熟悉的人, 这道题应该就是名副其实的hard题了