怒刷LeetCode的第23天（Java版）

2023-10-05 10:56
文章标签 java leetcode 23 怒刷

本文主要是介绍怒刷LeetCode的第23天（Java版），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

第一题

题目来源

题目内容

解决方法

方法一：贪心算法

方法二：动态规划

方法三：回溯算法

方法四：并查集

第二题

题目来源

题目内容

解决方法

方法一：排序和遍历

方法二：扫描线算法

方法三：栈

第三题

题目来源

题目内容

解决方法

方法一：遍历和比较

第一题

题目来源

55. 跳跃游戏 - 力扣（LeetCode）

题目内容

解决方法

方法一：贪心算法

这个算法使用贪心的思想，通过遍历数组中的每个元素，始终保持一个能够跳到的最远位置 maxPos。在遍历过程中，如果当前位置超过了 maxPos，则说明无法继续跳跃，返回 false。否则，更新 maxPos 的值，将其与 i + nums[i] 比较，取较大值作为新的 maxPos。最后判断 maxPos 是否已经超过或等于最后一个下标，如果是，则返回 true，否则返回 false。

class Solution {
public boolean canJump(int[] nums) {int n = nums.length;int maxPos = 0; // 当前能够跳到的最远位置for (int i = 0; i < n; i++) {if (i > maxPos) {// 如果当前位置超过了能够跳到的最远位置，说明无法继续跳跃，返回falsereturn false;}maxPos = Math.max(maxPos, i + nums[i]);// 更新能够跳到的最远位置if (maxPos >= n - 1) {// 如果能够跳到的最远位置已经超过或等于最后一个下标，说明可以到达最后一个下标，返回truereturn true;}}return false;
}}

复杂度分析：

  • 时间复杂度为 O(n)，其中 n 是数组的长度。因为我们只需遍历一次数组即可判断能否到达最后一个下标。
  • 空间复杂度为 O(1)，我们只需要保存一个额外的变量 maxPos。

LeetCode运行结果：

方法二：动态规划

除了贪心之外，还可以使用动态规划来解决这个问题。

该算法使用动态规划的思想，定义一个布尔型数组 dp，其中 dp[i] 表示能否从第0个位置跳到第i个位置。

为了计算 dp[i]，我们从前往后遍历数组中的每个位置 i，并在其中再次遍历所有位置 j < i。只有当某个位置 j 可以到达，并且从 j 位置可以到达 i 位置时，才有可能到达 i 位置。因此，如果存在一个位置 j 满足条件，即 dp[j] && j + nums[j] >= i，则说明当前位置 i 可以到达，我们将 dp[i] 设置为 true。最终返回 dp[n-1] ，表示能否从第 0 个位置跳到最后一个位置。

class Solution {
public boolean canJump(int[] nums) {int n = nums.length;boolean[] dp = new boolean[n]; // dp[i] 表示能否从第0个位置跳到第i个位置dp[0] = true; // 第0个位置一定可以到达for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (dp[j] && j + nums[j] >= i) {// 如果前面某一个位置可以到达，并且这个位置可以到达i，那么说明i也可以到达dp[i] = true;break;}}}return dp[n - 1];
}
}

复杂度分析：

  • 时间复杂度为 O(n^2)，因为在计算 dp[i] 时，需要遍历之前的所有位置 j，所以总共需要进行 n * (n-1) / 2 次比较。
  • 空间复杂度方面，动态规划算法使用了一个长度为 n 的数组 dp，所以空间复杂度为 O(n)。

与贪心算法相比，动态规划算法的时间复杂度较高，但是更加直观易懂，且可以解决更一般化的跳跃游戏问题。

LeetCode运行结果：

方法三：回溯算法

除了贪心算法和动态规划算法，还可以使用回溯算法来解决跳跃游戏问题。

该算法使用回溯的思想，在每个位置上探索所有可能的跳跃，直到找到能到达最后一个位置的路径，或者发现无法到达的情况。

具体实现中，我们定义一个辅助函数 backtrack，其中 position 参数表示当前所在的位置。首先，在每个位置上计算能够跳跃到的最远位置 furthestJump，然后从最远位置开始反向遍历，尝试从当前位置跳到下一个位置 nextPosition，并递归调用 backtrack 函数。如果最终找到一条路径能够到达最后一个位置，则返回 true；如果所有尝试都失败，则返回 false。

class Solution {
public boolean canJump(int[] nums) {return backtrack(nums, 0);
}private boolean backtrack(int[] nums, int position) {// 到达最后一个位置，返回 trueif (position == nums.length - 1) {return true;}int furthestJump = Math.min(position + nums[position], nums.length - 1);for (int nextPosition = furthestJump; nextPosition > position; nextPosition--) {if (backtrack(nums, nextPosition)) {return true;}}return false;
}}

复杂度分析：

回溯算法的时间复杂度是指数级的，因为在每个位置上都会进行多次递归调用。具体来说，在最坏情况下，即每次跳跃只能跳一个格子，需要进行 n 层递归调用，每层调用需要遍历 nums 数组中的所有元素，因此总时间复杂度是 O(n^n)。

空间复杂度主要取决于递归调用栈的深度，最坏情况下，递归调用栈的深度为数组的长度，所以空间复杂度为 O(n)。

尽管回溯算法能够找到所有可能的路径，但由于其指数级的时间复杂度，对于较大的输入可能会导致超时。因此，在实际应用中，贪心算法和动态规划算法更常用和高效。

LeetCode运行结果：

方法四：并查集

除了贪心算法、动态规划、回溯算法，还可以使用特殊的数据结构来解决跳跃游戏问题，例如并查集。

并查集是一种用于处理元素分组和查找连通性的数据结构。在跳跃游戏问题中，我们可以将每个位置看作一个节点，并按照能够跳跃到的下一个位置建立连通关系。

在实现中，我们首先定义了一个并查集类 UnionFind，其中包含 find、union 和 isConnected 等操作。在构造函数中，将每个位置初始化为其自身的根节点。

接下来，遍历数组 nums 中的每个位置，并计算出从当前位置能够跳跃到的最远位置 maxJump。然后，将当前位置与从 i+1 到 maxJump 的位置进行合并操作，表示它们之间存在连通关系。

最后，判断起点位置 0 和终点位置 n-1 是否连通，即可得出是否能够跳跃到终点位置。

class Solution {
class UnionFind {int[] parent;public UnionFind(int n) {parent = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;}}public int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];}public void union(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {parent[rootX] = rootY;}}public boolean isConnected(int x, int y) {return find(x) == find(y);}
}public boolean canJump(int[] nums) {if (nums == null || nums.length == 0) {return false;}int n = nums.length;UnionFind uf = new UnionFind(n);for (int i = 0; i < n; i++) {int maxJump = Math.min(i + nums[i], n - 1);for (int j = i + 1; j <= maxJump; j++) {uf.union(i, j);}}return uf.isConnected(0, n - 1);
}}

复杂度分析：

  • 时间复杂度：O(n^2)，其中 n 是数组的长度。需要进行两层循环，对每个位置都进行合并操作。
  • 空间复杂度：O(n)，需要使用一个并查集来保存每个位置的根节点。

需要注意的是，并查集不适用于所有类型的跳跃游戏问题，只适用于某些特定情况下。在一般情况下，仍然推荐使用贪心算法、动态规划或回溯算法来解决跳跃游戏问题。

LeetCode运行结果：

第二题

题目来源

56. 合并区间 - 力扣（LeetCode）

题目内容

解决方法

方法一：排序和遍历

这个问题可以使用排序和遍历的思路来解决。

  1. 首先，我们对给定的区间集合按照起始位置进行排序。这样可以确保如果有重叠的区间，它们会相邻。
  2. 然后，我们遍历排序后的区间集合，并维护一个当前合并区间的起始位置 start 和结束位置 end。初始时，我们将第一个区间的起始位置和结束位置分别赋值给 start 和 end。
  3. 接下来，我们从第二个区间开始遍历，比较当前区间的起始位置与当前合并区间的结束位置。如果当前区间的起始位置大于当前合并区间的结束位置，说明当前区间与前面的区间没有重叠，我们可以将当前合并区间 [start, end] 加入结果数组中，并更新 start 和 end 为当前区间的起始位置和结束位置。
  4. 否则，如果当前区间的起始位置小于等于当前合并区间的结束位置，说明当前区间与前面的区间有重叠，我们可以更新当前合并区间的结束位置为当前区间的结束位置。这样就实现了区间的合并。
  5. 最后，遍历完成后，将当前合并区间 [start, end] 加入结果数组中即可。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;class Solution {public int[][] merge(int[][] intervals) {if (intervals.length <= 1) {return intervals;}// 按照区间的起始位置进行排序Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));List<int[]> merged = new ArrayList<>();int start = intervals[0][0];int end = intervals[0][1];for (int i = 1; i < intervals.length; i++) {int intervalStart = intervals[i][0];int intervalEnd = intervals[i][1];if (intervalStart <= end) {// 当前区间和前面的区间有重叠，更新当前合并区间的结束位置end = Math.max(end, intervalEnd);} else {// 当前区间和前面的区间没有重叠，将当前合并区间加入结果数组中merged.add(new int[]{start, end});// 更新当前合并区间为当前区间start = intervalStart;end = intervalEnd;}}// 将最后一个合并区间加入结果数组中merged.add(new int[]{start, end});return merged.toArray(new int[merged.size()][]);}
}

复杂度分析：

  • 排序的时间复杂度为O(n log n)，其中 n 是区间的数量。这是因为我们对区间进行了一次排序操作。接下来，我们遍历排序后的区间集合，每个区间只会被访问一次。因此，遍历的时间复杂度是O(n)，其中 n 是区间的数量。最后，将合并后的区间转换为结果数组的过程需要O(n)的时间复杂度，其中 n 是合并后的区间数量。综上所述，算法的总时间复杂度为O(n log n) + O(n) + O(n) = O(n log n)。
  • 对于空间复杂度，我们使用了一个结果集合来存储合并后的区间，其大小最多为n。因此，空间复杂度为O(n)。

注意，这里不考虑返回结果的空间复杂度。如果按照题目要求返回二维数组作为结果，该空间复杂度为O(n)。

LeetCode运行结果：

方法二：扫描线算法

除了排序和遍历的方法，还可以使用扫描线算法来合并区间。这种方法在处理区间重叠的问题时也很高效。

  1. 首先，我们将所有区间的起始点和结束点提取出来，并分别存储在两个数组中。对于每个点，我们还需要记录它是一个起始点还是结束点。
  2. 然后，我们对这些点进行排序，并使用一个变量 count 来记录当前遍历到的起始点的个数。同时，我们还需要用一个变量 start 来记录当前合并区间的起始位置。
  3. 接着，我们从左到右遍历这些点，并根据每个点的类型来更新 count 的值。当遇到起始点时，说明有一个新的区间开始了，因此 count 加1。当遇到结束点时，说明一个区间结束了，因此 count 减1。
  4. 在遍历过程中，每当 count 的值从0变为1时，说明一个新的合并区间开始了，我们将当前点的位置赋值给 start。每当 count 的值从1变为0时，说明一个合并区间结束了，我们将当前点的位置作为这个区间的结束位置，并将合并区间 [start, end] 加入结果数组中。
  5. 最后，我们就可以得到合并后的区间。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;class Solution {public int[][] merge(int[][] intervals) {if (intervals.length <= 1) {return intervals;}int n = intervals.length;// 提取所有点的值和类型int[] points = new int[2 * n];int[] types = new int[2 * n];for (int i = 0; i < n; i++) {points[2 * i] = intervals[i][0];types[2 * i] = 1; // 起始点points[2 * i + 1] = intervals[i][1];types[2 * i + 1] = -1; // 结束点}// 对点进行排序Integer[] indices = new Integer[2 * n];for (int i = 0; i < 2 * n; i++) {indices[i] = i;}Arrays.sort(indices, (a, b) -> {if (points[a] != points[b]) {return Integer.compare(points[a], points[b]);}return Integer.compare(types[b], types[a]);});List<int[]> merged = new ArrayList<>();int count = 0;int start = 0;for (int index : indices) {int point = points[index];int type = types[index];if (count == 0) {start = point;}count += type;if (count == 0) {int end = point;merged.add(new int[]{start, end});}}return merged.toArray(new int[merged.size()][]);}
}

复杂度分析：

  • 算法的时间复杂度为O(n log n)，其中n是区间的数量。这是因为算法涉及对区间的排序操作，而排序的时间复杂度为O(n log n)。
  • 算法的空间复杂度为O(n)，用于存储排序后的区间和合并后的结果。

需要注意的是，在最坏情况下，即所有的区间都不重叠时，算法需要将所有区间都合并为一个大区间，此时时间复杂度为O(n)。

总之，本算法的时间复杂度和空间复杂度都是比较优秀的，是解决区间合并问题的一个非常好的算法。

LeetCode运行结果：

方法三：栈

除了排序和遍历、扫描线算法外，还有一种常见的方法是使用栈来合并区间。

具体实现思路如下：

  1. 首先将所有区间按照起始位置进行排序。
  2. 创建一个栈，将第一个区间放入栈中。
  3. 遍历剩余的区间，如果当前区间的起始位置大于栈顶区间的结束位置，说明两个区间不重叠，直接将当前区间入栈。 否则，将当前区间与栈顶区间合并，更新栈顶区间的结束位置为两者中的较大值。
  4. 遍历完所有区间后，栈中存储的就是合并后的区间。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;class Solution {public int[][] merge(int[][] intervals) {if (intervals.length <= 1) {return intervals;}// 根据起始位置对区间进行排序Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));// 使用栈来合并区间Stack<int[]> stack = new Stack<>();stack.push(intervals[0]);for (int i = 1; i < intervals.length; i++) {int[] currentInterval = intervals[i];int[] topInterval = stack.peek();if (currentInterval[0] > topInterval[1]) {// 当前区间与栈顶区间不重叠，直接入栈stack.push(currentInterval);} else {// 合并当前区间和栈顶区间topInterval[1] = Math.max(topInterval[1], currentInterval[1]);}}// 将栈中的区间转化为数组返回List<int[]> merged = new ArrayList<>(stack);return merged.toArray(new int[merged.size()][]);}
}

复杂度分析：

使用栈的方法时间复杂度取决于排序的时间复杂度，因此为 O(n log n)，其中n是区间的数量。空间复杂度为O(n)，用于存储合并后的区间。

具体分析如下：

  • 对区间进行排序的时间复杂度为 O(n log n)，因为我们需要对所有区间按照起始位置进行排序。
  • 遍历整个区间数组的时间复杂度为 O(n)，因为我们只需要遍历每个区间一次，并将合并后的区间存储在一个栈中。
  • 最后将栈中的元素转化为二维数组的时间复杂度为 O(n)，因为我们需要遍历栈中所有元素一次，并将它们存储在一个二维数组中。

因此，总的时间复杂度为 O(n log n) + O(n) + O(n) = O(n log n)。空间复杂度为O(n)，因为我们需要存储合并后的区间。

需要注意的是，排序操作是这种方法的时间复杂度瓶颈，因此如果输入区间已经有序或者近似有序，则使用这种方法可能更加高效，因为排序的时间复杂度可以达到O(n)。但是一般情况下，排序和遍历、扫描线算法仍然是解决区间合并问题的首选方法。

LeetCode运行结果：

第三题

题目来源

57. 插入区间 - 力扣（LeetCode）

题目内容

解决方法

方法一：遍历和比较

思路与算法：

  1. 首先，根据题目要求，我们可以将给定的区间列表按照起始端点进行排序，这样可以方便后续的处理。

  2. 接下来，我们需要遍历排序后的区间列表，逐个与新的区间进行比较和合并。

  3. 初始化一个结果列表 merged，用于存储最终的合并后的区间。

  4. 遍历排序后的区间列表，对于每个区间 intervals[i]，与新的区间 newInterval 进行比较和合并。

    • 如果 intervals[i] 的结束位置小于 newInterval 的起始位置，说明两个区间没有重叠，直接将 intervals[i] 加入 merged 中。

    • 如果 intervals[i] 的起始位置大于 newInterval 的结束位置，说明后面的区间也不会有重叠，直接将 newInterval 和后面的区间加入 merged 中，并返回最终结果。

    • 如果 intervals[i] 和 newInterval 存在重叠，我们需要不断地更新 newInterval 的范围，使其包括当前区间 intervals[i] 及可能的后续重叠区间，直到找到一个不与 newInterval 重叠的区间或者完成遍历。

  5. 最后，将 newInterval 添加到 merged 中，并将剩余的 intervals[i] 依次加入 merged。

  6. 返回 merged 列表中的区间数组作为最终结果。

import java.util.ArrayList;
import java.util.List;class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {List<int[]> merged = new ArrayList<>(); // 用于存储合并后的区间int i = 0;// 将起始位置小于newInterval的区间加入结果列表while (i < intervals.length && intervals[i][1] < newInterval[0]) {merged.add(intervals[i]);i++;}// 合并与newInterval相交的区间while (i < intervals.length && intervals[i][0] <= newInterval[1]) {newInterval[0] = Math.min(newInterval[0], intervals[i][0]);newInterval[1] = Math.max(newInterval[1], intervals[i][1]);i++;}// 将合并后的newInterval加入结果列表merged.add(newInterval);// 将剩余的区间加入结果列表while (i < intervals.length) {merged.add(intervals[i]);i++;}// 将结果列表转换为数组返回return merged.toArray(new int[merged.size()][2]);}
}

复杂度分析：

  • 该算法的时间复杂度为 O(n)，其中 n 是区间的个数，因为需要遍历整个区间列表一次。
  • 算法中使用了一个额外的空间 merged 来存储合并后的区间，空间复杂度为 O(n)，其中 n 是合并后的区间的个数。

LeetCode运行结果：

这篇关于怒刷LeetCode的第23天（Java版）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/4522。

相关文章

JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
Java进阶13讲__第12讲_1/2

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory
阅读更多...
JAVA智听未来一站式有声阅读平台听书系统小程序源码

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来，一站式有声阅读平台听书系统 🌟&nbsp;开篇：遇见未来，从“智听”开始 在这个快节奏的时代，你是否渴望在忙碌的间隙，找到一片属于自己的宁静角落？是否梦想着能随时随地，沉浸在知识的海洋，或是故事的奇幻世界里？今天，就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统，它正悄悄改变着我们的阅读方式，让未来触手可及！ 📚&nbsp;第一站：海量资源，应有尽有 走进“智听
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2