面试经典150题——数组/字符串（二）

1、跳跃游戏

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

提示：

• 1 <= nums.length <= 10⁴
• 0 <= nums[i] <= 10⁵

1.3 解题代码

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int i = 0;
        int most_right = 0;
        while(i <= most_right){
            most_right = Math.max(i + nums[i], most_right);
            if(most_right >= n - 1){
                return true;
            }
            ++i;
        }
    return false;
    }
}

1.4 解题思路

1. 一次遍历，每次设置一个最大右端（能跳到的最右端），值为i + nums[i]。
2. 如果指针指到最大右端并且无法跳到整个数组的最右端时候就返回false。
3. 如果最大右端已经大于等于数组右端则返回true。

2、跳跃游戏 II

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i]
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

2.3 解题代码

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n+1];
        for(int i = 1; i <= n; ++i){
            dp[i] = n + 1;
        }
        for(int i = 1; i < n; ++i){
            for(int j = 0; j <= i; ++j){
                if(nums[j] + j >= i){
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
    return dp[n-1];
    }
}

2.4 解题思路

1. 从目标点开始往前推，计算到达该点所需的最短步数。

3、H 指数

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。

提示：

• n == citations.length
• 1 <= n <= 5000
• 0 <= citations[i] <= 1000

3.3 解题代码

class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int n = citations.length;
        int h = 0;
        int i = n - 1;
        while(i >= 0 && citations[i] > h){
            i--;
            h++;
        }
    return h;
    }
}

3.4 解题思路

1. 先将citations从小到大排序。
2. 逆序遍历，h从0开始算，如果citations[i] > h的话，h可以增加，此时至少有n - i（因为h是从0开始增加的，所以h一定等于n - i）篇论文大于等于h。如果citations[i] < h的话，h肯定不会增加，如果citations[i] = h的时候，如果h增加的话，此时的citations[i] 一定是小于h的，就变成不满足了，所以循环的判定条件一定是citations[i] > h。

4、O(1) 时间插入、删除和获取随机元素

4.1 题目链接

点击跳转到题目位置

4.2 题目描述

实现RandomizedSet 类：

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

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

提示：

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

4.3 解题代码

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

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

/**
 * 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();
 */

4.4 解题思路

1. 借助HashMap这一数据结构，在末尾进行操作。

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

5.1 题目链接

点击跳转到题目位置

5.2 题目描述

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

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

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

提示：

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

5.3 解题代码

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] preifix_sum = new int[n];
        int[] suffix_sum = new int[n];
        int[] ret = new int[n];
        for(int i = 0; i < n; ++i){
            if(i == 0){
                preifix_sum[i] = 1;
            } else{
                preifix_sum[i] = preifix_sum[i - 1] * nums[i - 1];
            }
        }
        for(int i = n - 1; i >= 0; --i){
            if(i == n - 1){
                suffix_sum[i] = 1;
            } else{
                suffix_sum[i] = suffix_sum[i + 1] * nums[i + 1];
            }
        }
        for(int i = 0; i < n; ++i){
            if(i == 0){
                ret[i] = suffix_sum[i];
            } else if(i == n - 1){
                ret[i] = preifix_sum[i];
            } else{
                ret[i] = preifix_sum[i] * suffix_sum[i];
            }
        }
    return ret;
    }
}

5.4 解题思路

1. 前缀和+后缀和问题
2. 前缀和数组用来维护下标为i之前所有数的乘积
3. 后缀和数组用来维护下标为i之后所有数的乘积
4. i 等于 0 的时候， 为suffix_sum[0]，i 等于 n - 1 的时候为prefix_sum[n - 1]，否则为prefix_sum[i] * suffix_sum[i]。

6、加油站

6.1 题目链接

点击跳转到题目位置

6.2 题目描述

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

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

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

提示:

• gas.length == n
• cost.length == n
• 1 <= n <= 10⁵
• 0 <= gas[i], cost[i] <= 10⁴

6.3 解题代码

class Solution {
    int end = 0;
    boolean judge(int[] gas, int[] cost, int start, int n){
        int ret = 0;
        for(int i = 0; i < n; ++i){
            ret += (gas[(i + start) % n] - cost[(i + start) % n]);
            if(ret < 0){
                end = (i + start) % n;
                return false;
            }
        }
    return ret >= 0;
    }
    
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int i = 0;
        while(i < n){
            if(judge(gas, cost, i, n)){
                return i;
            } else if(end >= i){
                i = end + 1;
            } else{
                return -1;
            }
        }            
    return -1;
    }
}

6.4 解题思路

1. 假设每次遍历的起点是start，终点是end。
2. 如果end最后遍历 < start，又已知end走不到start，所以此时后面的点没有必要遍历了，一定是走不通的，如果end >= start的时候， 起点设置为end + 1即可（因为走到end走不下去了（如果从end开始的话，初始油量为0））。

7、分发糖果

7.1 题目链接

点击跳转到题目位置

7.2 题目描述

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

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

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

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

提示：

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

7.3 解题代码

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] left = new int[n];
        for (int i = 0; i < n; i++) {
            if (i > 0 && ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            } else {
                left[i] = 1;
            }
        }
        int right = 0, ret = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (i < n - 1 && ratings[i] > ratings[i + 1]) {
                right++;
            } else {
                right = 1;
            }
            ret += Math.max(left[i], right);
        }
        return ret;
    }
}

7.4 解题思路

1. 先从左往右进行遍历，先用一个数组存储从左往右中的结果，如果当前位置的rating比左边高，则left[i] 等于 left[i - 1] + 1，否则设置为1。
2. 再从右往左进行遍历，如果ratings[i] 低于右边则设置为1，如果高于的话则比右侧的多一个，最后当前点的糖果数即为左边和右边得出的结果两者取最大值。
3. 最后累加得到结果即可。

8、接雨水

8.1 题目链接

点击跳转到题目位置

8.2 题目描述

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

提示：

• n == height.length
• 1 <= n <= 2 * 10⁴
• 0 <= height[i] <= 10⁵

8.3 解题代码

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] prefix_sum = new int[n];
        int[] suffix_sum = new int[n];
        for(int i = 0; i < n; ++i){
            if(i == 0){
                prefix_sum[i] = height[i];
            } else{
                prefix_sum[i] = Math.max(prefix_sum[i - 1], height[i]);
            }
        }
        for(int i = n - 1; i >= 0; --i){
            if(i == n - 1){
                suffix_sum[i] = height[i];
            } else{
                suffix_sum[i] = Math.max(suffix_sum[i + 1], height[i]);
            }
        }
        int ret = 0;
        for(int i = 0; i < n; ++i){
            ret += (Math.min(prefix_sum[i], suffix_sum[i]) - height[i]);
        }
    return ret;
    }
}

8.4 解题思路

1. 前缀和+后缀和问题
2. 前缀和负责维护当前位置及之前位置的所有的柱子的最高值。
3. 后缀和负责维护当前位置及之后位置的所有的柱子的最高值。
4. 当前位置的蓄水为当前位置的前缀和与后缀和的最小者减去当前高度。
5. 累加总和即最后的答案。