LeetCode面试热题150中12-18题学习笔记（用Java语言描述）

Day 03

12、$O(1)$时间插入、删除元素和获取元素

需求：实现RandomizedSet 类：

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

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

代码表示

class RandomizedSet {
    List<Integer> nums; //成员变量，用来存储集合中的元素
    Map<Integer, Integer> indices;//键为集合中的元素，值为该元素在nums列表中的索引。
    Random random;

    public RandomizedSet() {    //初始化nums列表，indices映射及random对象。
        nums = new ArrayList<Integer>();
        indices = new HashMap<Integer, Integer>();
        random = new Random();
    }

    public boolean insert(int val) {    //插入操作
        if (indices.containsKey(val)) {
            return false;
        }
        int index = nums.size();
        nums.add(val);
        indices.put(val, index);
        return true;
    }

    public boolean remove(int val) {    //删除操作
        if (!indices.containsKey(val)) {
            return false;
        }
        int index = indices.get(val);   //检查元素是否在集合中
        int last = nums.get(nums.size() - 1);
        nums.set(index, last);
        indices.put(last, index);
        nums.remove(nums.size() - 1);
        indices.remove(val);
        return true;
    }

    public int getRandom() {
        int randomIndex = random.nextInt(nums.size());
        return nums.get(randomIndex);
    }
}

13、除自身以外数组的乘积

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

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

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

思路

• 计算前缀乘积：对于数组中的每个元素，计算其左侧所有元素的乘积；
• 计算后缀乘积：对于数组中的每个元素，计算其右侧所有元素的乘积；
• 最终结果：将每个元素的前缀乘积和后缀乘积相乘，得到最终结果。

代码表示

public class Q13_1 {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] answer = new int[length]; //创建和nums长度相同的answer数组，存储最终结果。

        //计算前缀乘积
        answer[0] = 1;  //第一个元素的左侧无元素
        for (int i = 1; i < length; i++) {  //从第二个元素开始遍历
            answer[i] = answer[i - 1] * nums[i - 1];
        }

        //计算右缀乘积
        int rightProduct = 1;
        for (int i = length - 1; i >= 0; i--) { //从数组最后一个元素开始遍历
            answer[i] = answer[i] * rightProduct;
            rightProduct *= nums[i];
        }
        return answer;
    }
}

复杂度分析

时间复杂度：$O(n)$,代码中使用了两个 for 循环，每个循环都只遍历一遍数组。

空间复杂度：$O(1)$

14、加油站

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

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

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

代码表示

public class Q14_1 {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0;   //记录所有加油站的汽油总量。
        int totalCost = 0;  //记录环绕一周所需的汽油总量
        int currentGas = 0; //记录从某个加油站出发到当前加油站时油箱中的剩余汽油量
        int start = 0;  //记录可能的出发加油站编号

        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i];		//累加所有加油站的总量
            totalCost += cost[i];   //累加需要的汽油总量
            currentGas += gas[i] - cost[i];//计算从当前加油站出发到下一个加油站油箱剩余油量

            if (currentGas < 0) {
                currentGas = 0;
                start = i + 1;
            }
            /*说明从之前记录的 start 加油站出发无法到达当前加油站，
            需要将 start 更新为下一个加油站编号（i + 1），并将 currentGas 重置为 0。*/
        }

        //遍历结束后，进行判断
        if (totalGas < totalCost) {
            return -1;
        }
        return start;
    }
}

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(1)$

15、分发糖果

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

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

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

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

代码表示

public class Q15_1 {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n]; //创建一个长度为n的数组，记录每个孩子拿到的糖果数。

        for (int i = 0; i < n; i++) {   //先每人一个
            candies[i] = 1;
        }

        /*从左到右遍历。
         * 如果当前孩子的评分比前一个孩子高，则当前孩子的糖果数比前一个孩子多 1   */
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        /*从右到左遍历
         * 从倒数第二个孩子开始遍历数组，如果当前孩子的评分比后一个孩子高
         * 则当前孩子的糖果数要取当前值和后一个孩子糖果数加 1 中的较大值
         * 以保证满足相邻孩子评分更高获得更多糖果的条件。*/
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }

        /*计算总糖果数
         *   遍历 candies 数组，将每个孩子的糖果数累加起来，得到总共需要准备的糖果数。 */
        int sum = 0;
        for (int candy : candies) { //增强 for 循环
            sum += candy;
        }
        return sum;

    }
}

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(n)$

16、接雨水问题

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

方法一

动态规划

思路

计算每个柱子能够接住的雨水量，然后将所有柱子的雨水量累加起来。

对于每个柱子，它能接住的雨水量取决于其左侧最高柱子的高度和右侧最高柱子的高度中的较小值，再减去该柱子自身的高度。

代码演示

public class Q16_1 {
    public int trap(int[] height) {
        int n = height.length;

        if (n == 0) {   //如果数组长度为0，说明无柱子
            return 0;
        }

        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        /*  记录左侧的最大高度
         *   第一个柱子的最大高度等于自身高度
         *   从第二个开始，对于每个柱子，左侧的最大高度leftMax[i]等于前一个
         *   柱子的左侧最大高度和当前柱子高度中的最大值   */
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        /*  记录右侧的最大高度
         *   最后一个柱子的右侧高度等于自身的高度
         *   从倒数第二个柱子开始，对于每个柱子，右侧的最大高度等于后一个
         *   柱子的右侧最大高度和当前柱子高度中的最大值   */
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        /*计算每个柱子的接水量并累加*/
        int result = 0;
        for (int i = 0; i < n; i++) {
            result += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return result;
    }
}

复杂度分析

时间复杂度：$O(n)$，n是数组长度。对数组进行三次遍历。

空间复杂度：$O(n)$,使用了两个长度为 n 的数组存储左右的最大高度。

方法二

双指针

核心思路

使用两个指针分别从数组的两端开始向中间移动，同时记录左右两侧的最大高度，以此计算每个柱子能接住的雨水量。

代码表示

public class Q16_2 {

    public int trap(int[] height) {
        /*初始化*/
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int result = 0;


        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    result += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    result += rightMax - height[right];
                }
                right--;
            }
        }
        return result;
    }

}

此方法理解较第一种困难。

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(1)$,只使用常数级的额外空间。

17、罗马数字转整数

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

给定一个罗马数字，将其转换成整数。

代码表示

import java.util.Map;
import java.util.HashMap;

public class Q17_1 {
    public int romanToInt(String s) {

        /*创建映射表
         *   将罗马数字存储为键，对应整数为值。*/
        Map<Character, Integer> romanMap = new HashMap<>();
        romanMap.put('I', 1);
        romanMap.put('V', 5);
        romanMap.put('X', 10);
        romanMap.put('L', 50);
        romanMap.put('C', 100);
        romanMap.put('D', 500);
        romanMap.put('M', 1000);

        int result = 0;
        int prevValue = 0;  //初始化变量

        //从右到左遍历字符串
        for (int i = s.length() - 1; i >= 0; i--) {
            int currentValue = romanMap.get(s.charAt(i));
            if (prevValue < currentValue) {
                result -= currentValue;
            } else {
                result += currentValue;
            }
            prevValue = currentValue;
        }
        return result;
    }
}

18、整数转罗马数字

代码表示

public class Q18_1 {
    public String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "Ix", "V", "IV", "I"};

        StringBuffer result = new StringBuffer();

        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                num -= values[i];
                result.append(symbols[i]);
            }
        }
        return result.toString();
    }
}