Java 高频算法
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面试中最常见的数据结构和算法问题。建议不仅要理解这些解决方案，还要能够分析它们的时间复杂度和空间复杂度，并思考可能的优化方法。
