Java 面试中的高频算法题详解

server/2025/1/15 9:47:58/

💖 欢迎来到我的博客！ 非常高兴能在这里与您相遇。在这里，您不仅能获得有趣的技术分享，还能感受到轻松愉快的氛围。无论您是编程新手，还是资深开发者，都能在这里找到属于您的知识宝藏，学习和成长。

🔍 博客内容包括：

  • Java核心技术与微服务：涵盖Java基础、JVM、并发编程、Redis、Kafka、Spring等，帮助您全面掌握企业级开发技术。
  • 大数据技术：涵盖Hadoop（HDFS）、Hive、Spark、Flink、Kafka、Redis、ECharts、Zookeeper等相关技术。
  • 开发工具：分享常用开发工具（IDEA、Git、Mac、Alfred、Typora等）的使用技巧，提升开发效率。
  • 数据库与优化：总结MySQL及其他常用数据库技术，解决实际工作中的数据库问题。
  • Python与大数据：专注于Python编程语言的深度学习，数据分析工具（如Pandas、NumPy）和大数据处理技术，帮助您掌握数据分析、数据挖掘、机器学习等技术。
  • 数据结构与算法：总结数据结构与算法的核心知识，提升编程思维，帮助您应对大厂面试挑战。

🌟 我的目标：持续学习与总结，分享技术心得与解决方案，和您一起探索技术的无限可能！在这里，我希望能与您共同进步，互相激励，成为更好的自己。

📣 欢迎订阅本专栏，与我一起在这个知识的海洋中不断学习、分享和成长！💻🚀

📍版权声明：本博客所有内容均为原创，遵循CC 4.0 BY-SA协议，转载请注明出处。

目录

1. 两数之和

题目描述

解题思路

代码实现

处理方式

2. 反转链表

题目描述

解题思路

代码实现

处理方式

3. 深度优先搜索

题目描述

解题思路

代码实现

处理方式

4. 排序相关算法

4.1 快速排序（Quick Sort）

题目描述

解题思路

解题步骤

代码实现

复杂度分析

4.2 归并排序（Merge Sort）

题目描述

解题思路

解题步骤

代码实现

复杂度分析

5. 动态规划算法

5.1 背包问题（Knapsack Problem）

题目描述

解题思路

解题步骤

代码实现

复杂度分析

5.2 最长公共子序列（Longest Common Subsequence）

题目描述

解题思路

解题步骤

复杂度分析

6. 回溯算法

6.1 N皇后问题（N-Queens Problem）

题目描述

解题思路

解题步骤

代码实现

复杂度分析

7. 贪心算法

7.1 活动选择问题（Activity Selection Problem）

题目描述

解题思路

解题步骤

代码实现

复杂度分析

Java 面试中，算法题是一个重要且常见的涉及领域。面试对算法效率和处理方式有高要求，下面将通过解析经典题目，配合解题思路和代码实现进行详细说明。

1. 两数之和

题目描述

给定一个整数数组（nums）和一个目标值（target），请从数组中找出两个元素，使它们之和为 target。假设每种计算仅能有一个结果，不允许重复使用数组中的元素。

解题思路

  1. 设计一个响应快速查询的数据结构（如 HashMap），用于存储数组元素和它们的位置。

  2. 遍历数组，对于每个元素（nums[i]），计算 target - nums[i]，检查该值是否已存在于 HashMap。

  3. 如果存在，返回它们的位置；如果不存在，将当前元素和位置保存到 HashMap。

代码实现
java">import java.util.HashMap;public class TwoSum {public int[] twoSum(int[] nums, int target) {HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int complement = target - nums[i];if (map.containsKey(complement)) {return new int[]{map.get(complement), i};}map.put(nums[i], i);}throw new IllegalArgumentException("No two sum solution");}
}
处理方式

  • 时间处理复杂度： O(n)，遍历数组一次。

  • 空间复杂度： O(n)，依赖于 HashMap。

2. 反转链表

题目描述

给定一个单链表，请反转该链表。

解题思路

  1. 通过一个进程实现反转：保存当前节点的上一节点，重新设置指针。

  2. 使用三个指针：pre、cur和next，采用进程尽头更新。

代码实现
java">class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}public class ReverseLinkedList {public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode current = head;while (current != null) {ListNode nextTemp = current.next;current.next = prev;prev = current;current = nextTemp;}return prev;}
}
处理方式

  • 时间复杂度： O(n)，遍历链表一次。

  • 空间复杂度： O(1)，只依赖指针。

3. 深度优先搜索

题目描述

给定一个整数矩阵，通过深度优先搜索（DFS）进行访问，并实现目标方案。

解题思路

  1. 通过通用的算法回退，可以对于任何格式基于规划优先加量。

  2. 用一个标记数据进行处理。

代码实现
java">public class DepthFirstSearch {private static final int[] dx = {-1, 1, 0, 0};private static final int[] dy = {0, 0, -1, 1};public void dfs(int[][] grid, boolean[][] visited, int x, int y) {if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || visited[x][y] || grid[x][y] == 0) {return;}visited[x][y] = true;for (int i = 0; i < 4; i++) {int nx = x + dx[i];int ny = y + dy[i];dfs(grid, visited, nx, ny);}}
}
处理方式

  • 时间复杂度： O(n × m)，基于全部格式可进行加量进。

  • 空间复杂度： O(n × m)，采用标记记录。

4. 排序相关算法

4.1 快速排序（Quick Sort）
题目描述

给定一个无序的数组，要求通过快速排序算法将数组排序。

解题思路

快速排序的基本思想是：通过一个基准元素（pivot）将数组分成两部分，其中一部分的元素都小于基准元素，另一部分的元素都大于基准元素。然后递归地对这两部分进行排序。

解题步骤
  1. 选择一个基准元素，通常选择数组的第一个元素或最后一个元素。
  2. 通过一次排序将数组分成两部分，左侧部分小于基准元素，右侧部分大于基准元素。
  3. 递归地对左右两部分数组进行排序，直到数组的大小为1。
代码实现
java">public class QuickSort {public void quickSort(int[] arr, int left, int right) {if (left < right) {int pivotIndex = partition(arr, left, right);quickSort(arr, left, pivotIndex - 1);quickSort(arr, pivotIndex + 1, right);}}private int partition(int[] arr, int left, int right) {int pivot = arr[right];int i = left - 1;for (int j = left; j < right; j++) {if (arr[j] <= pivot) {i++;swap(arr, i, j);}}swap(arr, i + 1, right);return i + 1;}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static void main(String[] args) {int[] arr = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};QuickSort qs = new QuickSort();qs.quickSort(arr, 0, arr.length - 1);System.out.println(Arrays.toString(arr));}
}
复杂度分析
  • 时间复杂度：
    • 最好和平均情况：O(n log n)
    • 最坏情况：O(n^2)，发生在每次选择的基准元素是最小或最大的情况下。
  • 空间复杂度：O(log n)，主要是递归调用的栈空间。
4.2 归并排序（Merge Sort）
题目描述

给定一个无序的数组，要求通过归并排序算法将数组排序。

解题思路

归并排序的核心思想是分治法，将数组分成两个子数组，对每个子数组进行排序后合并。

解题步骤
  1. 将数组分成两个子数组。
  2. 递归地对子数组进行排序。
  3. 合并两个已排序的子数组，最终得到一个有序数组。
代码实现
java">public class MergeSort {public void mergeSort(int[] arr) {if (arr.length < 2) {return;}int mid = arr.length / 2;int[] left = Arrays.copyOfRange(arr, 0, mid);int[] right = Arrays.copyOfRange(arr, mid, arr.length);mergeSort(left);mergeSort(right);merge(arr, left, right);}private void merge(int[] arr, int[] left, int[] right) {int i = 0, j = 0, k = 0;while (i < left.length && j < right.length) {if (left[i] <= right[j]) {arr[k++] = left[i++];} else {arr[k++] = right[j++];}}while (i < left.length) {arr[k++] = left[i++];}while (j < right.length) {arr[k++] = right[j++];}}public static void main(String[] args) {int[] arr = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};MergeSort ms = new MergeSort();ms.mergeSort(arr);System.out.println(Arrays.toString(arr));}
}
复杂度分析
  • 时间复杂度：O(n log n)，无论是最坏、最好还是平均情况，归并排序的时间复杂度始终是O(n log n)。
  • 空间复杂度：O(n)，归并排序需要额外的空间来存储临时数组。

5. 动态规划算法

5.1 背包问题（Knapsack Problem）
题目描述

给定一组物品，每个物品有重量和价值，背包的最大承重是W，要求选择一些物品放入背包，使得背包中的物品总价值最大。

解题思路

动态规划的解法通过构建一个二维数组，表示每个背包容量下能够获得的最大价值。通过递推公式，逐步填充数组，最终求得最大价值。

解题步骤
  1. 定义状态：dp[i][j]表示前i个物品，在背包容量为j时的最大价值。
  2. 递推公式：
    • 如果不选择第i个物品：dp[i][j] = dp[i-1][j]。
    • 如果选择第i个物品：dp[i][j] = dp[i-1][j-weight[i]] + value[i]。
  3. 初始化状态：dp[0][j] = 0（没有物品时，背包的最大价值为0）。
代码实现
java">public class Knapsack {public int knapsack(int W, int[] weights, int[] values) {int n = weights.length;int[][] dp = new int[n + 1][W + 1];for (int i = 1; i <= n; i++) {for (int w = 1; w <= W; w++) {if (weights[i - 1] <= w) {dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);} else {dp[i][w] = dp[i - 1][w];}}}return dp[n][W];}public static void main(String[] args) {int[] weights = {2, 3, 4, 5};int[] values = {3, 4, 5, 6};int W = 5;Knapsack knapsack = new Knapsack();System.out.println(knapsack.knapsack(W, weights, values));}
}
复杂度分析
  • 时间复杂度：O(n * W)，其中n是物品数量，W是背包的最大承重。
  • 空间复杂度：O(n * W)，用于存储dp数组。
5.2 最长公共子序列（Longest Common Subsequence）
题目描述

给定两个字符串，求它们的最长公共子序列的长度。子序列是一个序列，可以通过删除一些字符（或不删除）来得到，但不能改变字符的顺序。

解题思路

使用动态规划的方法来解决这个问题。我们定义 dp[i][j] 为字符串 s1 的前 i 个字符与字符串 s2 的前 j 个字符的最长公共子序列的长度。

递推公式如下：

  • 如果 s1[i-1] == s2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。
  • 如果 s1[i-1] != s2[j-1]，则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
解题步骤
  1. 初始化状态：dp[i][0] = 0 和 dp[0][j] = 0，表示任意一个字符串为空时，公共子序列长度为0。
  2. 递推填充 dp 数组。
  3. 最终答案为 dp[s1.length][s2.length]。
java">public class LCS {public int longestCommonSubsequence(String s1, String s2) {int m = s1.length();int n = s2.length();int[][] dp = new int[m + 1][n + 1];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (s1.charAt(i - 1) == s2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[m][n];}public static void main(String[] args) {LCS lcs = new LCS();String s1 = "abcde";String s2 = "ace";System.out.println(lcs.longestCommonSubsequence(s1, s2));  // Output: 3}
}
复杂度分析
  • 时间复杂度：O(m * n)，其中m和n分别是两个字符串的长度。
  • 空间复杂度：O(m * n)，用于存储dp数组。

6. 回溯算法

6.1 N皇后问题（N-Queens Problem）
题目描述

在一个 n x n 的棋盘上放置 n 个皇后，使得每个皇后都不能互相攻击。皇后可以攻击同一行、同一列和同一对角线上的其他皇后。求所有可能的放置方式。

解题思路

回溯算法的基本思想是通过递归构建解的过程，并在发现不满足条件时返回。对于N皇后问题，我们可以逐行放置皇后，然后通过回溯来尝试不同的放置方式。

我们可以使用三个数组来标记列和两个对角线的使用情况，确保每个皇后都不互相攻击：

  • cols[i]：表示列 i 是否已经有皇后。
  • diag1[i]：表示主对角线是否已被占用。
  • diag2[i]：表示副对角线是否已被占用。
解题步骤
  1. 从第一行开始放置皇后，并递归地尝试其他行。
  2. 每放置一个皇后，检查其列、主对角线和副对角线是否已经有其他皇后。
  3. 如果某一行没有合法的放置位置，则回溯到上一行并尝试新的放置方案。
代码实现
java">import java.util.ArrayList;
import java.util.List;public class NQueens {public List<List<String>> solveNQueens(int n) {List<List<String>> result = new ArrayList<>();boolean[] cols = new boolean[n];  // 是否已经在列上放置皇后boolean[] diag1 = new boolean[2 * n];  // 主对角线boolean[] diag2 = new boolean[2 * n];  // 副对角线List<String> current = new ArrayList<>();backtrack(result, current, cols, diag1, diag2, n, 0);return result;}private void backtrack(List<List<String>> result, List<String> current, boolean[] cols, boolean[] diag1, boolean[] diag2, int n, int row) {if (row == n) {result.add(new ArrayList<>(current));return;}for (int col = 0; col < n; col++) {if (cols[col] || diag1[row + col] || diag2[row - col + n - 1]) {continue;  // 该位置被攻击}// 放置皇后cols[col] = true;diag1[row + col] = true;diag2[row - col + n - 1] = true;char[] rowArr = new char[n];for (int i = 0; i < n; i++) {rowArr[i] = (i == col) ? 'Q' : '.';}current.add(new String(rowArr));// 尝试放置下一个皇后backtrack(result, current, cols, diag1, diag2, n, row + 1);// 回溯current.remove(current.size() - 1);cols[col] = false;diag1[row + col] = false;diag2[row - col + n - 1] = false;}}public static void main(String[] args) {NQueens nq = new NQueens();List<List<String>> solutions = nq.solveNQueens(4);for (List<String> solution : solutions) {for (String row : solution) {System.out.println(row);}System.out.println();}}
}
复杂度分析
  • 时间复杂度：O(N!)，因为在每一行可能有 N 个选择，最坏情况下递归的次数为 N!。
  • 空间复杂度：O(N)，用于存储列、对角线的状态和当前解的数组。

7. 贪心算法

7.1 活动选择问题（Activity Selection Problem）
题目描述

有若干个活动，每个活动有一个开始时间和结束时间，要求选择尽可能多的活动，使得每个活动都不与已选择的活动重叠。

解题思路

贪心算法的思想是，选择结束时间最早的活动。每次选择当前活动时，要求它与之前选择的活动不重叠。

解题步骤
  1. 将所有活动按照结束时间排序。
  2. 从第一个活动开始选择，选择的条件是活动的开始时间要晚于已选活动的结束时间。
  3. 继续选择下一个符合条件的活动，直到所有活动处理完毕。
代码实现
java">import java.util.Arrays;public class ActivitySelection {public void selectActivities(int[] start, int[] end) {int n = start.length;int[] selected = new int[n];// 根据活动的结束时间排序Integer[] indices = new Integer[n];for (int i = 0; i < n; i++) {indices[i] = i;}Arrays.sort(indices, (a, b) -> end[a] - end[b]);// 选择第一个活动selected[0] = indices[0];int lastEnd = end[indices[0]];for (int i = 1; i < n; i++) {if (start[indices[i]] >= lastEnd) {selected[i] = indices[i];lastEnd = end[indices[i]];}}System.out.println("Selected Activities:");for (int i = 0; i < n; i++) {if (selected[i] != 0) {System.out.println("Activity " + selected[i] + ": Start = " + start[selected[i]] + ", End = " + end[selected[i]]);}}}public static void main(String[] args) {ActivitySelection as = new ActivitySelection();int[] start = {1, 3, 0, 5, 8, 5};int[] end = {2, 4, 6, 7, 9, 9};as.selectActivities(start, end);}
}
复杂度分析
  • 时间复杂度：O(N log N)，因为排序操作

http://www.ppmy.cn/server/158516.html

相关文章

字符串算法篇——字里乾坤，算法织梦，解构字符串的艺术（下）

字符串算法篇——字里乾坤，算法织梦，解构字符串的艺术（下）

文章目录 前言第一章&#xff1a;最长公共前缀1.1 题目链接&#xff1a;https://leetcode.cn/problems/longest-common-prefix/description/1.2 题目分析&#xff1a;1.3 思路讲解&#xff1a;1.4 代码实现&#xff1a; 第二章&#xff1a;最长回文子串2.1 题目链接&#xff1a…
阅读更多...
GET 和 POST 请求的详细区别及代码示例

GET 和 POST 请求的详细区别及代码示例

文章目录 前言一、请求参数的处理方式二、安全性和幂等性三、缓存机制四、数据类型支持五、请求体的区别六、示例代码结语 前言 GET 和 POST 是 HTTP 协议中两种最常用的请求方法&#xff0c;它们在如何发送数据、安全性、幂等性等方面有着显著的不同。下面将更深入地探讨这两…
阅读更多...
android framework.jar 在应用中使用

android framework.jar 在应用中使用

在开发APP中&#xff0c;有时会使用系统提供的framework.jar 来替代 android.jar, 在gradle中配置如下&#xff1a; 放置framework.jar 依赖配置 3 优先级配置 gradle.projectsEvaluated {tasks.withType(JavaCompile) {Set<File> fileSet options.bootstrapClasspat…
阅读更多...
信号与系统初识---信号的分类

信号与系统初识---信号的分类

文章目录 0.引言1.介绍2.信号的分类3.关于周期大小的求解4.实信号和复信号5.奇信号和偶信号6.能量信号和功率信号 0.引言 学习这个自动控制原理一段时间了&#xff0c;但是只写了一篇博客&#xff0c;其实主要是因为最近在打这个华数杯&#xff0c;其次是因为在补这个数学知识…
阅读更多...
Kotlin 快速上手指南：从安装 IntelliJ IDEA 到编写第一个程序

Kotlin 快速上手指南：从安装 IntelliJ IDEA 到编写第一个程序

文章目录 什么是kotlinIntelliJ IDEA安装 IntelliJ IDEA创建 Kotlin 项目运行 Kotlin 程序更改进入后默认打开上一次项目的设置打开 IntelliJ IDEA进入设置：重新启动 IntelliJ IDEA：快速学习Kotlin变量声明类型推断条件表达式定义函数单表达式函数when 表达式when 语句的基本…
阅读更多...
Zookeeper特性与节点数据类型详解

Zookeeper特性与节点数据类型详解

1、 Zookeeper介绍 ZooKeeper 是一个开源的分布式协调框架&#xff0c;是Apache Hadoop 的一个子项目&#xff0c;主要用来解决分布式集群中应用系统的一致性问题。Zookeeper 的设计目标是将那些复杂且容易出错的分布式一致性服务封装起来&#xff0c;构成一个高效可靠的原语集…
阅读更多...
微信小程序集成Vant Weapp移动端开发的框架

微信小程序集成Vant Weapp移动端开发的框架

什么是Vant Weapp Vant 是一个轻量、可靠的移动端组件库&#xff0c;于 2017 年开源。 目前 Vant 官方提供了 Vue 2 版本、Vue 3 版本和微信小程序版本&#xff0c;并由社区团队维护 React 版本和支付宝小程序版本。 官网地睛&#xff1a;介绍 - Vant Weapp (vant-ui.gith…
阅读更多...
在 .NET 9 中使用 Scalar 替代 Swagger

在 .NET 9 中使用 Scalar 替代 Swagger

前言 在.NET 9发布以后ASP.NET Core官方团队发布公告已经将Swashbuckle.AspNetCore&#xff08;一个为ASP.NET Core API提供Swagger工具的项目&#xff09;从ASP.NET Core Web API模板中移除&#xff0c;这意味着以后我们创建Web API项目的时候不会再自动生成Swagger API文档了…
阅读更多...
最新文章

Copyright @ 2022~2023