Java高頻算法面試題
以下是Java面試中常見的高頻算法題目，涵蓋了數據結構、算法思想和實際應用場景。
一、數組與字符串
1. 兩數之和
public int[] twoSum(int[] nums, int target) {Map<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");
}
2. 最長無重復字符子串
public int lengthOfLongestSubstring(String s) {Map<Character, Integer> map = new HashMap<>();int max = 0, left = 0;for (int right = 0; right < s.length(); right++) {char c = s.charAt(right);if (map.containsKey(c)) {left = Math.max(left, map.get(c) + 1);}map.put(c, right);max = Math.max(max, right - left + 1);}return max;
}
二、鏈表操作
3. 反轉鏈表
public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;
}
4. 合并兩個有序鏈表
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(-1);ListNode curr = dummy;while (l1 != null && l2 != null) {if (l1.val < l2.val) {curr.next = l1;l1 = l1.next;} else {curr.next = l2;l2 = l2.next;}curr = curr.next;}curr.next = l1 == null ? l2 : l1;return dummy.next;
}
三、樹結構
5. 二叉樹的最大深度
public int maxDepth(TreeNode root) {if (root == null) return 0;return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
6. 驗證二叉搜索樹
private boolean isValidBST(TreeNode node, long lower, long upper) {if (node == null) return true;if (node.val <= lower || node.val >= upper) return false;return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
}
四、排序與搜索
7. 快速排序
public void quickSort(int[] arr, int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}private int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;swap(arr, i, j);}}swap(arr, i + 1, high);return i + 1;
}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}
8. 二分查找
public 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;if (nums[mid] < target) left = mid + 1;else right = mid - 1;}return -1;
}
五、動態規劃
9. 爬樓梯
public int climbStairs(int n) {if (n == 1) return 1;int[] dp = new int[n + 1];dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];
}
10. 最長遞增子序列
public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];Arrays.fill(dp, 1);int max = 1;for (int i = 1; i < nums.length; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}max = Math.max(max, dp[i]);}return max;
}
六、回溯算法
11. 全排列
public List<List<Integer>> permute(int[] nums) {List<List<Integer>> res = new ArrayList<>();backtrack(res, new ArrayList<>(), nums);return res;
}private void backtrack(List<List<Integer>> res, List<Integer> temp, int[] nums) {if (temp.size() == nums.length) {res.add(new ArrayList<>(temp));} else {for (int i = 0; i < nums.length; i++) {if (temp.contains(nums[i])) continue;temp.add(nums[i]);backtrack(res, temp, nums);temp.remove(temp.size() - 1);}}
}
12. 組合總和
public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> res = new ArrayList<>();Arrays.sort(candidates);backtrack(res, new ArrayList<>(), candidates, target, 0);return res;
}private void backtrack(List<List<Integer>> res, List<Integer> temp, int[] candidates, int remain, int start) {if (remain < 0) return;if (remain == 0) {res.add(new ArrayList<>(temp));return;}for (int i = start; i < candidates.length; i++) {temp.add(candidates[i]);backtrack(res, temp, candidates, remain - candidates[i], i);temp.remove(temp.size() - 1);}
}
七、其他重要算法
13. LRU緩存機制
class LRUCache {class DLinkedNode {int key;int value;DLinkedNode prev;DLinkedNode next;}private Map<Integer, DLinkedNode> cache = new HashMap<>();private int size;private int capacity;private DLinkedNode head, tail;public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;head = new DLinkedNode();tail = new DLinkedNode();head.next = tail;tail.prev = head;}public int get(int key) {DLinkedNode node = cache.get(key);if (node == null) return -1;moveToHead(node);return node.value;}public void put(int key, int value) {DLinkedNode node = cache.get(key);if (node == null) {DLinkedNode newNode = new DLinkedNode();newNode.key = key;newNode.value = value;cache.put(key, newNode);addNode(newNode);size++;if (size > capacity) {DLinkedNode tail = popTail();cache.remove(tail.key);size--;}} else {node.value = value;moveToHead(node);}}private void addNode(DLinkedNode node) {node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}private void removeNode(DLinkedNode node) {DLinkedNode prev = node.prev;DLinkedNode next = node.next;prev.next = next;next.prev = prev;}private void moveToHead(DLinkedNode node) {removeNode(node);addNode(node);}private DLinkedNode popTail() {DLinkedNode res = tail.prev;removeNode(res);return res;}
}
14. 實現Trie(前綴樹)
class Trie {class TrieNode {TrieNode[] children = new TrieNode[26];boolean isEnd;}private TrieNode root;public Trie() {root = new TrieNode();}public void insert(String word) {TrieNode node = root;for (char c : word.toCharArray()) {if (node.children[c - 'a'] == null) {node.children[c - 'a'] = new TrieNode();}node = node.children[c - 'a'];}node.isEnd = true;}public boolean search(String word) {TrieNode node = searchPrefix(word);return node != null && node.isEnd;}public boolean startsWith(String prefix) {return searchPrefix(prefix) != null;}private TrieNode searchPrefix(String prefix) {TrieNode node = root;for (char c : prefix.toCharArray()) {if (node.children[c - 'a'] == null) return null;node = node.children[c - 'a'];}return node;}
}
這些算法題目覆蓋了Java面試中最常見的數據結構和算法問題。建議不僅要理解這些解決方案，還要能夠分析它們的時間復雜度和空間復雜度，并思考可能的優化方法。
)
)
