Java 面试中的高频算法题详解
💖 欢迎来到我的博客! 非常高兴能在这里与您相遇。在这里,您不仅能获得有趣的技术分享,还能感受到轻松愉快的氛围。无论您是编程新手,还是资深开发者,都能在这里找到属于您的知识宝藏,学习和成长。
🔍 博客内容包括:
- 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协议,转载请注明出处。
目录
5.2 最长公共子序列(Longest Common Subsequence)
7.1 活动选择问题(Activity Selection Problem)
Java 面试中,算法题是一个重要且常见的涉及领域。面试对算法效率和处理方式有高要求,下面将通过解析经典题目,配合解题思路和代码实现进行详细说明。
1. 两数之和
题目描述
给定一个整数数组(nums)和一个目标值(target),请从数组中找出两个元素,使它们之和为 target。假设每种计算仅能有一个结果,不允许重复使用数组中的元素。
解题思路
-
设计一个响应快速查询的数据结构(如 HashMap),用于存储数组元素和它们的位置。
-
遍历数组,对于每个元素(nums[i]),计算 target - nums[i],检查该值是否已存在于 HashMap。
-
如果存在,返回它们的位置;如果不存在,将当前元素和位置保存到 HashMap。
代码实现
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. 反转链表
题目描述
给定一个单链表,请反转该链表。
解题思路
-
通过一个进程实现反转:保存当前节点的上一节点,重新设置指针。
-
使用三个指针:pre、cur和next,采用进程尽头更新。
代码实现
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)进行访问,并实现目标方案。
解题思路
-
通过通用的算法回退,可以对于任何格式基于规划优先加量。
-
用一个标记数据进行处理。
代码实现
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。
代码实现
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)
题目描述
给定一个无序的数组,要求通过归并排序算法将数组排序。
解题思路
归并排序的核心思想是分治法,将数组分成两个子数组,对每个子数组进行排序后合并。
解题步骤
- 将数组分成两个子数组。
- 递归地对子数组进行排序。
- 合并两个已排序的子数组,最终得到一个有序数组。
代码实现
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,要求选择一些物品放入背包,使得背包中的物品总价值最大。
解题思路
动态规划的解法通过构建一个二维数组,表示每个背包容量下能够获得的最大价值。通过递推公式,逐步填充数组,最终求得最大价值。
解题步骤
- 定义状态:dp[i][j]表示前i个物品,在背包容量为j时的最大价值。
- 递推公式:
- 如果不选择第i个物品:dp[i][j] = dp[i-1][j]。
- 如果选择第i个物品:dp[i][j] = dp[i-1][j-weight[i]] + value[i]。
- 初始化状态:dp[0][j] = 0(没有物品时,背包的最大价值为0)。
代码实现
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])
。
解题步骤
- 初始化状态:
dp[i][0] = 0
和dp[0][j] = 0
,表示任意一个字符串为空时,公共子序列长度为0。 - 递推填充
dp
数组。 - 最终答案为
dp[s1.length][s2.length]
。
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]
:表示副对角线是否已被占用。
解题步骤
- 从第一行开始放置皇后,并递归地尝试其他行。
- 每放置一个皇后,检查其列、主对角线和副对角线是否已经有其他皇后。
- 如果某一行没有合法的放置位置,则回溯到上一行并尝试新的放置方案。
代码实现
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)
题目描述
有若干个活动,每个活动有一个开始时间和结束时间,要求选择尽可能多的活动,使得每个活动都不与已选择的活动重叠。
解题思路
贪心算法的思想是,选择结束时间最早的活动。每次选择当前活动时,要求它与之前选择的活动不重叠。
解题步骤
- 将所有活动按照结束时间排序。
- 从第一个活动开始选择,选择的条件是活动的开始时间要晚于已选活动的结束时间。
- 继续选择下一个符合条件的活动,直到所有活动处理完毕。
代码实现
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),因为排序操作
原文地址:https://blog.csdn.net/weixin_45710998/article/details/145136900
免责声明:本站文章内容转载自网络资源,如侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!