Java面試黃金寶典15

1. 請找出增序排列中一個數字第一次和最后一次出現的數組下標

定義

由于數組是增序排列的，我們可以利用二分查找的特性來高效地定位目標數字。對于查找第一次出現的位置，當中間元素等于目標數字時，我們需要繼續向左搜索，以確保找到最左邊的目標數字；對于查找最后一次出現的位置，當中間元素等于目標數字時，我們需要繼續向右搜索，以確保找到最右邊的目標數字。

要點

采用二分查找算法，其時間復雜度為 O(logn)，可以大大提高查找效率。
分別編寫兩個二分查找函數，一個用于查找第一次出現的位置，另一個用于查找最后一次出現的位置。

代碼示例

java

public class FindFirstAndLastPosition {public static int[] searchRange(int[] nums, int target) {int first = findFirst(nums, target);int last = findLast(nums, target);return new int[]{first, last};}private static int findFirst(int[] nums, int target) {int left = 0, right = nums.length - 1;int result = -1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] >= target) {right = mid - 1;if (nums[mid] == target) {result = mid;}} else {left = mid + 1;}}return result;}private static int findLast(int[] nums, int target) {int left = 0, right = nums.length - 1;int result = -1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] <= target) {left = mid + 1;if (nums[mid] == target) {result = mid;}} else {right = mid - 1;}}return result;}public static void main(String[] args) {int[] nums = {1, 2, 2, 2, 3, 4, 4, 5};int target = 2;int[] range = searchRange(nums, target);System.out.println("First position: " + range[0]);System.out.println("Last position: " + range[1]);}
}

應用

若數組不是嚴格增序，存在重復元素且可能有相等元素打亂順序的情況，可先對數組進行排序，再使用上述方法。不過排序會增加額外的時間復雜度，如使用快速排序，時間復雜度為 O(nlogn)。

2. 如何實現海量數據去重

定義

哈希表：利用哈希表的特性，其鍵具有唯一性。將數據作為鍵插入哈希表中，重復的數據會自動覆蓋，最終哈希表中的鍵即為去重后的數據。
位圖（BitMap）：對于整數數據，位圖是一個不錯的選擇。位圖是一個二進制數組，每個位代表一個數據，通過設置相應位的值來標記數據的出現情況。

要點

哈希表適用于各種類型的數據，但需要較多的內存空間，空間復雜度為 O(n)。
位圖適用于整數數據，內存占用較小，但數據范圍不能太大。

代碼示例（哈希表）

java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;public class MassiveDataDeduplication {public static List<Integer> deduplicate(List<Integer> data) {Set<Integer> set = new HashSet<>();List<Integer> result = new ArrayList<>();for (int num : data) {if (set.add(num)) {result.add(num);}}return result;}public static void main(String[] args) {List<Integer> data = List.of(1, 2, 2, 3, 4, 4, 5);List<Integer> deduplicatedData = deduplicate(data);System.out.println(deduplicatedData);}
}

應用

當數據量極大，無法全部加載到內存時，可采用分治策略。將數據分成多個小文件，分別對每個小文件進行去重，最后再合并結果。這樣可以降低單次處理的數據量，避免內存溢出。

3. 如何找出海量數據中前 10 個最大的數（數據有重復）

定義

可以使用最小堆來解決該問題。首先創建一個大小為 10 的最小堆，將前 10 個數據插入堆中。然后遍歷剩余的數據，如果當前數據大于堆頂元素，則將堆頂元素替換為當前數據，并調整堆，以保持最小堆的性質。最后堆中的元素就是前 10 個最大的數。

要點

最小堆的時間復雜度為 O(nlogk)，其中 n 是數據的總數，k 是要找的最大數的個數。
堆的插入和刪除操作的時間復雜度為 O(logk)。

代碼示例

java

import java.util.PriorityQueue;public class TopKNumbers {public static int[] topK(int[] nums, int k) {PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);for (int i = 0; i < nums.length; i++) {if (i < k) {minHeap.offer(nums[i]);} else if (nums[i] > minHeap.peek()) {minHeap.poll();minHeap.offer(nums[i]);}}int[] result = new int[k];for (int i = k - 1; i >= 0; i--) {result[i] = minHeap.poll();}return result;}public static void main(String[] args) {int[] nums = {3, 2, 1, 5, 6, 4};int k = 2;int[] topK = topK(nums, k);for (int num : topK) {System.out.print(num + " ");}}
}

應用

可以考慮使用分布式算法，將數據分散到多個節點上，每個節點找出自己的前 10 個最大的數，然后將這些結果合并，再找出最終的前 10 個最大的數。這樣可以充分利用分布式系統的并行計算能力，提高處理效率。

4. 數組先升序在降序，找出最大數

定義

由于數組先升序后降序，我們可以使用二分查找來找到最大數。通過比較中間元素和其相鄰元素的大小，來判斷最大數在左半部分還是右半部分。

要點

二分查找的時間復雜度為 O(logn)，可以高效地找到最大數。
比較中間元素和其相鄰元素的大小，以此來確定最大數的位置。

代碼示例

java

public class FindMaxInAscDescArray {public static int findMax(int[] nums) {int left = 0, right = nums.length - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < nums[mid + 1]) {left = mid + 1;} else {right = mid;}}return nums[left];}public static void main(String[] args) {int[] nums = {1, 2, 3, 4, 5, 4, 3, 2, 1};int max = findMax(nums);System.out.println("Max number: " + max);}
}

應用

若數組中有重復元素，需要對二分查找的條件進行適當調整。例如，當中間元素與其相鄰元素相等時，需要進一步判斷左右兩側的趨勢。

5. 正整數數組，如何拼出一個最大的正數

定義

自定義排序規則，將數組中的元素進行排序。排序規則是將兩個元素拼接成兩個字符串，比較這兩個字符串的大小，將拼接后較大的字符串對應的元素排在前面。

要點

自定義排序規則，使用 Comparator 接口。
將元素拼接成字符串進行比較。

代碼示例

java

import java.util.Arrays;
import java.util.Comparator;public class LargestNumber {public static String largestNumber(int[] nums) {String[] strs = new String[nums.length];for (int i = 0; i < nums.length; i++) {strs[i] = String.valueOf(nums[i]);}Arrays.sort(strs, new Comparator<String>() {@Overridepublic int compare(String s1, String s2) {return (s2 + s1).compareTo(s1 + s2);}});if (strs[0].equals("0")) {return "0";}StringBuilder sb = new StringBuilder();for (String str : strs) {sb.append(str);}return sb.toString();}public static void main(String[] args) {int[] nums = {3, 30, 34, 5, 9};String largest = largestNumber(nums);System.out.println("Largest number: " + largest);}
}

應用

若數組中包含負數，需要先將負數進行處理，例如將負數轉換為正數，或者在排序時單獨處理負數。

6. 一個正整數數組，給其中一個數字加 1，使得所有數乘積最大，找出加 1 的那個數字

定義

遍歷數組，計算給每個數字加 1 后的所有數的乘積，找出乘積最大時對應的數字。

要點

遍歷數組，計算每種情況下的乘積。
記錄最大乘積和對應的數字下標。

代碼示例

java

public class MaxProductAfterIncrement {public static int findNumberToIncrement(int[] nums) {int maxProduct = Integer.MIN_VALUE;int index = -1;for (int i = 0; i < nums.length; i++) {int product = 1;for (int j = 0; j < nums.length; j++) {if (j == i) {product *= (nums[j] + 1);} else {product *= nums[j];}}if (product > maxProduct) {maxProduct = product;index = i;}}return index;}public static void main(String[] args) {int[] nums = {1, 2, 3};int index = findNumberToIncrement(nums);System.out.println("Index of number to increment: " + index);}
}

應用

可以考慮優化算法，通過數學推導找出更高效的方法。例如，分析數組元素的大小關系，找出對乘積影響最大的元素。

7. 手寫快排、堆排二分查找

快速排序

java

public class QuickSort {public static void quickSort(int[] nums, int left, int right) {if (left < right) {int pivotIndex = partition(nums, left, right);quickSort(nums, left, pivotIndex - 1);quickSort(nums, pivotIndex + 1, right);}}private static int partition(int[] nums, int left, int right) {int pivot = nums[right];int i = left - 1;for (int j = left; j < right; j++) {if (nums[j] < pivot) {i++;swap(nums, i, j);}}swap(nums, i + 1, right);return i + 1;}private static void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}public static void main(String[] args) {int[] nums = {3, 2, 1, 5, 6, 4};quickSort(nums, 0, nums.length - 1);for (int num : nums) {System.out.print(num + " ");}}
}

堆排序

java

public class HeapSort {public static void heapSort(int[] nums) {int n = nums.length;// 構建最大堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(nums, n, i);}// 一個個交換元素for (int i = n - 1; i > 0; i--) {// 將堆頂元素（最大值）與當前未排序部分的最后一個元素交換int temp = nums[0];nums[0] = nums[i];nums[i] = temp;// 重新調整堆heapify(nums, i, 0);}}private static void heapify(int[] nums, int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;// 如果左子節點大于根節點if (left < n && nums[left] > nums[largest]) {largest = left;}// 如果右子節點大于當前最大節點if (right < n && nums[right] > nums[largest]) {largest = right;}// 如果最大節點不是根節點if (largest != i) {int swap = nums[i];nums[i] = nums[largest];nums[largest] = swap;// 遞歸調整受影響的子樹heapify(nums, n, largest);}}public static void main(String[] args) {int[] nums = {3, 2, 1, 5, 6, 4};heapSort(nums);for (int num : nums) {System.out.print(num + " ");}}
}

二分查找

java

public class BinarySearch {public static int binarySearch(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;}public static void main(String[] args) {int[] nums = {1, 2, 3, 4, 5};int target = 3;int index = binarySearch(nums, target);System.out.println("Index of target: " + index);}
}

8. 手寫單詞接龍的程序

java

import java.util.*;public class WordChain {public static boolean isValidChain(List<String> words) {if (words.size() <= 1) {return true;}for (int i = 1; i < words.size(); i++) {String prev = words.get(i - 1);String curr = words.get(i);if (prev.charAt(prev.length() - 1) != curr.charAt(0)) {return false;}}return true;}public static void main(String[] args) {List<String> words = Arrays.asList("apple", "elephant", "tiger");boolean isValid = isValidChain(words);System.out.println("Is valid chain: " + isValid);}
}

9. 如何實現括號匹配

定義

使用棧來實現括號匹配。遍歷字符串，遇到左括號時將其壓入棧中，遇到右括號時，檢查棧頂元素是否為對應的左括號，如果是則彈出棧頂元素，否則返回不匹配。最后檢查棧是否為空，如果為空則匹配成功。

要點

使用棧來存儲左括號。
遍歷字符串，根據括號類型進行相應的操作。

代碼示例

java

import java.util.Stack;public class BracketMatching {public static boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (char c : s.toCharArray()) {if (c == '(' || c == '[' || c == '{') {stack.push(c);} else {if (stack.isEmpty()) {return false;}char top = stack.pop();if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {return false;}}}return stack.isEmpty();}public static void main(String[] args) {String s = "()[]{}";boolean isValid = isValid(s);System.out.println("Is valid: " + isValid);}
}

應用

可以考慮處理多種類型的括號嵌套的情況，以及處理包含其他字符的字符串。在處理時，需要忽略非括號字符，只對括號進行匹配檢查。

10. 一個數組存著負數與正數，將正數放在前面，負數放在后面

定義

使用雙指針法，一個指針從左往右遍歷，一個指針從右往左遍歷。當左指針指向負數，右指針指向正數時，交換兩個指針所指的元素。

要點

使用雙指針，時間復雜度為 O(n)。
交換元素的位置。

代碼示例

java

public class RearrangeArray {public static void rearrange(int[] nums) {int left = 0, right = nums.length - 1;while (left < right) {while (left < right && nums[left] > 0) {left++;}while (left < right && nums[right] < 0) {right--;}if (left < right) {int temp = nums[left];nums[left] = nums[right];nums[right] = temp;}}}public static void main(String[] args) {int[] nums = {1, -2, 3, -4, 5};rearrange(nums);for (int num : nums) {System.out.print(num + " ");}}
}