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

news/2025/1/15 19:22:16/

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

🔍 博客内容包括：

  • 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/news/1563403.html

相关文章

ssh2详细使用步骤，以及常用方法介绍

ssh2详细使用步骤，以及常用方法介绍

开源地址&#xff1a;https://github.com/mscdex/ssh2 ssh2 是一个功能强大的 Node.js 库&#xff0c;用于通过 SSH 协议与远程服务器交互。它支持命令执行、文件上传下载、端口转发等操作&#xff0c;常用于自动化脚本和远程服务器管理。 下面是 ssh2 的详细使用步骤和常用方…
阅读更多...
在ES6模块中导入和导出

在ES6模块中导入和导出

在ES6模块中导入和导出 以最简单的例子举例 //shoppingCart.js //导出模块 console.log(导出模块);//script.js //导出模块 import ./shoppingCart.js; console.log(导入模块);所以要导入其他模块必须指定类型 <script type"Modules" defer src"script.js&…
阅读更多...
2Hive表类型

2Hive表类型

2Hive表类型 1 Hive 数据类型2 Hive 内部表3 Hive 外部表4 Hive 分区表5 Hive 分桶表6 Hive 视图 1 Hive 数据类型 Hive的基本数据类型有&#xff1a;TINYINT&#xff0c;SAMLLINT&#xff0c;INT&#xff0c;BIGINT&#xff0c;BOOLEAN&#xff0c;FLOAT&#xff0c;DOUBLE&a…
阅读更多...
【计算机网络】深入浅出计算机网络

【计算机网络】深入浅出计算机网络

第一章 计算机网络在信息时代的作用 计算机网络已由一种通信基础设施发展成一种重要的信息服务基础设施 CNNIC 中国互联网网络信息中心 因特网概述 网络、互联网和因特网 网络&#xff08;Network&#xff09;由若干结点&#xff08;Node&#xff09;和连接这些结点的链路…
阅读更多...
（Arxiv-2023）LORA-FA：针对大型语言模型微调的内存高效低秩自适应

（Arxiv-2023）LORA-FA：针对大型语言模型微调的内存高效低秩自适应

LORA-FA&#xff1a;针对大型语言模型微调的内存高效低秩自适应 paper是香港浸会大学发表在Arxiv 2023的工作 paper title&#xff1a;LORA-FA: MEMORY-EFFICIENT LOW-RANK ADAPTATION FOR LARGE LANGUAGE MODELS FINE-TUNING ABSTRACT 低秩自适应 (LoRA) 方法可以大大减少微调…
阅读更多...
计算机网络 | 什么是公网、私网、NAT？

计算机网络 | 什么是公网、私网、NAT？

关注&#xff1a;CodingTechWork 引言 计算机网络是现代信息社会的基石&#xff0c;而网络通信的顺畅性和安全性依赖于有效的IP地址管理和网络转换机制。在网络中&#xff0c;IP地址起到了标识设备和进行数据传输的核心作用。本文将详细讨论公网IP、私网IP以及NAT转换等网络技…
阅读更多...
Excel中双引号问题

Excel中双引号问题

背景&#xff1a; 从Excel中读取数据时&#xff0c;发现有的单元格读出来是一个双引号&#xff0c;有的是一个双引号 "{""accountName"": ""全字段"",""accountState"": ""NORMAL"",&q…
阅读更多...
C++实现设计模式---单例模式 (Singleton)

C++实现设计模式---单例模式 (Singleton)

单例模式 (Singleton) 概念 单例模式 确保一个类在整个程序生命周期中只有一个实例&#xff0c;并提供一个全局访问点。 它是一种创建型设计模式&#xff0c;广泛用于需要共享资源的场景。 使用场景 配置管理器&#xff1a;程序中需要一个全局的配置对象。日志系统&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023