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協議，轉載請注明出處。

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。假設每種計算僅能有一個結果，不允許重復使用數組中的元素。

解題思路

設計一個響應快速查詢的數據結構（如 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);}
}